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,808092977,55 71355,25 245696,70 329521,85 1096303,85 17166321,75
Acuna-Agost, Michelon, Feillet, Gueye 44938,40 374763,75 672790,35 108081,9016134976,15 86283,00 452752,85 1065896,20 187144,40 20892659,25
Darlay, Kronek, Schrenk, Zaourar 317525,05 765351,40 438681,05 789399,058012044,00 269462,00 546110,00 799238,00 938095,80 15098771,00
Jozefowiez, Mancel, Mora-Camino 150095,70 377992,90 473992,15 2520586,0013640667,40 111540,50 623236,80 997137,80 6163295,90 23840247,85
Eggermont, Firat, Hurkens, Modelski 987236,15 770971,35 1588231,40 1573294,5023990055,70 1032790,50 834044,65 1559644,90 1478106,60 29639201,15
Demassey, Jussien, Lorca, Menana-Quillet, Richaud 158485,35 540895,65 567124,65 4842154,7041037750,05 125286,85 634489,95 1320747,05 8750676,50 58046489,60
Dickson, Smith, Li 1345066,80 986506,60 1794442,25 2406499,2536011581,05 1389306,45 883862,40 1949700,65 2529246,70 44798632,70
Estellon, Gardi, Nouioua 297019,05 928384,65 2180182,40 1733066,6042259652,80 247315,35 1031022,70 2586730,75 2205772,30 58333715,85
Eggenberg, Salani 3860511,50 721588,60 2395934,10 6161533,2043978009,85 4980974,40 1545630,05 5048257,00 10509766,30 69097236,55
Peekstok, Kuipers 23789,05 83515,00 135225,60 INFINF 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.