The (Over)zealous Snow Remover Problem
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. The authors address the problem facing a single vehicle, including details such as precedence requirements and turning penalties. The authors 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. The authors compare the solutions to lower bounds obtained by solving a mixed integer programming model. The authors 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.
- Record URL:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
- Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
- Holmberg, Kaj
- Publication Date: 2019-5
- Media Type: Web
- Features: References;
- Pagination: pp 867-881
- TRT Terms: Mixed integer programming; Optimization; Snow removal; Traveling salesman problem
- Subject Areas: Highways; Maintenance and Preservation; Operations and Traffic Management; Planning and Forecasting;
- Accession Number: 01714942
- Record Type: Publication
- Files: TRIS
- Created Date: Jun 17 2019 3:36PM