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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	17
Journal	ACM Transactions on Algorithms
Volume	19
Issue number	2
DOIs	https://doi.org/10.1145/3575799
Publication status	Published - 10 Mar 2023

Keywords

Approximation algorithms
capacitated vehicle routing
combinatorial optimization
graph algorithms

Access to Document

10.1145/3575799

Cite this

@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",

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

UR - https://www.scopus.com/pages/publications/85159188017

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this