An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem

Xiaofan Lai (), Liang Xu (), Zhou Xu () and Yang Du ()
Additional contact information
Xiaofan Lai: Institute of Big Data Intelligent Management and Decision, College of Management, Shenzhen University, Shenzhen 518055, China
Liang Xu: School of Business Administration, The Southwestern University of Finance and Economics, Chengdu 611130, China
Zhou Xu: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hong Kong, China
Yang Du: School of Business Administration, The Southwestern University of Finance and Economics, Chengdu 611130, China

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 1179-1194

Abstract: A multidepot capacitated vehicle routing problem aims to serve customers’ demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k -depot split delivery vehicle routing problem (or k -DSDVRP in short), for the situation where each customer’s demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k -DSDVRP, ensuring an approximation ratio of ( 6 − 4 / k ) and a polynomial running time for any fixed constant k ≥ 2 . To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k -DSDVRP with k ≥ 2 being a fixed constant.

Keywords: approximation algorithm; multiple depot; vehicle routing problem; split delivery (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.0193 (application/pdf)

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:inm:orijoc:v:35:y:2023:i:5:p:1179-1194

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().