Estimation-pruning (EP) algorithm for point-to-point travel cost minimization in a non-FIFO dynamic network

This paper presents the estimation-pruning (EP) algorithm for finding the best path (with minimum cost) from a source to a destination in a dynamic network that does not necessarily obey the first-in-first-out (FIFO) property. The EP algorithm consists of two steps. The first step is the forward or the estimation step in which a bound on the traveling cost of each possible path is calculated. The second step is the backward or the pruning step in which the paths that are unlikely to produce the best route are eliminated. The resulting network is then expanded in time and is converted to a static network, which is used to find the best route.