Solving Multiple Vehicle Pickup and Delivery Problems in Multisite Systems by a Rigorous Optimization Approach

R. DONDO; C.A. MÉNDEZ; J. CERDÁ

Supply Chain Optimization - Part II

WILEY-VCH

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

Transportation plays a central role in every supply chain (SC) because products are rarely produced and consumed in the same location. In the general case, the supply chain comprises a set of facilities (production plants, suppliers, warehouses), manufacturing, and/or storing the products, which need to be efficiently delivered to a set of consumer nodes (retailers, stores, customers) in order to fulfill certain requests. This work presents a novel MILP-based mathematical formulation focused on the operational level of multiple vehicle pickup and delivery problems with time windows (MVPDPTW) commonly arising in multisite systems. 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 formoderate-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 procedures 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 and 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 and delivery locations, and 14 vehicles can be solved to optimality in quite reasonable CPU times. Hybrid solution methods combining the proposed exact model with heuristic-type procedures can be used to provide effective solutions for large scale problems.