Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios

Zhouchun Huang (), Qipeng P. Zheng (), Eduardo L. Pasiliao and Daniel Simmons
Additional contact information
Zhouchun Huang: University of Central Florida
Qipeng P. Zheng: University of Central Florida
Eduardo L. Pasiliao: Air Force Research Laboratory
Daniel Simmons: West Virginia University

Annals of Operations Research, 2017, vol. 249, issue 1, No 9, 162 pages

Abstract: Abstract Network routing problems are often modeled with the assumption that the network structure is deterministic, though they are often subject to uncertainty in many real-life scenarios. In this paper, we study the traveling salesman and the shortest path problems with uncertain topologies modeled by arc failures. We present the formulations that incorporate chance constraints to ensure reliability of the selected route considering all arc failure scenarios. Due to the computational complexity and large scales of these stochastic network optimization problems, we consider two cutting plane methods and a Benders decomposition algorithm to respectively solve them. We also consider to solve the reformulations of the problems obtained by taking the logarithm transformation of the chance constraints. Numerical experiments are performed to obtain results for comparisons among these proposed methods.

Keywords: Reliable routing; Traveling salesman problem; Shortest path problem; Arc failures; Benders decomposition; Compact formulation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-016-2244-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:249:y:2017:i:1:d:10.1007_s10479-016-2244-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-016-2244-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().