The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs

This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the result...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 2010-08, Vol.44 (3), p.383-399
Main Authors: Battarra, Maria, Erdoǧan, Güneş, Laporte, Gilbert, Vigo, Daniele
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Applied sciences
combinatorial optimization
Commodities
Cost efficiency
Delivery costs
Economic aspects
exact algorithm
Exact sciences and technology
Ground, air and sea transportation, marine construction
Heuristic
Integer programming
Japanese encephalitis viruses
Linear programming
Mathematical optimization
Methods
Postal & delivery services
Routing
Sales management
Studies
the traveling salesman problem
Transportation
Transportation costs
Transportation industry
Transportation planning, management and economics
Travel expenses
Traveling salesman problem
Vehicles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cut algorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.1100.0316