Multi-Objective Optimization for the m-PDPTW: Aggregation Method With Use of Genetic Algorithm and Lower Bounds

  • Imen Harbaoui Dridi LAGIS : Ecole Centrale de Lille, Villeneuve d’Ascq, France LACS : Ecole Nationale des Ingénieurs de Tunis, Tunis - Belvédère. Tunisie
  • Ryan Kammarti LACS : Ecole Nationale des Ingénieurs de Tunis, Tunis - Belvédère. Tunisie
  • Mekki Ksouri LACS : Ecole Nationale des Ingénieurs de Tunis, Tunis - Belvédère. Tunisie
  • Pierre Borne LAGIS : Ecole Centrale de Lille, Villeneuve d’Ascq, France

Abstract

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

[1] 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.

[2] Christofides N. Mingozzi A. and Toth P. The vehicle routing problem. In Combinatorial Optimization, volume 11, pages 315-338. John Wiley, 1979.

[3] 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

[4] 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.

[5] 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

[6] 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.

[7] 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.

[8] 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.

[9] Savelsbergh M.P.W. and SOL M., "The general pickup and delivery problem", Transportation Science 1995.

[10] 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

[11] 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

[12] Jih. W. and Hsu J. Dynamic vehicle routing using hybrid genetic algorithms. International Conference on Robotics and Automation, pages 453-458, 1999.

[13] Velasco N. Dejax P. Gueret C. and Prins C. Un algorithme génétique pour un problème de collecte bi-objectif. MOSIM 2006.

[14] 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.

[15] 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.

[16] 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

[17] 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.

[18] 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.

[19] 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

[20] 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.

[21] 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.

[22] 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.

[23] 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.

[24] 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.

[25] Pareto. V. Cours d'économie politique, Lausanne : Rouge, 1896-7, reproduit in Vilfredo Pareto, Oeuvres complètes, Genève : Librairie Droz, 1964.

[26] 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

[27] 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.

[28] Jurich, B. Scheduling Jobs in Shops with Multi-purpose Machines. Ph.D thesis, Fachbereich Mathematik / Informatik, Universitat Osnabruck., 1992.

[29] 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

[30] 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.

[31] 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.

[32] 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

[33] 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
2011-06-01
How to Cite
DRIDI, Imen Harbaoui et al. Multi-Objective Optimization for the m-PDPTW: Aggregation Method With Use of Genetic Algorithm and Lower Bounds. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 6, n. 2, p. 246-257, june 2011. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2172>. Date accessed: 22 oct. 2020. doi: https://doi.org/10.15837/ijccc.2011.2.2172.

Keywords

PDPTW, multi-objective, aggregation method, lower bounds