×

The one-commodity pickup and delivery travelling salesman problem on a path or a tree. (English) Zbl 1103.90098

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 \(0(n^2/\min(k,n))\) algorithm for any arbitrary \(k\), and two \(O(n)\) algorithms for \(k=1\) and \(k=\infty\). For the tree case, \(O(n^2)\) and \(O(n)\) algorithms are proposed for \(k=1\) and \(k=\infty\), respectively. Moreover, when \(k\) is arbitrary, the problem becomes NP-hard in the strong sense.

MSC:

90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anily, Naval Res Logistics 56 pp 654– (1999)
[2] Anily, SIAM J Comput 29 pp 327– (1999)
[3] Anily, Networks 22 pp 419– (1992)
[4] Anily, Oper Res Lett 16 pp 11– (1994)
[5] Estimating and bidding for heavy construction, Prentice-Hall, Englewood Cliffs, NJ, 2000.
[6] Chalasani, SIAM J Comput 28 pp 2133– (1999)
[7] , Computers and intractability–A guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
[8] Gendreau, Comput Oper Res 26 pp 699– (1999)
[9] Henderson, Eur J Oper Res 145 pp 72– (2003)
[10] Hernandez-Perez, Discrete Appl Math 145 pp 126– (2004)
[11] Labbe, Oper Res 39 pp 616– (1991)
[12] Mosheiov, Eur J Oper Res 79 pp 299– (1994)
[13] Psaraftis, Manage Sci 36 pp 212– (1990)
[14] Tsitsiklis, Networks 22 pp 263– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.