The Undirected Team Orienteering Arc Routing Problem: Formulations, Valid Inequalities, and Exact Algorithms

We introduce a new variant of the Undirected Team Orienteering Arc Routing Problem (UTOARP) that incorporates three key features: required edges, capacitated vehicles, and multiple services. These features have been investigated individually in the literature but have not been considered simultaneously. 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 on the maximum duration of each route and a capacity limit on the demand served by each vehicle. The problem asks for a set of up to |K| maximum profit routes while ensuring all required edges are served. We exploit optimality conditions for this problem and propose a new unified, undirected formulation with binary variables. We also introduce a logic-based Benders decomposition derived from this formulation, resulting in a new problem reformulation, and show how to strengthen the logic-based Benders cuts. Crucially, the structure of the Benders subproblems remains unchanged regardless of which of the above features are enabled, highlighting the modularity and flexibility of the approach. Furthermore, we design several new families of valid inequalities, where some of them are derived from conflict graphs. Extensive computational tests are conducted to examine the performance of the proposed formulations and valid inequalities under various settings. We further analyze the solution structure of a real-world instance to illustrate the practical impact of the different features. 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.

Funding: E. Fernández acknowledges partial support from [Grant PID2023-146643NB-I00], funded by the AEI of the Spanish Ministry of Science, Innovation, and Universities [MICIU/AEI/10.13039/501100011033].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0155.