Greedy subtour methodology run times (symmetric instances)
| Milliseconds | Directional | Non-directional | |||||
|---|---|---|---|---|---|---|---|
| Instance | Stat | EL | MF | GT | EL | MF | GT |
| bays29 | Mean | 23.2 | 52.0 | 22.4 | 29.7 | 44.2 | 24.4 |
| Std dev. | 0.7 | 0.8 | 1.0 | 0.9 | 0.8 | 0.7 | |
| gr48 | Mean | 25.4 | 56.1 | 25.0 | 30.5 | 46.8 | 25.8 |
| Std dev. | 0.8 | 0.8 | 0.8 | 0.7 | 1.1 | 0.8 | |
| eil51 | Mean | 26.7 | 53.2 | 24.4 | 32.3 | 50.4 | 28.1 |
| Std dev. | 1.5 | 0.8 | 0.8 | 0.7 | 1.3 | 1.1 | |
| berlin52 | Mean | 26.6 | 53.1 | 24.1 | 31.4 | 47.9 | 26.3 |
| Std dev. | 1.2 | 0.8 | 0.8 | 0.7 | 1.4 | 0.8 | |
| pr76 | Mean | 30.8 | 56.9 | 28.5 | 32.8 | 46.9 | 29.9 |
| Std dev. | 1.3 | 0.8 | 1.3 | 0.6 | 0.6 | 1.3 | |
| kroa100 | Mean | 36.8 | 60.8 | 34.5 | 36.5 | 50.4 | 30.8 |
| Std dev. | 1.6 | 1.2 | 0.6 | 1.1 | 1.3 | 0.8 | |
| gr120 | Mean | 41.9 | 66.5 | 43.1 | 40.5 | 52.2 | 34.9 |
| Std dev. | 0.9 | 1.9 | 1.9 | 1.4 | 1.0 | 1.1 | |
| ch130 | Mean | 48.9 | 70.4 | 43.7 | 43.3 | 52.9 | 35.7 |
| Std dev. | 1.5 | 1.2 | 1.8 | 1.7 | 1.2 | 0.8 | |
| rat195 | Mean | 76.8 | 98.6 | 73.6 | 54.5 | 65.0 | 50.3 |
| Std dev. | 1.6 | 2.2 | 2.7 | 1.1 | 0.7 | 1.2 | |
| ts225 | Mean | 97.8 | 113.9 | 95.4 | 61.8 | 68.1 | 57.3 |
| Std dev. | 2.2 | 3.1 | 3.5 | 1.7 | 0.8 | 2.9 | |
| pma343 | Mean | 193.7 | 193.9 | 177.0 | 121.2 | 111.9 | 107.7 |
| Std dev. | 3.4 | 3.4 | 3.5 | 3.0 | 2.2 | 4.5 | |
| pcb442 | Mean | 363.7 | 312.8 | 317.2 | 177.0 | 166.1 | 180.5 |
| Std dev. | 4.4 | 4.4 | 4.1 | 2.3 | 2.1 | 4.7 | |
| dsj1000 | Mean | 1.667(s) | 1.341(s) | 1.440(s) | 906.9 | 660.1 | 750.2 |
| Std dev. | 3.7 | 4.6 | 3.5 | 7.8 | 5.6 | 8.1 | |
| pr1002 | Mean | 1.595(s) | 1.308(s) | 1.374(s) | 863.3 | 637.3 | 761.8 |
| Std dev. | 5.4 | 5.0 | 4.7 | 3.8 | 4.0 | 17.1 | |
| pr2392 | Mean | 9.268(s) | 7.214(s) | 7.611(s) | 4.900(s) | 3.405(s) | 3.796(s) |
| Std dev. | 20.4 | 24.2 | 22.9 | 15.6 | 9.8 | 20.6 | |
| fnl4461 | Mean | 27.416(s) | 23.096(s) | 24.198(s) | 16.752(s) | 11.268(s) | 12.286(s) |
| Std dev. | 42.3 | 48.2 | 53.1 | 49.0 | 40.9 | 39.6 | |
| rl5934 | Mean | 72.697(s) | 51.579(s) | 54.703(s) | 41.937(s) | 22.301(s) | 25.171(s) |
| Std dev. | 0.042(s) | 5.789(s) | 5.368(s) | 4.113(s) | 0.742(s) | 2.616(s) | |
| Milliseconds | Directional | Non-directional | |||||
|---|---|---|---|---|---|---|---|
| Instance | Stat | EL | MF | GT | EL | MF | GT |
| bays29 | Mean | 23.2 | 52.0 | 22.4 | 29.7 | 44.2 | 24.4 |
| Std dev. | 0.7 | 0.8 | 1.0 | 0.9 | 0.8 | 0.7 | |
| gr48 | Mean | 25.4 | 56.1 | 25.0 | 30.5 | 46.8 | 25.8 |
| Std dev. | 0.8 | 0.8 | 0.8 | 0.7 | 1.1 | 0.8 | |
| eil51 | Mean | 26.7 | 53.2 | 24.4 | 32.3 | 50.4 | 28.1 |
| Std dev. | 1.5 | 0.8 | 0.8 | 0.7 | 1.3 | 1.1 | |
| berlin52 | Mean | 26.6 | 53.1 | 24.1 | 31.4 | 47.9 | 26.3 |
| Std dev. | 1.2 | 0.8 | 0.8 | 0.7 | 1.4 | 0.8 | |
| pr76 | Mean | 30.8 | 56.9 | 28.5 | 32.8 | 46.9 | 29.9 |
| Std dev. | 1.3 | 0.8 | 1.3 | 0.6 | 0.6 | 1.3 | |
| kroa100 | Mean | 36.8 | 60.8 | 34.5 | 36.5 | 50.4 | 30.8 |
| Std dev. | 1.6 | 1.2 | 0.6 | 1.1 | 1.3 | 0.8 | |
| gr120 | Mean | 41.9 | 66.5 | 43.1 | 40.5 | 52.2 | 34.9 |
| Std dev. | 0.9 | 1.9 | 1.9 | 1.4 | 1.0 | 1.1 | |
| ch130 | Mean | 48.9 | 70.4 | 43.7 | 43.3 | 52.9 | 35.7 |
| Std dev. | 1.5 | 1.2 | 1.8 | 1.7 | 1.2 | 0.8 | |
| rat195 | Mean | 76.8 | 98.6 | 73.6 | 54.5 | 65.0 | 50.3 |
| Std dev. | 1.6 | 2.2 | 2.7 | 1.1 | 0.7 | 1.2 | |
| ts225 | Mean | 97.8 | 113.9 | 95.4 | 61.8 | 68.1 | 57.3 |
| Std dev. | 2.2 | 3.1 | 3.5 | 1.7 | 0.8 | 2.9 | |
| pma343 | Mean | 193.7 | 193.9 | 177.0 | 121.2 | 111.9 | 107.7 |
| Std dev. | 3.4 | 3.4 | 3.5 | 3.0 | 2.2 | 4.5 | |
| pcb442 | Mean | 363.7 | 312.8 | 317.2 | 177.0 | 166.1 | 180.5 |
| Std dev. | 4.4 | 4.4 | 4.1 | 2.3 | 2.1 | 4.7 | |
| dsj1000 | Mean | 1.667(s) | 1.341(s) | 1.440(s) | 906.9 | 660.1 | 750.2 |
| Std dev. | 3.7 | 4.6 | 3.5 | 7.8 | 5.6 | 8.1 | |
| pr1002 | Mean | 1.595(s) | 1.308(s) | 1.374(s) | 863.3 | 637.3 | 761.8 |
| Std dev. | 5.4 | 5.0 | 4.7 | 3.8 | 4.0 | 17.1 | |
| pr2392 | Mean | 9.268(s) | 7.214(s) | 7.611(s) | 4.900(s) | 3.405(s) | 3.796(s) |
| Std dev. | 20.4 | 24.2 | 22.9 | 15.6 | 9.8 | 20.6 | |
| fnl4461 | Mean | 27.416(s) | 23.096(s) | 24.198(s) | 16.752(s) | 11.268(s) | 12.286(s) |
| Std dev. | 42.3 | 48.2 | 53.1 | 49.0 | 40.9 | 39.6 | |
| rl5934 | Mean | 72.697(s) | 51.579(s) | 54.703(s) | 41.937(s) | 22.301(s) | 25.171(s) |
| Std dev. | 0.042(s) | 5.789(s) | 5.368(s) | 4.113(s) | 0.742(s) | 2.616(s) | |
Note:
For each instance, a mean of 100 runs is provided on first line and standard deviation on second line
Sharing content requires targeting cookies to be enabled. Please update your cookie preferences to use this feature.