Multi-Objective Optimization for the m-PDPTW: Aggregation Method With Use of Genetic Algorithm and Lower Bounds
Keywords:
PDPTW, multi-objective, aggregation method, lower boundsAbstract
The PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers in purpose to satisfy precedence, capacity and time constraints. We present, in this paper, a genetic algorithm for multi-objective optimization of a multi pickup and delivery problem with time windows (m-PDPTW), based on aggregation method and lower bounds. We propose in this sense a brief literature review of the PDPTW, present our approach to give a satisfying solution to the m-PDPTW minimizing the compromise between total travel cost and total tardiness time.
References
H. Ezzedine T. Bonte C. Kolski and C. Tahon. Integration of traffic management and traveller information systems: basic principles and case study in intermodal transport system management. International Journal of Computers, Communications & Control (IJCCC), ISSN 1841 9836, E-ISSN 1841-9844 Vol. III, No. 3, pp. 281-294, 2008.
Christofides N. Mingozzi A. and Toth P. The vehicle routing problem. In Combinatorial Optimization, volume 11, pages 315-338. John Wiley, 1979.
Lenstra J. and Rinnooy Kan A. Complexity of the vehicle routing and scheduling problems. In Networks, volume 11, pages 221-228. Springer, 1981. http://dx.doi.org/10.1002/net.3230110211
Nabaa M. Zeddini B. and Tranouez P. Approche décentralisée pour résoudre le problème du transport ŕ la demande. Schedae, prépublication n◦ 23, (fascicule n◦ 2, p. 133-140), 2007.
Toth P. and Vigo D. The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, 2002, ISBN 0-89871-498-2. http://dx.doi.org/10.1137/1.9780898718515
Montamenni R. Gambardella L.M. Rizzoli A.E. and Donati A.V. A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System. IDSIA, Switzerland, 2002.
Sorin C. Negulescu, Claudiu V. Kifor, and Constantin Oprean. Ant Colony Solving Multiple Constraints Problem: Vehicle Route Allocation. Int. J. of Computers, Communications & Control (IJCCC), ISSN 1841-9836, E-ISSN 1841-9844, Vol. III, No. 4, pp. 366-373, 2008.
Kaoru Hirota, Fangyan Dong and Kewei Chen. A Computational Intelligence Approach to VRSDP (Vehicle Routing, Scheduling, and Dispatching Problems). ICCCC, Baile Felix- Oradea, Romania pp. 53-54, 2006.
Savelsbergh M.P.W. and SOL M., "The general pickup and delivery problem", Transportation Science 1995.
Psaraftis H.N. An exact algorithm for the single vehicle many to many immediate request dial a ride problem with time windows. Transportation Science, 17, 351-357, 1983. http://dx.doi.org/10.1287/trsc.17.3.351
Psaraftis H.N. A dynamic programming solution to the single vehicle many to many immediate request dial a ride problem. Transportation Science, 14(2):130-154, 1980. http://dx.doi.org/10.1287/trsc.14.2.130
Jih. W. and Hsu J. Dynamic vehicle routing using hybrid genetic algorithms. International Conference on Robotics and Automation, pages 453-458, 1999.
Velasco N. Dejax P. Gueret C. and Prins C. Un algorithme génétique pour un problème de collecte bi-objectif. MOSIM 2006.
Kammarti. R. Hammadi. S. Borne. P. and Ksouri. M. A new hybrid evolutionary approach for the pickup and delivery problem with time windows. IEEE International Conference on Systems, Man and Cybernetic. 2004. Volume 2, P 1498-1503, Oct 2004.
Kammarti. R. Hammadi. S. Borne. P. and Ksouri. M. "Improved tabu search in an hybrid evolutionary approach for the pickup and delivery problem with time windows", Intelligent Transportation Systems, 2005. Proceeding 2005 IEEE, p 148-153, 2005.
Kammarti. R. Hammadi. S. Borne P. and Ksouri. M. "Solving the Real Time dynamic Pickup and Delivery Problem with an hybrid evolutionary approch". Multiconference on Computational Engineering in Systems Application. Volume 2, P 1520-1525, Oct 2006. http://dx.doi.org/10.1109/CESA.2006.4281878
Sol M. and Savelsbergh M. A branch-and-price algorithm for the pickup and delivery problem with time windows. Memorandum COSOR 94-22, Dept. of Mathematics and Computing Science, Eindoven University of Technology, Eindoven, The Netherlands, 1994.
Quan L. and Maged M. A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows. Science direct, European Journal of Operational Research 2003.
Li H. and Lim A. A metaheuristic for the pickup and delivery problem with time windows. In IEEE International Conference on Tools with Artificial Intelligence, volume 13, pages 160- 167, 2001. http://dx.doi.org/10.1109/ictai.2001.974461
Li H. Lim A. and Rodrigues B. Solving the pickup and delivery problem with time windows using squeaky wheel" optimization with local search. SMU Business Conference Paper Series, 2002.
Harbaoui Dridi I. Kammarti R. Borne P. and Ksouri M. Un Algorithme génétique pour le problème de ramassage et de livraison avec fenętres de temps ŕ plusieurs véhicules. CIFA 2008, Bucarest (Roumanie), Septembre 2008 Proc. Article 176.
Harbaoui Dridi I. Kammarti R. Borne P. and Ksouri M. Approche multicritère pour le problème de ramassage et de livraison avec fenętres de temps ŕ plusieurs véhicules. Symposium LT'2009, Tunisie, (Sousse), LT09-006, Mars 2009.
Harbaoui Dridi I. Kammarti R. Borne P. and Ksouri M. Genetic Algorithm for Multicriteria Optimization of a Multi-Pickup and Delivery Problem with Time Windows. 13th INCOM IFAC symposium, Moscow (Russia), pp 1521-1526, June 2009.
Harbaoui Dridi I. Kammarti R. Ksouri M and Borne P. A Genetic Algorithm for the Multi- Pickup and Delivery Problem with time windows. Studies in Informatics and Control (SIC), Vol 18, Nâ—¦2, pp 173-180, Juin 2009.
Pareto. V. Cours d'économie politique, Lausanne : Rouge, 1896-7, reproduit in Vilfredo Pareto, Oeuvres complètes, Genève : Librairie Droz, 1964.
Hwang, C. and Masud, A. Multiple objective decision making - methods and applications. In Lectures Notes in Economics and Mathematical Systems, volume 164. Springer-Verlag, Berlin, 1979. http://dx.doi.org/10.1007/978-3-642-45511-7
Jouglet. A, Baptiste. B et Carlier. J. Exact Procedures for Single Machine Total cost Scheduling. Proceeding of the IEEE / SMC'02 Conf. 6-9 October, Hammamet, Tunisia, 2002.
Jurich, B. Scheduling Jobs in Shops with Multi-purpose Machines. Ph.D thesis, Fachbereich Mathematik / Informatik, Universitat Osnabruck., 1992.
Carlier, J. Scheduling jobs with release dates and tails on identical machines to minimize the makespan. European Journal of Operational Research, 29 (1987) 298-306, North-Holland. http://dx.doi.org/10.1016/0377-2217(87)90243-8
Billaut, J.C, Carlier, J, Néron, E. Ordonnancement d'ateliers ŕ ressources multiples. Chapitre dans l'ouvrage : Ordonnancement de la production, Edition Hermès, France, 2001.
I. Kacem. Ordonnancement multicritères des job shops flexibles : formulation, bornes inferieures et approche éévolutionniste coopérative. Thèse en Automatique et informatique industrielle ŕ l'université de Lille 1, 2003.
Solomon M.M., "Algorithms for the vehicle Routing and Scheduling Problem with Time Window Constraints", Operations Research, 41, 469-488, 1987. http://dx.doi.org/10.1287/opre.35.2.254
Kammarti. R. Hammadi. S. Borne. P. and Ksouri. M. "Lower Bounds In An Hybrid Evolutionary Approach For The Pickup And Delivery Problem With Time Windows". IEEE International Conference on Systems, Man and Cybernetics. 2005. Volume 2, P 1156-1161, Oct 2005. http://dx.doi.org/10.1109/icsmc.2005.1571302
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.
