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

DONDO, RODOLFO G.; MENDEZ, CARLOS A.; CERDÁ, JAIME

Supply Chain Optimization

Wiley-VCH Verlag GmbH

Lugar: Weinheim, Alemania; Año: 2007;

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 multi-site 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 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. Hybrid solution methods combining the proposed exact model with heuristic-type procedures can be used to provide effective solutions for large-scale problems.