Branch-and-cut algorithms for the split delivery vehicle routing problem

Claudia Archetti, Nicola Bianchessi and M. Grazia Speranza

European Journal of Operational Research, 2014, vol. 238, issue 3, 685-698

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.

Keywords: Split Delivery Vehicle Routing Problem; Branch-and-cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171400352X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:238:y:2014:i:3:p:685-698

DOI: 10.1016/j.ejor.2014.04.026

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().