Snow removal is an important optimization problem in countries with snowfall. Bus stops can only be cleared after the adjacent street is cleared. The problem of optimizing snow removal for bus stops in an urban area is a special case of the Travelling Salesman Problem with Time Windows, where each stop only can be cleared after a certain time has passed. The solver Gurobi is used to solve the mathematical model of this problem to optimality. A local search and a tabu search is implemented. The results of the mathematical model are compared to the results of the implemented tabu search method. The results show that if a solution needs to be produced quickly, the tabu search provides better solutions than Gurobi. / Snöröjning är ett viktigt optimeringsproblem i länder med snöfall. Busshållplatsen kan bara röjas efter att den angränsande vägen är röjd. Problemet att optimera snöröjning av busshållplatser i en stad är ett Handelsresandeproblem med tidsfönster, där varje hållplats bara kan röjas efter att en tid har gått. I arbetet har vi implementerat en tabusökning för att hitta snabbt hitta bra tillåtna lösningar till problemet. För att utvärdera prestandan hos tabusökningen har vi också implementerat en matematisk modell och använt Gurobi som lösare. Resultaten visar att tabusökningen är snabbast på att hitta tillåtna lösningar av god kvalité.
Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-193687 |
Date | January 2023 |
Creators | Hüni, Corina |
Publisher | Linköpings universitet, Tillämpad matematik, Linköpings universitet, Tekniska fakulteten |
Source Sets | DiVA Archive at Upsalla University |
Language | English |
Detected Language | English |
Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
Format | application/pdf |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0166 seconds