Single vehicle’s package delivery strategy with online traffic congestion of certain delay time

Songhua Li; Yinfeng Xu

doi:10.1007/978-3-319-78455-7_16

Single vehicle’s package delivery strategy with online traffic congestion of certain delay time

Songhua Li
, Yinfeng Xu

School of Management

Xi'an Jiaotong University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Urban package delivery by single vehicle can be modeled as online Steiner travelling salesman problem. This paper investigates the scenario that delay time of traffic congestion is certain and of real-time information to delivery vehicle, the vehicle can obtain specific delay time of traffic congestion just upon reaching an end vertex of the corresponding edge. Given a graph G = (V, E) and a subset D in V, the goal is to design a minimum-weight closed tour that departs from the depot s in D and returns to s after visiting each destination node in D at least once. When delivery vehicle encounters at most k times of traffic congestion, we first show {k + 1,ρ_Σ + 1} is a lower bound on competitive ratio for the problem, where ρ_Σ is the ratio compared sum of delay time of all congested edges with cost of optimal route. We further present an online algorithm for the problem with its competitive ratio proved to be very close to the lower bound.

Original language	English
Title of host publication	Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings
Editors	Pinyan Lu, Jianer Chen
Publisher	Springer Verlag
Pages	212-223
Number of pages	12
ISBN (Print)	9783319784540
DOIs	https://doi.org/10.1007/978-3-319-78455-7_16
State	Published - 2018
Event	12th International Frontiers of Algorithmics Workshop, FAW 2018 - Guangzhou, China Duration: 8 May 2018 → 10 May 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10823 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Frontiers of Algorithmics Workshop, FAW 2018
Country/Territory	China
City	Guangzhou
Period	8/05/18 → 10/05/18

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure
SDG 11 Sustainable Cities and Communities

Keywords

Competitive analysis
Package delivery
Traffic congestion

Access to Document

10.1007/978-3-319-78455-7_16

Cite this

Li, S., & Xu, Y. (2018). Single vehicle’s package delivery strategy with online traffic congestion of certain delay time. In P. Lu, & J. Chen (Eds.), Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings (pp. 212-223). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10823 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-78455-7_16

Li, Songhua ; Xu, Yinfeng. / Single vehicle’s package delivery strategy with online traffic congestion of certain delay time. Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. editor / Pinyan Lu ; Jianer Chen. Springer Verlag, 2018. pp. 212-223 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e88e515e022744c68934dff72daac4d0,

title = "Single vehicle{\textquoteright}s package delivery strategy with online traffic congestion of certain delay time",

abstract = "Urban package delivery by single vehicle can be modeled as online Steiner travelling salesman problem. This paper investigates the scenario that delay time of traffic congestion is certain and of real-time information to delivery vehicle, the vehicle can obtain specific delay time of traffic congestion just upon reaching an end vertex of the corresponding edge. Given a graph G = (V, E) and a subset D in V, the goal is to design a minimum-weight closed tour that departs from the depot s in D and returns to s after visiting each destination node in D at least once. When delivery vehicle encounters at most k times of traffic congestion, we first show \{k + 1,ρΣ + 1\} is a lower bound on competitive ratio for the problem, where ρΣ is the ratio compared sum of delay time of all congested edges with cost of optimal route. We further present an online algorithm for the problem with its competitive ratio proved to be very close to the lower bound.",

keywords = "Competitive analysis, Package delivery, Traffic congestion",

author = "Songhua Li and Yinfeng Xu",

note = "Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 12th International Frontiers of Algorithmics Workshop, FAW 2018 ; Conference date: 08-05-2018 Through 10-05-2018",

year = "2018",

doi = "10.1007/978-3-319-78455-7\_16",

language = "英语",

isbn = "9783319784540",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "212--223",

editor = "Pinyan Lu and Jianer Chen",

booktitle = "Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings",

}

Li, S & Xu, Y 2018, Single vehicle’s package delivery strategy with online traffic congestion of certain delay time. in P Lu & J Chen (eds), Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10823 LNCS, Springer Verlag, pp. 212-223, 12th International Frontiers of Algorithmics Workshop, FAW 2018, Guangzhou, China, 8/05/18. https://doi.org/10.1007/978-3-319-78455-7_16

Single vehicle’s package delivery strategy with online traffic congestion of certain delay time. / Li, Songhua; Xu, Yinfeng.
Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. ed. / Pinyan Lu; Jianer Chen. Springer Verlag, 2018. p. 212-223 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10823 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Single vehicle’s package delivery strategy with online traffic congestion of certain delay time

AU - Li, Songhua

AU - Xu, Yinfeng

PY - 2018

Y1 - 2018

N2 - Urban package delivery by single vehicle can be modeled as online Steiner travelling salesman problem. This paper investigates the scenario that delay time of traffic congestion is certain and of real-time information to delivery vehicle, the vehicle can obtain specific delay time of traffic congestion just upon reaching an end vertex of the corresponding edge. Given a graph G = (V, E) and a subset D in V, the goal is to design a minimum-weight closed tour that departs from the depot s in D and returns to s after visiting each destination node in D at least once. When delivery vehicle encounters at most k times of traffic congestion, we first show {k + 1,ρΣ + 1} is a lower bound on competitive ratio for the problem, where ρΣ is the ratio compared sum of delay time of all congested edges with cost of optimal route. We further present an online algorithm for the problem with its competitive ratio proved to be very close to the lower bound.

AB - Urban package delivery by single vehicle can be modeled as online Steiner travelling salesman problem. This paper investigates the scenario that delay time of traffic congestion is certain and of real-time information to delivery vehicle, the vehicle can obtain specific delay time of traffic congestion just upon reaching an end vertex of the corresponding edge. Given a graph G = (V, E) and a subset D in V, the goal is to design a minimum-weight closed tour that departs from the depot s in D and returns to s after visiting each destination node in D at least once. When delivery vehicle encounters at most k times of traffic congestion, we first show {k + 1,ρΣ + 1} is a lower bound on competitive ratio for the problem, where ρΣ is the ratio compared sum of delay time of all congested edges with cost of optimal route. We further present an online algorithm for the problem with its competitive ratio proved to be very close to the lower bound.

KW - Competitive analysis

KW - Package delivery

KW - Traffic congestion

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

U2 - 10.1007/978-3-319-78455-7_16

DO - 10.1007/978-3-319-78455-7_16

M3 - 会议稿件

AN - SCOPUS:85046747415

SN - 9783319784540

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 212

EP - 223

BT - Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings

A2 - Lu, Pinyan

A2 - Chen, Jianer

PB - Springer Verlag

T2 - 12th International Frontiers of Algorithmics Workshop, FAW 2018

Y2 - 8 May 2018 through 10 May 2018

ER -

Li S, Xu Y. Single vehicle’s package delivery strategy with online traffic congestion of certain delay time. In Lu P, Chen J, editors, Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Proceedings. Springer Verlag. 2018. p. 212-223. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-78455-7_16

Single vehicle’s package delivery strategy with online traffic congestion of certain delay time

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this