Winter Gritting Routes with Multiple Visits: A heuristic for a capacitated arc routing problem with heterogenous vehicles with different covering widths.
Translated title
Winter Gritting Routes with Multiple Visits
Author
Nielsen, Lasse Damtoft
Term
4. term
Education
Publication year
2019
Pages
28
Abstract
I dette projekt undersøger vi, hvordan man planlægger vintergrusning—at sprede grus eller salt for at modvirke is—som et Capacitated Arc Routing Problem (CARP). CARP er en optimeringsmodel, der bestemmer, hvordan køretøjer med begrænset kapacitet skal servicere vejstrækninger. Gennem drøftelser med COWI og en litteraturgennemgang identificerer vi to huller i den eksisterende viden og fokuserer på det vigtigste: hvor mange gange et køretøj skal køre en vej for at behandle den afhænger af det konkrete køretøj, så behovet for gennemkørsler varierer. Vi foreslår en heuristik (en praktisk søgemetode), der afgør, hvilke veje hvert køretøj skal servicere, og tager højde for veje, der kan kræve flere besøg af det samme køretøj. Tilgangen kombinerer etablerede metoder til velundersøgte delproblemer med en ny komponent, der håndterer flere gennemkørsler. Vi tuner metodens parametre og tester den på publicerede testinstanser. Resultaterne viser, at tilgangen virker og er lovende. Da denne variant ikke dækkes af eksisterende løsninger, er direkte sammenligninger ikke mulige; vi skitserer derfor mulige forbedringer.
This project studies how to plan winter road gritting—spreading grit or salt to prevent ice—as a Capacitated Arc Routing Problem (CARP). CARP is an optimization model for deciding how vehicles with limited capacity should service road segments. From discussions with COWI and a literature review, we identify two gaps and focus on the most important: the number of passes required to properly treat a road depends on the specific vehicle, so service needs vary. We propose a heuristic (a practical search method) that decides which roads each vehicle should service and accounts for roads that may need multiple visits by the same vehicle. Our approach combines established techniques for well-studied subproblems with a new component that handles multiple passes. We tune the method’s parameters and evaluate it on published test instances. The results indicate the approach works and is promising. Because this variant is not covered by existing solutions, direct comparisons are not possible; we therefore outline potential improvements.
[This abstract was generated with the help of AI]
Documents