Abstract
We propose to continue research into development of a system for real-time optimization and management of snow plowing operations. The envisioned system will (1) generate near-optimal plowing plans (or alternatively will import and adapt pre-existing plowing plans) to fit current resource constraints and storm characteristics (vehicles, salt inventories, road priorities), (2) dynamically update these plans as execution proceeds and provide early alerting of potential problems, and (3) generate routing adjustments for efficiently recovering from detected problems (e.g., impassable route, broken down vehicle). To enable this closed-loop capability, the system will exploit GPS tracking information to maintain the state of snowplow vehicles, and incorporate an application running on mobile devices for communicating turn-by-turn routing instructions to vehicle drivers. Our goal is field test and subsequently transition the system to the City of Pittsburgh’s Department of Public Works (DPW).
During the past year, we have made great progress toward this goal:
- We have worked with the City of Pittsburgh’s DPW to understand the problem they face and the in-house data sources and software support tools they are adopting;
- We have developed and demonstrated a prototype route optimization procedure that takes into account most snow plowing constraints considered relevant by the DPW; and
- We have developed and field-tested a tablet-based application for in-vehicle installation and communication of turn-by-turn instructions.
We propose to extend the prototype snowplow route planner (1) to incorporate the remaining constraints relevant to DPW operations and to support dynamic, real-time route revision, (2) to conduct a comparative analysis of generated snowplow plans with current PWD generated plans, measuring reduction in such metrics as overall clearing time, (3) to integrate both the planner and the in-vehicle app with PWD’s data sources and software tools, and (4) to carry out a series of field tests to validate the developed technology and transition results. To carry out these tasks we request funding of $105,151.
Problem: In cold weather cities like Pittsburgh, snowstorms can have a significant disruptive effect on both mobility and safety, and consequently the faster that streets can be cleared the better. Yet in most cities (including Pittsburgh), static plans for snowplowing are developed using simple allocation schemes, e.g., streets are divided among vehicles based on geographic area, and each driver determines his/her individual route. These schemes are used because they are easy to implement and they work but the resulting snow plowing operation can be quite inefficient. In extreme cases (e.g., the Pittsburgh storm of February 5-6, 2010 where snow removal took several days to accomplish), this inefficiency can lead to protracted periods of hardship for urban residents and travelers.
The generation of efficient vehicle routes for snow removal is a challenging optimization problem, requiring consideration of constraints relating to resources (vehicle and crew availability; vehicle speed, range, home location), coverage topology (number of passes per road, one way roads, dead ends, refueling locations), snow-clearing priorities (main arteries before side streets) and refresh rates (depending on storm intensity). Variations of the problem have been formalized as the Chinese Postman problem and the Capacitated Arc Routing Problem, and both problems have been shown to be inherently difficult to solve optimally (in other words it is only possible to generate optimal solutions for very small instances of the problem). Nevertheless, it is possible to produce near-optimal solutions with a variety of approximate search procedures (e.g., [Perrier 2008, Salazar 2012]), and these solutions can lead to substantial improvements in snowplowing performance. Centennial, Colorado, for example, recently reduced the time required to clear streets by 28-40% by focusing on optimization of routes [Sedlak 2013].
Any ability to produce efficient snowplowing routes, however, is susceptible to execution-time dynamics. Impassible road segments due to blocking vehicles that are stuck or to unaccounted for construction projects will mandate deviations from pre-planned routes, which can result in significant efficiency loss if left to driver response. Events such as snow plow breakdowns or shifts in storm intensity can similarly render pre-planned routes obsolete and require re-optimization. As has been recently suggested in [ITS 2014], even greater improvements to snow removal operations can be expected if snow plow route optimization is coupled with a real-time ability to re-route vehicles when circumstances warrant.
Over the past year and a half, the City of Pittsburgh Department of Public Works (DPW) has begun to take steps to improve their snow plowing operations. First, following the lead of Chicago Public Works, a “snow plow tracker” web site has been put in place to provide residents with real-time information on the locations and progress being made by various City vehicles during the course of a storm. Second, a commercial software product called Route Smart was adopted by DPW to, most basically to provide a basis for maintaining snow plow routing plans in electronic form (as opposed to the current paper routes that are used in practice), and in the longer term to provide a more flexible means of generating new snow plow plans. Work in DPW over the past year has focused on analyzing and extending the core data sources used by Route Smart to produce snowplow routing plans (e.g., here.com map data) to accurately encode all relevant road geometry, topology and movement constraints (e.g., number of lanes, width of road segments, barriers that prevent u-turns, hills that must be plowed in only one direction, road segment priorities, etc.). As of last month (November 2015), PWD has achieved the ability to generate an initial snowplow routing plan in Route Smart, and work continues on improving this capability and the underlying data sources. The goal over the next several months is to generate a set of 1.5 - 2 hour routes to replace those currently used by District 3 – the portion of the City that encompasses several East End communities, including Oakland, Squirrel Hill, Point Breeze, and Shadyside. (Interestingly, the current operational concept is to continue to print out these routes on paper to provide these plans to drivers.)
Description
Approach and Progress: Our research over the last year has focused on providing a complementary dynamic snowplow routing (and rerouting) solution. By dynamic snowplow routing we refer to the following set of real-time capabilities: (1) to customize a pre-generated static plan (as would be produced by Route Smart) that is “pulled off the shelf” to fit the available resources and constraints of the current storm situation, (2) to generate a customized snow plow routing plan from scratch if a static starting point plan does not exist, (3) to update and monitor the plan as execution proceeds, and (4) to incrementally adjust a snowplow routing plan as conditions that prevent its execution (e.g., impassable road segment) become known. To facilitate both detection of unexpected events and communication of dynamic updates to snowplow routes, our research has also focused on development of a mobile app to enable real-time interaction with snowplow drivers.
Over the past year, we have made significant progress toward our research goals:
• Incremental constraint-based route generation – Building from our prior research in constraint-based search and its application to various vehicle routing problems [Smith 2004, Barbulescu 2010, Rubinstein 2011, 2012], we have developed a prototype snowplow route generation procedure and demonstrated its scalability and optimizing capability [Kinable 2015]. The procedure exploits a constructive heuristic to quickly generate a good feasible solution, and then conducts a local search to improve the solution as time permits. The constructive heuristic is inherently incremental, and thus the procedure is naturally extensible to the problem of incrementally adjusting snowplow routing plans in response to unexpected events.
Because we have not yet been able to obtain the City of Pittsburgh DPW data sources (due to the parallel DPW data validation and cleansing efforts mentioned above), we have imported and experimented Open Street Maps data (an open source platform). Using this data we have incorporated a large number of the constraints relevant to the City of Pittsburgh problem, and through interaction with the DPW we have acquired additional constraints related to vehicles, salt allocation and fuel consumption. Our utilization of Open Street Maps has also served to assist DPW’s constraint modeling efforts within Route Smart.
• In-vehicle turn-by-turn instructions - We have developed a tablet-based mobile app for communicating snowplow routes (and route updates) to snowplow drivers, and for enabling communication of unexpected events back to the dynamic planner. The app accepts a snowplow route as input from a remote server process and then using GPS location data, issues turn-by-turn instructions to the driver in the manner of a typical navigation system. The app also indicates salt resupply excursions and refueling stops as necessary. In the event of an unexpected problem, the app allows the driver to communicate this information back to the planner to initiate rerouting.
Successful trial runs with the app have been made, using plans generated by our prototype dynamic routing procedure in open loop (a demonstration video is forthcoming). Originally developed on an android phone, the app is now running on Google Nexus 9 tablet.
We propose to continue this research and further develop these technology components to enable a full pilot test of this dynamic snowplow routing system and promote its subsequent transition to DPW. Specifically, we propose to (1) extend our prototype route planning system to incorporate the remaining constraints relevant to City of Pittsburgh operations, (2) generalize the prototype to additionally provide a dynamic re-planning capability, (3) integrate with Route Smart data sources to enable inter-operability with the dynamic route planner and the mobile app, and (4) testing and validation of the overall system.
Timeline
Major Tasks: We propose to carry out the following tasks:
• Task 1: Integration of Route Smart plan outputs with mobile app [3 months] –Now that DPW has developed the capability to produce snowplow routes with Route Smart, a logical next step is to establish the ability to push a city generated plan to the mobile app and demonstrate the ability to provide turn-by-turn capability in open loop (i.e., without capability to dynamically re-plan routes when problems arise). A meeting with DPW personnel was held earlier this month to discuss the details of a Route Smart generated plan in anticipation of this task. We will develop an API that translates a plan exported by Route Smart into the input format required by the mobile app. This capability will provide the early opportunity to field test the use of turn-by-turn instructions during execution of a vehicle’s snowplowing route. Once developed, we will conduct an experiment where a District 3 snowplow route generated using Route Smart is imported into our mobile app and used in real-time to drive the route. We will also demonstrate the capability to District 3 drivers, and gather feedback on overall utility of the in-vehicle route guidance capability. Based on both the field test and user feedback, further refinements will be made to the mobile app.
• Task 2: Dynamic Route Planner Development [8 months] – Further development of the current prototype route planner will involve three principal subtasks:
o Task 2a: Integration with Route Smart data sources [3 months] – As noted earlier, the current route planning prototype operates with Open Street Maps data. This path was taken out of necessity to allow progress to be made while DPW was coming up to speed with Route Smart data sources and extending these sources to capture all constraints relevant to route generation. However, at this point, DPW is now in a position to export these data sources for CMU use. These data sources are built on here.com map data and exportable as ESRI-formatted geographical data. Accordingly, this task involves adaptation of the route planner’s current map data interface to one that provides a comparable API to the ESRI software platform.
o Task 2b: Extended Coverage of Snow Plow routing constraints [3 months] – Concurrent with the integration task in Task 2a, we will extend the current route planning prototype to incorporate the important remaining constraints relevant to Pittsburgh operations. Such constraints include restrictions on the classes (size) of vehicles that can be used to clear various road segments, maximum ride time constraints, prohibited u-turn options, and road segment priorities.
o Task 2c: Comparative analysis of route generation capability [1 month] – Following completion of Tasks 2a and 2b, we will perform a comparative analysis of the planner’s route generation capabilities with that of Route Smart, using a set of generated District 3 snowplow routing plans. We will evaluate performance on both plan quality metrics such as overall clearing time required and the efficiency of the plan generation process.
o Task 2.d: Incremental Re-routing [4 months]– Finally, we will generalize the prototype capability resulting from Tasks 2a and 2b to enable real-time adjustment of snowplow routes in response to unexpected events (e.g., impassible road segment, broken down vehicle). The constructive heuristic that forms the basis for the current route generation capability provides a natural basis for incrementally a previously generated route. We will develop strategies for balancing overall optimization criteria (i.e., minimize clearing time) with a change minimization objective (to maintain coherence and continuity in plowing operations).
• Task 3: System Integration [3 months] – We will integrate the route planner with the City’s current AVL data feeds (i.e., those used to feed TeMeDa’s web-based vehicle tracking display) to obtain real-time information on vehicle locations for purposes of tracking execution progress and synchronizing the communication of future routing instructions. We will also establish an infrastructure for two-way communication between the dynamic route planner and the mobile device onboard each vehicle.
• Task 4: Field Test [1 month] – During the final month of the project, we will conduct a field test of the full dynamic route-planning prototype. We will start the field test by importing a routing plan into the mobile app (generate either by Route Smart or from scratch), begin execution, and then simulate a problem that requires real-time rerouting. If circumstances permit, we will subsequently undertake a pilot test of the system during a snowstorm to measure practical impact.
Strategic Description / RD&T
Deployment Plan
We propose to continue this research and further develop these technology components to enable a full pilot test of this dynamic snowplow routing system and promote its subsequent transition to DPW. Specifically, we propose to (1) extend our prototype route planning system to incorporate the remaining constraints relevant to City of Pittsburgh operations, (2) generalize the prototype to additionally provide a dynamic re-planning capability, (3) integrate with Route Smart data sources to enable inter-operability with the dynamic route planner and the mobile app, and (4) testing and validation of the overall system.
Collaboration Plan: We intend to continue to work closely with Lee Haller, Deputy Director of Public Works for the City of Pittsburgh. Over the first year of the project, Lee and his staff have met with us several times to help us understand the details of Pittsburgh’s snowplowing problem, and to provide us with the necessary data to develop and preliminarily evaluate our technology results. Lee has indicated his willingness to continue to work closely with us to enable tighter integration with their data sources and software tools, and to provide us with the opportunity to pilot test the system in the field.
Expected Outcomes/Impacts
Broader Impact of Proposed Work: There are increasing examples in recent years of various cities achieving efficiency improvements in snow removal operations as a result of conscious efforts to optimize snow plowing routes, and commercial tools offering such capabilities are becoming available. However, to date these efforts and tools have generally focused on static, upfront route optimization, and efficiency losses that result from unexpected dynamics during plan execution continue to leave headroom for further efficiency gains. The proposed work aims to create a novel, dynamic route planning system capable of responding to such unexpected execution events with appropriately re-optimized routing plans and further improving the performance of snow removal operations.
For the City of Pittsburgh specifically, we expect this project to result in an ability to provide better snow removal service at lower cost, and this is our principal objective. But more broadly, we believe that our results will demonstrate the operational efficiency gains that can be realized in urban environments through the use of real-time, execution-driven snow plow routing (and rerouting) technologies. Given the increasing budgetary strain that many municipalities are currently faced with, the potential for commercializing and propagating the technology we propose to develop to other cities seems very promising.
Expected Outputs
TRID
Individuals Involved
| Email |
Name |
Affiliation |
Role |
Position |
| jkinable@cs.cmu.edu |
Kinable, Joris |
Carnegie Mellon University |
Other |
Faculty - Research/Systems |
| zbr@cs.cmu.edu |
Rubinstein, Zachary |
Carnegie Mellon University |
Other |
Faculty - Research/Systems |
| sfs@cs.cmu.edu |
Smith, Stephen |
Carnegie Mellon University |
PI |
Faculty - Research/Systems |
| jqz@andrew.cmu.edu |
Zhou, Joseph |
Carnegie Mellon University |
Other |
Other |
Budget
Amount of UTC Funds Awarded
$12345.00
Total Project Budget (from all funding sources)
$12345.00
Documents
| Type |
Name |
Uploaded |
| Publication |
Optimization Models for a Real-World Snow Plow Routing Problem |
March 27, 2018, 12:29 p.m. |
| Progress Report |
4_Progress_Report_2018-03-31 |
March 27, 2018, 12:29 p.m. |
| Report |
SnowPlowRoutingFinalReport.docx |
July 19, 2019, 2:05 p.m. |
| Final Report |
4_-_Final_Report.pdf |
July 22, 2019, 4:59 a.m. |
| Publication |
Snow Plow Route Optimization: A Constraint Programming Approach |
Sept. 25, 2020, 6:32 a.m. |
Match Sources
No match sources!
Partners
| Name |
Type |
| City of Pittsburgh |
Deployment Partner Deployment Partner |
