Speed-up Technique in Time-Varying Shortest Path Problems with Arbitrary Waiting Times

Document Type : Original Article

Authors

1 Associate Prof., Department of Mathematics, Faculty of Basic Sciences, University of Qom, Qom, Iran.

2 Ph.D, Applied Mathematics, Faculty of Basic Sciences, University of Qom, Qom, Iran.

Abstract

Network flow problems are considered a vital branch of operations research. These problems are classified into static and time-varying classes. Network flow problems are time-varying in real application, because any flow must take a given amount of time to traverse an arc. Moreover, all the parameters in the network can be time-dependent. In this paper, the speed-up technique on time-varying shortest path problems is studied. First of all, the time-varying shortest path problem is explained. The problem is to find the shortest paths from a specific vertex (which is called a source) to other vertices, so that the total cost of the path is minimized and the total travel times and waiting times reach a maximum value of T, where T is a given positive integer. Then the speed-up technique is explained for a shortest path problem.

Keywords

Main Subjects

References

Ahuja, R. K. & Magnanti, T. L. & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. DC: Prentice-Hall, Englewood Cliffs, NJ.
Ford, L. R. & Fulkerson, D. R.  (1958). Constructing maximal dynamic flows from static flows, Operations Research, 6, 419–433.
Aronson, J. (1989). A survey of dynamic network flows. Annals of Operations Research, 20, 1–66.
Hoppe, B. (1995). Efficient Dynamic Network Flow Algorithms. Ph.D. Thesis, Cornell University.
Chabini, L. (1998). Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record, 1645, 170–175.
Glockner, G. & Nemhauser, G. (2000). A dynamic network flow problem with uncertain arc capacities: formulation and problem structure, Operations Research, 48 (2): 33–242.
Salehi Fathabadi, H. & Hosseini, S.A. (2010).  Maximum flow problem on dynamic generateve network flows with time-varying bounds. Applied Mathematical Modeling, 34, 2136–2147.
Orda, A. & Rom, R. (1990). Shortest-path and minimum-delay algorithms in networks with time-dependent edge length. Journal of the Association for Computing, 37, 607–625.
Orda, A. & Rom, R. (1991). Minimum weight paths in time-dependent networks. Networks, 21, 295–320.
Cai, X. & Kloks, T. & Wong, C.k. (1997). Time-varying shortest path problems with constraints. Networks, 29, 141–149.
Cai, X. & Sha, D. & Wong, C. K. (2001). Time-varying minimum cost flow problems. European Journal of Operational Research, 131, 352–374.
Nasrabadi, E. & Hashemi, M. (2010). Minimum cost time-varying network flow problems. Optimization Methods & Software, 25 (3): 429–447.
Shirdel, Gh. & Rezapour, H. (2015). K-Objective Time-Varying Shortest Path Problem with Zero Waiting Times at Vertices. Trends in Applied Sciences Research, 10 (5): 278-285.
Shirdel, Gh. & Rezapour, H.  (2016). the Arbitrary Waiting Times in the Time-Varying Shortest Path with Triangular Fuzzy Costs. Advances and Applications in Mathematical Sciences, 15, (2): 75-85.
Shirdel, Gh. & Rezapour, H. (2016). Time-varying maximum capacity path problem with zero waiting times and fuzzy capacities, SpringerPlus 5, 981-990.
Send comment about this article
CAPTCHA Image

Files

Share

How to cite

Statistics