Arc routing problems are combinatorial optimization problems that have many real-world applications, such as mail delivery, snow plowing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. Presented here is a generic algorithmic framework that can be applied to a variety of arc routing problems where a fleet of vehicles is used to visit a predefined set of edges. The main characteristic of the problem that qualifies it for the proposed framework is that each edge should be visited no more than once. This proposed framework uses genetic algorithms, dynamic programming, and local searches in a systematic manner and provides guidelines for applying them to the arc routing problem of one’s choice. We select two problems to test the effectiveness of our proposed framework: the min-max windy K-vehicle rural postman problem and the undirected capacitated arc routing problem. We implement our proposed framework and compare it with existing algorithms using an established benchmark set for each problem. We demonstrate that our generic proposed framework can outperform existing custom-built algorithms.
Article
View Solving Various Classes of Arc Routing Problems with a Memetic Algorithm-based Framework