Winter is coming. Routes must adapt. : From static CVRP to DCVRP

Sammanfattning

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.