A hybrid travel distance approximation for a GIS-based decision support system

This paper presents a new method to model travel distances for use in a geographic information system (GIS)-based decision support system. The widespread availability of digital roadway databases and GIS software has led to new approaches and solutions for many logistics and transportation problems. This has also sharpened the focus on how best to use such data and tools for effective decision-making. The distance approximation presented in this paper was developed to model travel distance for trucks hauling snow in an urban snow disposal decision support system. Because these trucks can have significant impacts on traffic and neighborhoods, around the clock, they may be encouraged or required to concentrate their travel on certain roadways (for example, to minimize their impact on residential neighborhoods, or reduce traffic congestion). Thus, the shortest distance or travel time path between two points may not represent the actual truck travel distance. The hybrid approximation presented in this paper combines the shortest path distance on a subset of an urban street network with an analytical distance approximation. This approach blends the accuracy and realism of shortest path travel with the simplicity and reduced computational burden of a distance approximation. The distance approximation was developed and tested using data for the City of Montreal, Canada. This approach may also be useful for logistics and transportation modeling in other contexts, especially when the majority of travel occurs on a small subset of the roadways.

This paper presents a distance approximation developed as part of a project to create a personal computer-based decision support system (DSS) for improving urban snow disposal. This DSS is an interactive tool for strategic and tactical decision making. Strategic design of a snow disposal system includes partitioning an urban region into small geographic sectors, assigning these sectors to snow disposal sites, and allocating snow hauling trucks to sectors. Because of the complexities of the operating environment, the DSS is designed to be used in an iterative and interactive design process that incorporates the expertise of the user. The DSS is also used for real-time tactical decision making such as responding to equipment breakdowns and other contingencies. To assist in all of these decisions, the DSS utilizes travel distance models since major costs in snow disposal are incurred for transporting snow to disposal sites. The goal of the distance modeling portion of the DSS development was to develop a method to approximate distances traveled by large trucks hauling snow that would be easy to use, accurate, and fast enough for use in an interactive personal computer-based decision support environment. Our approach is to model truck travel distance in two parts: first, using a simple and accurate analytical approximation for the short travel on local streets to a major roadway, then adding the shortest path distance on a reduced street network of major roadways.

This paper reports on the development of the hybrid distance approximation and presents results using data for Montreal, Canada. The paper first briefly describes snow removal and disposal operations. (For further details see Campbell and Langevin 1995a; Labelle, Langevin, and Campbell, forthcoming.) Following sections then describe relevant previous work and our approach, with an application in Montreal. The paper also addresses implementation issues and calibration of the model.

URBAN SNOW DISPOSAL OPERATIONS

Snow and ice control on roadways are essential and expensive winter maintenance operations necessary to maintain safe travel conditions. In urban regions that experience heavy snowfall, the snow plowed off the roadways will accumulate and impede pedestrian and vehicular traffic. In these cases, snow disposal operations are required to remove the snow to disposal sites (for example, water bodies, sewers, or surface lots) where it will not interfere with travel. This is usually accomplished by loading the snow into trucks which then haul the snow to assigned disposal sites. Snow hauling can occur around the clock following a storm. In Montreal, this involves an average of 300,000 truckloads per year hauling 7 million cubic meters of snow. Note that snow plowing to clear streets, which is an important and expensive component of snow and ice control, is not the focus of this work. We are interested in the snow removal and disposal operations following the initial plowing to clear streets.

Snow fighting is an expensive public service. The average annual winter maintenance budget for Montreal is approximately $60 million. (Sapporo, Japan, which receives an average of 5 meters of snow per year, has a winter maintenance budget of over $80 million!) Even cities that do not typically experience heavy persistent snowfalls, can experience very large expenses from serious storms. For example, New York City spent $57 million in 1995-1996 (the winter of the "Blizzard of '96" in January), four times their budget for winter maintenance.

For snow disposal in Montreal (and many other urban centers) the city is divided into distinct geographic sectors. In Montreal, each contains approximately 20 km of streets. Crews work concurrently in all sectors throughout the day to load snow into trucks. Each sector is assigned to a disposal site, and each sector is allocated a number of snow hauling trucks. For administrative reasons, all the snow from a given sector is hauled to a single disposal site, and a fixed number of trucks assigned to each sector, often under multi-year contracts with private companies. In Montreal there are approximately 60 sectors and 20 disposal sites.

