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

Shirdel, Gholamhasan; Rezapour, Hasan

doi:10.22091/jemsc.2018.1688.1049

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

Document Type : Original Article

Authors

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

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

10.22091/jemsc.2018.1688.1049

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