Novel Modeling Approach for Arc Routing Problems

This paper introduces a novel modeling approach for arc routing problems (ARPs) which is easily applied to multiple ARP variants (e.g., capacitated ARPs, multiple depot ARPs, heterogeneous fleets). Our approach tracks the order in which arcs are serviced, rather than explicitly tracking deadheading, and couples the sequence of serviced arcs to the cumulative demand collected along the route. As each route is defined solely by the order of serviced arcs, our approach does not use vehicle indices to represent individual vehicles/routes, but rather the vehicle type, which makes our approach agnostic to vehicle fleet size and thereby suitable for solving ARPs with large fleets and capable of solving ARPs with heterogeneous fleets with unknown distributions of vehicle type without significantly increasing model size compared to ARPs on the same graph with a homogeneous fleet. We also propose a novel method of formulating “return‐to‐facility” (RtF) constraints in location arc routing problems (LARPs) by using a “tagging” system built into the flow variables to ensure each vehicle route returns to the depot it departed from. Our “tagging” method does not add depot indices to flow and binary variables, nor does it add constraints with separate binaries assigning arcs to depots, leading to a more compact model for LARPs. Using a proposed four‐step solution algorithm, we can solve several benchmark LARP instances to optimality, and are often able to obtain solutions of comparable or better objective value than those found by heuristics. We demonstrate the application of our modeling approach not only on the basic CARP and LARP, but also on the LARP with capacitated depots, CARP with time windows, and multi‐depot CARP.