Premium
An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree
Author(s) -
Xu Zhou,
Lai Xiaofan,
Lim Andrew,
Wang Fan
Publication year - 2014
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.21535
Subject(s) - pickup , travelling salesman problem , tree (set theory) , computer science , approximation algorithm , algorithm , vehicle routing problem , product (mathematics) , mathematical optimization , mathematics , routing (electronic design automation) , combinatorics , artificial intelligence , computer network , geometry , image (mathematics)
In this research, we study the capacitated traveling salesman problem with pickup and delivery (CTSPPD) on a tree, which aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree network, such that the vehicle's total travel distance is kept to a minimum. It has several applications in logistics and is known to be NP‐hard. We develop a 2‐approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing CTSPPD literature. Computational results show that the proposed algorithm also achieves good average performance over randomly generated instances. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 179–195 2014