THE SHORTEST-PATH PROBLEM WITH 2 OBJECTIVE FUNCTIONS

The author presents methods to find the shortest path in a network where each path is associated with two objectives. He describes how to obtain the nondominated paths and the extreme nondominated paths, and compares the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, the author describes how to find the optimalextreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case he suggests a branch and bound method to solve the problem.