PSR Group Ltd

ROUTE
OPTIMIZATION

Snowfighting with GIS:
Route Planning Applications

prepared for URISA '97, Toronto, Canada
July 22, 1997

James F. Campbell
School of Business Administration
University of Missouri - St. Louis
8001 Natural Bridge Road 
St.Louis, MO USA 63121 - 4499

Snow and ice control is a key component of winter maintenance for many urban and regional public works agencies.  Ensuring safe mobility for passengers and pedestrians, even in the worst of winter weather, is a difficult and expensive task.  Geographic information systems (GIS), coupled with optimization techniques and global positioning system (GPS) technology, provide new tools and opportunities to improve winter travel.  This paper describes some applications of GIS to route planning for snow fighting in urban and regional organizations.  The goal is to present real world experiences from implementations, including actual costs and benefits, when possible. 

The paper is organized as follows.  Section 1 describes snow and ice control activities and discusses some GIS opportunities in winter maintenance.  Section 2 presents results from three applications of route optimization in Ottawa, Canada, Suffolk County, UK and Indiana, USA.  Section 3 is the conclusion.

Section 1: Snow and Ice Control Activities 

Snow and ice control are important and expensive winter activities in many regions.  The basic objective is to provide safe transportation by maintaining mobility on the transportation network.  Table 1 lists the major steps in snow removal and disposal for a large city Montreal, (300,000 truckloads) in an average year.  In Montreal the first step in snow disposal is to establish temporary (12 hour) parking restrictions to remove vehicles that may otherwise hinder operations.   Then the snow can be plowed into rows or piles in the middle of the road.   Snow is then loaded into trucks using snow loading vehicles (such as snow blowers) or front-end loaders.  Loaded trucks then transport the snow to designated disposal sites where it may safely accumulate.  Table 2 lists snow fighting equipment used in Montreal to provide an indication of the magnitude of resources involved.  Some cities, especially in Japan, augment snow hauling with elaborate snow gutter systems that allow individuals to manually dump snow into gutter or sewer systems which contain flowing water that transports the snow outside the city.

Snow fighting in urban areas is particularly difficult and expensive due to the greater population densities and the lack of space for allowing snow to accumulate.  Table 3 shows population, snowfall and average January temperature for several large world and U.S. cities.  Sapporo, Japan is an extreme case with an average of over 5 meters of snow each winter.  The budget for winter maintenance in Sapporo exceeds $80 million.  Montreal, Canada, which receives about half as much snow has a winter maintenance budget of approximately $60 million.   Cities in more temperate regions can also face large expenses for severe winters.   For example, New York City, which receives less than 100 cm of snow on average, had a budget of $14 million for the 1995-96 Winter, but spent $57 million!  The so called "Blizzard of '96" in the eastern U.S. had an estimated cost of $20 billion (according to Byron Lord of the Federal Highway Administration) and shut down the federal government of the United States for several days due to the inability of the City of Washington D.C. to clear and remove the snow.

The advent of geographic information systems provides a host of opportunities for improving winter maintenance operations.  Because snow and ice control operations involve spatial or geographic activities and components, including travel on roadways to and from depots, storage sites and disposal sites, geographic information systems can provide a foundation for creating, maintaining and analyzing relevant data.  A key component of the data is obviously the road network.   However the basic spatial data needs to be augmented with a variety of road and traffic descriptive (or attribute) data to be useful for winter maintenance.  This includes information on the length, width, and priority class for each street in the network, detailed information on interchanges, intersections, bridges and other special features, as well as traffic information such as volumes, speeds, etc.  In addition to the road data, information is needed on the available equipment, including the type of vehicle, operating characteristics and depot location; as well as the materials, including amount available and locations.

This paper focuses on use of GIS-based decision support systems to optimize vehicle routes for spreading and plowing operations.  GIS is also a component of automated vehicle location (AVL) systems that provide real-time and historical tracking of vehicles using global positioning system (GPS) technology.   Other uses of GIS for snow fighting occur in snow disposal operations.

Section 2: Route Optimization

A large cost for winter maintenance is incurred by the vehicles involved in spreading and plowing operations.  Route optimization involves determining the best routes for such vehicles.  This involves the use of GIS to maintain and display road network data and routes, and mathematical modeling techniques to optimize vehicle routes.  The objective in route design generally falls in one of two categories: minimize cost for given service levels, or optimize service level for given equipment.  The first objective (minimize cost for given service levels) may be operationalized as minimize total length of travel or minimize deadhead travel.   Since the entire road network must be serviced, minimizing the deadhead (i.e., non-service) travel minimizes total travel.  The second objective (optimize service level for given equipment) seeks to make the best use of the available fleet and personnel.   

