EUVIMEDEUVIMED entdecken
Crossref

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

Xiaofan Lai, Liang Xu, Zhou Xu, Yang Du

INFORMS Journal on Computing · 2023-09 · 35 (5) · 1179-1194

DOI: 10.1287/ijoc.2021.0193 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2023-09. Verfasst von Xiaofan Lai und 3 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 37 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 [Formula: see text], 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 [Formula: see text] and a polynomial running time for any fixed constant [Formula: see text]. 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 [Formula: see text] being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193 . The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0193 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0193 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Zitieren

APA

Lai, X., Xu, L., Xu, Z., & Du, Y. (2023). An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem. INFORMS Journal on Computing, 35(5), 1179-1194. https://doi.org/10.1287/ijoc.2021.0193

Vancouver

Lai X, Xu L, Xu Z, Du Y. An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem. INFORMS Journal on Computing. 2023;35(5):1179-1194. doi:10.1287/ijoc.2021.0193

BibTeX
@article{Lai2023,
  author = {Lai, Xiaofan and Xu, Liang and Xu, Zhou and Du, Yang},
  title = {An Approximation Algorithm for k -Depot Split Delivery Vehicle Routing Problem},
  journal = {INFORMS Journal on Computing},
  year = {2023},
  volume = {35},
  number = {5},
  pages = {1179--1194},
  doi = {10.1287/ijoc.2021.0193}
}
Kostenlos starten →