Improved Approximation Algorithms for Capacitated Location Routing
Jingyang Zhao, Mingyu Xiao, Shunwang Wang
Abstract
The Capacitated Location Routing Problem is an important planning and routing problem in logistics, which generalizes the capacitated vehicle routing problem and the uncapacitated facility location problem. In this problem, we are given a set of depots and a set of customers where each depot has an opening cost and each customer has a demand, and we need to use minimum cost to open some depots and route capacitated vehicles in the opened depots to satisfy all customers' demand. In this paper, we propose a 4.169-approximation algorithm for this problem, improving the best-known 4.38-approximation ratio (Transportation Science 2013). Moreover, if the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined 4.092-approximation algorithm. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of previous algorithms and is also much closer to optimality than the provable approximation factor.
BibTeX
@inproceedings{ijcai2024p752,
title = {Improved Approximation Algorithms for Capacitated Location Routing},
author = {Zhao, Jingyang and Xiao, Mingyu and Wang, Shunwang},
booktitle = {Proceedings of the Thirty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-24}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Kate Larson},
pages = {6805--6813},
year = {2024},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2024/752},
url = {https://doi.org/10.24963/ijcai.2024/752},
}