Solving, Generating, and Modeling Arc Routing Problems

Abstract

Arc routing problems are an important class of network optimization problems. In this dissertation, we develop an open source library with solvers that can be applied to several uncapacitated arc routing problems. The library has a flexible architecture and the ability to visualize real-world street networks. We also develop a software tool that allows users to generate arc routing instances directly from an open source map database. Our tool has a visualization capability that can produce images of routes overlaid on a specific instance.

We model and solve two variants of the standard arc routing problem: (1) the windy rural postman problem with zigzag time windows and (2) the min-max K windy rural postman problem. In the first variant, we allow servicing of both sides of some streets in a network, that is, a vehicle can service a street by zigzagging. We combine insertion and local search techniques to produce high-quality solutions to a set of test instances. In the second variant, we design a cluster-first, route-second heuristic that compares favorably to an existing heuristic and produces routes that are intuitively appealing. Finally, we show how to partition a street network into routes that are compact, balanced, and visually appealing.