The (Over)zealous Snow Remover Problem

Kaj Holmberg ()
Additional contact information
Kaj Holmberg: Department of Mathematics, Linköping Institute of Technology, 581 83 Linköping, Sweden

Transportation Science, 2019, vol. 53, issue 3, 867-881

Abstract: Planning snow removal is a difficult, infrequently occurring optimization problem, concerning complicated routing of vehicles. Clearing a street includes several different activities, and the tours must be allowed to contain subtours. The streets are classified into different types, each type requiring different activities. We address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. We describe a solution approach based on a reformulation to an asymmetric traveling salesman problem in an extended graph, plus a heuristic for finding feasible solutions and a reordering procedure. The method has been implemented and tested on real life examples, and the solution times are short enough to allow online usage. We compare the solutions to lower bounds obtained by solving a mixed integer programming model. We study two different principles for the number of sweeps on a normal street, encountered in discussions with snow removal contractors. A principle using a first sweep in the middle of the street around the block, in order to quickly allow usage of the streets, is found to yield interesting theoretical and practical difficulties. The online appendix is available at https://doi.org/10.1287/trsc.2018.0851 .

Keywords: routing; traveling salesman; snow removal (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0851 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:3:p:867-881

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().