Finding Reliable Shortest Paths in Road Networks U

Authors: Bi Yu Chen William H K Lam Agachai Sumalee Qingquan Li Hu Shao Zhixiang Fang

Publish Date: 2012/05/16

Volume: 13, Issue: 2, Pages: 123-148

PDF Link

Abstract

The aim of this study is to investigate the solution algorithm for solving the problem of determining reliable shortest paths in road networks with stochastic travel times The availability of reliable shortest paths enables travelers in the face of travel time uncertainty to plan their trips with a prespecified ontime arrival probability In this study the reliable shortest path between origin and destination nodes is determined using a multiplecriteria shortest path approach when link travel times follow normal distributions The dominance conditions involved in such problems are established thereby reducing the number of generated nondominated paths during the search processes Two solution algorithms multicriteria labelsetting and A algorithms are proposed and their complexities analyzed Computational results using large scale networks are presented Numerical examples using data from a realworld advanced traveller information system is also given to illustrate the applicability of the solution algorithms in practiceThe authors are thankful to the anonymous referees for their comments and suggestions that improved this paper The work described in this paper was jointly supported by a competitive earmarked research grant from the Research Grant Council of the Hong Kong Special Administration Region PolyU 5195/07E an internal research grant JBB7Q from the Research Committee of the Hong Kong Polytechnic University research grants from National Natural Science Foundation of China 70901073 40830530 and 41071285 the National Hightech RD Program of China 863 program 2012AA12A211 and the School of Traffic Transportation of Beijing Jiaotong University 2010RC005

Keywords: