Single vehicle pickup and delivery with time windows: made to measure genetic encoding and operators

ABSTRACT

To the best of our knowledge, only a few researchers have experimented with genetic algorithms (GAs) to tackle the single vehicle pickup and delivery problem with time windows, possibly due to the large number of constraints involved and the difficulty in handling them. In particular, there is the difficulty in designing an appropriate genetic representation and intelligent genetic operators that are able to transfer the ordering characteristic of the parents to the offspring, while preserving the feasibility of the solution. In this research, we will experiment with a genetic encoding and operators specially designed to deal with the problem in hand. We will present a duplicate gene encoding that guarantees the satisfaction of the the precedence constraint, between the pickup and the delivery requests, throughout the search. We aim to show that GAs, if guided by some problem-specific information, will be able to handle this hard problem and possibly other similarly highly constrained problems.

REFERENCES

• 1: Joe L. Blanton, Jr. , Roger L. Wainwright, Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.452-459, June 01, 1993
• 2: J.-C. Créput, A. Koukam, J. Kozlak, and J. Lukasik. An evolutionary approach to pickup and delivery problem with time windows. Lecture Notes in Computer Science, 3038:1102--1108, 2004.
• 3: J. Desrosiers, Y. Dumas, and F. Soumis. A dynamic programming solution of the large-scale single vehicle dial-a-ride problem with time windows. American Journal of Mathematical and Management Sciences, 6:301--325, 1986.
• 4: M. Diana and M. Dessouky. A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows. Transportation Research Part B: Methodological, 38(6):539--557, 200
• 5: P. Healy and R. Moll. A new extension of local search applied to the dial-a-ride problem. European Journal of Operational Research, 83:83--104, 1995.
• 6: W. Jih and Y. Hsu. A family competition genetic algorithm for the pickup and delivery problems with time window. Bulletin of the College of Engineering, 90:121--130.
• 7: W. Jih and Y. Hsu. Dynamic vehicle routing using hybrid genetic algorithms. In Proceedings of the 1999 IEEE International Conference on Robotics and Automation, pages 453--458, 1999. Detroit, Michigan.
• 8: R. M. Jorgensen, J. Larsen, and K. B. Bergvinsdottir. Solving the dial-a-ride problem using genetic algorithms. Journal of Operational Research Society, 2006.
• 9: A. Landrieu, Y. Mati, and Z. Binder. A tabu search heuristic for the single vehicle pickup and delivery problem with time windows. Journal of Intelligent Manufacturing, 12:497--508, 2001.
• 10: Hoong Chuin Lau , Zhe Liang, Pickup and Delivery with Time Windows: Algorithms and Test Case Generation, Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01), p.333, November 07-09, 2001
• 11: Haibing Li , Andrew Lim, A Metaheuristic for the Pickup and Delivery Problem with Time Windows, Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01), p.160, November 07-09, 2001
• 12: Q. Lu and M. M. Dessouky. A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows. European Journal of Operational Research, 175:672--687, 2006.
• 13: W. P. Nanry and J. W. Barnes. Solving the pickup and delivery problem with time windows using reactive tabu search. Transportation Research Part B: Methodological, 34:107--121, 2000.
• 14: G. Pankratz. A grouping genetic algorithm for the pickup and delivery problem with time windows. OR Spectrum, 27:21--24, 2005.
• 15: H. Psaraftis. An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows. Transportaion Science, 17:351--357, 1983.
• 16: Jacques Renaud , Fayez F. Boctor , Jamal Ouenniche, A heuristic for the pickup and delivery traveling salesman problem, Computers and Operations Research, v.27 n.9, p.905-916, Aug.2000 [doi>10.1016/S0305-0548(99)00066-0]
• 17: M. W. P. Savelsbergh and M. Sol. The general pickup and delivery problem. Transportation Science, 29(1):17--29, 1995.
• 18: Vincent Tam , Lois C. Y. Tseng, Effective Heuristics to Solve Pickup and Delivery Problems with Time Windows, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.184, November 03-05, 2003
• 19: Transport Statistics. Road Freight Statistics 2005. Anational statistics publication produced for the departement of transport, United Kingdom, 29th June 2006. (This document can be downloaded from www.dft.gov.uk/transtat.)
• 20: L. J. J. Van-der-Bruggen, J. Lenstra, and P. Schuur. Variable-depth search for the single-vehicle pickup and delivery problem with time windows. Transportation Sience, 27:298--311, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Performance

Keywords:
dial-a-ride, genetic algorithms, pickup and delivery with time windows, vehicle routing