A bicriteria approximation algorithm for DVRP with time windows

Hao Gu; Liang Song; Hejiao Huang; Hongwei Du

doi:10.1007/978-3-319-12691-3_18

A bicriteria approximation algorithm for DVRP with time windows

Hao Gu^*
, Liang Song
, Hejiao Huang
, Hongwei Du

^*Corresponding author for this work

Harbin Institute of Technology Shenzhen
Shenzhen Key Laboratory of Internet Information Collaboration

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

Abstract

In this paper, we study a distance constrained vehicle routing problem with time windows (DVRPTW). DVRPTW is defined as follows: given a metric space on a set of vertices, a release time and a deadline for each vertex, a length bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D, and visit as many vertices as possible within their time windows. We give a bicriteria approximation algorithm for DVRPTW on the metric plane, and all the distances satisfy the triangle inequality.

Original language	English
Pages (from-to)	231-238
Number of pages	8
Journal	Lecture Notes in Computer Science
Volume	8881
DOIs	https://doi.org/10.1007/978-3-319-12691-3_18
State	Published - 2014
Externally published	Yes

Keywords

Approximation algorithm
DVRPTW
Metric space

Access to Document

10.1007/978-3-319-12691-3_18

Cite this

@article{3efa22ecfd1c4e5ebd0da4f07c08c637,

title = "A bicriteria approximation algorithm for DVRP with time windows",

abstract = "In this paper, we study a distance constrained vehicle routing problem with time windows (DVRPTW). DVRPTW is defined as follows: given a metric space on a set of vertices, a release time and a deadline for each vertex, a length bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D, and visit as many vertices as possible within their time windows. We give a bicriteria approximation algorithm for DVRPTW on the metric plane, and all the distances satisfy the triangle inequality.",

keywords = "Approximation algorithm, DVRPTW, Metric space",

author = "Hao Gu and Liang Song and Hejiao Huang and Hongwei Du",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-12691-3\_18",

language = "英语",

volume = "8881",

pages = "231--238",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - A bicriteria approximation algorithm for DVRP with time windows

AU - Gu, Hao

AU - Song, Liang

AU - Huang, Hejiao

AU - Du, Hongwei

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - In this paper, we study a distance constrained vehicle routing problem with time windows (DVRPTW). DVRPTW is defined as follows: given a metric space on a set of vertices, a release time and a deadline for each vertex, a length bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D, and visit as many vertices as possible within their time windows. We give a bicriteria approximation algorithm for DVRPTW on the metric plane, and all the distances satisfy the triangle inequality.

AB - In this paper, we study a distance constrained vehicle routing problem with time windows (DVRPTW). DVRPTW is defined as follows: given a metric space on a set of vertices, a release time and a deadline for each vertex, a length bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D, and visit as many vertices as possible within their time windows. We give a bicriteria approximation algorithm for DVRPTW on the metric plane, and all the distances satisfy the triangle inequality.

KW - Approximation algorithm

KW - DVRPTW

KW - Metric space

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

U2 - 10.1007/978-3-319-12691-3_18

DO - 10.1007/978-3-319-12691-3_18

M3 - 文章

AN - SCOPUS:84921653090

SN - 0302-9743

VL - 8881

SP - 231

EP - 238

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

ER -

A bicriteria approximation algorithm for DVRP with time windows

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this