The amount of snow to be hauled from each sector depends on the amount of snowfall and the area of the streets and sidewalks to be cleared of snow. Each disposal site may have an hourly and an annual capacity for receiving snow. The hourly capacity depends on the configuration of the site and the arrangements for unloading trucks. The annual capacity depends on the space available for storing snow throughout the winter season. For example, in Montreal one disposal site is a large abandoned quarry with multiple unloading stations cantilevered out over the edge of the quarry (to allow greater volumes to be dumped). This site has a large annual capacity (3 million cubic meters) due to its large size, and a large hourly capacity (10,000 cubic meters per hour) due to the multiple unloading stations. Some of the smaller disposal sites in Montreal are openings into the sewer system, with hourly capacities ranging from 400 to 2,800 cubic meters, and surface lots, with annual capacities as low as 154,000 cubic meters. The assignment of sectors to disposal sites is a complex problem due to the multiple capacities at the disposal sites (Campbell and Langevin 1995b).

A number of trucks operate within each sector to carry snow to the disposal sites. Trucks are loaded with snow (for example, by snowblowers or front loaders), and when full they depart for an assigned disposal site where they dump their load. (The average truck load is about 23 cubic meters.) The trucks then return to their assigned sectors to be loaded again. The loading process is nearly continuous in each sector to minimize the time required to clear the snow and to minimize citizen complaints from idle loading equipment. Thus, as soon as one full truck departs for the disposal site, another empty truck should be available for filling. In practice, there are typically several empty trucks waiting to be loaded in each sector to ensure the loading equipment is not idle. The longer the travel time to and from the disposal site, the greater the number of trucks needed to ensure the loading equipment is never idle.

Snow disposal is typically a continual process, day and night, that begins following the end of a storm and finishes when all snow is removed. Trucks loaded with snow traveling to and from their assigned disposal site can cause congestion and noise, often during the night. To facilitate traffic flow and minimize disruptions, many smaller streets and residential streets may not be used for truck travel, and certain specified roadways (connected to the disposal sites) receive the bulk of truck travel. This reduced network of specified roadways for snow hauling would include those on which travel by a large number of trucks (at all hours) would be desirable and appropriate. However, since trucks may be filled at any location on any street (snow is removed from all streets), the trip to the disposal site may originate, and terminate, at any location on any street.

Our snow disposal DSS was developed to assist users in designing and operating a minimum cost snow disposal system. The primary costs of snow disposal are for loading trucks with snow, for transporting snow from sectors to disposal sites, and for operating the disposal sites. Many of these costs depend directly or indirectly on the transportation distance between sectors and disposal sites, so an accurate model of distance is required to develop an effective solution procedure.

The main decisions addressed by our snow disposal decision support system are the design of the sectors, the assignment of sectors to disposal sites and the allocation of snow hauling trucks to disposal sites. (These are described in detail in Campbell and Langevin 1995a; Labelle, Langevin, and Campbell, forthcoming.) Each of these decisions requires a model of the truck travel distance. The design of the sectors is accomplished by aggregating small geographic zones into larger districts of an appropriate size and shape. The optimal size and shape of districts depends on the travel time from the sector to the disposal site. The minimum cost assignment of sectors to disposal sites depends on the travel distance between sectors and sites. Finally, the number of trucks allocated to each sector depends on the travel time from the sector to its assigned disposal site.

DISTANCE APPROXIMATIONS

There are a variety of approaches for modeling travel distances between two points, ranging from shortest path calculations on a detailed street network to analytical approximations based on a few parameters. Our approach was to combine the accuracy of shortest paths, where appropriate, with the simplicity of approximations. Although accurate digital road network databases are now available, because of the size and complexity of urban road networks in large cities, use of shortest paths on the complete street network to model travel distance or time is computationally intensive. (The network for the City of Montreal included 15,000 nodes and 60,000 arcs.)

