On the sum–max bicriterion path problem

In this paper, we study a special class of bicriterion path problems where the objective functions are defined by a sum and a maximum: the sum–max bicriterion path problem (SMBPP). After reviewing some special kinds of efficient paths, we propose some algorithms to generate these kinds of efficient paths, based on a progressive reduction of the original network. We analyse its relationship with the quickest path problem (QPP), showing that this is equivalent to the weighted problem associated to the SMBPP, which is also solved by a modification of an algorithm proposed for the QPP. A computational study is presented which shows the superiority of the algorithm proposed in this paper over other existing algorithms to generate the entire set E of efficient paths of the SMBPP.