GIS and mathematical modeling have been applied successfully for many vehicle routing problems in distribution and logistics, and there are a number of commercial software packages, as well as vendors and consultants, available for solving such problems.  However, the experience and available software in the area of winter maintenance is much more limited.  While there are a number of small scale test studies reported, there are few large scale success stories and very few documented applications.  However, a variety of projects are under way and reports of applications are likely to increase in the next few years.  This section provides details on three real-world applications.

Ottawa, Canada

Ottawa, Canada has a population of 314,000 and an annual snowfall of 220 cm (87 inches).  The budget for winter maintenance is approximately $16 million for treating 2400 lane-km.  Ottawa has develop plow routes for approximately one-third (800 lane-km) of the city using the GeoRoute software (from PSR Group Ltd.).  The experience in Ottawa includes both computer simulation tests, as well as field tests in Winter 1995-96.  The results are from Miner and Bretherton (1996) and a conversation with Simon Bretherton (Projects Director of PSR Group Ltd.).

For the computer simulation tests, the region of interest was originally served by 24 single plow routes and 9 tandem plow routes (two plow routes operating together).  Table 4 provides results of the computer simulation tests.   The row for "Original" refers to the routes prior to optimization with GeoRoute.  Two sets of routes were developed using the GeoRoute software.  A revised set of routes were developed by allowing the streets in a route to be re-sequenced, but not allowing any changes in the streets treated by each route.   Thus, the revised routes included the exact set of streets as the original routes, but the streets are traveled in a different sequence.  An optimized set of routes were developed by allowing the GeoRoute software to determine which streets are on each route and in what sequence they are visited.  

For the revised routes, both the average length of a route and the variation in route length are reduced.  Thus, the routes are shorter (on average) and the workload is better balanced among the routes.  This is true for both single and tandem routes.  The optimized routes show further improvements.   Although the average route time increases relative to the revised routes, for both single and tandem routes, optimization eliminates routes: five single routes and one tandem route are eliminated.  The result is that the total plowing time (number of routes x average route length) decreased from 165.6 hours for the 24 single original routes to 114 hours for the 19 single optimized routes.  The total time for the tandem routes decreased from 37.8 hours for the 9 tandem original routes to 32.8 for the 8 tandem optimized routes.  The variation in route length was also greatly reduced by optimization.  The results of the optimization produced projected savings of 17% of the hired plow hours per storm, which equated to $15,000 per storm, or $150,000 per year.  

To better evaluate the optimized routes, field tests were carried out in Winter 1995-96.  For the field tests, only the optimized single routes were considered.  Drivers were given a map and text description of their new optimized route.  A number of problems became apparent after the first storm (November 14, 1995), due to drivers not adequately understanding the new routes.   Consequently, for the remainder of the winter, the field tests were scaled back to include only four routes and the drivers on these routes were trained to be familiarized with their routes.  The remaining portion of the city was served by its original (current) routes.  In the following eight storms that winter, the optimized routes fared better than the non-optimized (current) routes.  Productivity on the four optimized routes ranged from 3.2 km per hour to 3.75 km per hour.  Productivity on the original routes averaged 2.0 km per hour.  Thus, the optimized routes showed an increased productivity of 60% to almost 90%.

Suffolk County, UK

Suffolk County, England has a population of 660,000 and experiences icing conditions, as well as a small amount of snow each winter (less than 10 cm of snow on average).  The budget for winter maintenance is approximately £1.2 million and prior to 1997 the County had been responsible for maintaining approximately 6900 km of roadways.  This total includes 400 km of trunk roads, for which maintenance responsibilities were transferred away from the County (to consultants employed by the central government) in April 1997.  Thus, these 400 km were no longer the County's responsibility, and the existing routes needed to be re-designed to treat only the County roads.

Suffolk County began using the GeoRoute software in September 1996 to develop new routes.  Results are expected to be implemented in winter 1997-98.  Some preliminary results are available based on the application of GeoRoute to re-design the Priority 1 salting network.  The Priority 1 salting network originally included 37 routes covering 1430 km of county roads.  All these routes were limited to a length of two hours to provide frequent treatment.  The GeoRoute software produced 35 routes rather than 37, with the two hour treatment time.   The software allowed other service levels (time limits) to be evaluated and produced 35 routes with a 2.5 hour time limit.  Thus, the number of routes was reduced by 2 or 4, depending on the time limit.  The estimated savings for each route eliminated was £11,000 per year, so the total savings for the Priority 1 network is projected to be £22,000-£44,000 per year, depending on the level of service.

