EFFICIENT CHAINS IN A NETWORK WITH TIME COST TRADE-OFF FUNCTION ON EACH ARC

In this paper, we consider a network in which each arc is associated w ith a time-cost trade-off function. This function is assumed to be non -increasing, piece-wise linear and convex. The objective is to enumera te all efficient chains in the context of two criteria, the total time and the total cost required to traverse from source node to sink node . We develop a solution procedure based on a labelling scheme to deriv e all efficient chains from source node to sink node. The problem with finite number of discrete choices for the time-cost pair on each arc is NP-hard. It is shown that a modified version of the algorithm of An eja and Nair [1] yields all efficient chains for the discrete case.