An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem

Quan Lu () and Maged Dessouky ()
Additional contact information
Quan Lu: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193
Maged Dessouky: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193

Transportation Science, 2004, vol. 38, issue 4, 503-514

Abstract: We consider the multiple vehicle pickup and delivery problem (MVPDP) with the objective of minimizing the total travel cost and the fixed vehicle cost. Most of the optimization-based approaches for solving the MVPDP are developed for a restrictive hard time window or tight capacity environment that depend significantly on the reduction of the feasible solution space. We develop an alternative optimization solution approach for the MVPDP that does not require these constraints to be tight. The problem is formulated as a 0–1 integer-programming problem. A branch-and-cut algorithm is developed to optimally solve the problem. Four classes of valid inequalities for the MVPDP are proposed. By using the proposed solution approach, we were able to optimally solve problem instances of up to 5 vehicles and 17 customers on problems without clusters and up to 5 vehicles and 25 customers on problems with clusters within a stopping criterion of three CPU hours on a SUN Fire 4800 server.

Keywords: pickup and delivery; routing; optimization; 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 (31)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0040 (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:4:p:503-514

Access Statistics for this article

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