Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Combining constraint programming, lagrangean relaxation and probabilistic algorithms to solve the vehicle routing problem
Erscheinungsjahr
2011
Link zum Volltext
Quelle
SpringerLink (Online service)
Beschreibungen/Notizen
This paper presents an original hybrid approach to solve the Capacitated
Vehicle Routing Problem (CVRP). The approach combines a Probabilistic Algorithm
with Constraint Programming (CP) and Lagrangian Relaxation (LR). After
introducing the CVRP and reviewing the existing literature on the topic, the paper
proposes an approach based on a probabilistic Variable Neighbourhood Search
(VNS) algorithm. Given a CVRP instance, this algorithm uses a randomized version
of the classical Clarke and Wright Savings constructive heuristic to generate a starting
solution. This starting solution is then improved through a local search process which
combines: (a) LR to optimise each individual route, and (b) CP to quickly verify the
feasibility of new proposed solutions. The efficiency of our approach is analysed after
testing some well-known CVRP benchmarks. Benefits of our hybrid approach over
already existing approaches are also discussed. In particular, the potential flexibility
of our methodology is highlighted.
Peer Reviewed