We address the Undirected Team Orienteering Arc Routing Problem (UTOARP). In this problem, demand is placed at some edges of a given undirected graph and served demand edges produce a profit. Feasible routes must start and end at a given depot and there is a time limit constraint on the maximum duration of each route. The problem asks for a set of \(|K|\) maximum profit routes. We exploit optimality conditions for this problem and propose two new undirected formulations with binary variables. We also introduce a logic-based Benders decomposition derived from these formulations and show how to strengthen the logic-based Benders cuts. Furthermore, we design several new families of valid inequalities, where some of them are derived from conflict graphs. We also develop a problem-specific GRASP-based heuristic to improve the performance of exact algorithms. Extensive computational tests are conducted to examine the performance of the proposed formulations, valid inequalities, and heuristics. Our findings highlight the pivotal role of logic-based Benders decomposition and conflict graphs in solving the UTOARP, marking their first application in the context of arc routing problems to the best of our knowledge. Moreover, these techniques hold promise for advancing solution approaches in broader arc routing contexts.
The Undirected Team Orienteering Arc Routing Problem: Formulations, Valid Inequalities, and Exact Algorithms
\(\)