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

Imen Harbaoui Dridi, Ryan Kammarti, Mekki Ksouri, Pierre Borne

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.


Keywords


PDPTW, multi-objective, aggregation method, lower bounds

Full Text:

PDF

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




DOI: https://doi.org/10.15837/ijccc.2011.2.2172



Copyright (c) 2017 Imen Harbaoui Dridi, Ryan Kammarti, Mekki Ksouri, Pierre Borne

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.