Using a multi-criteria approach to solve path finding problem in road networks with uncertainty

Bi Yu Chen; Hing Keung William Lam; Mei Lam Tam

Using a multi-criteria approach to solve path finding problem in road networks with uncertainty

Bi Yu Chen, Hing Keung William Lam, Mei Lam Tam

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

Abstract

It was empirically found that travelers would make their route choice not only based on travel time saving but also on reduction of travel cost and travel time variability. However, little attention has been given to determine optimal reliable shortest path (RSP) in stochastic network effectively and efficiently. This paper investigates the stochastic reliable shortest path problem (SRSPP) in road networks with travel time uncertainty and toll charges. Based on the chance-constrained model formulation, the SRSPP is formulated as an equivalent multi-criteria shortest path problem (MSPP) in this paper. A reliable shortest path algorithm (RSPA) is proposed to solve the SRSPP. A numerical example is used to demonstrate the performance of the proposed algorithm. Comparison is made by using the conventional label correcting approach (LCA) for solving the MSPP. The computational results indicate that the proposed RSPA is much efficient than LCA for finding the optimal RSP in Hong Kong road network.

Original language	English
Title of host publication	Proceedings of the 13th International Conference of Hong Kong Society for Transportation Studies
Subtitle of host publication	Transportation and Management Science
Pages	229-238
Number of pages	10
Publication status	Published - 1 Dec 2008
Event	13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science - Kowloon, Hong Kong Duration: 13 Dec 2008 → 15 Dec 2008

Conference

Conference	13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science
Country/Territory	Hong Kong
City	Kowloon
Period	13/12/08 → 15/12/08

ASJC Scopus subject areas

Transportation

Cite this

@inproceedings{1276b6c3207c4d8883c0dc98b6f45230,

title = "Using a multi-criteria approach to solve path finding problem in road networks with uncertainty",

abstract = "It was empirically found that travelers would make their route choice not only based on travel time saving but also on reduction of travel cost and travel time variability. However, little attention has been given to determine optimal reliable shortest path (RSP) in stochastic network effectively and efficiently. This paper investigates the stochastic reliable shortest path problem (SRSPP) in road networks with travel time uncertainty and toll charges. Based on the chance-constrained model formulation, the SRSPP is formulated as an equivalent multi-criteria shortest path problem (MSPP) in this paper. A reliable shortest path algorithm (RSPA) is proposed to solve the SRSPP. A numerical example is used to demonstrate the performance of the proposed algorithm. Comparison is made by using the conventional label correcting approach (LCA) for solving the MSPP. The computational results indicate that the proposed RSPA is much efficient than LCA for finding the optimal RSP in Hong Kong road network.",

author = "Chen, {Bi Yu} and Lam, {Hing Keung William} and Tam, {Mei Lam}",

year = "2008",

month = dec,

day = "1",

language = "English",

isbn = "9789889884734",

pages = "229--238",

booktitle = "Proceedings of the 13th International Conference of Hong Kong Society for Transportation Studies",

note = "13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science ; Conference date: 13-12-2008 Through 15-12-2008",

}

Chen, BY, Lam, HKW & Tam, ML 2008, Using a multi-criteria approach to solve path finding problem in road networks with uncertainty. in Proceedings of the 13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science. pp. 229-238, 13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science, Kowloon, Hong Kong, 13/12/08.

Using a multi-criteria approach to solve path finding problem in road networks with uncertainty. / Chen, Bi Yu; Lam, Hing Keung William; Tam, Mei Lam.
Proceedings of the 13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science. 2008. p. 229-238.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Using a multi-criteria approach to solve path finding problem in road networks with uncertainty

AU - Chen, Bi Yu

AU - Lam, Hing Keung William

AU - Tam, Mei Lam

PY - 2008/12/1

Y1 - 2008/12/1

N2 - It was empirically found that travelers would make their route choice not only based on travel time saving but also on reduction of travel cost and travel time variability. However, little attention has been given to determine optimal reliable shortest path (RSP) in stochastic network effectively and efficiently. This paper investigates the stochastic reliable shortest path problem (SRSPP) in road networks with travel time uncertainty and toll charges. Based on the chance-constrained model formulation, the SRSPP is formulated as an equivalent multi-criteria shortest path problem (MSPP) in this paper. A reliable shortest path algorithm (RSPA) is proposed to solve the SRSPP. A numerical example is used to demonstrate the performance of the proposed algorithm. Comparison is made by using the conventional label correcting approach (LCA) for solving the MSPP. The computational results indicate that the proposed RSPA is much efficient than LCA for finding the optimal RSP in Hong Kong road network.

AB - It was empirically found that travelers would make their route choice not only based on travel time saving but also on reduction of travel cost and travel time variability. However, little attention has been given to determine optimal reliable shortest path (RSP) in stochastic network effectively and efficiently. This paper investigates the stochastic reliable shortest path problem (SRSPP) in road networks with travel time uncertainty and toll charges. Based on the chance-constrained model formulation, the SRSPP is formulated as an equivalent multi-criteria shortest path problem (MSPP) in this paper. A reliable shortest path algorithm (RSPA) is proposed to solve the SRSPP. A numerical example is used to demonstrate the performance of the proposed algorithm. Comparison is made by using the conventional label correcting approach (LCA) for solving the MSPP. The computational results indicate that the proposed RSPA is much efficient than LCA for finding the optimal RSP in Hong Kong road network.

UR - http://www.scopus.com/inward/record.url?scp=84896690257&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 9789889884734

SP - 229

EP - 238

BT - Proceedings of the 13th International Conference of Hong Kong Society for Transportation Studies

T2 - 13th International Conference of Hong Kong Society for Transportation Studies: Transportation and Management Science

Y2 - 13 December 2008 through 15 December 2008

ER -

Using a multi-criteria approach to solve path finding problem in road networks with uncertainty

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this