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 the subject of many research papers over the last 3 decades, very few practical decision support systems have been developed to deal with the complex decision problems involved in this process. In this work, we look into the operational aspects of snow plowing, thereby laying the foundations for an integrated snow plow optimization system. We propose a novel Constraint Programming formulation which captures a large number of practical routing and resource constraints. We show that this CP model scales better than alternative Mathematical Programming formulations. To demonstrate the efficacy of our CP formulation, an extensive computational evaluation is performed. Unlike many traditional works which perform computations on synthetic benchmark data, we utilize geospatial data from the city of Pittsburgh. For this purpose, we elaborate how to extract, process and store the necessary data. Computational experiments show that our approach produces 3\%-156\% shorter routes than the routes the city generated with commercial routing software.

Article

Download

View Snow Plow Route Optimization: A Constraint Programming Approach