A multi-start local search matheuristic for the capacitated arc routing problem with irregular services
研究带不规则服务的周期性容量弧路径问题，提出一种结合数学规划与多起点局部搜索的启发式算法，在垃圾收集等场景中有效降低路由成本。
This paper investigates the periodic capacitated arc routing problem with irregular services, a challenging combinatorial optimization problem that arises in various real-world scenarios, such as waste collection and road maintenance. This problem is defined over a mixed graph and asks for scheduling a fleet of capacitated vehicles to meet the demands associated with a set of required links, while minimizing the routing costs over a given planning horizon. Each required link has its own service plan, indicating the frequency with which its demand must be met over the planning horizon. To solve this problem, we propose a novel matheuristic approach that combines a route-based mathematical formulation with a multi-start local search framework. The matheuristic incorporates two distinct local search strategies, which are crucial for improving solution quality, as revealed by the computational experiments. Additional experiments further confirm the effectiveness of the proposed matheuristic, comparing its performance against an exact method and a heuristic algorithm from the literature, solving the uncapacitated version of the problem. Finally, we analyze the impact of introducing the capacity constraint by comparing the solutions obtained in the two cases. • A novel matheuristic approach for the periodic CARP with Irregular Services is presented. • A multi-start Local Search Matheuristic is developed. • The presented Matheuristic exploits the mathematical formulation. • An extensive computational study supports the effectiveness of the Matheuristic.