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 publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)179-195
Number of pages17
JournalNetworks
Volume63
Issue number2
DOIs
Publication statusPublished - 1 Mar 2014

Keywords

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

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this