New Models and Methods for Arc Routing

Abstract. The talk presents two non-standard extensions for single-vehicle arc-routing problems a.k.a. postman problems: First, street seg-ments that require a service on both sides of the street can be covered either by two separate services or by a single zigzag service. Instead of deciding the type of service beforehand, we propose to take into account the zigzagging option when designing a tour. We present MIP models for the extension of Undirected Chinese and Rural Postman Problem (UCPP, URPP). We show that these models can be solved reasonable well using a cutting-plane or branch-and-cut algorithm. Second, capacitated postman problems occur as subproblems in column-generation and Lagrangian-relaxation approaches of the capacitated arc-routing problem. In order to model these and similar subproblems or submodels, we present the Profitable Capacitated Rural Postman Prob-lem (PCRPP): In the PCRPP, edges that are serviced give a profit, but deadheading through edges generates costs. Both service and deadhead-ing consume time. The task is to find a tour that maximizes the difference of profits and costs, while the overall duration of the tour must not ex-ceed a given bound. The solution approach for this problem is again based on branch-and-cut