×

Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks. (English) Zbl 1011.90009

Summary: Travel times in congested transportation networks are time-varying quantities that can at best be known a priori probabilistically. In such networks, the arc weights (travel times) are represented by random variables whose probability distribution functions vary with time. These networks are referred to herein as stochastic, time-varying, or STV, networks. The determination of “least time” routes in STV networks is more difficult than in deterministic networks, in part because, for a given departure time, more than one path may exist between an origin and destination, each with a positive probability of having the least travel time. In this paper, measures for comparing time-varying, random path travel times over a time period are given for both a priori optimization and time-adaptive choices (where a driver may react to revealed arrival times at intermediate nodes). The resulting measures are central to the development of methodologies for determining “optimal” paths in STV networks.

MSC:

90B15 Stochastic network models in operations research
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aboudi, R.; Thon, D., Efficient algorithms for stochastic dominance tests based on financial market data, Management Science, 40, 508-515 (1994) · Zbl 0807.90001
[2] Ahuja, R.; Magnanti, T.; Orlin, J., Network Flows (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, (Chapters 4 and 5)
[3] Eiger, A.; Mirchandani, P.; Soroush, H., Path preferences and optimal paths in probabilistic networks, Transportation Science, 19, 75-84 (1985)
[4] Hadar, J.; Russell, W., Rules for ordering uncertain prospects, The American Economic Review, 59, 25-34 (1969)
[5] Hall, R., The fastest path through a network with random time-dependent travel times, Transportation Science, 20, 182-188 (1986)
[6] Hanoch, G.; Levy, H., The efficiency analysis of choices involving risk, The Review of Economic Studies, 36, 335-346 (1969) · Zbl 0184.45202
[7] Kaufman, D.; Smith, R., Fastest paths in time-dependent networks for intelligent vehicles highway systems application, IVHS Journal, 1, 1-11 (1993)
[8] Loui, R., Optimal paths in graphs with stochastic or multidimensional weights, Communications of the ACM, 26, 670-676 (1983) · Zbl 0526.90085
[9] Miller-Hooks, E., 1997. Optimal routing in time-varying, stochastic networks: Algorithms and implementation. Ph.D. Dissertation, Department of Civil Engineering, The University of Texas at Austin; Miller-Hooks, E., 1997. Optimal routing in time-varying, stochastic networks: Algorithms and implementation. Ph.D. Dissertation, Department of Civil Engineering, The University of Texas at Austin
[10] Miller-Hooks, E., Adaptive least expected time paths in stochastic, time-varying transportation and data networks, Networks, 37, 1, 35-52 (2001) · Zbl 0997.90038
[11] Miller-Hooks, E.; Mahmassani, H., Least possible time paths in stochastic, time-varying networks, Computers and Operations Research, 25, 1107-1125 (1998) · Zbl 1042.90520
[12] Miller-Hooks, E., Mahmassani, H., 1998b. On the generation of nondominated paths in stochastic, time-varying transportation networks. In: Proceedings of TRISTAN III (Triennial Symposium on Transportation Analysis); Miller-Hooks, E., Mahmassani, H., 1998b. On the generation of nondominated paths in stochastic, time-varying transportation networks. In: Proceedings of TRISTAN III (Triennial Symposium on Transportation Analysis) · Zbl 1042.90520
[13] Miller-Hooks, E.; Mahmassani, H., Least expected time paths in stochastic, time-varying transportation networks, Transportation Science, 34, 198-215 (2000) · Zbl 0990.90011
[14] Milne, F.; Neave, E., Dominance relations among standardized variables, Management Science, 40, 1343-1351 (1994) · Zbl 0822.90002
[15] Mirchandani, P.; Soroush, H., Optimal paths in probabilistic networks: A case with temporary preferences, Computers and Operations Research, 12, 365-381 (1985) · Zbl 0607.90086
[16] Nguyen, S.; Pallottino, S., Hyperpaths and shortest hyperpaths, (Combinatorial Optimization. Combinatorial Optimization, Lecture Notes in Mathematics, vol. 1403 (1986), Springer: Springer Berlin), 258-271 · Zbl 0678.90088
[17] Nguyen, S.; Pallottino, S., Equilibrium traffic assignment for large scale transit networks, European Journal of Operational Research, 37, 176-186 (1988) · Zbl 0649.90049
[18] Psaraftis, H.; Tsitsiklis, J., Dynamic shortest paths in acyclic networks with Markovian arc costs, Operations Research, 41, 91-101 (1993) · Zbl 0771.90045
[19] Spiess, H.; Florian, M., Optimal strategies: A new assignment model for transit networks, Transportation Research B, 23, 83-102 (1989)
[20] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0063.05930
[21] Wu, J.; Florian, M., A simplical decomposition method for the transit equilibrium assignment problem, Annals of Operations Research, 44, 245-260 (1993) · Zbl 0801.90042
[22] Wu, J.; Florian, M.; Marcotte, P., Transit equilibrium assignment: A model and solution algorithms, Transportation Science, 28, 193-203 (1994) · Zbl 0814.90025
[23] Ziliaskopoulos, A.; Mahmassani, H., Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications, Transportation Research Record, 1408, 94-100 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.