In this paper, an exact algorithm is proposed for determining adjustable preference path strategies in multicriteria, stochastic, and time-varying (MSTV) networks. In MSTV networks, multiple arc attributes are associated with each arc, each being a time-varying random variable. Solution paths that seek to minimize the expected value of each of multiple criteria are sought from all origins to a specified destination for all departure times in a period of interest. These solution strategies allow a traveler to update a preference for which criterion of multiple criteria is of greatest importance and then adaptively select the best path for the selected criterion at each node in response to knowledge of experienced travel times on the arcs. Such adjustable preference path strategies are particularly useful for providing real-time path-finding assistance.
Get full access to this article
View all access options for this article.
References
1.
GalloG.LongoG.PallottinoS. and NguyenS.Directed Hypergraphs and Applications. Discrete Applied Mathematics, Vol. 42, 1993, pp. 177–201.
2.
ChenT.-Y.ChangH.-L. and TzengG.-H.Using a Weight-Assessing Model to Identify Route Choice Criteria and Information Effects. Transportation Research Part A, Vol. 35, 2001, pp. 197–224.
3.
HallR.Fastest Path through a Network with Random Time-Dependent Travel Times. Transportation Science, Vol. 20, No. 31986, pp. 182–188.
4.
Miller-HooksE. and MahmassaniH.Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks. Transportation Science, Vol. 34, No. 22000, pp. 198–215.
5.
PretolaniD.A Directed Hypergraph Model for Random Time Dependent Shortest Paths. European Journal of Operational Research, Vol. 123, 2000, pp. 315–324.
6.
MartinsE. Q. V.On a Multicriteria Shortest Path Problem. European Journal of Operational Research, Vol. 16, 1984, pp. 236–245.
7.
CorleyH. W. and MoonI. D.Shortest Path in Networks with Vector Weights. Journal of Optimization Theory and Applications, Vol. 46, No. 11985, pp. 79–86.
8.
NozickL. K.ListG. F. and TurnquistM. A.Integrated Routing and Scheduling in Hazardous Materials Transportation. Transportation Science, Vol. 31, No. 31997, pp. 200–215.
9.
WijeratneA. B.TurnquistM. A. and MirchandaniP. B.Multiobjective Routing of Hazardous Materials in Stochastic Networks. European Journal of Operational Research, Vol. 65, 1993, pp. 33–43.
10.
Miller-HooksE. and MahmassaniH. S.Optimal Routing of Hazardous Materials in Stochastic, Time-Varying Transportation. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 143–151.
11.
AhujaR.MagnantiT. and OrlinJ.Network Flows: Theory, Algorithms and Applications.Prentice Hall, Englewood Cliffs, N.J., 1993, Chapts. 4, 5.
12.
ChangT. S.NozickL. K. and TurnquistM. A.Multi-Objective Path-Finding in Stochastic Dynamic Networks, with Application to Routing Hazardous Materials Shipments. Transportation Science, in press.
13.
NielsenL. R.AndersenK. A. and PretolaniD.Bicriterion Shortest Hyperpaths in Random Time-Dependent Networks. IMA Journal of Management Mathematics, Vol. 14, No. 32003, pp. 271–303.
14.
OpasanonS. and Miller-HooksE.Multicriteria Adaptive Hyperpaths in Stochastic, Time-Varying Networks. European Journal of Operational Research, in press.
15.
WieB.-W.TobinR. L. and CareyM.The Existence, Uniqueness and Computation of an Arc-Based Dynamic Network User Equilibrium Formulation. Transportation Research Part B, Vol. 36, 2002, pp. 897–918.
16.
JangW.RanB. and ChoiK.A Discrete Time Dynamic Flow Model and a Formulation and Solution Method for Dynamic Route Choice. Transportation Research Part B, in press, 2005.
17.
LouiR. P.Optimal Paths in Graphs with Stochastic or Multidimensional Weights. Communications of the ACM, Vol. 26, 1983, pp. 670–676.
18.
EigerA.MirchandaniP. B. and SoroushH.Path Preferences and Optimal Paths in Probabilistic Networks. Transportation Science, Vol. 19, No. 11985, pp. 75–84.
19.
HenigM. I.The Shortest Path Problem with Two Objective Functions. European Journal of Operational Research, Vol. 25, 1985, pp. 281–291.
20.
MirchandaniP. B. and SoroushH.Optimal Paths in Probabilistic Networks: A Case with Temporary Preferences. Computers and Operations Research, Vol. 12, No. 41985, pp. 365–381.
21.
ModestiP. and SciomachenA.A Utility Measure for Finding Multi-objective Shortest Paths in Urban Multimodal Transportation Networks. European Journal of Operational Research, Vol. 111, 1998, pp. 495–508.
22.
OrdaA. and RomR.Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length. Journal of the Association for Computing Machinery, Vol. 37, No. 31990, pp. 607–625.
23.
OpasanonS.On Finding Paths and Flows in Multicriteria, Stochastic and Time-Varying Networks.Ph.D. dissertation. University of Maryland, College Park, 2004.
