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

Hernández-Pérez, Hipólito; Salazar-Gonz´lez, Juan-José
May 2004
Transportation Science;May2004, Vol. 38 Issue 2, p245
Academic Journal
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.


Related Articles

  • Fleet Size Planning when Outside Carrier Services Are Available. Klincewicz, John G.; Luss, Hanan; Pilcher, Martha G. // Transportation Science;Aug90, Vol. 24 Issue 3, p169 

    The delivery of goods from a warehouse to local customers is a critical aspect of a material logistics system. A strategic decision must be made periodically (e.g., once a year) whether to maintain a private delivery fleet, to employ outside commercial carrier services, or to use a combination...

  • Time Window Constrained Routing and Scheduling Problems. Solomon, Marius M.; Desrosiers, Jacques // Transportation Science;Feb88, Vol. 22 Issue 1, p1 

    We have witnessed recently the development of a fast growing body of research focused on vehicle routing and scheduling problem structures with time window constraints. It is the aim of this paper to survey the significant advances made for the following classes of routing problems with time...

  • A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy. Powell, Warren B. // Transportation Science;Nov89, Vol. 23 Issue 4, p231 

    Summarizes the basic theory behind network sensitivity to establish the theoretical properties of the new approximation. Sensitivity questions in the context of truckload trucking; Characteristics of the new approximation; Summary of the theory of network degeneracy; Numerical experiments on...

  • 'There is a Claim.' Clark, Doug // Traffic World;1/5/2004, Vol. 268 Issue 1, p6 

    Comments on the key factors to consider when transporting goods. Common complaints of customers; Need to educate the driver picking up the load; Walk-through areas of the empty trailer; Necessity of checking anything that could change the condition of the load while in normal transit before it...

  • Routing Revolution. Klie, Leonard // Food Logistics;Oct2004, Issue 72, p30 

    Focuses on modern routing and transportation management solutions for delivery companies in 2004. Direct Route software from Appian Logistics Software Inc.; Effect of implementing the Tracking and Planning Service from Cube Route on Piller's Sausages and Delicatessens and Stewart Foodservice;...

  • Rising to the challenge.  // Canadian Transportation & Logistics;Aug2005, Vol. 108 Issue 8, p24 

    Reports on the fourth annual Shipper's Choice Awards survey of the "Canadian Transportation and Logistics" magazine which sets industry benchmarks for performance excellence and identifies the 44 carriers that exceed them. Seven key performance indicators; Record number of participants; Survey...

  • Are They "Accessorial" or "Excess-orial" Charges? Bradley, Jack // Canadian Transportation & Logistics;Aug2005, Vol. 108 Issue 8, p54 

    Discusses the management of transportation costs and charges in Canada. Loading and unloading delay/detention; Border crossing fees and delays; Declared valuation and insurance fees; Fuel, currency and other surcharges; Payment terms; Control of the "extra" costs.

  • Thinking the unthinkable. Perry, John // Sustain' Magazine;2007, Vol. 8 Issue 5, p31 

    The article focuses on sustainability efforts of logisticians to create an environmentally friendly supply chain. According to the author, doing right things in business logistics such as less packaging and fewer vehicles used to deliver provide significant environmental benefits. The author...

  • PRINCIPLES OF LOGISTIC MANAGEMENT OF FREIGHT FORWARDING SERVICE. Dmitriev, A. V. // Vestnik of Astrakhan State Technical University Series: Economic;2013, Issue 1, p126 

    The general questions of logistic management of freight forwarding services are studied. The main logistic processes in transportation systems are revealed. The principal scheme of transport and logistic system of freight delivery is considered. The basics of building an effective system of...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics