DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2012.325

k-delivery traveling salesman problem on tree networks

Authors: Binay Bhattacharya and Yuzhuang Hu

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract

In this paper we study the k-delivery traveling salesman problem (TSP)on trees, a variant of the non-preemptive capacitated vehicle routing problem with pickups and deliveries. We are given n pickup locations and n delivery locations on trees, with exactly one item at each pickup location. The k-delivery TSP is to find a minimum length tour by a vehicle of finite capacity k to pick up and deliver exactly one item to each delivery location. We show that an optimal solution for the k-delivery TSP on paths can be found that allows succinct representations of the routes. By exploring the symmetry inherent in the k-delivery TSP, we design a 5/3-approximation algorithm for the k-delivery TSP on trees of arbitrary heights. The ratio can be improved to (3/2 - 1/2k) for the problem on trees of height 2. The developed algorithms are based on the following observation: under certain conditions, it makes sense for a non-empty vehicle to turn around and pick up additional loads.

Cite as

Binay Bhattacharya and Yuzhuang Hu. k-delivery traveling salesman problem on tree networks. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 325-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.FSTTCS.2012.325,
  author =	{Bhattacharya, Binay and Hu, Yuzhuang},
  title =	{{k-delivery traveling salesman problem on tree networks}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{325--336},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.325},
  URN =		{urn:nbn:de:0030-drops-38707},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.325},
  annote =	{Keywords: k-delivery traveling salesman problem, approximation algorithms}
}

Search Results

Documents authored by Hu, Yuzhuang

k-delivery traveling salesman problem on tree networks

Abstract

Cite as

Thanks for your feedback!

Could not send message