Workplace :
| office: | B116 |
|---|---|
| tel: | (+33)47340 5368 |
Authors:
 |
Maxime Chassaing |
||
 |
Christophe Duhamel |
 |
Philippe Lacomme |
Results
Legend
Instances : instance’s name
m : numbers of vehicle
n : numbers of clients
BKS : value of best known solution obtained in the article : Parragh 2003,[4]
Optimal : value of optimal solution obtained in the article : [référence]
Avg : average value obtained with 5 runs
: gap, 100 * (Avg – Optimal) / Optimal
Best : value of best solution from 5 runs
: gap, 100 * (Best – Optimal) / Optimal
: CPU time in minutes to obtain the best find solution (average from 5 runs)
: total CPU time in minutes (average from 5 runs)
Computer used: Core™ i7-3770 CPU with 3.40Ghz (2529 Mflop by Jack Dongarra's works)
Results
Appendix 1: instances of (Cordeau and Laporte, 2003)
Download the best solution obtained with 5 runs
| Instances | m | n | BKS | Best | solution Cordeau's format* | solution Chassaing's format* | solution simplest format* |
|---|---|---|---|---|---|---|---|
| R1a | 3 | 24 | 190.02 | 190.02 | download | download | download |
| R2a | 5 | 48 | 301.34 | 301.34 | download | download | download |
| R3a | 7 | 72 | 532 | 532.42 | download | download | download |
| R4a | 9 | 96 | 570.25 | 570.55 | download | download | download |
| R5a | 11 | 120 | 626.93 | 630.81 | download | download | download |
| R6a | 13 | 144 | 785.26 | 792.81 | download | download | download |
| R7a | 4 | 36 | 291.71 | 291.71 | download | download | download |
| R8a | 6 | 72 | 487.84 | 491.58 | download | download | download |
| R9a | 8 | 108 | 658.31 | 672.88 | download | download | download |
| R10a | 10 | 144 | 851.82 | 857.34 | download | download | download |
| R1b | 3 | 24 | 164.46 | 164.46 | download | download | download |
| R2b | 5 | 48 | 295.66 | 295.66 | download | download | download |
| R3b | 7 | 72 | 484.83 | 489.02 | download | download | download |
| R4b | 9 | 96 | 529.33 | 531.06 | download | download | download |
| R5b | 11 | 120 | 577.29 | 578.45 | download | download | download |
| R6b | 13 | 144 | 730.67 | 731.27 | download | download | download |
| R7b | 4 | 36 | 248.21 | 248.21 | download | download | download |
| R8b | 6 | 72 | 458.73 | 461.22 | download | download | download |
| R9b | 8 | 108 | 593.49 | 595.39 | download | download | download |
| R10b | 10 | 144 | 785.68 | 796.57 | download | download | download |
| All | All | All | All |
Appendix 2: instances of (Ropke and Cordeau, 2007): Part A
Download the best solution obtained with 5 runs
Appendix 3: instances of (Ropke and Cordeau, 2007): Part B
Download the best solution obtained with 5 runs
Explanations : formats solutions
Chassaing's solution format
Cordeau's solution format
The simplest solution format
References
[1]. J-F. Cordeau, G. Laporte. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B Methodological, 37 (2003), pp. 579–94.
[2]. S. Ropke, J-F. Cordeau, G. Laporte. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks, 49(4) (2007), pp. 258–272.
[3]. S.N. Parragh, K.F. Doerner, R.F. Hartl. Variable neighborhood search for the dial-a-ride problem. Computers & Operations Research, 37 (2010), pp. 1129–1138
[4]. S.N. Parragh, V. Schmid. Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research, 40 (2013), pp. 490–497
[5]. R. Masson, F. Lehuédé, O. Péton. The Dial-A-Ride Problem with Transfers. Computers & Operations Research 41 (2014), pp. 12-23.
[6]. K. Braekers, A. Caris, G.K. Janssens. Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B 67 (2014), pp. 166-186.
