Adaptive least-expected time paths in stochastic, time-varying transportation and data networks.

*(English)*Zbl 0997.90038Summary: In congested transportation and data networks, travel (or transmission) times are time-varying quantities that are at best known a priori with uncertainty. In such Stochastic, Time-Varying (STV) networks, one can choose to use the a priori Least-Expected Time (LET) path or one can make improved routing decisions en route as traversal times on traveled arcs are experienced and arrival times at intermediate locations are revealed. In this context, for a given origin-destination pair at a specific departure time, a single path may not provide an adequate solution, because the optimal path depends on intermediate information concerning experienced traversal times on traveled arcs. Thus, a set of strategies, referred to as hyperpaths, are generated to provide directions to the destination node conditioned upon arrival times at intermediate locations.

In this paper, an efficient label-setting-based algorithm is presented for determining the adaptive LET hyperpaths in STV networks. Such a procedure is useful in making critical routing decisions in intelligent transportation systems (ITS) and data communication networks. A side-by-side comparison of this procedure with a label-correcting-based algorithm for solving the same problem is made. Results of extensive computational tests to assess and compare the performance of both algorithms, as well as to investigate the characteristics of the resulting hyperpaths, are presented. An illustrative example of both procedures is provided.

In this paper, an efficient label-setting-based algorithm is presented for determining the adaptive LET hyperpaths in STV networks. Such a procedure is useful in making critical routing decisions in intelligent transportation systems (ITS) and data communication networks. A side-by-side comparison of this procedure with a label-correcting-based algorithm for solving the same problem is made. Results of extensive computational tests to assess and compare the performance of both algorithms, as well as to investigate the characteristics of the resulting hyperpaths, are presented. An illustrative example of both procedures is provided.

##### MSC:

90B36 | Stochastic scheduling theory in operations research |

90B06 | Transportation, logistics and supply chain management |

##### Keywords:

optimal routing; dynamic stochastic networks; shortest paths; intelligent transportation systems; data networks; network algorithms
Full Text:
DOI

**OpenURL**

##### References:

[1] | and Network flows, Prentice-Hall, Englewood, NJ, 1993, Chapters 4-5. |

[2] | Chabini, Trans Res Rec 1645 pp 170– (1998) |

[3] | Fu, Trans Res B 32 pp 499– (1998) |

[4] | Hall, Trans Sci 20 pp 182– (1986) |

[5] | and Stochastic programming, Wiley, New York, 1994. |

[6] | Optimal routing in time-varying, stochastic networks: Algorithms and implementation, Ph.D. Dissertation, Department of Civil Engineering, the University of Texas at Austin, 1997. |

[7] | Miller-Hooks, Comput Oper Res 25 pp 1107– (1998) |

[8] | and On the generation of nondominated paths in stochastic, time-varying transportation networks, Proc TRISTAN III (Triennial Symposium on Transportation Analysis), 1998. |

[9] | Miller-Hooks, Trans Res Rec 1645 pp 143– (1998) |

[10] | and Path comparison for a priori and time-adaptive route choice in stochastic, time-varying networks, submitted for publication. |

[11] | Miller-Hooks, Trans Sci 34 pp 198– (2000) |

[12] | and Determining robust paths for real-time routing in transportation networks, submitted for publication. |

[13] | and Hyperpaths and shortest hyperpaths, Combinatorial optimization, Lecture notes in mathematics 1403, Springer-Verlag, Berlin, 1986, pp. 258-271. |

[14] | Pape, Math Program 7 pp 212– (1974) |

[15] | Polychronopoulos, Networks 27 pp 133– (1996) |

[16] | Psaraftis, Oper Res 41 pp 91– (1993) |

[17] | Optimum path algorithms on multidimensional networks: Analysis and design, implementation and computational experience, Ph.D. Dissertation, Department of Civil Engineering, University of Texas at Austin, 1994. |

[18] | Ziliaskopoulos, Trans Res Rec 1408 pp 94– (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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.