Contributed by Luca Gobbato, Guido Perboli and Francesca Maggioni
The test problem suite consists of data and computational results for 5 two-stage stochastic mixed-integer programs arising in City Logistics contexts. More precisely, given a graph characterized by a set on nodes connected by arcs, in the mpTSPs we consider that, for every pair of nodes, we have multiple paths between the two nodes. Each path is characterized by a random travel time which can be decomposed in the sum of a deterministic term and a stochastic term, which represents the travel time oscillation due to the path congestion.
The problem formulation is described in [1, 2], while the instance generation is reported in [2]. The problems have pure binary first-stage and second-stage variables. All possible discrete values that the random variable can assume, are represented by a set of 100 scenarios and are assumed to be exogenous to the problem. The data files are contained in the zipped folder MPTSPs.zip. The format is described in Format_Instance.txt contained in the data folder.
The following table presents the instance set. The instances are named MPTSPs_Dd_n, where d is the number of potential server locations, n is the nodes distribution strategies [2] and n is the potential number of customers.
Table 1: Instance set
| Name | Node distribution | Customers | Scenarios |
|---|---|---|---|
| MPTSPs_D0_50 | City center | 54 | 100 |
| MPTSPs_D1_50 | Suburban area | 55 | 100 |
| MPTSPs_D2_50 | City center and Suburban area (3:1) | 56 | 100 |
| MPTSPs_D3_50 | City center and Suburban area (1:1) | 56 | 100 |
| MPTSPs_D1_100 | Suburban area | 105 | 100 |
Computational results are given in Table 2. The CPLEX 12.5 was used for solving the stochastic problems to optimality. For each instance we solved:
Table 2: Computational Results
| Name | RP | EEV | GLUSS 25% | GLUSS 50% | GLUSS 75% | GLUSS 100% |
|---|---|---|---|---|---|---|
| MPTSPs_D0_50 | 23544.2 | 24537.3 | 23544.2 | 24064.1 | 24278.4 | 24537.3 |
| MPTSPs_D1_50 | 15250.7 | 15964.3 | 15250.7 | 15250.7 | 15821.8 | 15964.3 |
| MPTSPs_D2_50 | 16509.8 | 16836.3 | 16509.8 | 16509.8 | 16631.5 | 16836.3 |
| MPTSPs_D3_50 | 11898.7 | 12173.4 | 11898.7 | 11972.5 | 12090.1 | 12173.4 |
| MPTSPs_D1_100 | 22094 | 22855.6 | 22094 | 22094 | 22119.7 | 22855.6 |
The complete solutions are included in the zipped folder containing data files.
[1] Roberto Tadei, Guido Perboli, Francesca Perfetti, The multi-path Traveling Salesman Problem with stochastic travel costs, EURO Journal on Transportation and Logistics, 2014
[2] Guido Perboli, Luca Gobbato, Francesca Maggioni, A Progressive Hedging method for the multi-path Traveling Salesman Problem with stochastic travel times, submitted to Journal of Management Mathematics, 2014
[3] Francesca Maggioni, Stein W. Wallace, Analyzing the quality of the expected value solution in stochastic programming, Annals of Operations Research, 2010
[3] Francesca Maggioni, Guido Perboli, Generalized skeleton solution in two-stage stochastic programming, in preparation