Optimization models for a real-world snow plow routing problem

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

14 Citaten (Scopus)
3 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
TitelIntegration of AI and OR Techniques in Constraint Programming
Subtitel13th International Conference, CPAIOR 2016, Banff, AB, Canada, May 29 - June 1, 2016, Proceedings
RedacteurenC.-G. Quimper
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's229-245
Aantal pagina's17
ISBN van elektronische versie978-3-319-33954-2
ISBN van geprinte versie978-3-319-33953-5
DOI's
StatusGepubliceerd - 2016
Extern gepubliceerdJa
Evenement13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016) - Banff, Canada
Duur: 29 mei 20161 jun 2016
Congresnummer: 13

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9676
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016)
Verkorte titelCOAIOR 2016
Land/RegioCanada
StadBanff
Periode29/05/161/06/16

Vingerafdruk

Duik in de onderzoeksthema's van 'Optimization models for a real-world snow plow routing problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit