An interactive algorithm for vehicle routeing for winter — gritting

Yuk On Li, Richard W. Eglese

Research output: Journal article publicationJournal articleAcademic researchpeer-review

81 Citations (Scopus)

Abstract

In winter, when roads may become dangerously slippery due to frost, ice or snow, a de-icing agent (usually salt) is spread on them by a local authority for safety reasons. A gritter only needs to travel once down all those roads requiring treatment, as it can spread the salt onto both sides of the carriageway. The problem studied is how to design routes for gritters which will minimise costs. This problem is a type of Capacitated Arc Routeing Problem including consideration of multiple depot locations, limited vehicle capacities, time constraints on when roads must be gritted, roads with different priorities for gritting, the existence of one-way roads and salt-refilling locations. The objective function to be optimised depends on both the total distance travelled and the number and capacity of the gritters. A heuristic algorithm is devised with a computer program which allows user-interaction, and provides a practical tool for planning gritter routes. The model is linked to a GIS containing information on the road network for the County of Lancashire. Test results from the interactive algorithm are found to outperform another existing approach which solves the same problem.
Original languageEnglish
Pages (from-to)217-228
Number of pages12
JournalJournal of the Operational Research Society
Volume47
Issue number2
DOIs
Publication statusPublished - 1 Jan 1996

Keywords

  • Heuristics
  • Vehicle routeing
  • Winter gritting

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this