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 segments 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 Problem (PCRPP):  In the PCRPP, edges that are serviced give a profit, but deadheading through edges generates costs.  Both service and deadheading 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 exceed a given bound.  The solution approach for this problem is again based on branch-and-cut.