2026-08-17T19:48:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5460 2024-03-06T10:29:48Z ddc:004 open_access

Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows Paulsen, Niklas Diedrich, Florian Jansen, Klaus TSPTW minimum tour duration dynamic programming heuristics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niklas Paulsen and Florian Diedrich and Klaus Jansen 2015 Is Part Of OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2015.42 urn:nbn:de:0030-drops-54608 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.42 eng https://creativecommons.org/licenses/by/3.0/legalcode