Optimization models for a real-world snow plow routing problem

J. Kinable, W.J. van Hoeve, S.F. Smith

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
3 Downloads (Pure)

Abstract

In cold weather cities, snowstorms can have a significant disruptive effect on both mobility and safety, and consequently the faster that streets can be cleared the better. Yet in most cities, plans for snowplowing are developed using simple allocation schemes that while easy to implement can also be quite inefficient. In this paper we consider the problem of optimizing the routes of a fleet of snow plowing vehicles, subject to street network topology, vehicle operating restrictions, and resource (salt, fuel) usage and replenishment constraints. We develop and analyze the performance of three different optimization models: a mixed-integer programming (MIP) model, a constraint programming (CP) model, and a constructive heuristic procedure that is amplified by an iterative improvement search. The models are evaluated on a set of snow plow routing problems of various sizes, constructed using Open Streets map data of Pittsburgh PA. Experimental results are presented that illustrate the differential strengths and weaknesses of each model, and suggest an alternative hybrid solution approach.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication13th International Conference, CPAIOR 2016, Banff, AB, Canada, May 29 - June 1, 2016, Proceedings
EditorsC.-G. Quimper
Place of PublicationDordrecht
PublisherSpringer
Pages229-245
Number of pages17
ISBN (Electronic)978-3-319-33954-2
ISBN (Print)978-3-319-33953-5
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016) - Banff, Canada
Duration: 29 May 20161 Jun 2016
Conference number: 13

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9676
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016)
Abbreviated titleCOAIOR 2016
CountryCanada
CityBanff
Period29/05/161/06/16

Fingerprint Dive into the research topics of 'Optimization models for a real-world snow plow routing problem'. Together they form a unique fingerprint.

  • Cite this

    Kinable, J., van Hoeve, W. J., & Smith, S. F. (2016). Optimization models for a real-world snow plow routing problem. In C-G. Quimper (Ed.), Integration of AI and OR Techniques in Constraint Programming : 13th International Conference, CPAIOR 2016, Banff, AB, Canada, May 29 - June 1, 2016, Proceedings (pp. 229-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9676). Springer. https://doi.org/10.1007/978-3-319-33954-2_17