Xu, Zhou; Lai, Xiaofan; Lim, Andrew; Wang, Fan An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree. (English) Zbl 1387.90041 Networks 63, No. 2, 179-195 (2014). Summary: 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. Cited in 1 Document MSC: 90B06 Transportation, logistics and supply chain management 90C59 Approximation methods and heuristics in mathematical programming Keywords:approximation algorithm; pickup and delivery; traveling salesman problem; tree PDFBibTeX XMLCite \textit{Z. Xu} et al., Networks 63, No. 2, 179--195 (2014; Zbl 1387.90041) Full Text: DOI