English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we propose an adapted version of the progressive hedging algorithm (PHA) (Rockafellar and Wets, 1991; Lokketangen and Woodruff, 1996; Watson and Woodruff, 2011) for the two-stage stochastic traveling salesman problem (STSP) introduced in (Adasme et al., 2016). Thus, we compute feasible solutions for small, medium and large size instances of the problem. Additionally, we compare the PHA method with the sample average approximation (SAA) method for all the randomly generated instances and compute statistical lower and upper bounds. For this purpose, we use the compact polynomial formulation extended from (Miller et al., 1960) in (Adasme et al., 2016) as it is the one that allows us to solve large size instances of the problem in short CPU time with CPLEX. Our preliminary numerical results show that the results obtained with the PHA algorithm are tight when compared to the optimal solutions of small and medium size instances. Moreover, we obtain significantly better feasible solutions than CPLEX for large size instances with up to 100 nodes and 10 scenarios in significantly low CPU time. Finally, the bounds obtained with SAA method provide an average reference interval for the stochastic problem.

Progressive Hedging and Sample Average Approximation for the Two-stage Stochastic Traveling Salesman Problem