TY - JOUR

T1 - Identifying multiple and reasonable paths in transportation networks

T2 - A heuristic approach

AU - Park, Dongjoo

AU - Rilett, Laurence R.

PY - 1997

Y1 - 1997

N2 - A fundamental component of many transportation engineering applications is the identification of the route between a given origin and destination. Typically, some type of shortest-path algorithm is used for this task. However, shortest-path algorithms are only applicable when a single criterion, such as minimizing travel time, is used for path selection. When multiple criteria, such as the mean and variance of travel time, are used for path selection, then alternative-path identification methods must be found. The present objective is to develop an algorithm that can identify multiple and reasonable routes in transportation networks so that multiple-criteria decision-making techniques can be used in route selection. First, the definitions of single and multiple routes from a transportation engineering perspective are examined. It is indicated that although the traditional k-shortest-path algorithms can find routes with similar route travel times, the routes may be too similar with respect to the links used and consequently are not appropriate for certain transportation applications. A definition of a reasonable path is developed on the basis of transportation engineering rather than purely mathematical considerations. Two k-reasonable-path algorithms are then illustrated. These algorithms can be used to identify multiple and reasonable routes in transportation networks. Lastly, the two heuristic algorithms were tested on a network from Bryan to College Station, Texas, and the results were compared with the results obtained with a traditional k-shortest-path algorithm. It was found that the reasonable-path algorithms can identify routes that are similar in route travel time but significantly different in terms of the links used.

AB - A fundamental component of many transportation engineering applications is the identification of the route between a given origin and destination. Typically, some type of shortest-path algorithm is used for this task. However, shortest-path algorithms are only applicable when a single criterion, such as minimizing travel time, is used for path selection. When multiple criteria, such as the mean and variance of travel time, are used for path selection, then alternative-path identification methods must be found. The present objective is to develop an algorithm that can identify multiple and reasonable routes in transportation networks so that multiple-criteria decision-making techniques can be used in route selection. First, the definitions of single and multiple routes from a transportation engineering perspective are examined. It is indicated that although the traditional k-shortest-path algorithms can find routes with similar route travel times, the routes may be too similar with respect to the links used and consequently are not appropriate for certain transportation applications. A definition of a reasonable path is developed on the basis of transportation engineering rather than purely mathematical considerations. Two k-reasonable-path algorithms are then illustrated. These algorithms can be used to identify multiple and reasonable routes in transportation networks. Lastly, the two heuristic algorithms were tested on a network from Bryan to College Station, Texas, and the results were compared with the results obtained with a traditional k-shortest-path algorithm. It was found that the reasonable-path algorithms can identify routes that are similar in route travel time but significantly different in terms of the links used.

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

U2 - 10.3141/1607-05

DO - 10.3141/1607-05

M3 - Article

AN - SCOPUS:0002989488

SN - 0361-1981

SP - 31

EP - 37

JO - Transportation Research Record

JF - Transportation Research Record

IS - 1607

ER -