کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1023427 1483032 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An outer approximation algorithm for the robust shortest path problem
موضوعات مرتبط
علوم انسانی و اجتماعی مدیریت، کسب و کار و حسابداری کسب و کار و مدیریت بین المللی
پیش نمایش صفحه اول مقاله
An outer approximation algorithm for the robust shortest path problem
چکیده انگلیسی


• We model the weighted mean standard deviation robust shortest path problem.
• A conic integer programming formulation is provided.
• Problem is solved using the outer approximation algorithm.
• The algorithm delivers the optimal solution for four real world transportation networks.
• The algorithm outperforms standard GAMS/CPLEX conic quadratic programming solver.

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. We 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, we 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Part E: Logistics and Transportation Review - Volume 58, November 2013, Pages 52–66
نویسندگان
, , ,