Bicriterion shortest path problem with a general nonadditive cost

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. The authors 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, the authors 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.

• Record URL:
  • https://doi.org/10.1016/j.trb.2013.05.008
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0191261513000908
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission by Elsevier.
• Authors:
  • Chen, Peng
  • Nie, Yu (Marco)
• Publication Date: 2013-11

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 419-435
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 57
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Numerical analysis; Optimization; Shortest path algorithms; Traffic assignment
• Subject Areas: Highways; Planning and Forecasting; I71: Traffic Theory;

Filing Info

• Accession Number: 01504968
• Record Type: Publication
• Files: TRIS
• Created Date: Jan 27 2014 10:45AM