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.
['Jonatas B. C. Chagas', 'Ulisses Eduardo Ferreira da Silveira', 'Marcelo Pinheiro Leite Benedito', 'André Gustavo dos Santos']
Simulated annealing metaheuristic for the Double Vehicle Routing Problem with Multiple Stacks