Thursday , March 28 2024

Volume 18-Issue2-2009-DRIDI

A Genetic Algorithm for the Multi-Pickup and Delivery Problem with Time Windows

Harbaoui DRIDI
LAGIS: Ecole Centrale de Lille
Villeneuve d’Ascq, France
LACS: Ecole Nationale des Ingénieurs de Tunis
Tunis – Belvédère. Tunisie

R. KAMMARTI
LAGIS: Ecole Centrale de Lille
Villeneuve d’Ascq, France
LACS: Ecole Nationale des Ingénieurs de Tunis
Tunis – Belvédère. Tunisie

M. 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: In this paper we present a genetic algorithm for the multi-pickup and delivery problem with time windows (m-PDPTW). The m-PDPTW is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence, capacity and time constraints. This paper purposes a brief literature review of the PDPTW, present our approach based on genetic algorithms to minimizing the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.

Keywords: vehicles routing, pickup and delivery problem, time windows, optimization, genetic algorithm.

Harbaoui Dridi was born in 1981 in TUNISIA; she graduated in engineering from the National Institute of Applied Science and Technology (INSAT) in 2006 and Masters Degree in Computer Science and Industrial Automation (INSAT) in 2007. Currently, it is doctoral student (in Electrical and Computer Engineering and Industrial Automation) at the National School of Engineers of Tunis (ENIT – TUNISIA) and the Central School of Lille (EC LILLE – FRANCE) and contractual assistant at the Higher Institute of Informatics (TUNISIA).

Ryan Kammarti was born in Tunis, Tunisia in 1978. He received the M.E. and the Master degree in Automatics and Industrial Computing from the National Institute of Applied Sciences and Technology (INSAT) in 2003 and the Ph.D. degree in automatics and industrial computing from the Ecole Centrale de Lille, Villeneuve d’Ascq, France, and the University of Lille and the National School of Engineers of Tunis in 2006.He currently occupies a assistant teacher position with the University of Tunis EL Manar, Tunis, Tunisia. Hes also a team head in the ACS research laboratory in the National School of Engineers of Tunis (ENIT).Ryan Kammarti was born in Tunis, Tunisia in 1978. He received the M.E. and the Master degree in Automatics and Industrial Computing from the INSAT in 2003 and the Ph.D. degree in automatics and industrial computing from the Ecole Centrale de Lille, Villeneuve dAscq, France, and the University of Lille and the National School of Engineers of Tunis (ENIT) in 2006.He currently occupies a assistant teacher position with the University of Tunis EL Manar, Tunis, Tunisia. Hes also a team head in the ACS research laboratory in the ENIT.

Mekki Ksouri was born in Jendouba, Tunisia in 1948. He received the M.A. degree in physics in the FST in Tunis in 1973, the M.E. degree Ingenieur SupElec from the High School of Electricity (Ecole Suprieure d’Electricite French Grande Ecole) in Paris in 1973, degree, the D.Sc. degree, and the Ph.D. degree from the University of Paris VI, Paris, France, in 1975 and 1977 respectively. He is Professor at the National School of Engineers of Tunis (ENIT). He was principal of the National Institute of Applied Sciences and Technology (INSAT) from 1999 to 2005, principal and founder of the High School of Statistics and Information Analysis from 2001 to 2005 and the High Institute of Technologic Studies from 1996 to 1999 and principal of The High Normal School of Technological Education from 1978 to 1990. Pr. Ksouri is the author or coauthor of many journal articles, book chapters, and communications in international conferences. He is also the author of 6 books. His activities focus on automatic control, robust control, and optimization in planning and scheduling, including implementation of fuzzy logic, neural nets, and genetic algorithms. Pr. Ksouri had received many distinctions like the Outstanding Contribution Award for Leadership in on the Organization of the CIFA 2004 Symposium, Chevalier dans l’Ordre des Palmes Academiques; France decret en date du 19/4/2002, Outstanding Contribution Award ; IEEE SMC 1998 and Ordre national du merite de l’education; Tunisie decret n97- 1369 du 18/07/97. Pr. Ksouri is a senior member IEEE and he’s the head and founder of many scientific associations like ATTNA and ASET.

Pierre Borne received the Master degree of Physics in 1967, the Masters of Electronics, of Mechanics and of Applied Mathematics in 1968. The same year he obtained the Diploma of “Ingénieur IDN” (French “Grande Ecole”). He obtained the PhD in Automatic Control of the University of Lille in 1970 and the DSc of the same University in 1976. He became Doctor Honoris Causa of the Moscow Institute of Electronics and Mathematics (Russia) in 1999, of the University of Waterloo (Canada) in 2006 and of the Polytechnic University of Bucarest (Romania). He is author or co-author of about 200 Journal articles and book chapters, and of 38 plenary lectures and of more than 250 communications in international conferences. He has been the supervisor of 71 PhD thesis and is author of 20 books.

