Solving multiple vehicle pickup and delivery problems in multisite systems by a rigorous optimization approach

DONDO, RODOLFO; MENDEZ, CARLOS; CERDÁ, JAIME

Supply Chain Optimization Part II. (Vol. Eds. Papageorgiou L. and M. Georgiadis)

Wiley-VCH Verlag GmbH & Co.

Lugar: Weinheim - Germany; Año: 2008; p. 29 - 60

Abstract: This work presents a novel MILP mathematical formulation for the multiple vehicle pickup and delivery problem with time windows (MVPDPTW). Since it is a NP-hard problem, most of the current solution approaches are of heuristic type, thus providing good but not necessarily optimal solutions. The proposed two-index model can be solved using a branch-and-cut commercial package to find the best vehicle routes and schedules for moderate-size MVPDPTW problems. The formulation has been generalized to also consider pure pickup and delivery nodes, heterogeneous vehicles, multiple depots as well as many-to-many transportation requests. The definition of allocation variables assigning requests rather nodes to vehicles allows to drastically diminishing the number of 0-1 variables.  Using the notion of compatible requests, exact pruning rules aim to eliminate unnecessary variables and constraints and speed-up the MILP solution procedure have been derived. Optimal solutions for a variety of benchmark problems featuring different sizes in terms of customer requests and vehicles, distinct cluster/random pickup & delivery locations and a range of time-window width distributions are reported. A MVPDPTW problem instance with many-to-many transportation requests was also successfully tackled. From the results, it follows that medium-size MVPDPTW problem instances comprising up to 25 customer requests, 50 pickup & delivery locations and 14 vehicles can be solved to optimality in quite reasonable CPU times.