The vehicle routing problem with split pickup and split delivery: mathematical formulations and heuristics

Abstract

The development of algorithms and mathematical methods for solving the vehicle routing problem (VRP) is fundamental to supporting efficient decision-making in logistic systems. Several variants of the VRP have been studied, and nowadays they allow modeling different types of practical and objective requirements. A variant of interest for this project is the Split Delivery VRP (SDVRP), in which the demand of the customers does not need to be satisfied by a single vehicle, therefore multiple visits may occur by different vehicles to the same customer. Another variant of interest is the Pickup and Delivery Problem with Time Windows (PDPTW), which addresses the case in which determined loads should be transported between specific pickup and delivery locations. The purpose of this project is to study a variant of the VRP that combines the SDVRP and the PDP, resulting in the Split Pickup and Split Delivery VRP, which has relevant applications in different situations, like road and maritime transportation. The project intends to elaborate new mathematical models for the combined problem, as well as for its variant with time windows, bringing it closer to real-world scenarios. Unlike past works, the formulations that will be proposed in this project are not based on vehicle-indexed variables. This brings a number of computational advantages related to the reduction of symmetry in the solution space, as observed in related variants. In addition to the proposal of new formulations, the project also intends to develop new tailored heuristics for solving the addressed problems, aiming at determining high-quality solutions in relatively short time spans.(AU)