Search for a command to run...
ABSTRACT The split delivery vehicle routing problem with time windows (SDVRPTW) extends the well‐known VRPTW by the option of satisfying individual customer demands with more than one vehicle. The SDVRPTW is relatively well studied from an exact viewpoint, but efficient heuristics that are able to provide near‐optimal solutions within short runtimes have not been proposed in the literature. In this article, we design a heuristic for the SDVRPTW, called granular tabu search with balanced customer splitting (GTS‐BCS), that is based on the principle of a priori customer splitting introduced by Chen, International Transactions in Operational Research, 24, 27–41, 2017. The main idea of this approach is to split customers into subcustomers with an a priori splitting rule and then use a solver for the unsplit counterpart of the problem to solve the resulting split‐instance. We use theoretical properties of optimal SDVRPTW solutions and numerical experiments to find well‐balanced splitting rules that find a good tradeoff between the flexibility needed to explore a large number of promising splits of the original demand and keeping the number of generated subcustomers as low as possible. We observe that starting the search from a so‐called no‐split solution, that is, a solution in which customer splits are only possible for customers whose demand exceeds the vehicle capacity, has strong positive effects on both solution quality and runtimes. The final configuration of our GTS‐BCS is able to compute near‐optimal solutions on the common SDVRPTW benchmark sets within comparatively short runtimes. We also investigate whether the proposed splitting rules can be transferred to the standard SDVRP. To this end, we use the same a priori customer splitting framework as in GTS‐BCS and integrate the hybrid genetic search of Vidal, Computers and Operations Research, 140, 105643, 2022 for solving the unsplit counterpart of the SDVRP – the CVRP. Numerical experiments show that the resulting algorithm is nearly competitive to the state‐of‐the‐art dedicated methods for the SDVRP.