Analysing Stagecoach Network Problem Using Dynamic Programming Algorithm

Abstract

The stagecoach problem is a special type of network analysis problem in which the cities (nodes) are arranged in stages. By such human or natural arrangement, a journey from City 1 in stage 1 to City n in stage n involves visiting only one city in each intermediate stage. The stagecoach problem involves the determination of the minimum cost flow in which basically two methods have been in use. One of the methods is by listing all possible routes, computing their corresponding costs and selecting the minimum cost route. This procedure entails much computational effort. The second procedure is to determine the suboptimal cost of routes between any two consecutive stages. Though this second approach has less computational effort, its overall optimal policy could be wrong because the choice of a least expensive route at one stage may result in our adopting a more expensive route at a later stage. In this paper we present a recursive dynamic programming algorithm for solving the stagecoach problem. The algorithm is computationally more efficient than the first method as it obtains its minimum total cost using the suboptimal policies of the different stages without computing the cost of all the routes. By the dynamic programming algorithm of this paper, the possibility of missing the minimum cost route is ruled out as could happen in the second approach. The dynamic programming algorithm for obtaining the minimum cost path in a stagecoach problem is numerically illustrated

Keywords: Network analysis, stagecoach, dynamic programming algorithm

Global Journal of Mathematical Sciences Vol. 7 (1) 2008: pp. 15-20