Document Open Access Logo

Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows

Authors Niklas Paulsen, Florian Diedrich, Klaus Jansen

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2015.42.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Niklas Paulsen
Florian Diedrich
Klaus Jansen

Cite AsGet BibTex

Niklas Paulsen, Florian Diedrich, and Klaus Jansen. Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 42-55, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/OASIcs.ATMOS.2015.42

Abstract

We present heuristics to handle practical travelling salesman problems with multiple time windows per node, where the optimization goal is minimal tour duration, which is the time spent outside the depot node. We propose a dynamic programming approach which combines state labels by encoding intervals to handle the larger state space needed for this objective function. Our implementation is able to solve many practical instances in real-time and is used for heuristic search of near-optimal solutions for hard instances. In addition, we outline a hybrid genetic algorithm we implemented to cope with hard or unknown instances. Experimental evaluation proves the efficiency and suitability for practical use of our algorithms and even leads to improved upper bounds for yet unsolved instances from the literature.
Keywords
  • TSPTW
  • minimum tour duration
  • dynamic programming
  • heuristics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Slim Belhaiza, Pierre Hansen, and Gilbert Laporte. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Computers &Operations Research, 52:269-281, 2014. Google Scholar
  2. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1):61-63, 1962. Google Scholar
  3. Jacques Desrosiers, Yvan Dumas, Marius M Solomon, and François Soumis. Time constrained routing and scheduling. Handbooks in operations research and management science, 8:35-139, 1995. Google Scholar
  4. Yvan Dumas, Jacques Desrosiers, Eric Gelinas, and Marius M Solomon. An optimal algorithm for the traveling salesman problem with time windows. Operations research, 43(2):367-371, 1995. Google Scholar
  5. Peter Eades, Brendan D McKay, and Nicholas C Wormald. On an edge crossing problem. In Proc. 9th Australian Computer Science Conference, volume 327, page 334, 1986. Google Scholar
  6. Michel Gendreau, Alain Hertz, Gilbert Laporte, and Mihnea Stan. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46(3):330-335, 1998. Google Scholar
  7. David S Johnson. A theoretician’s guide to the experimental analysis of algorithms. Data structures, near neighbor searches, and methodology: fifth and sixth DIMACS implementation challenges, 59:215-250, 2002. Google Scholar
  8. Shen Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, The, 44(10):2245-2269, 1965. Google Scholar
  9. Chryssi Malandraki and Robert B Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90(1):45-55, 1996. Google Scholar
  10. Gilles Pesant, Michel Gendreau, Jean-Yves Potvin, and Jean-Marc Rousseau. On the flexibility of constraint programming models: From single to multiple time windows for the traveling salesman problem. European Journal of Operational Research, 117(2):253-263, 1999. Google Scholar
  11. Jean-Yves Potvin and Samy Bengio. The vehicle routing problem with time windows part II: genetic search. INFORMS journal on Computing, 8(2):165-172, 1996. Google Scholar
  12. Martin WP Savelsbergh. Local search in routing problems with time windows. Annals of Operations research, 4(1):285-305, 1985. Google Scholar
  13. Martin WP Savelsbergh. The vehicle routing problem with time windows: Minimizing route duration. ORSA journal on computing, 4(2):146-154, 1992. Google Scholar
  14. Hiroaki Sengoku and Ikuo Yoshihara. A fast TSP solver using GA on Java. In Third International Symposium on Artificial Life, and Robotics (AROB III’98), pages 283-288, 1998. Google Scholar
  15. Christian Tilk and Stefan Irnich. Dynamic programming for the minimum tour duration problem. Technical Report LM-2014-04, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact