Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design
We present a method for bundling scenarios in a progressive hedging heuristic (PHH) applied to stochastic service network design, where the uncertain demand is represented by a finite number of scenarios. Given the number of scenario bundles, we first calculate a vector of probabilities for every sc...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2020
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/64316/ |
| _version_ | 1848800115443105792 |
|---|---|
| author | Jiang, Xiaoping Bai, Ruibin Wallace, Stein W. Kendall, Graham Landa-Silva, Dario |
| author_facet | Jiang, Xiaoping Bai, Ruibin Wallace, Stein W. Kendall, Graham Landa-Silva, Dario |
| author_sort | Jiang, Xiaoping |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | We present a method for bundling scenarios in a progressive hedging heuristic (PHH) applied to stochastic service network design, where the uncertain demand is represented by a finite number of scenarios. Given the number of scenario bundles, we first calculate a vector of probabilities for every scenario, which measures the association strength of a scenario to each bundle center. This membership score calculation is based on existing soft clustering algorithms such as Fuzzy C-Means (FCM) and Gaussian Mixture Models (GMM). After obtaining the probabilistic membership scores, we propose a strategy to determine the scenario-to-bundle assignment. By contrast, almost all existing scenario bundling methods such as K-Means (KM) assume before the scenario-to-bundle assignment that a scenario belongs to exactly one bundle, which is equivalent to requiring that the membership scores are Boolean values. The probabilistic membership scores bring many advantages over Boolean ones, such as the flexibility to create various degrees of overlap between scenario bundles and the capability to accommodate scenario bundles with different covariance structures. We empirically study the impacts of different degrees of overlap and covariance structures on PHH performance by comparing PHH based on FCM/GMM with that based on KM and the cover method, which represents the state-of-the-art scenario bundling algorithm for stochastic network design. The solution quality is measured against the lower bound provided by CPLEX. The experimental results show that, GMM-based PHH yields the best performance among all methods considered, achieving nearly equivalent solution quality in a fraction of the run-time of the other methods. |
| first_indexed | 2025-11-14T20:46:26Z |
| format | Article |
| id | nottingham-64316 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:46:26Z |
| publishDate | 2020 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-643162021-01-22T05:56:18Z https://eprints.nottingham.ac.uk/64316/ Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design Jiang, Xiaoping Bai, Ruibin Wallace, Stein W. Kendall, Graham Landa-Silva, Dario We present a method for bundling scenarios in a progressive hedging heuristic (PHH) applied to stochastic service network design, where the uncertain demand is represented by a finite number of scenarios. Given the number of scenario bundles, we first calculate a vector of probabilities for every scenario, which measures the association strength of a scenario to each bundle center. This membership score calculation is based on existing soft clustering algorithms such as Fuzzy C-Means (FCM) and Gaussian Mixture Models (GMM). After obtaining the probabilistic membership scores, we propose a strategy to determine the scenario-to-bundle assignment. By contrast, almost all existing scenario bundling methods such as K-Means (KM) assume before the scenario-to-bundle assignment that a scenario belongs to exactly one bundle, which is equivalent to requiring that the membership scores are Boolean values. The probabilistic membership scores bring many advantages over Boolean ones, such as the flexibility to create various degrees of overlap between scenario bundles and the capability to accommodate scenario bundles with different covariance structures. We empirically study the impacts of different degrees of overlap and covariance structures on PHH performance by comparing PHH based on FCM/GMM with that based on KM and the cover method, which represents the state-of-the-art scenario bundling algorithm for stochastic network design. The solution quality is measured against the lower bound provided by CPLEX. The experimental results show that, GMM-based PHH yields the best performance among all methods considered, achieving nearly equivalent solution quality in a fraction of the run-time of the other methods. Elsevier 2020-12-17 Article PeerReviewed application/pdf en cc_by https://eprints.nottingham.ac.uk/64316/1/011510252858MergePDF.pdf Jiang, Xiaoping, Bai, Ruibin, Wallace, Stein W., Kendall, Graham and Landa-Silva, Dario (2020) Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design. Computers & Operations Research, 128 . p. 105182. ISSN 03050548 Network design； Stochastic mixed-integer programs； Progressive hedging； Scenario bundling http://dx.doi.org/10.1016/j.cor.2020.105182 doi:10.1016/j.cor.2020.105182 doi:10.1016/j.cor.2020.105182 |
| spellingShingle | Network design； Stochastic mixed-integer programs； Progressive hedging； Scenario bundling Jiang, Xiaoping Bai, Ruibin Wallace, Stein W. Kendall, Graham Landa-Silva, Dario Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title | Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title_full | Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title_fullStr | Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title_full_unstemmed | Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title_short | Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| title_sort | soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design |
| topic | Network design； Stochastic mixed-integer programs； Progressive hedging； Scenario bundling |
| url | https://eprints.nottingham.ac.uk/64316/ https://eprints.nottingham.ac.uk/64316/ https://eprints.nottingham.ac.uk/64316/ |