Decision Support System for Snow Emergency Vehicle Routing: Algorithms and Application

Abstract

The results of research conducted to develop a decision support system for assisting the Maryland State Highway Administration Office of Maintenance staff in designing snow emergency routes for Calvert County are presented. The research deals with the problem of designing efficient routes for salting trucks in snow emergencies. The task is formulated for mathematical optimization and classified as a capacitated rural postman problem. The capacitated arc routing problem has been shown to be nonpolynomial hard. Several heuristic operations are described, and an algorithm that is a combination of these operations is proposed to solve the real-world snow emergency vehicle routing problems in Calvert County. The results of the implementations indicate that such a system may achieve improvements in service and savings in operational costs.

Get full access to this article

View all access options for this article.

References

Golden

B. L.

, and Wong

R. T.

. Capacitated Arc Routing Problems. Networks, Vol. 11, 1981, pp. 305–315.

Campbell

J. F.

, and Langevin

. Operations Management for Urban Snow Removal and Disposal. Transportation Research A, Vol. 29, 1995, pp. 359–369.

Cook

T. M.

, and Alprin

B. S.

. Snow and Ice Removal in Urban Environment. Management Science, Vol. 23, 1976, pp. 227–234.

Eglese

R. W.

Routing Winter Gritting Vehicles. Discrete Applied Mathematics, Vol. 48, 1994, pp. 231–244.

Haslam

, and Wright

J. R.

. Application of Routing Technologies to Rural Snow and Ice Control. In Transportation Research Record 1304, TRB, National Research Council, Washington, D.C., 1991, pp. 202–211.

Liebling

T. M.

Routing Problems for Street Cleaning and Snow Removal. In Models for Environmental Pollution Control ( Deininger

, ed.), Ann Arbor Publishers, Ann Arbor, Mich., 1973, pp. 363–374.

Marks

H. D.

, and Stricker

. Routing for Public Service Vehicles. ASCE Journal of the Urban Planning and Development Division, Vol. 97, 1971, pp. 165–178.

Gilbert

Fenerateur d’Itineraires d’Enlevement de la Neige. Publication CRT-648. Centre for Research on Transportation, University of Montreal, Quebec, Canada, 1990.

Gelinas

Le Probleme du Postier Chinois avec Constraites Generales de Preseance. M.Sc. dissertation. Ecole Polytechnique de Montreal, Quebec, Canada, 1992.

10.

England

Computer Analysis Ensures a Clean Sweep. Surveyor, Vol. 6, 1982.

11.

Belenguer

H. M.

, and Benavent

. Polyhedral Results on the Capacitated Arc Routing Problem. Working paper. Departamento de Estatistica e Investigacion Operativa, Universidad de Valencia, Spain, 1991.

12.

Floyd

R. W.

Algorithm 97. Shortest Path Communications of AACM, Vol. 5, 1962, p. 345.

13.

Golden

B. L.

, DeArmon

J. S.

, and Baker

E. K.

. Computational Experiments with Algorithms for a Class of Routing Problem. Computers Operations Research, Vol. 13, 1983, pp. 47–59.

14.

Potvin

J. Y.

, and Rousseau

J. M.

. A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows. European Journal of Operational Research, Vol. 66, 1995, pp. 331–340.

15.

Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking. Ph.D. dissertation. Northwestern University, Evanston, Ill., 1976.