A simulation-optimization approach for the stochastic discrete cost multicommodity flow problem. Issue 3 (3rd March 2020)

• Record Type: Journal Article
• Authors: Mejri, Imen; Layeb, Safa Bhar; Haouari, Mohamed; Mansour, Farah Zeghal
• Is Part Of: Engineering optimization. Volume 52:Issue 3(2020)
• Page Start: 507
• Page End: 526
• Publication Date: 2020-03-03
• Subjects: Networks -- stochastic programming -- simulation-optimization approach -- Monte Carlo simulation -- sample average approximation; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2019.1603299
• Languages: English
• ISSNs: 0305-215X

Abstract

ABSTRACT: This article addresses a variant of the Discrete Cost Multicommodity Flow (DCMF) problem with random demands, where a penalty is incurred for each unrouted demand. The problem requires finding a network topology that minimizes the sum of the fixed installation facility costs and the expected penalties of unmet multicommodity demands. A two-stage stochastic programming with recourse model is proposed. A simulation-optimization approach is developed to solve this challenging problem approximately. To be precise, the first-stage problem requires solving a specific multi-facility network design problem using an exact enhanced cut-generation procedure coupled with a column generation algorithm. The second-stage problem aims at computing the expected penalty using a Monte Carlo simulation procedure together with a hedging strategy. To assess the empirical performance of the proposed approach, a Sample Average Approximation (SAA) procedure is developed to derive valid lower bounds. Results of extensive computational experiments attest to the efficacy of the proposed approach.