Incorporating Uncertainty and Multiple Objectives in Real-Time Route Selection
Publication: Journal of Transportation Engineering
Volume 127, Issue 6
Abstract
There is a requirement in real-time, routing information systems to identify the “optimal” route based on the multiple objectives and the individual decision-making rules of the users. While a number of utility theory-based techniques have been developed to accomplish this goal, there are a number of shortcomings regarding implementation. These problems, in particular, are: (1) obtaining a mathematical representation of the driver's utility function for each trip type is difficult in practice; (2) the drivers' utility function is a function of the choice set and is difficult to calibrate prior to the identification of the choice set (i.e., it is context-dependent); and (3) identifying the optimal path using a realistic multiple attribute nonlinear utility function is a nondeterministic polynomial time hard problem. Consequently, a heuristic two-stage strategy that identifies multiple reasonable routes and then selects the “near-optimal” path may be an effective and practical alternative. The second step of this proposed strategy is the focus of this paper. A fuzzy logic-based multiple objective route choice model (or decision support system) is developed in order to evaluate the alternative routes identified in the first step. Fuzzy logic is used to take into account crisp values, fuzzy numbers, and linguistic variables that are common phenomena in a real-time vehicle routing environment. The routes and the route attributes are identified and a posterior utility function is developed by combining the prior utility function with a context-dependent utility function that is derived from an entropy model. The proposed strategy is illustrated using Intelligent Transportation System (ITS) data from Houston, Texas, and tested on a traffic network from Austin, Texas, under various traffic conditions. When multiple attributes were considered, an alternative path to the fastest path was found to be the “optimal” path for a significant number of O-D pairs, and this was likely to occur as the level of congestion and the O-D distance increased.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Abdel-Aty, A. M., Kitamura, R., and Jovanis, P. P. ( 1995). “Exploring route choice behavior using geographical information system-based alternative routes and hypothetical travel time information input.” Transp. Res. Record 1493, Transportation Research Board, Washington, D.C., 74–80.
2.
Azevedo, J. A., Costa, M.E.O.S., Madeira, J. J. E. R. S., and Martins, E. Q. V. ( 1993). “An algorithm for the ranking of shortest paths.” Eur. J. Operational Res., 69, 97–106.
3.
Blue, V., Adler, J., and List, G. ( 1997). “Real-time multiple objective path search for in-vehicle guidance systems.” Transp. Res. Rec. 1588, Transportation Research Board, Washington, D.C., 10–17.
4.
Carraway, R. L., Morin, T. L., and Moskowitz, H. ( 1990). “Generalized dynamic programming for multicriteria optimization.” Eur. J. Operational Res., 44, 95–104.
5.
Chen, S.-J., and Hwang, C.-L. ( 1992). Fuzzy multiple attribute decisionmaking: methods and applications, Springer-Verlag, Berlin.
6.
Current, J. R., ReVelle, C. S., and Cohon, J. L. ( 1990). “An interactive approach to identify the best compromise solution for two objective shortest path problems.” Comp. and Operations Res., 17(2), 187–198.
7.
Dial, R. B. ( 1979). “A model and algorithm for multicriteria route-mode choice.” Transp. Res., Part B, 13, 311–316.
8.
Dial, R. B. ( 1996). “Bicriterion traffic assignment: basic theory and elementary algorithms.” Transp. Sci., 30(2), 93–111.
9.
Fu, L., and Rilett, L. R. ( 1998). “Expected shortest paths in dynamic and stochastic traffic networks.” Transp. Res., Part B, 32(7), 499–514.
10.
Hall, R. ( 1986). “The fastest path through a network with random time-dependent travel time.” Transp. Sci., 20(3), 182–188.
11.
Henig, M. I. ( 1985). “The shortest path problem with two objective functions.” Eur. J. Operational Res., 25, 281–291.
12.
Khattak, A. J., Schofer, J. L., and Koppleman, F. S. ( 1992). “Factors influencing commuter's enroute diversion behavior in response to delay.” Transp. Res. Rec. 1318, Transportation Research Board, Washington, D.C., 125–136.
13.
Loui, R. P. ( 1983). “Optimal paths in graphs with stochastic or multidimensional weights.” J. Assn. for Comp. Machinery, 26(9), 670–676.
14.
Namkoong, S., Rho, J. H., and Choi, J. U. ( 1996). “Opportunistic approach to developing a knowledge-based optimal path finding system.” Proc., 3rd World Congr. on Intelligent Transportation Sys., Intelligent Transportation Society of America, Washington, D.C., 1–11.
15.
Martins, E. Q. V. ( 1984). “An algorithm for ranking paths that may contain cycles.” Eur. J. Operational Res., 18, 123–130.
16.
Park, D. ( 1998). “Multiple path based vehicle routing in dynamic and stochastic transportation networks.” PhD thesis, Dept. of Civ. Engrg., Texas A&M University, College Station, Tex.
17.
Park, D., and Rilett, L. R. ( 1997). “Identifying multiple and reasonable paths in transportation networks: a heuristic approach.” Transp. Res. Rec. 1607, Transportation Research Board, Washington, D.C., 31–37.
18.
Park, D., and Rilett, L. R. ( 1998). “Forecasting multiple-period freeway link travel times using modular neural networks.” Transp. Res. Rec. 1617, Transportation Research Board, Washington, D.C., 163–170.
19.
Park, D., and Rilett, L. R. ( 2000). “A class of multi-criteria shortest problems for real-time in-vehicle routing.” Transp. Sci., in press.
20.
Park, D., Rilett, L. R., and Han, G. (1999). “Spectral basis neural networks for real-time link travel time forecasting.”J. Transp. Engrg., ASCE, 125(6), 515–523.
21.
Sancho, N. G. F. ( 1988). “A new type of multi-objective routing problem.” Engrg. Optimization, 14, 115–119.
22.
Scott, K. G., and Bernstein, D. ( 1998). “Solving a best path problem when the value of time function is nonlinear.” 77th Transp. Res. Board Ann. Mtg., National Research Council, Washington, D.C., Preprint 980976.
23.
Schofer, J. L., Koppleman, F. S., and Charlton, W. A. ( 1997). “Perspectives on driver preferences for dynamic route guidance systems.” Transp. Res. Rec. 1588, Transportation Research Board, Washington, D.C., 26–31.
24.
SmartRoute Systems. ( 1999). “Traveler information services.” 〈http://www.smartroute.com/〉.
25.
Wohlschlaeger, S. D. ( 1997). “Factors affecting motorist route choice and diversion potential.” 76th Transp. Res. Board Ann. Mtg., National Research Council, Washington, D.C., Preprint 970968.
26.
Yen, J., and Langari, L. ( 1997). Fuzzy logic in control and intelligent systems, Prentice Hall, Englewood Cliffs, N.J.
27.
Zeleny, M. ( 1976). “The attribute-dynamic attitude model (ADAM).” Mgmt. Sci., 23(1), 12–26.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 127 • Issue 6 • December 2001
Pages: 531 - 539
History
Received: Jun 5, 2001
Published online: Dec 1, 2001
Published in print: Dec 2001
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.