Bicriterion shortest path problem with a general nonadditive cost

Peng Chen, Yu Nie*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

A bicriterion shortest path problem with a general nonadditive cost seeks to optimize a combination of two path costs, one of which is evaluated by a nonlinear function. This paper first identifies a number of emerging transportation applications for which such a shortest path problem might be considered a core subproblem. We propose to first approximate the general nonlinear cost function with a piecewise linear counterpart, and then solve each linear subproblem sequentially. A specialized algorithm is developed to solve the subproblems, which makes use of the efficient path set (or the convex hull) to update upper and lower bounds of the original problem. Conditions under which the solution to a subproblem must belong to the efficient path set are specified. Accordingly, we show that the optimal path must be efficient if the nonlinear cost function is concave. If the optimal path to a subproblem is not efficient, partial path enumeration, implemented using a simple K-shortest path ranking procedure, is conducted to close the gap. The proposed algorithm includes strategies aiming to expedite path enumeration by using upper bounds derived from the efficient path set. Numerical experiments are conducted to demonstrate correctness and effectiveness of the proposed algorithm.

Original languageEnglish (US)
Pages (from-to)419-435
Number of pages17
JournalTransportation Research Part B: Methodological
Volume57
DOIs
StatePublished - Jan 1 2013

Keywords

  • Bicriterion shortest path
  • Efficient path set
  • K-shortest path
  • Nonadditive cost
  • Path enumeration

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint

Dive into the research topics of 'Bicriterion shortest path problem with a general nonadditive cost'. Together they form a unique fingerprint.

Cite this