A novel approach to solve the split delivery vehicle routing problem. (12th January 2016)

• Record Type: Journal Article
• Authors: Chen, Ping; Golden, Bruce; Wang, Xingyin; Wasil, Edward
• Other Names: Cancela Héctor guestEditor.; Martins Simone guestEditor.; Mauttone Antonio guestEditor.; Urquhart María E. guestEditor.
• Is Part Of: International transactions in operational research. Volume 24:Number 1/2(2017)
• Page Start: 27
• Page End: 41
• Publication Date: 2016-01-12
• Subjects: vehicle routing problem -- split delivery; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12250
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: The split delivery vehicle routing problem (SDVRP) is a relaxed version of the classic capacitated vehicle routing problem (CVRP). Customer demands are allowed to split among vehicles. This problem is computationally challenging and the state‐of‐the‐art heuristics are often complicated to describe and difficult to implement, and usually have long computing times. All these hinder their application by practitioners to solve real‐world problems. We propose a novel, efficient, and easily implemented approach to solve the SDVRP using an a priori split strategy, that is, each customer demand is split into small pieces in advance. Our computational experiments on 82 benchmark instances show that our algorithm is overall much more efficient and produces results that are comparable to those from the state‐of‐the‐art approaches.