Efficient chains in a network with time-cost trade-off function on each arc

In this paper, the authors consider a network in which each arc is associated with a time-cost trade-off function. This function is assumed to be non-increasing, piece-wise linear and convex. The objective is to enumerate 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. The authors develop a solution procedure based on a labelling scheme to derive 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 Aneja and Nair yields all efficient chains for the discrete case.