Exact Algorithms On Reliable Routing Problems Under Uncertain Topology Using Aggregation Techniques For Exponentially Many Scenarios

Keywords

Arc failures; Benders decomposition; Compact formulation; Reliable routing; Shortest path problem; Traveling salesman problem

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.

Publication Date

2-1-2017

Publication Title

Annals of Operations Research

Volume

249

Issue

1-2

Number of Pages

141-162

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10479-016-2244-y

Socpus ID

84973161328 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84973161328

This document is currently not available here.

Share

COinS