An Algorithm for Non-additive Shortest Path Problem

This paper presents a solution methodology for general formulation of the shortest path problem with non-additive continuous convex travel cost functions. The proposed solution methodology is based on outer approximation (OA) algorithm which solves the original problem by iterating between the solution of two optimization problems known as subproblem and a master problem. The authors show that subproblem solution in OA framework for non-additive shortest path problem can be expressed through closed form equations and thus the OA framework can be reduced to solving only the mixed integer linear program of the master problem. Numerical experiments conducted on varying size networks based on different combinations of nonlinear cost functions show the ability and efficiency of the proposed framework in providing the exact global solution.

• Supplemental Notes:
  • This paper was sponsored by TRB committee ADB30(9) Paper Reveiw Group #5. Alternate title: New Algorithm for Nonadditive Shortest-Path Problem.
• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Shahabi, Mehrdad
  • Unnikrishnan, Avinash
  • Boyles, Stephen D
• Conference:
  • Transportation Research Board 93rd Annual Meeting
  • Location: Washington DC
  • Date: 2014-1-12 to 2014-1-16
• Date: 2014

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; References; Tables;
• Pagination: 19p
• Monograph Title: TRB 93rd Annual Meeting Compendium of Papers

Subject/Index Terms

• TRT Terms: Mixed integer programming; Routing; Shortest path algorithms
• Uncontrolled Terms: Closed form equations; Cost functions; Outer approximation algorithms
• Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01519060
• Record Type: Publication
• Report/Paper Numbers: 14-5178
• Files: TRIS, TRB, ATRI
• Created Date: Mar 23 2014 5:49PM