THE SINGLE MOST VITAL ARC IN THE MOST ECONOMICAL PATH PROBLEM - A PARAMETRIC ANALYSIS

For a network with two specified nodes, an arc is called a single most vital arc in the shortest path problem, if its removal from the netwo rk results in the greatest increase in the shortest distance between t he specified nodes. In this paper, we consider the single most vital a rc in a generalized shortest path problem, called the most economical path problem, in which the cost for transshipping lambda units of carg o along an arc depends on lambda. Clearly, the single most vital arc i n the most economical path problem depends on lambda. Moreover, lambda changes frequently in practical applications. We propose an algorithm to find the single most vital arcs in the network for all possible va lues of lambda.