An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree

Zhou Xu; Xiaofan Lai; Andrew Lim; Fan Wang

doi:10.1002/net.21535

An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree

Zhou Xu, Xiaofan Lai, Andrew Lim, Fan Wang

Research output: Journal article publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

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.

Original language	English
Pages (from-to)	179-195
Number of pages	17
Journal	Networks
Volume	63
Issue number	2
DOIs	https://doi.org/10.1002/net.21535
Publication status	Published - 1 Mar 2014

Keywords

approximation algorithm
pickup and delivery
traveling salesman problem
tree

ASJC Scopus subject areas

Information Systems
Computer Networks and Communications

More information

10.1002/net.21535

Cite this

@article{282a780746de4604875c7318e0f9b63f,

title = "An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree",

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.",

keywords = "approximation algorithm, pickup and delivery, traveling salesman problem, tree",

author = "Zhou Xu and Xiaofan Lai and Andrew Lim and Fan Wang",

year = "2014",

month = mar,

day = "1",

doi = "10.1002/net.21535",

language = "English",

volume = "63",

pages = "179--195",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree

AU - Xu, Zhou

AU - Lai, Xiaofan

AU - Lim, Andrew

AU - Wang, Fan

PY - 2014/3/1

Y1 - 2014/3/1

N2 - 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.

AB - 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.

KW - approximation algorithm

KW - pickup and delivery

KW - traveling salesman problem

KW - tree

UR - http://www.scopus.com/inward/record.url?scp=84891762132&partnerID=8YFLogxK

U2 - 10.1002/net.21535

DO - 10.1002/net.21535

M3 - Journal article

SN - 0028-3045

VL - 63

SP - 179

EP - 195

JO - Networks

JF - Networks

IS - 2

ER -

An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this