The focus of this research is to develop minimum-cost dynamic routing policies that can identify connecting paths between nodes in a stochastic-state network. In this context, the stochastic element of the network is the network structure, that is, the set of links that exist under each realization of the network state. It is assumed that information about the true network state can be gathered only endogenously through the routing decisions themselves. As such, the objective becomes finding a dynamic policy that accounts for information gathered en route that minimizes the cost of detection of a viable path between a given origin and destination. An exact solution method, based on a Markovian decision process, is presented, and then a heuristic based on an aggregating function of the network is developed.
Get full access to this article
View all access options for this article.
References
1.
DijsktraE. W.A Note on Two Problems in Connection with Graphs. Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
2.
SigalC.E., PritskerA. A. B., and SolbergJ. J.The Stochastic Shortest Route Problem. Operations Research, Vol. 28, 1980, pp. 1122–1129.
3.
CoreaG.A., and KulkarniV. G.Minimum Cost Routing on Stochastic Networks. Operations Research, Vol. 38, No. 3, 1990, pp. 527–536.
4.
CoreaG.A., and KulkarniV. G.Shortest Paths in Stochastic Networks with Arc Lengths Having Discrete Distributions. Networks, Vol. 23, No. 3, 1993, pp. 175–183.
5.
Miller-HooksE., and MahmassaniH. S.Least Possible Time Paths in Stochastic, Time-Varying Networks. Computers and Operations Research, Vol. 25, No. 12, 1998, pp. 1107–1125.
6.
KulkarniV. G.Shortest Paths in Networks with Exponentially Distributed Arc Lengths. Networks, Vol. 16, No. 3, 1986, pp. 255–274.
7.
FrankH.Shortest Paths in Probabilistic Graphs. Operations Research, Vol. 17, No. 4, 1969, pp. 583–599.
8.
ZiliaskopoulosA.K., and MahmassaniH. S.Time-Dependent, Shortest-Path Algorithm for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.
9.
PretolaniD.A Directed Hypergraph Model for Random Time Dependent Shortest Paths. European Journal of Operational Research, Vol. 123, No. 2, 2000, pp. 315–324.
10.
WallerS.T., and ZiliaskopoulosA. K.On the Online Shortest Path Problem with Limited Arc Cost Dependencies. Networks, Vol. 40, No. 4, 2002, pp. 216–227.
11.
PolychronopoulosG.H., and TsitsiklisJ. N.Stochastic Shortest Path Problems with Recourse. Networks, Vol. 27, No. 2, 1996, pp. 133–143.
12.
LouiR. P.Optimal Paths in Graphs with Stochastic or Multidimensional Weights. Communications of the Association of Computing Machinery, Vol. 26, No. 9, 1983, pp. 670–676.
13.
EigerA., MirchandaniP.B., and SoroushH.. Path Preferences and Optimal Paths in Probabilistic Networks. Transportation Science, Vol. 19, No. 1, 1985, p. 75.
14.
MirchandaniP.B., and SoroushH.. Optimal Paths in Probabilistic Networks: A Case with Temporary Preferences. Computers and Operations Research, Vol. 12, No. 4, 1985, pp. 365–381.
15.
MurthyI., and SarkarS.. A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems. Transportation Science, Vol. 30, No. 3, 1996, p. 220.
16.
MirchandaniP. B.Shortest Distance and Reliability of Probabilistic Networks. Computers and Operations Research, Vol. 3, No. 4, 1976, pp. 347–355.
17.
BertsekasD.P., and TsitsiklisJ. N.An Analysis of Stochastic Shortest Path Problems. Mathematics of Operations Research, Vol. 16, No. 3, 1991, pp. 580–595.
18.
FuL., and RilettL. R.Expected Shortest Paths in Dynamic and Stochastic Traffic Networks. Transportation Research Part B: Methodological, Vol. 32, No. 7, 1998, pp. 499–516.
19.
ZhangJ., ZhuK., MukherjeeB., and ZangH.. Service Provisioning to Provide Per-Connection-Based Availability Guarantee in WDM Mesh Networks. Proc., Optical Fiber Communications Conference, 2003.IEEE, New York, 2004, pp. 622–624.
20.
ModianoE.H., and LeeH. W. Diverse Routing in Networks with Probabilistic Failures. Proc., INFOCOM. IEEE, New York, 2009, pp. 1035–1043.
21.
AndreattaG., and RomeoL.. Stochastic Shortest Paths with Recourse. Networks, Vol. 18, No. 3, 1988, pp. 193–204.
