Application of Genetic Algorithms for the DARPTW Problem
Keywords:
Dial-a-ride, Passenger Transportation, DARPTW, Heuristic, SchedulingAbstract
On the Dial-a-Ride with time windows (DARPTW) customer transportation problem, there is a set of requests from customers to be transported from an origin place to a delivery place through a locations network, under several constraints like the time windows. The problem complexity (NP-Hard) forces the use of heuristics on its resolution. In this context, the application of Genetic Algorithms (GA) on DARPTW was not largely considered, with the exception of a few researches. In this work, under a restrictive scenario, a GA model for the problem was developed based on the adaptation of a generic GA model from literature. Our solution applies data pre-processing techniques to reduce the search space to points that are feasible regarding time windows constraints. Tests show competitive results on Cordeau & Laporte benchmark datasets while improving processing times.References
K. Bergvinsdottir, The Genetic Algorithm for solving the Dial-a-Ride Problem, Master's thesis, Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2004.
R. M. Jorgensen, J. Larsen, K. B. Bergvinsdottir, Solving the Dial-a-Ride problem using genetic algorithms, J. Oper. Res. Soc., Vol.58, pp. 1321-1331, 2006. http://dx.doi.org/10.1057/palgrave.jors.2602287
J. Cordeau, A Branch-and-Cut Algorithm for the Dial-a-Ride Problem, Operations Research, Vol. 54, pp. 573-586, 2006. http://dx.doi.org/10.1287/opre.1060.0283
J. Cordeau, G. Laporte, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transportation Research Part B, Vol. 37, Issue 6, pp. 579-594, 2003. http://dx.doi.org/10.1016/S0191-2615(02)00045-0
J. Cordeau, G. Laporte, Benchmark datasets accessed on march-2007, available online at: http://neumann.hec.ca/chairedistributique/data/darp/. 2007.
C. Cubillos, MADARP: Multi-Agent Framework for Transportation Systems, Thesis for the academic degree of Dottore di Ricerca in Ingegneria Informatica e dei Sistemi (ciclo XVII), Politecnico di Torino, 2005.
C. Cubillos, N. Rodriguez, B. Crawford, A Study on Genetic Algorithms for the DARP Problem, Springer Berlin-Heidelberg LNCS, vol. 4527, pp. 498-507, 2007. http://dx.doi.org/10.1007/978-3-540-73053-8_50
G. Harik, D.E. Goldberg, Learning linkage, Foundations of Genetic Algorithms, vol. 4, pp. 247-262, 1996.
J.H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to biology, control and artificial intelligence, MIT Press, ISBN 0-262-58111-6, 1998.
M.W.P. Savelsbergh, The General Pickup and Delivery Problem, Transportation Science, Vol. 29, pp. 17-29, 1995. http://dx.doi.org/10.1287/trsc.29.1.17
S. Thangiah, Vehicle Routing with Time Windows using Genetic Algorithms, Application Handbook of Genetic Algorithms: New Frontiers, Vol. II. Lance Chambers (Ed.). CRC Press, 1995.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
