HEURISTICS FOR THE ONE-COMMODITY PICKUP-AND-DELIVERY TRAVELING SALESMAN PROBLEM

This paper presents two heuristic algorithms for a generalization of the well-known traveling salesman problem (TSP) called one-commodity pickup-and-delivery TSP. In this problem, cities correspond to customers providing or requiring known amounts of a product, and the vehicle is given an upper limit capacity. Each customer must be visited exactly once by the vehicle serving the demands while minimizing the total travel distance. It is assumed that any unit of product collected from a pickup customer can be delivered to any delivery customer. The authors propose two heuristic approaches for the problem: the first is based on a greedy algorithm and improved with a k-optimality criterion and the second 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, which involves two commodities. Computational results from applying the proposed approaches demonstrate that the approaches can solve instances with up to 500 customers.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Hernandez-Perez, H
  • Salazar-Gonzalez, J-J
• Publication Date: 2004-5

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 245-255
• Serial:
  • Transportation Science
  • Volume: 38
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Algorithms; Heuristic methods; Optimization; Pickup and delivery service; Traveling salesman problem
• Uncontrolled Terms: Branch and cut algorithms
• Subject Areas: Highways; Planning and Forecasting; Society; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00974044
• Record Type: Publication
• Files: TRIS
• Created Date: May 22 2004 12:00AM