Partitioning a street network into compact, balanced, and visually appealing routes

In practice, it is often desirable for the routes of vehicles to be compact and separate. A set of routes is compact if the streets serviced by each route are geographically clustered, and separated if the routes overlap minimally. We consider the Min–Max K Windy Rural Postman Problem (MMKWRPP), in which the objective is to route a homogeneous fleet of K vehicles such that the cost of the longest route is minimized. We develop a heuristic that is algorithmically simple, produces solutions that are comparable in quality to those produced by an existing approach, and performs well with respect to metrics that quantify compactness and separation. Our heuristic uses a partitioning scheme in which the weight of a vertex includes contributions from both incident streets requiring service and the distance needed to travel to a vertex. We present computational results for a set of instances that we generate from real-world street networks and for a set of artificial instances. Our code is part of the Open-source Arc Routing Library (OAR Lib) at https://github.com/Olibear/ArcRoutingLibrary. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 290–303 2017.