Snow plow route optimization: A constraint programming approach

Joris Kinable, Willem-Jan van Hoeve and Stephen F. Smith

IISE Transactions, 2020, vol. 53, issue 6, 685-703

Abstract: 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.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2020.1831713 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:53:y:2020:i:6:p:685-703

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2020.1831713

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().