Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length

ABSTRACT

In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting constraints are presented and the properties of the derived path are investigated. It is shown that if departure time from the source node is unrestricted, then a shortest path can be found that is simple and achieves a delay as short as the most unrestricted path. In the case of restricted transit, it is shown that there exist cases in which the minimum delay is finite, but the path that achieves it is infinite.

REFERENCES

• 1: COOKE, K. L., AND HALSEY, E. The shortest route through a network with time dependent internodal transit times. J. Math. Anal. Appl. 14 (1966), 493-498.
• 2: DEO, N., AND PANG, C.Y. Shortest path algorithms: Taxonomy and annotation. Networks 14 (1984), 275-323.
• 3: DIJKSTRA, E.W. A note on two problems in connection with graphs. Num. Anal. 1 (Oct. 1959), 269-271.
• 4: DREYFUS, S.E. An appraisal of some shortest path algorithms. Oper. Res. 17 (1969), 395-412.
• 5: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 6: EVEN, S., AND GAZIT, H. Updating distances in dynamic graphs. Meth. Oper. Res. 49 (May 1985), 371-387.
• 7: FORD, L. R., JR., AND FULKERSON, D.R. Constructing maximal dynamic flows from static flows. Oper. Res. 6 (1958), 419-433.
• 8: FORD, L. R., JR., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.
• 9: GERLA, M., AND KLEINROCK, L. Flow control: A comparative survey. IEEE Trans. Commun. COM-28, 4 (Apr. 1980), 553-574.
• 10: HALPERN, J. The shortest route with time dependent length of edges and limited delay possibilities in nodes. Z. Oper. Res. 21 (1977), 117-124.
• 11: KLAFSZKY, E. Determination of shortest path in a network with time-dependent edge-lengths. Math. Oper. Stat. 3 (1972), 255-257.
• 12: LING, S. T., FURUNO, K., AND TEZUKA, Y. Optimal path in networks with time-varying traverse time and expenses branches. Tech. Rep. of Osaka University, Japan, 1972.
• 13: McQUILLAN, J. M., RICHER, I., AND ROSEN, E.C. The new routing algorithm for the ARPANET. IEEE Trans. Commun. COM-28, 5 (May 1980), 71 I-719.
• 14: ORDA, A., AND ROM, R. Distributed shortest-path protocols for time-dependent networks. In Proceedings oflCCC 88 (Tel Aviv, Israel, Nov. 1988), pp. 439-445.
• 15: ORDA, A., AND ROM, R. Minimum weight paths in time-dependent networks. EE Publication No. 710. Faculty of Electrical Engineering, Technion, Haifa, Israel, Mar. 1989.
• 16: SEGALL, A. Distributed network protocols. IEEE Trans. on Inf. Theory(Jan. 1983), 23-34.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance