ROADEF'2009 qualification results
The following table presents the qualified candidates and provides the ranking using the average normalized score, computed as follows. Let z(M,I)denote the objective function value obtained by Method M on Instance I. Let zb(I) and zw(I) denote the best and worst objective function values found on instance I, respectively. The normalized score obtained by Method M on Instance I is given by (zw(I)-z(M,I))/(zw(I)-zb(I)). Note that, besides the quality of the obtained results, the jury took also the method originality into consideration for qualification decision.
| Team | Category | Rank | Average score |
|---|---|---|---|
| Bisaillon, Cordeau, Laporte, Pasin | Senior | 1 | 98,53 |
| Hanafi, Wilbaut, Mansi | Senior | 2 | 94,87 |
| Acuna-Agost, Michelon, Feillet, Gueye | Senior | 3 | 85,52 |
| Darlay, Kronek, Schrenk, Zaourar | Junior | 4 | 82,12 |
| Jozefowiez, Mancel, Mora-Camino | Senior | 5 | 75,29 |
| Eggermont, Firat, Hurkens, Modelski | Junior | 6 | 61,80 |
| Demassey, Jussien, Lorca, Menana-Quillet, Richaud | Senior | 7 | 53,58 |
| Dickson, Smith, Li | Junior | 8 | 47,82 |
| Estellon, Gardi, Nouioua | Senior | 9 | 47,05 |
| Eggenberg, Salani | Junior | 10 | 2,93 |
| Peekstok, Kuipers | Senior | 11 | 5 infeasible solutions |
The following table presents the detailed results obtained by the qualified candidates on the base A instances. For each instance, the obtained objective function value is provided. The best one is displayed in bold. INF indicates solution infeasibility.
| Team | A01 | A02 | A03 | A04 | A05 | A06 | A07 | A08 | A09 | A10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Bisaillon, Cordeau, Laporte, Pasin | 29891,75 | 116431,70 | 202358,10 | 139747,10 | 3717376,35 | 44305,05 | 202247,75 | 659572,00 | 215482,35 | 7210166,90 |
| Hanafi, Wilbaut, Mansi | 28155,60 | 126684,70 | 131694,60 | 523678,80 | 8092977,55 | 71355,25 | 245696,70 | 329521,85 | 1096303,85 | 17166321,75 |
| Acuna-Agost, Michelon, Feillet, Gueye | 44938,40 | 374763,75 | 672790,35 | 108081,90 | 16134976,15 | 86283,00 | 452752,85 | 1065896,20 | 187144,40 | 20892659,25 |
| Darlay, Kronek, Schrenk, Zaourar | 317525,05 | 765351,40 | 438681,05 | 789399,05 | 8012044,00 | 269462,00 | 546110,00 | 799238,00 | 938095,80 | 15098771,00 |
| Jozefowiez, Mancel, Mora-Camino | 150095,70 | 377992,90 | 473992,15 | 2520586,00 | 13640667,40 | 111540,50 | 623236,80 | 997137,80 | 6163295,90 | 23840247,85 |
| Eggermont, Firat, Hurkens, Modelski | 987236,15 | 770971,35 | 1588231,40 | 1573294,50 | 23990055,70 | 1032790,50 | 834044,65 | 1559644,90 | 1478106,60 | 29639201,15 |
| Demassey, Jussien, Lorca, Menana-Quillet, Richaud | 158485,35 | 540895,65 | 567124,65 | 4842154,70 | 41037750,05 | 125286,85 | 634489,95 | 1320747,05 | 8750676,50 | 58046489,60 |
| Dickson, Smith, Li | 1345066,80 | 986506,60 | 1794442,25 | 2406499,25 | 36011581,05 | 1389306,45 | 883862,40 | 1949700,65 | 2529246,70 | 44798632,70 |
| Estellon, Gardi, Nouioua | 297019,05 | 928384,65 | 2180182,40 | 1733066,60 | 42259652,80 | 247315,35 | 1031022,70 | 2586730,75 | 2205772,30 | 58333715,85 |
| Eggenberg, Salani | 3860511,50 | 721588,60 | 2395934,10 | 6161533,20 | 43978009,85 | 4980974,40 | 1545630,05 | 5048257,00 | 10509766,30 | 69097236,55 |
| Peekstok, Kuipers | 23789,05 | 83515,00 | 135225,60 | INF | INF | 3700144,95 | 794892,90 | INF | INF | INF |
Brief overview of proposed methods
The methods proposed by each candidate will not be revealed before the challenge final stage. Briefly, from the abstracts sent by the candidates, it appears that all the proposed methods are heuristic methods, which solve the problem by decomposing it into several parts. However, a large variety of approaches is observed. Among the elementary tools shared by most methods, optimal flow and path algorithms are generally used, which is not surprising. The general proposed solving scheme falls into different categories: pure greedy algorithms, descent methods with restart, simulated annealing, hybrid integer programming and local search methods, column generation. The programs were coded in Delphi, C, C++, Java with or without using data structure libraries and Linear Programming solvers.