Who: City of Centennial, Colo.
No. square miles: 28
No. lane miles: 1,066; 563 of which are plowed in winter
No. trucks: 10
Efficiency increases: 28% to 40% faster
Implementation cost: $65,000
Your department may take an ad-hoc approach to snowplowing, one that defines routes by geography and relies on drivers to navigate routes most efficiently. This strategy is popular because it works. Unfortunately, it also duplicates effort.
Efficiently moving people and products through a defined network of streets is an engineering challenge that goes back centuries. That’s because, regardless of design, any single network provides more than one potential route. Add the multiple resources and hierarchies common to snow plowing and other public works routes, and the number of possible routes expands exponentially.
Public works departments in Canada, China, Europe, and Japan address this challenge via arc-routing — finding the most efficient path within a network, or series of nodes. In 2012, Centennial, Colo., became one of the first U.S. cities to use another algorithm, based on the Chinese Postman Problem, to optimize snowplowing.
First, some theory
The challenge inherent in combinatorial routing is known as the Konigsberg bridge problem. A man wants to walk the seven bridges linking two islands with the City of Kaliningrad, Russia, just once (see graphic on page 30). Swiss mathematician Leonhard Euler’s 1735 solution applies to an arbitrary number of islands and bridges, giving rise to graph theory: visually modeling mathematical formulas as nodes connected by lines. In 1962, Chinese mathematician Kwan Mei-Ko applied graph theory to a mail carrier who must travel every road in a city but wants to do so just once.
A network with an odd number of nodes will contain routes that start and end at different nodes. It’s navigable but occasionally redundant. This can be rectified by linking pairs of odd nodes with additional arcs. The Chinese Postman algorithm considers all possible pairings of nodes of odd order and finds the connecting paths of minimum weight. The grouping with the minimum weight is selected and the arcs duplicated to find the route that contains every arc.
Now, the real-world application
Centennial used to assign 10 trucks to 10 routes divided into Priority One (arterial roads) and Priority Two (collector roads).
The city began its research by creating a histogram showing the number of routes and distance traveled for each Priority One and Priority Two truck. Some trucks covered 30 miles, others more than 60. During winter storms, operators and supervisors compensated for these unbalanced workloads by improvising.
One reason for the misallocation was hierarchical routing, which prioritizes which streets and roads will be plowed first, second, third, etc. Centennial’s Priority One routes, however, are better served with echelon plowing, which manages snow removal by placing trucks in sequence on a route.
Since the process of optimizing routes is highly iterative, FleetRoute software developer C2Logix Inc. was brought in to find the shortest distance through the city’s entire network of both Priority One and Priority Two roads using its 10 trucks. This produced two new networks:
Priority One: five routes of two trucks each for echelon plowing.
- Priority Two: 10 routes of one truck each.
- Process: After servicing Priority One routes in teams, the trucks plow Priority Two routes independently.
The software optimized the Priority One network based on completion times for each route, then developed an average time for the five teams to do the entire network.
-
In addition to snowplowing, the Chinese Postman Problem can be used to optimize bus, refuse collection, and street sweeping routes.In Eldorado, N.M., CH2M Hill applied the mathematical formula to water meter reading. The engineering consulting firm used the same approach it used to reconfigure snowplow routes for its client, the City of Centennial, Colo., but with even more dramatic results:
48% (an average of 3,873 miles) fewer miles driven per year66% lower fuel costs50% fewer labor hours48% (2.2 metric tons) less CO2 emissionsOne less day required to complete read cycle
Each team was timed, and routes were adjusted to bring each team as close as possible to the average elapsed time for the group overall. Since balancing routes is more art than science, C2Logix reviewed and tweaked the routes for the best spatial fit within the network.
The same process was applied to Priority Two routes using 10 single trucks instead of five two-truck teams.
However, crunching numbers is just the first step in route optimization. Organizational success depends on the ability to effectively lead employees through process change. Including supervisors and drivers was critical both to the overall performance of the routes and employee buy-in.
After the routes were created, supervisors drove them. The software modeled and balanced the routes based on their comments. Then drivers were asked to drive the new routes and the routes further refined.
GPS enhances efficiency
The city then programmed the new routes into Garmin nuvi 1450 LMT automotive GPS receivers, a technological enhancement that enabled drivers to focus on plowing and stay on track at night and during heavy snowfalls. Relief drivers performed at the same level as experienced drivers because they didn’t have to be familiar with the new routes. The results were phenomenal:
Dec. 21, 2011, 12-inch snowfall. Crews completed the old Priority One and Priority Two networks in eight hours.
- Feb. 2, 2012, 15-inch snowfall. They completed the reconfigured networks in 5.5 hours.
- Feb. 23, 2012, 4-inch snowfall. Completed in 4.5 hours.
Our efforts produced a high rate of return on investment. Savings were immediate and have been sustained. Operational efficiencies lowered resource requirements while improving service.
