License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2015.42
URN: urn:nbn:de:0030-drops-54608
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5460/
Go to the corresponding OASIcs Volume Portal

Paulsen, Niklas ; Diedrich, Florian ; Jansen, Klaus

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

pdf-format:
11.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{paulsen_et_al:OASIcs:2015:5460,
  author =	{Niklas Paulsen and Florian Diedrich and Klaus Jansen},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5460},
  URN =		{urn:nbn:de:0030-drops-54608},
  doi =		{10.4230/OASIcs.ATMOS.2015.42},
  annote =	{Keywords: TSPTW, minimum tour duration, dynamic programming, heuristics}
}

Keywords: TSPTW, minimum tour duration, dynamic programming, heuristics
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI