Real time critical edge of the shortest path in transportation networks

Yinfeng Xu; Huahai Yan

doi:10.1007/11750321_19

Real time critical edge of the shortest path in transportation networks

Yinfeng Xu
, Huahai Yan

School of Management

Xi'an Jiaotong University

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

3 Scopus citations

Abstract

In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an O(n²) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.

Original language	English
Title of host publication	Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings
Publisher	Springer Verlag
Pages	198-205
Number of pages	8
ISBN (Print)	3540340211, 9783540340218
DOIs	https://doi.org/10.1007/11750321_19
State	Published - 2006
Event	3rd International Conference on Theory and Applications of Models of Computation, TAMC 2006 - Beijing, China Duration: 15 May 2006 → 20 May 2006

Publication series

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

Conference

Conference	3rd International Conference on Theory and Applications of Models of Computation, TAMC 2006
Country/Territory	China
City	Beijing
Period	15/05/06 → 20/05/06

UN SDGs

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

SDG 11 Sustainable Cities and Communities

Keywords

Algorithm
Real Time Critical Edge
The Shortest Path
Transportation Networks

Access to Document

10.1007/11750321_19

Cite this

Xu, Y., & Yan, H. (2006). Real time critical edge of the shortest path in transportation networks. In Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings (pp. 198-205). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3959 LNCS). Springer Verlag. https://doi.org/10.1007/11750321_19

Xu, Yinfeng ; Yan, Huahai. / Real time critical edge of the shortest path in transportation networks. Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings. Springer Verlag, 2006. pp. 198-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e9ac2818fa474ebb8c87735b605b4441,

title = "Real time critical edge of the shortest path in transportation networks",

abstract = "In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an O(n2) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.",

keywords = "Algorithm, Real Time Critical Edge, The Shortest Path, Transportation Networks",

author = "Yinfeng Xu and Huahai Yan",

year = "2006",

doi = "10.1007/11750321\_19",

language = "英语",

isbn = "3540340211",

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

publisher = "Springer Verlag",

pages = "198--205",

booktitle = "Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings",

note = "3rd International Conference on Theory and Applications of Models of Computation, TAMC 2006 ; Conference date: 15-05-2006 Through 20-05-2006",

}

Xu, Y & Yan, H 2006, Real time critical edge of the shortest path in transportation networks. in Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3959 LNCS, Springer Verlag, pp. 198-205, 3rd International Conference on Theory and Applications of Models of Computation, TAMC 2006, Beijing, China, 15/05/06. https://doi.org/10.1007/11750321_19

Real time critical edge of the shortest path in transportation networks. / Xu, Yinfeng; Yan, Huahai.
Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings. Springer Verlag, 2006. p. 198-205 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3959 LNCS).

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

TY - GEN

T1 - Real time critical edge of the shortest path in transportation networks

AU - Xu, Yinfeng

AU - Yan, Huahai

PY - 2006

Y1 - 2006

N2 - In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an O(n2) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.

AB - In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an O(n2) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.

KW - Algorithm

KW - Real Time Critical Edge

KW - The Shortest Path

KW - Transportation Networks

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

U2 - 10.1007/11750321_19

DO - 10.1007/11750321_19

M3 - 会议稿件

AN - SCOPUS:33745842291

SN - 3540340211

SN - 9783540340218

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

SP - 198

EP - 205

BT - Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings

PB - Springer Verlag

T2 - 3rd International Conference on Theory and Applications of Models of Computation, TAMC 2006

Y2 - 15 May 2006 through 20 May 2006

ER -

Xu Y, Yan H. Real time critical edge of the shortest path in transportation networks. In Theory and Applications of Models of Computation - Third International Conference, TAMC 2006, Proceedings. Springer Verlag. 2006. p. 198-205. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11750321_19

Real time critical edge of the shortest path in transportation networks

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this