A PTAS for Capacitated Vehicle Routing on Trees

Claire Mathieu; Hang Zhou

doi:10.1145/3575799

A PTAS for Capacitated Vehicle Routing on Trees

Claire Mathieu
, Hang Zhou

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

11 Citations (Scopus)

Résumé

We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.

langue originale	Anglais
Numéro d'article	17
journal	ACM Transactions on Algorithms
Volume	19
Numéro de publication	2
Les DOIs	https://doi.org/10.1145/3575799
état	Publié - 10 mars 2023

Accès au document

10.1145/3575799

Contient cette citation

@article{9d33f74553b94b6780dbffd43541f91b,

title = "A PTAS for Capacitated Vehicle Routing on Trees",

abstract = "We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.",

keywords = "Approximation algorithms, capacitated vehicle routing, combinatorial optimization, graph algorithms",

author = "Claire Mathieu and Hang Zhou",

note = "Publisher Copyright: {\textcopyright} 2023 Association for Computing Machinery.",

year = "2023",

month = mar,

day = "10",

doi = "10.1145/3575799",

language = "English",

volume = "19",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery ",

number = "2",

}

TY - JOUR

T1 - A PTAS for Capacitated Vehicle Routing on Trees

AU - Mathieu, Claire

AU - Zhou, Hang

PY - 2023/3/10

Y1 - 2023/3/10

N2 - We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.

AB - We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.

KW - Approximation algorithms

KW - capacitated vehicle routing

KW - combinatorial optimization

KW - graph algorithms

U2 - 10.1145/3575799

DO - 10.1145/3575799

M3 - Article

AN - SCOPUS:85159188017

SN - 1549-6325

VL - 19

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 17

ER -

A PTAS for Capacitated Vehicle Routing on Trees

Résumé

Accès au document

Empreinte digitale

Contient cette citation