He is Fellow of IEEE, member of the Fellows Committee of IEEE and has been President of the IEEE/SMC society in 2000 and 2001 .He is Vice-Chair of the IFAC TC on Large Scale and Complex Systems. He is presently Professor “de classe exceptionnelle” at the Ecole Centrale de Lille and Director of the national french pluriformations group of research in Automatic Control.

>Full text
CITE THIS PAPER AS:
Harbaoui DRIDI, R. KAMMARTI, M. KSOURI, Pierre BORNE,  A Genetic Algorithm for the Multi-Pickup and Delivery Problem with Time Windows, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (2), pp. 173-180, 2009.

1. Introduction

With the time and economic constraints implications of the transport goods problem, its resolution becomes very difficult, requiring the use of tools from different disciplines (manufacturing, information technology, combinatorial optimization, etc.)… Indeed, the process from transport systems and scheduling are becoming more complex by their large size, by the nature of their relationship dynamics, and by the multiplicity of which they are subjected.

Many studies have been directed mainly towards solving the vehicle routing problem (VRP). It’s an optimization vehicle routing problem to meet travel demands. Other researchers became interested on an important variant of VRP which is the PDPTW (Pickup and Delivery Problem with Time Windows) with capacity constraints on vehicle.

The PDPTW is divided into two: 1-PDPTW (single-vehicle) and m-PDPTW (multi-vehicle).

Our object is to design a tool for m-PDPTW resolution based on genetic algorithms and Pareto dominance method to give a set of satisfying solutions to this problem minimizing the total travel distance and thereafter the total travel cost, by showing that an encoding represents the parameters of each individual.

5. Conclusion

In this paper we have proposed, following a study of the different approaches proposed for the resolution of 1-PDPTW and m-PDPTW, a genetic algorithm for minimizing the total travel cost. To do this, we presented the mathematical formulation of our problem, and we have detailed the calculation procedure for determine the optimal solution, that minimizes our objective function.

  1. Christofides, N., A. Mingozzi, and P. Toth, The vehicle routing problem. In Combinatorial Optimization, volume 11, John Wiley, 1979, pp. 315-338.
  2. Lenstra, J. and A. Rinnooy Kan, Complexity of the vehicle routing and scheduling problems, In Networks, volume 11, Springer, 1981, pp. 221-228.
  3. Matsinen, T., Savolainen, V., Efficient Combinatorial of heuristics for solving Travelling Salesman Problems, Published in: Studies in Informatics and Control, Vol. 1, No. 1, March 1992.
  4. Montamenni, R., L.M. Gambardella, A.E. Rizzoli, A.V. Donati, A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System, IDSIA, Switzerland, 2002.
  5. Sorin C., N., Claudiu V, Kifor, and Constantin, O., Ant Colony Solving Multiple Constraints Problem: Vehicle Route Allocation, Int. J. of Computers, Communications & Control, ISSN 1841-9836, E-ISSN 1841-9844 Vol. III, 2008.
  6. Nabaa, M., B. Zeddini and P. Tranouez, Approche décentralisée pour résoudre le problème du transport à la demande, Schedae, prépublication no. 23, fascicule no. 2, 2007, pp. 133-140.
  7. Savelsbergh, M.P.W., SOL M., The general pickup and delivery problem, Transportation Science 1995.
  8. 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, 1983, pp. 351-357.
  9. 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.
  10. Jih, W. and Hsu, J., Dynamic vehicle routing using hybrid genetic algorithms, International Conference on Robotics and Automation, 1999, pp. 453-458.
  11. Velasco, N., P. Dejax, C. Gueret and C. Prins. Un algorithme génétique pour un problème de collecte bi-objectif, MOSIM 2006.
  12. 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, Oct. 2004, pp. 1498-1503.
  13. 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, 2005, pp. 148-153.
  14. Kammarti, R., Hammadi, S., Borne P., and Ksouri M. Solving the Real Time dynamic Pickup and Delivery Problem with an hybrid evolutionary approach, Multicon-ference on Computational Engineering in Systems Application. Volume 2, Oct. 2006, pp. 1520-1525.
  15. Kammarti, R., Borne P., and Ksouri M., Hybrid Evolutionary Approaches and new Benchmark for the 1-PDPTW, 2007 IFAC. MCPL.
  16. Sol, M. and M. Savelsbergh, 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.
  17. Quan, L. and M. Maged, A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows, Science direct, European Journal of Operational Research 2003.
  18. Li, H. and A. Lim, A metaheuristic for the pickup and delivery problem with time windows, In IEEE International Conference on Tools with Artificial Intelligence, volume 13, 2001, pp. 160- 167.
  19. Li, H., A. Lim and B. Rodrigues. Solving the pickup and delivery problem with time windows using squeaky wheel optimization with local search, SMU Business Conference Paper Series, 2002.
  20. Harbaoui, I., Dridi R., Kammarti, P. Borne and M. Ksouri, Un Algorithme génétique pour le problème de ramassage et de livraison avec fenêtres de temps à plusieurs véhicules. CIFA 2008.