Analytical distance approximations provide an alternative to detailed network-based calculations. An extensive literature exists covering analytical approximations for the distance between two points for travel within urban regions, as well as inter-city travel in larger regions (Eilon, Watson-Gandy, and Christofides 1971; Love and Morris 1972; Love, Morris, and Wesolowsky 1988, Chapter 10). Brimberg, Dowling, and Love (1996) describe various uses for such approximations, including their incorporation in the two most widely used truck dispatching software packages. These approximations range from simple, single parameter models (Berens 1988; Berens and Korling 1985; Berens and Korling 1988; Love and Morris 1988) to more complicated models that may combine simpler models (Alpaydin, Altinel, and Alas 1996; Brimberg, Dowling, and Love 1994; Brimberg and Love 1991; Brimberg and Love 1992; Hurter and Van Buer 1996) and incorporate the orientation of the underlying roads and obstacles to travel (Brimberg and Love 1993; Brimberg, Love, and Walker 1995; Dubois and Semet 1995; Fildes and Westwood 1978; Love and Walker 1994; Love, Walker, and Tiku 1995).

CONCLUSION

This paper presents a new distance approximation approach that combines an analytical approximation for short travel with the shortest path on a reduced network. The motivation was to develop a simple and accurate distance approximation for use in an interactive GIS-based decision support system for urban snow disposal in Montreal, Canada. The hybrid approximation reduces data requirements and improves speed by eliminating local road details, but it maintains accuracy and incorporates obstacles by including the major roadways in a reduced network. We report results of an application in Montreal using a particular local distance approximation function, but the approach could easily be used with shortest paths or a more complex distance function for local travel.

Utilizing an improved travel distance model, the snow disposal DSS provides strategic and tactical benefits. Because travel cost is (approximately) proportional to travel distance, and travel cost comprises a major component of total snow disposal costs, having a more accurate distance model leads to system designs with lower costs. The savings result from better utilization of existing equipment (for example, reallocating trucks among a given number of sectors) and from a reduction in the amount of equipment required (for example, from fewer sectors). The ability to respond in real-time to contingencies with the DSS also allows for better tactical decision-making. Finally, the availability of an interactive tool for snow disposal design allows for a more structured and timely evaluation of different levels of service (for example, setting the deadline for clearing all snow to 60 hours, rather than 48 hours) or changes in operating conditions. For example, closing snow disposal sites along water bodies has been recommended to reduce negative environmental impacts of snow disposal. Closure of such sites (which are generally inexpensive to operate) would require using more expensive sites, or opening new sites.

The hybrid approach may provide advantages in a variety of different situations. For example, the shortest path in the complete urban road network may not be a realistic route when not all local neighborhood streets can be used by the vehicles of interest (for example, large trucks). This may be due to infrastructure constraints, environmental concerns, or legal conditions. Also, calculation of shortest paths in a very large network may be too time consuming for an interactive decision support environment. Another advantage is that obstacles, which may reduce the effectiveness of analytical approximations, can be incorporated explicitly in the reduced network.

NOTES

Alpaydin, Ethem, I. Kuban Altinel, and Necati Aras (1996), "Parametric Distance Functions vs. Nonparametric Neural Networks for Estimating Road Travel Distances," European Journal of Operational Research, Vol. 92, pp. 230-243.

Berens, Wolfgang (1988), "The Suitability of the Weighted Ip Norm in Estimating Actual Road Distances," European Journal of Operational Research, Vol. 34, pp. 39-43.

Berens, Wolfgang and Franz-Josef Korling (1985), "Estimating Road Distances by Mathematical Functions," European Journal of Operational Research, Vol. 21, pp. 54-56.

Berens, Wolfgang and Franz-Josef Korling (1988), "On Estimating Road Distances by Mathematical Functions -A Rejoinder," European Journal of Operational Research, Vol. 36, pp. 254-255.

Brimberg, Jack, Paul D. Dowling, and Robert F. Love (1994), "The Weighted One-Two Norm Distance Model: Empirical Validation and Confidence Interval Estimation," Location Science, Vol. 2, pp. 91-100.

Brimberg Jack, Paul D. Dowling, and Robert F Love (1996), "Estimating the Parameters of the Weighted Ip Norm by Linear Regression," IIE Transactions, Vol. 28, pp. 363-367.

