In transportation problems and in many other planning problems, there are important sources of uncertainty that must be addressed to find effective and efficient solutions. A common approach for solving these dynamic and stochastic problems is the Multiple Scenario Approach (MSA), that has been proved effective for transportation problems, but it does not provide flexibility for finding solutions that take into account all the uncertainty of the problem. Alternative approaches for solving problems with finite number of scenarios are the Progressive Hedging Algorithm (PHA) and the Subgradient Algorithm (SA). The similarity between PHA and SA are many, however, there are some differences that lead them to have very different theoretical guarantees and performance. We present a new exact algorithm, the Dynamic Progressive Hedging Algorithm, for which we provide theoretical guarantees that helps to understand both this algorithm and the PHA from a new point of view. In addition, we propose a DPHA-based Heuristic (DPHH), and show optimality guarantees for the solution obtained. Then, we present the MSA and the SA with consensus functions. Our analysis allows us to highlight the advantages and disadvantages of the DPHA, the SA and the MSA, which gives guidance for future research in choosing the proper method for the problem in hand. In a computational study, we study the Stochastic Server Location Problem (SSLP) and the Two-Stage Stochastic Assignment and Team-Orienteering Problem (TSSATOP), and we show the empirical performance of the proposed Scenario Consensus Algorithms (SCA).
Article
View Scenario Consensus Algorithms for Solving Stochastic and Dynamic Problems