Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8292
Title: An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree
Authors: Xu, Z 
Lai, X
Lim, A
Wang, F
Keywords: Approximation algorithm
Pickup and delivery
Traveling salesman problem
Tree
Issue Date: 2014
Publisher: Wiley-Blackwell
Source: Networks, 2014, v. 63, no. 2, p. 179-195 How to cite?
Journal: Networks 
Abstract: 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.
URI: http://hdl.handle.net/10397/8292
ISSN: 0028-3045
DOI: 10.1002/net.21535
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

1
Last Week
0
Last month
1
Citations as of Sep 7, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Sep 12, 2017

Page view(s)

60
Last Week
4
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.