The non-additive shortest path (NASP) problem asks for
finding an optimal path that minimizes a certain multi-attribute nonlinear
cost function. In this paper, we consider the case of a non-linear
convex and non-decreasing function on two attributes.We present an efficient
polynomial algorithm for solving a Lagrangian relaxation of NASP.
We also present an exact algorithm that is based on new heuristics we
introduce here, and conduct a comparative experimental study with synthetic
and real-world data that demonstrates the quality of our approach.