The one-commodity pickup and delivery travelling salesman problem on a path or a tree

Fan Wang, Andrew Lim, Zhou Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

Optimization algorithms for both path and tree topology classes of the one-commodity pickup and delivery travelling salesman problem (1-PDTSP) are proposed in this article, which focus on minimizing the route distance to transport products among pickup and delivery customers by a single vehicle with a limited capacity of k. Each pickup customer provides one unit volume of the product while each delivery customer requires one unit volume of the product. For the path case, we propose an O(n2/min (k, n)) algorithm for any arbitrary k, and two O(n) algorithms for k = 1 and k = ∞. For the tree case, O(n2) and O(n) algorithms are proposed for k = 1 and k = ∞, respectively. Moreover, when k is arbitrary, the problem becomes NP-hard in the strong sense.
Original languageEnglish
Pages (from-to)24-35
Number of pages12
JournalNetworks
Volume48
Issue number1
DOIs
Publication statusPublished - 1 Aug 2006
Externally publishedYes

Keywords

  • Path
  • Pickup and delivery
  • Travelling salesman problem
  • Tree

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this