Snow plow route optimization: A constraint programming approach

Joris Kinable (Corresponding author), Willem Jan van Hoeve, Stephen F. Smith

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)


Many cities have to cope with annual snowfall, but are struggling to manage their snow plowing activities efficiently. Despite the fact that winter road maintenance has been a popular research subject for decades, very few papers propose scalable models that can incorporate side constraints encountered in real-life applications. In this work, we propose a Constraint Programming formulation for a Snow Plow Routing Problem (SPRP). The SPRP under consideration involves finding a set of vehicle routes to service a street network in a pre-defined service area, while accounting for various vehicle constraints and traffic restrictions. The fundamental mathematical problem underlying SPRP is the well-known Capacitated Arc Routing Problem (CARP). Common Mathematical Programming (MP) approaches for CARP are typically based on: (i) a graph transformation, thereby transforming CARP into an equivalent node routing problem, or (ii) a sparse network formulation. The CP formulation in this article is based on the former graph transformation. Using geospatial data from the city of Pittsburgh, we empirically show that our CP approach outperforms existing MP formulations for SPRP. For some of the larger instances, our CP model finds 26% shorter plowing schedules than alternative Integer Programming formulations. A test pilot held with actual vehicles proves the applicability of our approach in practice: our routes are 3–156% shorter than the routes the city of Pittsburgh generated with commercial routing software.

Keywords: Winter road maintenance, arc routing, vehicle routing, mathematical programming
Originele taal-2Engels
Pagina's (van-tot)685-703
Aantal pagina's19
TijdschriftIISE Transactions
Nummer van het tijdschrift6
Vroegere onlinedatum16 nov 2020
StatusGepubliceerd - 2021


Duik in de onderzoeksthema's van 'Snow plow route optimization: A constraint programming approach'. Samen vormen ze een unieke vingerafdruk.

Citeer dit