Winter Gritting Routes with Multiple Visits: A heuristic for a capacitated arc routing problem with heterogenous vehicles with different covering widths.

Nielsen, Lasse Damtoft

4. term

Mathematics-Economics, Master

2019

2019-12-19

28 pages

I dette projekt adresserer vi de praktiske aspekter af at løse problemet man står overfor når man skal planlægge ruter til saltspredning. Dette gør vi som et Capacitated Arc Routing Problem (CARP). Specifikt og baseret på samtaler med COWI og en gennemgang af den relevante litteratur, finder vi to primære mangler i den nuværende litteratur. Vi udvælger den vigtigste af disse som fokus for rapporten. Det er problemet med at antallet af gange et saltspredningskøretøj skal besøge et stykke vej for at servicere det afhænger det specifikke køretøj. Vi foreslå derefter en løsnings heuristik som kan håndtere denne type problem, altså bestemme hvilke veje der skal serviceres af hvilke køretøjer. Den foreslåede løsning gør brug af eksisterende metoder til de underproblemer der er velbeskrevne i litteraturen og introducere samtidig en måde at håndtere de potentielt flere besøg. Vi tuner løsningens parametre og tester den på noget test data fra litteraturen. Vi finder ud af at løsningen fungerer, og selvom der ikke eksisterer andre løsninger vi kan sammenligne vores resultater med så finder vi potentiale for yderligere forbedringer hvilket vi adresserer til sidst.

In this project we address the practical aspects of solving the problem of winter gritting, as a Capacitated Arc Routing Problem (CARP). Specifically, based on discussions with COWI, and a literature review we find two main gaps in the current literature, and focus on the most important of these. That is the fact that the number of times a vehicle needs to visit a road to service it depends on the specific vehicle. We then proceed to propose a solution heuristic which can handle this type of problem, i.e. determining which roads should be serviced by which vehicles. The proposed solution utilizes existing methods for the sub-problems that are well researched, while introducing a method for the multiple visits. The parameters of the proposed solution are tuned and we test our heuristic on test instances from literature. We find that the proposed solution works and while there are no existing solutions in the literature to compare our results to, we find potential for improvement which we address at the end.

Download
View record in AAU Student Projects