Partitioning a street network into compact, balanced, and visually appealing routes. Issue 3 (10th February 2017)

• Record Type: Journal Article
• Authors: Lum, Oliver; Cerrone, Carmine; Golden, Bruce; Wasil, Edward
• Is Part Of: Networks. Volume 69:Issue 3(2017)
• Page Start: 290
• Page End: 303
• Publication Date: 2017-02-10
• Subjects: heuristic solution method -- metaheuristics -- vehicle routing -- arc routing -- open source -- min‐max K windy rural postman problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21730
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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) athttps://github.com/Olibear/ArcRoutingLibrary . © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 290–303 2017