Routing with nonlinear multiattribute cost functions

摘要

The paper first points out the connection between the problem of finding a set of Pareto-optimal paths in the presence of multiple criteria and the problem of finding the optimal path in the presence of a single multiattribute criterion. A survey of literature indicates that the former problem has received much attention and several exact (but nonpolynomial) and approximate algorithms are available for finding all and nearly all Pareto-optimal paths, respectively. The latter problem of finding the optimal path that minimizes a nonlinear cost function of multiple attributes has received less attention. The paper examines the properties of the optimal path when the cost function is monotonic and concave in the attributes, especially how it relates to the set of “efficient” paths within the nondominated set. When the cost function in convex in two attributes, a line-search algorithm is developed that finds a good, if not optimal, path without using any assumptions or information on the derivatives of the cost function.