Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910877836378112 |
|---|---|
| author | Zhao, Jingyang Xiao, Mingyu Wang, Shunwang |
| author_facet | Zhao, Jingyang Xiao, Mingyu Wang, Shunwang |
| contents | 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. The goal is to open some depots and route capacitated vehicles from the opened depots to satisfy all customers' demand, while minimizing the total cost. In this paper, we propose a $4.169$-approximation algorithm for this problem, improving the best-known $4.38$-approximation ratio. Moreover, if the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined $4.091$-approximation algorithm. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of the previous algorithm and is also much closer to optimality than the provable approximation factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_12502 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enhanced Approximation Algorithms for the Capacitated Location Routing Problem Zhao, Jingyang Xiao, Mingyu Wang, Shunwang Data Structures and Algorithms 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. The goal is to open some depots and route capacitated vehicles from the opened depots to satisfy all customers' demand, while minimizing the total cost. In this paper, we propose a $4.169$-approximation algorithm for this problem, improving the best-known $4.38$-approximation ratio. Moreover, if the demand of each customer is allowed to be delivered by multiple tours, we propose a more refined $4.091$-approximation algorithm. Experimental study on benchmark instances shows that the quality of our computed solutions is better than that of the previous algorithm and is also much closer to optimality than the provable approximation factor. |
| title | Enhanced Approximation Algorithms for the Capacitated Location Routing Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.12502 |