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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations

Author(s)

  • Zhou Xu
  • Xiaofan Lai
  • Andrew Lim
  • Fan Wang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)179-195
Journal / PublicationNetworks
Volume63
Issue number2
Online published8 Oct 2013
Publication statusPublished - Mar 2014

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. © 2013 Wiley Periodicals, Inc.

Research Area(s)

  • approximation algorithm, pickup and delivery, traveling salesman problem, tree

Citation Format(s)

An improved approximation algorithm for the capacitated TSP with pickup and delivery on a tree. / Xu, Zhou; Lai, Xiaofan; Lim, Andrew et al.
In: Networks, Vol. 63, No. 2, 03.2014, p. 179-195.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review