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.

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

CERRONE, Carmine;
2017-01-01

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) at https://github.com/Olibear/ArcRoutingLibrary. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 290–303 2017.
http://www.interscience.wiley.com/jpages/0028-3045/
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11695/62329
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact