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

Xu Zhou | Zendy; Lai Xiaofan | Zendy; Lim Andrew | Zendy; Wang Fan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

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

Author(s) -

Xu Zhou,

Lai Xiaofan,

Lim Andrew,

Wang Fan

Publication year - 2014

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.21535

Subject(s) - pickup , travelling salesman problem , tree (set theory) , computer science , approximation algorithm , algorithm , vehicle routing problem , product (mathematics) , mathematical optimization , mathematics , routing (electronic design automation) , combinatorics , artificial intelligence , computer network , geometry , image (mathematics)

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. NETWORKS, Vol. 63(2), 179–195 2014

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research