Multi-strategy grouping genetic algorithm for the pickup and delivery problem with time windows

ABSTRACT

The Pickup and Delivery Problem with Time Windows (PDPTW) is a generalization of the well studied Vehicle Routing Problem with Time Windows (VRPTW). This paper studies a Grouping Genetic Algorithm for solving the PDPTW. The insertion-searching heuristics (in GGA) which can generate feasible solutions was improved, new data structures were built, and then three routing adjustment strategies were added to come up with the Multi-Strategy Grouping Genetic Algorithm (MSGGA). The PDPTW benchmark problems with 100 customers are calculated with MSGGA, and the comparison between the result and that of the reference shows that the new algorithm shortens the calculating time with its astringency, better solutions of four cases are obtained and stability is improved.

REFERENCES

• 1: Savelsbergh M.W.P, Sol M. 1991. The General Pickup and Delivery Problem. Transportation Science 29, 17--29.
• 2: Dumas Y, Desrosiers J, Soumis F. 1991. The Pickup and Delivery Problem with Time Windows. European Journal of Operational Research 54, 7--22.
• 3: Lenstra J.K., Rinnooy K. 1981. Complexity of Vehicle Routing and Scheduling Problem. Networks 11, 221--227.
• 4: Giselher, Pankratz. 2006. A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows. Submitted for publication (available from ftp://ftp.fernuni-hangen.de/pub/fachb/wiwi/winf/forschng/publi/gp_p5_neu.pdf).
• 5: Potter T, Bossomaier T. 1995. Solving Vehicle Routing Problem with Genetic Algorithms. Computer Society, Los Alamitos, California, 788--793.
• 6: Jih, W.-R, Hsu,Y.-J. 1999. Dynamic Vehicle Routing Using Hybrid Genetic Algorithms. Computer Society, Los Alamitos, Califonia, 453--458.
• 7: Schonberger.J, Kopfer.H, Mattfeld.DC. 2002. A Combined Approach to Solve the Pickup and Delivery Selection Problem. Operations Research Proceedings, 150--155.
• 8: Jung S, Haghani A. 2000. A Genetic Algorithm for Pick-up and Delivery Problem with Time Windows. Transportation Research Board, 1--7.
• 9: Kopfer. H, Pankratz. G, Erkens. E. 1994. Die Entwicklung eines hybriden Genetischen Algorithmus fur das Tourenplanungs problem. Operational Research 16, 21--32.
• 10: 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
• 11: Emanuel Falkenauer, Genetic Algorithms and Grouping Problems, John Wiley & Sons, Inc., New York, NY, 1998
• 12: Li H, Lim A. 2001. A Metaheuristic for Solving the Pickup and Delivery Problem with Time Windows. Computer Society 13, 160--167.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures; Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
genetic algorithm, grouping genetic algorithm, multi-strategy grouping genetic algorithm, pickup and delivery problem with time windows, vehicle routing problem