Snow plow route optimization: A constraint programming approach - Robotics Institute Carnegie Mellon University

Snow plow route optimization: A constraint programming approach

Joris Kinable, Willem-Jan van Hoeve, and Stephen F. Smith
Journal Article, IISE Transactions, November, 2020

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.

Notes
The authors thank Mr. Lee M. Haller, Department of Innovation & Performance of Pittsburgh for providing us with the data used in the computational experiments, as well as the staff from the 3rd Division of Public Works for evaluating the quality of our routes.

BibTeX

@article{Kinable-2020-125790,
author = {Joris Kinable and Willem-Jan van Hoeve and Stephen F. Smith},
title = {Snow plow route optimization: A constraint programming approach},
journal = {IISE Transactions},
year = {2020},
month = {November},
}