Snow plow route optimization: A constraint programming approach

摘要

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: (ⅰ) a graph transformation, thereby transforming CARP into an equivalent node routing problem, or (ⅱ) 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.