An outer approximation algorithm for the robust shortest path problem

This paper describes a new algorithm for the stochastic shortest path problem where path costs are a weighted sum of expected cost and cost standard deviation. The authors allow correlation between link costs, subject to a regularity condition excluding unbounded solutions. The chief complication in this variant is that path costs are not an additive sum of link costs. In this paper, the authors reformulate this problem as a conic quadratic program, and develop an outer-approximation algorithm based on this formulation. Numerical experiments show that the outer-approximation algorithm significantly outperforms standard integer programming algorithms implemented in solvers.

• Record URL:
  https://doi.org/10.1016/j.tre.2013.07.002
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S1366554513001257
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13665545
• Supplemental Notes:
  • Abstract reprinted with permission from Elsevier.
• Authors:
  • Shahabi, Mehrdad
  • Unnikrishnan, Avinash
  • Boyles, Stephen D
• Publication Date: 2013-11

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 52-66
• Serial:
  • Transportation Research Part E: Logistics and Transportation Review
  • Volume: 58
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 1366-5545
  • Serial URL: http://www.sciencedirect.com/science/journal/13665545

Subject/Index Terms

• TRT Terms: Approximation (Mathematics); Costs; Integer programming; Routing; Shortest path algorithms; Standard deviation
• Subject Areas: Planning and Forecasting; Transportation (General); I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01494733
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 30 2013 10:37AM