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

Maria Battarra (), Güneş Erdoğan (), Gilbert Laporte () and Daniele Vigo ()
Additional contact information
Maria Battarra: Dipartimento di Elettronica, Informatica e Sistemica, University of Bologna, 47521 Cesena (FC), Italy
Güneş Erdoğan: Department of Industrial Engineering, Özyeğin University, 34662 Altunizade, İstanbul, Turkey
Gilbert Laporte: Department of Management Sciences, HEC Montréal, Montréal, Québec J3T 247, Canada
Daniele Vigo: Dipartimento di Elettronica, Informatica e Sistemica, University of Bologna, 47521 Cesena (FC), Italy

Transportation Science, 2010, vol. 44, issue 3, 383-399

Abstract: 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.

Keywords: the traveling salesman problem; combinatorial optimization; exact algorithm (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1100.0316 (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:44:y:2010:i:3:p:383-399

Access Statistics for this article

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