Solving the Capacitated Arc Routing Problem Using Logic‐Based Benders Decomposition

ABSTRACT

In this paper, we present a new exact algorithm for solving the capacitated arc routing problem using logic‐based benders decomposition. The master problem is formulated based on variables that measure the number of deadheadings of each edge. These variables have been converted into binary form, which enables the use of both new and stronger inequalities. The subproblem is transformed into a node‐routing feasibility problem, where we exploit that the number of edge traversals is fixed, as this information is provided by the master problem. The computational results show that the proposed algorithm outperforms the current state‐of‐the‐art on about half of the classical instances, in many cases by an order of magnitude. The algorithm is also able to determine the optimal solution for a previously unsolved instance.