Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月4日

查看全文
  • Simen T. Vadseth,
  • Henrik Andersson,
  • Jean-François Cordeau,
  • Magnus Stålhane

摘要

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.