Metraipolis › archive › dc_8f314defbf81

Improved Approximations for Vehicle Routing with Nonuniform Speeds — arXiv:2610.12195

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.12195
License (as archived)
CC0-1.0
Archived
2026-10-09T06:36:26.363Z
SHA-256 of the archived text
bb8543ac37cc4507f0cf42ab6d7ada46587c276ce3bfe7d6bc37d25e18c73aa5
Stable URL of this page
https://metraipolis.com/documento/dc_8f314defbf81

How to cite

Improved Approximations for Vehicle Routing with Nonuniform Speeds — arXiv:2610.12195 — arXiv (en), https://arxiv.org/abs/2610.12195 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8f314defbf81 (Metraipolis archive dc_8f314defbf81, sha256 bb8543ac37cc4507f0cf42ab6d7ada46587c276ce3bfe7d6bc37d25e18c73aa5)
BibTeX
@misc{dc8f314defbf81,
  title = {Improved Approximations for Vehicle Routing with Nonuniform Speeds — arXiv:2610.12195},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.12195},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8f314defbf81; sha256 bb8543ac37cc4507f0cf42ab6d7ada46587c276ce3bfe7d6bc37d25e18c73aa5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12195. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+\delta)$-approximation for any fixed $\delta>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+\delta)$-approximation for any fixed $\delta>0$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.12195 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:57:12.791Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).