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

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

• speed-up techniques
• time-varying shortest path