An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree. Issue 2 (8th October 2013)

• Record Type: Journal Article
• Authors: Xu, Zhou; Lai, Xiaofan; Lim, Andrew; Wang, Fan
• Is Part Of: Networks. Volume 63:Issue 2(2014:Mar.)
• Page Start: 179
• Page End: 195
• Publication Date: 2013-10-08
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21535
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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</p> </abstract>