Mixed integer programs to improve solutions of vehicle routing problems with intra-route constraints
Simen Tung Vadseth et al.
What the paper says
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.
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.