In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.
Branch-and-cut algorithms for the split delivery vehicle routing problem / C. Archetti, N. Bianchessi, M.G. Speranza. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 238:3(2014), pp. 685-698. [10.1016/j.ejor.2014.04.026]
Branch-and-cut algorithms for the split delivery vehicle routing problem
N. Bianchessi;
2014
Abstract
In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
