Loadingā¦
Robust Optimization Strategy for the Shortest Path Problem under Uncertain Link Travel Cost Distribution
This article employs a robust optimization approach for the shortest path problem where travel cost is uncertain and exact information on the distribution function is unavailable. We show that under such conditions the robust shortest path problem can be formulated as a binary nonlinear integer prog...
Saved in:
Published in: | Computer-aided civil and infrastructure engineering 2015-06, Vol.30 (6), p.433-448 |
---|---|
Main Authors: | , , |
Format: | Article |
Language: | English |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | This article employs a robust optimization approach for the shortest path problem where travel cost is uncertain and exact information on the distribution function is unavailable. We show that under such conditions the robust shortest path problem can be formulated as a binary nonlinear integer program, which can then be reformulated as a mixed integer conic quadratic program. Based on this reformulation, we present an outer approximation algorithm as a solution algorithm which is shown to be highly efficient for this class of programs. Numerical experiments conducted on small to large networks further compare the robust optimizationābased strategy to the classical deterministic shortest path in terms of the uncertainty in the network. |
---|---|
ISSN: | 1093-9687 1467-8667 |
DOI: | 10.1111/mice.12103 |