Improving Network Durability using Approximate Dynamic Programming

Download the paper, in pdf.

Authors:

Erik Hammel
RankMiner Inc.

John E. Mitchell
(email)
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A.

Thomas C. Sharkey
(email)
Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A.

William A. Wallace
(email)
Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, Troy, New York 12180-3590, U.S.A.

April 2016

The material in this paper is based upon work supported by the U.S. Department of Homeland Security under Grant Award Number, 2008-ST-061-ND0001-07. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security. The work of Thomas C. Sharkey was supported by the U.S. National Science Foundation under CMMI-1254258.

Abstract:

Our goal is to optimize the efficacy of reinforcing an existing flow network to prevent unmet demand from imminent disruptions. Estimates for the probabilities of failures for edges in the network are refined as the disaster draws nearer, and we are asked to find edges which will best provide durability to the network post-event. The problem is formulated as an approximate dynamic program (ADP). We derive several innovative adaptations from reinforcement learning concepts. We compare the performance of the policy resulting from the ADP against traditional two-stage stochastic programs with recourse utilizing a sample average approximation model. We provide empirical evidence which corroborates with basic theorems of convergence for more simplistic forms of the reinforcement learning process. The material presented here is developed in the context of preparing urban infrastructures against damages caused by disasters, however it is applicable to any flow network.

Keywords: disaster mitigation, infrastructure restoration, approximate dynamic programming

Download the paper, in pdf | Return to my list of papers | John E. Mitchell