Mixed integer programs to improve solutions of vehicle routing problems with intra-route constraints

Abstract Many variants of the vehicle routing problem (VRP) pose significant computational challenges in logistics optimization, and improvement heuristics have emerged as effective tools for refining solutions found by local search methods and meta-heuristics. This paper introduces exact route-modifying improvement models (RMIMs). They are improvement models that aim to assemble high-quality solutions by selecting routes from a pool while allowing modifications to be made to the selected routes. These models can be embedded in a complete heuristic or used to post-optimize solutions produced by other methods. We evaluate our proposed models on vehicle routing problems with intra-route constraints, including the multi-trip VRP (MTVRP), the pickup and delivery problem with time windows (PDPTW), and the VRP with time windows (VRPTW). For the MTVRP, we propose a full matheuristic that uses a RMIM to achieve best known solutions for most benchmark instances for the MTVRP. By warm-starting with the current best known solutions from the literature the RMIMs improve many existing solutions for both the PDPTW and the VRPTW. These findings showcase the value of using RMIMs to enhance solutions to different types of VRPs.