The need for supplies and products has become more and more immediate due to the increasing globalization and new international treaties. Routing Problems with Loading Constraints have become very attractive, engendering studies in operations research. The appeal lies in the complexity of these problems, which are NP-hard and NP-complete. In 2015, Iori and Riera-Ledesma formulated and proposed an exact solution for the Double Vehicle Routing Problem with Multiple Stacks (DVRPMS). The objective is to generate routes with the lowest cost possible, that gather products in a pickup region and drop them in their respective points in the delivery region, without changing the loading plan. In this paper we propose a heuristic approach based on the Simulated Annealing metaheuristic with an additional Local Search. The proposed approach was tested using instances defined in the literature and compared with all known approaches of the DVRPMS. Compared to current heuristic approaches, the SA+LS heuristic found better results in 84.6% of all instances. Analyzing the exact method, the SA+LS heuristic was 61.3% more efficient on find the optimal solution. The proposed approach was proved to be highly competitive when compared to the exact methods, outperforming the exact method in time and finding better solutions than the upper-bounds found in the literature.
Simulated annealing metaheuristic for the Double Vehicle Routing Problem with Multiple Stacks
01.11.2016
247325 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
A Simulated Annealing Heuristic for the Green Vehicle Routing Problem
Springer Verlag | 2013
|A Simulated Annealing Heuristic for the Vehicle Routing Problem with Cross-docking
Springer Verlag | 2014
|British Library Online Contents | 2008
|Solving Practical Vehicle Routing Problem with Time Windows Using Metaheuristic Algorithms
DOAJ | 2012
|