GeoRoute
PSR Group Ltd

ROUTE
OPTIMIZATION

            Intelligent
transportation
          
Solutions                 
    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Effective snowfighting requires solving a variety of difficult strategic and operational problems, most of which have a strong spatial component. GIS therefore is a natural candidate for helping develop better snow and ice control. Routing of spreader trucks and plows is an especially important part of snowfighting, in both rural and urban areas. Among the benefits from a GIS-based approach to route planning are:

  • 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.

The bottom line however, is better vehicle routes. This includes shorter routes as well as better balanced routes (all routes will be similar length). A GIS-based approach can also help ensure that desired service levels are met for all routes. The results from computer simulations, as well as field tests, indicate that optimized routes can create substantial savings. GIS therefore might be taken to mean Greatly Improved Snowfighting.

 

References

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

Gini, M. and Zhao, Y. (1977). Automated Route Planning and Optimizing Software. Final Report. Published by Minnesota Department of Transportation. February 1997.

Miner, W. Maxwell and Bretherton, Simon (1996). Route Optimization for Winter Maintenance Activities - 1995-1996 Field Trial of Roadway Snow Plowing. 1996 TAC Annual Conference. Draft.

Wang, Jin-Yuan, Kandula, Padma and Wright, Jeff R. (1995). Evaluation of Computer-Generated Routes for Improved Snow and Ice Control, Transportation Research Record 1509, 15-21.

Wang, Jin-Yuan and Wright, Jeff R. (1994). Interactive Design of Service Routes. Journal of Transportation Engineering 120, 6, 897-913.

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

Activity

Responsibility

Notes

1. Spreading De-icers &     Abrasives City approx. 100,000 metric tons/year
2. Snow Clearing City & Contractors snowplows, sidewalk plows
3. Parking Restrictions City & Contractors 30,000 temporary signs
10,000 permanent signs
4. Snow Loading City & Contractors snowblowers, front-end loaders, trucks
5. Snow Hauling & Disposal City 300,000 truckloads

    

Table 2: Snow Removal Equipment used in Montreal, Canada

Activity Equipment
Spreading 100 street spreaders
Sidewalks 106 sidewalk plows/spreaders
Clearing 208 sidewalk snowplows
195 graders
130 snowplows
123 front-end loaders
Removal & Disposal 90 snowblowers
188 graders
170 sidewalk plows
103 service vehicles
84 front-end loaders
79 pickup trucks
660 transport trucks

 

Table 3: Snow Cities

City

Population
(MSA)

Average
Snowfall (in.)

Average
January   Temp.

Sapporo, Japan

1,700,000

200

-5 C

St. Petersburg, Russia

4,400,000

110

-6 C

Harbin, China

2,600,000

100

-18 C

Montreal, Canada

3,300,000

92

-10 C

Ottawa, Canada

1,000,000

90

-10 C

Helsinki, Finland

520,000

71

-8 C

Calgary, Canada

820,000

59

-10 C

Toronto, Canada

4,200,000

51

-7 C

Syracuse, NY

740,000

114

Buffalo, NY

1,200,000

91

Rochester, NY

1,100,000

90

Denver, CO

1,600,000

65

New York, NY

19,550,000

29

Washington, D.C.

6,700,000

23

 

Table 4: Computer Simulation Tests in Ottawa, Canada

  number of routes

min

time (hrs)
avg

max

Original

24 single

3.7

6.9

11.9

Revised

24 single

2.5

5.0

8.0

Optimized

19 single

5.8

6.0

6.5

Original

9 tandem

2.1

4.2

6.5

Revised

9 tandem

2.0

3.5

5.5

Optimized

8 tandem

3.0

4.1

4.5

 

Table 5: Route Optimization Summary

Location

Software

Road Length

Cost

Savings
Ottawa, Canada

GeoRoute

2,400 lane-km

$85,000??

$150,000/yr

Suffolk County, UK

GeoRoute

1,430 km

65,000

22,000-44,000/yr

Indiana, USA

CASPER

46,400 lane-km

$172,000

$250,000-400,000/yr

 

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

GeoRoute

TransCAD

gdsICE??

Single license

$60,000

$10,000

$300,000

Additional licenses

$60,000

$9,000

to be determined

Data Conversion

$2,000

to be determined

included

On-site training/support

$25,000

to be determined

$8000/4 days

Customization

$10,000

to be determined

to be determined

Annual support

15%

$1000/copy

to be determined

Total

$175,000

???

>$1,000,000

source: Gini and Zhao (1997)

 

URISA ‘97 - GIS and Snow Removal Contacts

Dr. James F. Campbell
School of Business Administration
University of Missouri - St. Louis
8001 Natural Bridge Road
St. Louis, MO 63121-4499
314-516-6125
campbell@jinx.umsl.edu

 

ROUTE OPTIMIZATION/PLANNING

GeoRoute

Simon Bretherton, Project Director
PSR Group Ltd.
301 Moodie Dr., Suite 121
Nepean, Ontario
Canada K2H 9C4
613-820-6019
psrgroup@psrgroup.on.ca
www.psrgroup.on.ca/psrsite.htm

CASPER

Jeff Wright
School Of Civil Engineering
Purdue University Indiana DOT
West Lafayette, IN 47907-1284
765-494-2175
wrightje@ecn.purdue.edu

Larry Goode
Operations Support Section
100 N. Senate Avenue, Room 925
Indianapolis, IN 46204-5551
317-232-5424

TransCAD

Howard A. Slavin, President
Caliper Corporation
617-527-4700
www.caliper.com

Automated Route Planning

Marc Simcox
Hennepin County
612-930-2629


GO TO:
    
LIST OF WHITE PAPERS        OPTIMIZATION HOME PAGE        ATIS HOME PAGE