Premium
The one‐commodity pickup and delivery travelling salesman problem on a path or a tree
Author(s) -
Wang Fan,
Lim Andrew,
Xu Zhou
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20116
Subject(s) - travelling salesman problem , pickup , path (computing) , tree (set theory) , product (mathematics) , computer science , mathematics , mathematical optimization , combinatorics , algorithm , artificial intelligence , computer network , geometry , image (mathematics)
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 ( n 2 / min ( k , n )) algorithm for any arbitrary k , and two O ( n ) algorithms for k = 1 and k = ∞. For the tree case, O ( n 2 ) 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. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 24–35 2006