The Capacitated Vehicle Routing Problem (CVRP) is a key optimization problem in logistics. The aim is to minimize the total travel distance while respecting the capacity limits of the vehicles. Exact optimization methods can solve small static CVRP instances in optimality. However, in many real-world applications, customer requests arrive incrementally, creating a constantly changing scenario. In such cases, repeatedly solving the problem exactly is computationally too expensive. This thesis investigates the transition from a static CVRP to a Dynamic Capacitated Vehicle Routing Problem (DCVRP) and analyzes the trade-off between solution quality and computational effort. An exact mixed-integer linear programming model is used to compute an optimal benchmark for the static case. The same instances are then studied in a dynamic simulation framework, where customer requests appear one after another, and the routes must be updated in real time. Two heuristic methods are considered: a rolling insertion heuristic and a simulated annealing metaheuristic. The results show that exact optimization achieves the best solution quality but leads to rapidly growing computation times. The insertion heuristic allows very fast re-optimization but produces less optimal routes, while simulated annealing clearly improves route quality at the cost of higher, but still reasonable,computational cost. In general, the study underlines the importance of heuristic approaches for real-time dynamic routing.
Det kapaciterade fordonsruttplaneringsproblemet (Capacitated Vehicle Routing Problem, CVRP) är ett centralt optimeringsproblem inom logistik. Målet är att minimera den totala körsträckan samtidigt som fordonens kapacitetsbegränsningar respekteras. Exakta optimeringsmetoder kan lösa små, statiska CVRP-instanser optimalt. I många verkliga tillämpningar uppstår dock kundförfrågningar successivt över tid, vilket skapar en dynamisk miljö. I sådana fall är det beräkningsmässigt för kostsamt att upprepade gånger lösa problemet exakt. Denna uppsats undersöker övergången från ett statiskt CVRP till ett dynamiskt CVRP (Dynamic Capacitated Vehicle Routing Problem, DCVRP) och analyserar avvägningen mellan lösningskvalitet och beräkningsinsats. En exakt mixed-integer-linjär programmeringsmodell används för att beräkna ett optimalt referensresultat för det statiska fallet. Samma instanser studeras därefter i ett dynamiskt simuleringsramverk, där kundförfrågningar dyker upp successivt och rutterna måste uppdateras i realtid. Två heuristiska metoder beaktas: en rullande insättningsheuristik och en simulated annealing metaheuristik. Resultaten visar att exakt optimering ger den bästa lösningskvaliteten men leder till snabbt ökande beräkningstider. Insättningsheuristiken möjliggör mycket snabb omoptimering men resulterar i sämre rutter, medan SA tydligt förbättrar rutternas kvalitet till priset av högre, men fortfarande rimlig, beräkningsinsats. Sammantaget understryker studien vikten av heuristiska metoder for dynamisk ruttplanering i realtid.