DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2015.42

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

Authors: Niklas Paulsen, Florian Diedrich, and Klaus Jansen

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{paulsen_et_al:OASIcs.ATMOS.2015.42,
  author =	{Paulsen, Niklas and Diedrich, Florian and Jansen, Klaus},
  title =	{{Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{42--55},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.42},
  URN =		{urn:nbn:de:0030-drops-54608},
  doi =		{10.4230/OASIcs.ATMOS.2015.42},
  annote =	{Keywords: TSPTW, minimum tour duration, dynamic programming, heuristics}
}

Search Results

Documents authored by Paulsen, Niklas

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

Abstract

Cite as

Thanks for your feedback!

Could not send message