Nonadditive Shortest Paths

008137621999PDFResearch PaperAutomobile navigation systemsAlgorithmsShortest path algorithmsCostsHeuristic methodsLinear programmingTrip generationPathUnited StatesNew Jersey TIDE CenterGabriel, Steven A.Bernstein, DavidNew Jersey Institute of TechnologyNew Jersey TIDE CenterUS Transportation CollectionTo find the shortest path in a network is often a problem in transportation applications. This paper considers a shortest path problem in which the costs are a particular nonlinear, nonseparable function. An algorithm of feasible-directions variety in which subproblems are simple minimum cost flow linear programs is presented. To ensure that a path which produces a lower function value is found, the algorithm contains a heuristic component.73