Heuristics for the One-Commodity Pickup-and-Delivery Traveling Salesman Problem

Hipólito Hernández-Pérez () and Juan-José Salazar-González ()
Additional contact information
Hipólito Hernández-Pérez: DEIOC, Facultad de Matemáticas, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain
Juan-José Salazar-González: DEIOC, Facultad de Matemáticas, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain

Transportation Science, 2004, vol. 38, issue 2, 245-255

Abstract: This paper deals with a generalisation of the well-known traveling salesman problem (TSP) in which cities correspond to customers providing or requiring known amounts of a product, and the vehicle has a given upper limit capacity. Each customer must be visited exactly once by the vehicle serving the demands while minimising the total travel distance. It is assumed that any unit of product collected from a pickup customer can be delivered to any delivery customer. This problem is called one-commodity pickup-and-delivery TSP (1-PDTSP). We propose two heuristic approaches for the problem: (1) is based on a greedy algorithm and improved with a k -optimality criterion and (2) is based on a branch-and-cut procedure for finding an optimal local solution. The proposal can easily be used to solve the classical “TSP with pickup-and-delivery,” a version studied in literature and involving two commodities. The approaches have been applied to solve hard instances with up to 500 customers.

Keywords: pickup and delivery; traveling salesman; heuristics; branch and cut (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0086 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:38:y:2004:i:2:p:245-255

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().