New exact solution approaches for the split delivery vehicle routing problem

Gizem Ozbaygin (), Oya Karasan () and Hande Yaman ()
Additional contact information
Gizem Ozbaygin: Bilkent University
Oya Karasan: Bilkent University
Hande Yaman: Bilkent University

EURO Journal on Computational Optimization, 2018, vol. 6, issue 1, No 4, 85-115

Abstract: Abstract In this study, we propose exact solution methods for the split delivery vehicle routing problem (SDVRP). We first give a new vehicle-indexed flow formulation for the problem and then a relaxation obtained by aggregating the vehicle-indexed variables over all vehicles. This relaxation may have optimal solutions where several vehicles exchange loads at some customers. We cut off such solutions, in a nontraditional way, either by extending the formulation locally with vehicle-indexed variables or by node splitting. We compare these approaches using instances from the literature and new randomly generated instances. Additionally, we introduce two new extensions of the SDVRP by restricting the number of splits and by relaxing the depot return requirement and modify our algorithms to handle these extensions.

Keywords: Split delivery; Vehicle routing problem; Valid inequalities; Extended formulations; Exact approaches; 90 (specifically 90-04 and 90-08); 90B; 90C (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-017-0089-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:eurjco:v:6:y:2018:i:1:d:10.1007_s13675-017-0089-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-017-0089-z

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().