Arc-routing for winter road maintenance

Abstract The winter road maintenance arc-routing is recognized as a notoriously hard problem not only from the algorithmic point of view. This paper lays down foundations of theoretical understanding of our new winter road maintenance optimization for the Plzeň region of the Czech Republic which has been implemented by the regional authorities since the winter of 2019–20. Our approach is not, contrary to most of existing work, based on the integer and linear programming machinery. We concentrate on studying arc-routing on trees. This is practical since routes of single vehicles can be well represented by trees, and allows algorithms and complementary hardness results. We then extend the approach to the bounded tree width graphs. This leads to considering planar graphs which well abstract the realistic road networks. We formalize important aspects of the winter road maintenance problem which were not formalized before, e.g., public complaints. The number of complaints from public against the winter road maintenance is a quantitative measure of the quality of the service which is focused on, e.g., in media or in election campaigns. A fear of ’complaints’ is a fact every optimizer must deal with. Hence, a formal model of public complaints and its inclusion in the optimization is vital. Our formalization of the winter road maintenance is robust in the sense that it relates to well-known extensively studied concepts of discrete mathematics like graph cutting and splitting of necklaces.