1 Search Results for "Paulsen, Niklas"

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-dev.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}
}
  • Refine by Author
  • 1 Diedrich, Florian
  • 1 Jansen, Klaus
  • 1 Paulsen, Niklas

  • Refine by Classification

  • Refine by Keyword
  • 1 TSPTW
  • 1 dynamic programming
  • 1 heuristics
  • 1 minimum tour duration

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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