An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem
Authors:
- 1 November 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 38 (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
This publication has 15 references indexed in Scilit:
- A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectivesAnnals of Operations Research, 1995
- A Request Clustering Algorithm for Door-to-Door Handicapped TransportationTransportation Science, 1995
- The pickup and delivery problem with time windowsEuropean Journal of Operational Research, 1991
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman ProblemsSIAM Review, 1991
- An efficient algorithm for the minimum capacity cut problemMathematical Programming, 1990
- An Additive Bounding Procedure for Combinatorial Optimization ProblemsOperations Research, 1989
- A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time WindowsAmerican Journal of Mathematical and Management Sciences, 1986
- An algorithm for the traveling salesman problem with pickup and delivery customersEuropean Journal of Operational Research, 1985
- Optimal Routing under Capacity and Distance RestrictionsOperations Research, 1985
- A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride ProblemTransportation Science, 1980