Brimberg, Jack and Robert F Love (1991), "Estimating Travel Distances by the Weighted lp Norm," Naval Research Logistics, Vol. 38, pp. 241-259.

Brimberg, Jack and Robert F. Love (1992), "A New Distance Function for Modeling Travel Distances in a Transportation Network," Transportation Science, Vol. 26, pp. 129-137.

Brimberg, Jack and Robert F. Love (1993), "General Considerations on the Use of the Weighted Ip Norm as an Empirical Distance Measure," Transportation Science, Vol. 27, pp. 341-349.

Brimberg, Jack, Robert F Love, and John H. Walker (1995), "The Effect of Axis Rotation on Distance Estimation," European Journal of Operational Research, Vol. 80, pp. 357-364.

Campbell, James F. and Andre Langevin (1 995a), "Operations Management for Urban Snow Removal and Disposal," Transportation Research, Vol. 29A, pp. 359-370.

Campbell, James F. and Andr6 Langevin (1995b), "The Snow Disposal Assignment Problem," Journal of the Operational Research Society, Vol. 46, pp. 919-929.

Dubois, Nicolas and Frederic Semet (1995), "Estimation and Determination of Shortest Path Length in a Road Network with Obstacles," European Journal of Operational Research, Vol. 83, pp. 105-116.

Eilon, Samuel, C. D. T. Watson-Gandy, and Nicos Christofides (1971), Distribution Management, London: Griffin.

Fildes, Ray A. and J.B. Westwood (1978), "The Development of Linear Distance Functions for Distribution Analysis," Journal of the Operational Research Society, Vol. 29, pp. 585-592.

Hurter, Arthur P. and Michael G. Van Buer (1996), "The Newspaper Production/Distribution Problem," Journal of Business Logistics, Vol. 17, No. 1, pp. 85-107.

Labelle, Alain (1995), Optimisation du Deneigement en Milieu Urbain, Master of Applied Science Thesis, Ecole Polytechnique de Montr6al, Montreal, Canada.

Labelle, Alain, Andr6 Langevin, and James E Campbell (forthcoming), "Sector Design for Snow Removal and Disposal in Urban Areas," Socio-Economic Planning Sciences.

Love, Robert F. and James G. Morris (1972), "Modelling Inter-city Road Distances by Mathematical Functions," Operational Research Quarterly, Vol. 23, pp. 61-71.

Love, Robert F. and James G. Morris (1988), "On Estimating Road Distances by Mathematical Functions," European Journal of Operational Research, Vol. 36, pp. 251-253.

Love, Robert F., James G. Morris, and George 0. Wesolowsky (1988), Facilities Location: Models and Methods, New York: North-Holland, Chapter 10.

Love, Robert R and John H. Walker (1994), "An Empirical Comparison of Block and Round Norms for Modelling Actual Distances," Location Science, Vol. 2, pp. 21-43.

Love, Robert F., John H. Walker, and Moti L. Tiku (1995), "Confidence Intervals for lkp,O Distances," Transportation Science, Vol. 29, pp. 341-349.

James F. Campbell

University of Missouri-St. Louis

Alain Labelle

and

Andre Langevin

GERAD AND Ecole Polytechinque

ABOUT THE AUTHORS

James F. Campbell is Professor of Management Science and Information Systems in the College of Business Administration at the University of Missouri-St. Louis. He received his Ph.D. in Industrial Engineering and Operations Research from the University of California-Berkeley. His current research focuses on mathematical modeling and optimization for hub location and network design, and for snow removal and disposal.

Alain Labelle completed this work while a graduate student in the Department of Mathematics and Industrial Engineering at Ecole Polytechnique in Montreal. He holds a Master of Applied Science degree from Ecole Polytechnique de Montreal. His interests include mathematical modeling and development of decision support systems.

Andre Langevin is Professor of Mathematics and Industrial Engineering in Ecole Polytechnique in Montreal and a member of GERAD, the Group for Research in Decision Analysis in Montreal. He received his Ph.D. in Operations Research from Ecole Polytechnique in Montreal. His current research interests include operations research for facilities layout, materials handling, warehousing, and distribution.

Copyright Council of Logistics Management 2001
Provided by ProQuest Information and Learning Company. All rights Reserved