Peter Thompson (Suffolk County Director of Environment and Transport) estimated the cost for route re-design to be £65,000, including purchase of the GeoRoute software.  He estimated the cost of re-designing the routes manually to be at least £30,000.  In addition, he indicated that manual solution (as in the past) would have produced less efficient routes and prevented evaluation of different levels of service.

Indiana, USA

The state of Indiana, USA has a population of 5,800,000 and receives an average snowfall that ranges from 150 cm in the northwest (near lake Michigan) to 30 cm in the south.  The Indiana Department of Transportation (INDOT) is responsible for winter maintenance on approximately 29,000 lane-miles of roadways and has an annual budget for snow and ice control of $23 million.  INDOT is currently using the CASPER (Computer Aided System for Planning Efficient Routes) system to design its routes.  This was develop in a joint highway research project by researchers art Purdue University and INDOT.  Work continues on refinements and enhancements of the system.  The CASPER system and its use are described in several publications (Wright 1993; Wang and Wright 1994; Wang, Kandula and Wright 1995).  It is not a stand-alone system that produces final routes automatically, but is designed to be used in an interactive fashion by a knowledgeable planner to help the planner develop better routes.   It is not commercially available at this time.

CASPER was used to develop routes for approximately one-third of the state (in the north and west portions) in 1992-93 and these routes were subsequently tested in the winters of 1994-97.  Extensive data collection efforts were conducted to evaluate the routes.  The region was originally covered by over 300 routes.  Use of CASPER software eliminated 26 routes initially.  The new routes were implemented and tested over several winters beginning in 1993.  Field experiences resulted in many modifications, and after two years nine routes were added back.   Thus, the net result after three years was a decrease of 17 routes (26 minus 9).

The cost to develop CASPER was reported as $172,000, as a joint Purdue University - INDOT project.  Based on the field experiences in one-third of the state since 1993, Larry Goode of  INDOT has projected savings of $250,000 - $400,000 per year for using CASPER in the entire state.  These are based on savings of $75,000 per truck (ten-year life) for each route eliminated and savings of $7,130 per year for maintenance, fuel and labor for each route eliminated.  He further has estimated the net present savings for the state over 20 years to be $4.1 million.

Table 5 summarizes the three route optimization applications described above.  In this table I have estimated the cost of the GeoRoue solution in Ottawa to be $85,000.  There have been a number of applications of GIS-based route optimization to snow and ice control routing, but details are not readily available.  For example, the GeoRoute software has been used in a variety of other Canadian cities including Laval, Charlesbourg, Nepean, and the Ottawa-Carlton Regional Government, but details have not been published.  I am not aware of other large-scale commercial GIS-based route optimization software packages, nor of other successful software packages designed for routing vehicles for snow and ice control.  A variety of GIS-based routing software is available for many transportation and delivery operations, but systems that specifically address routing of snow plows and spreader trucks are sorely lacking.  The GeoRoute software is the most complete package for such operations - and probably the most widely used.

Table 6 summarizes some information from an ongoing project in Hennepin County, Minnesota, USA to select route planning software.   (Hennepin County includes the city of Minneapolis).  The county and state department of transportation are collaborating on a project to implement computerized route planning for snow and ice control, and as a first step they undertook a survey of existing software packages (Gini and Zhao, 1997).  The three software packages they identified as potential solutions were GeoRoute, TransCad and gsICE.  TransCad is a more general purpose transportation software system that would require modifications to address winter maintenance operations.  The gdsICE system is an attempt to commercialize the CASPER system (developed by Purdue and INDOT).  I have not been able to obtain information on gdsICE from a vendor and I believe it is not available.   (This may be due to a dispute over the ownership of the CASPER/gdsICE system and to reorganization of the vendor of gdsICE).

Section 3: Conclusion

• Travel distances and costs are more accurate.
• Alternatives can be evaluated/explored to answer "What if..." questions.
• Updates and revisions are easier.
• Response to contingencies is improved.

 

References

Campbell, J.F. and Langevin, A. (1995). Operations Management for Urban Snow Removal and Disposal. Transportation Research 29A, 359-370.

Wright, Jeff R. (1993). The Computer Aided System for Planning Efficient Routes, Joint Highway Research Project Draft Final Report, FHWA/IN/JHRP-93-8, Purdue University, West Lafayette, Indiana.

Tables

Table 1: Snow Removal & Disposal Operations in Montreal, Canada

Table 2: Snow Removal Equipment used in Montreal, Canada

Table 3: Snow Cities

Table 4: Computer Simulation Tests in Ottawa, Canada

Table 5: Route Optimization Summary

Table 6: Route Planning Software Costs For Hennepin County, Minnesota, USA

source: Gini and Zhao (1997)

URISA ‘97 - GIS and Snow Removal Contacts