| Article ID: | iaor201524551 |
| Volume: | 21 |
| Issue: | 5-6 |
| Start Page Number: | 279 |
| End Page Number: | 298 |
| Publication Date: | Sep 2014 |
| Journal: | Journal of Multi-Criteria Decision Analysis |
| Authors: | T'kindt Vincent, Lent Christophe, Atahran Ahmed |
| Keywords: | programming: multiple criteria, combinatorial optimization, demand, transportation: road, heuristics: genetic algorithms |
The Dial‐a‐Ride Problem is a complex combinatorial optimization problem with many real‐world applications in transportation of persons. It consists in routing a fleet of vehicles based at a common depot in order to satisfy users' transportation requests. Each request may consist, in a number of persons, a specified pickup location, a destination location, desired departure and arrival time windows. In this paper, we investigate a new and general model for the transportation of persons. It involves three objective functions that have to be optimized in order to measure the potential efficiency of the Dial‐a‐Ride Problem solution on different aspects: the cost for the transportation operator, the quality of service for users and the impact on the environment. For an efficient search through the solution space, we use a multiobjective genetic algorithm, which allows us to identify a good approximation of the set of Pareto optimal solutions. Among this set of solutions, the decision‐maker can select the solution with best compromise according to its preferences, without introducing a priori information about these ones. The proposed genetic algorithm is based on an optimal timing algorithm that computes pickup and delivery dates when the requests are sequenced on the vehicles.