An exact algorithm for the multiple vehicle pickup and delivery problem

We consider the Multiple Vehicle Pickup and Delivery Problem (MVPDP) with 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.