Optimization Online


New Exact Solution Approaches for the Split Delivery Vehicle Routing Problem

Gizem Ozbaygin(ozbaygin***at***bilkent.edu.tr)
Oya Karasan(karasan***at***bilkent.edu.tr)
Hande Yaman(hyaman***at***bilkent.edu.tr)

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 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

Category 1: Applications -- OR and Management Sciences (Transportation )

Citation: Department of Industrial Engineering, Bilkent University, Ankara, Turkey

Download: [PDF]

Entry Submitted: 12/03/2014
Entry Accepted: 12/03/2014
Entry Last Modified: 12/03/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society