This page gives further information on the
research carried out in the following paper.
· Lewis, R. and K. Smith-Miles (2018) A Heuristic Algorithm for Finding Cost-Effective Solutions to Real-World School Bus Routing Problems, Journal of Discrete Algorithms, vol. 52-53, pp. 2-17.
A simple description of this problem can also
be viewed at https://www.rhydlewis.eu/bus.
The links in the table below show the ten
problem instances used in the above study. Clicking on the links in the leftmost
column shows an interactive visualisation of each problem on a real-world map. These
problem instances can be downloaded at https://rhydlewis.eu/resources/busprobs.zip
The geographic locations of these instances were chosen to reflect a wide range
of problem features arising in the real world, including problem size (in terms
of school enrolment figures and the number of bus stops in their catchment
areas), urban or rural settings, coastal and inland, and organic or grid city
layouts.
Location |
Country /
State |
Num. Bus
Stops |
Num.
Addresses |
Num. Students |
Minimum
Eligibility Distance (km) |
Maximum Walk
Distance (km) |
South Australia |
1188 |
342 |
565 |
1.6 |
1.6 |
|
Wales |
633 |
221 |
381 |
4.82 |
1.6 |
|
Queensland |
1817 |
438 |
757 |
3.2 |
1.6 |
|
ACT |
331 |
296 |
499 |
4.8 |
1 |
|
Wales |
552 |
90 |
156 |
4.8 |
1.6 |
|
Scotland |
959 |
409 |
680 |
1.6 |
1.6 |
|
Scotland |
917 |
190 |
320 |
1.6 |
1.6 |
|
England |
579 |
149 |
274 |
4.8 |
1.6 |
|
Wales |
153 |
42 |
66 |
3.2 |
1.6 |
|
England |
174 |
123 |
209 |
4.8 |
1.6 |
The table below now gives links to the solutions produced by the algorithm for the three values of the d parameter used in the paper. Lower values of d lead to longer run times, but also better quality solutions. A full description of the meaning of the d parameter is given in the paper.
Location |
Num Routes
(k) |
d = 1 secs |
d = 10 secs |
d = 30 secs |
Adelaide |
9 |
|||
Bridgend |
6 |
|||
Brisbane |
11 |
|||
Canberra |
8 |
|||
Cardiff |
3 |
|||
Edinburgh-1 |
10 |
|||
Edinburgh-2 |
5 |
|||
Milton Keynes |
5 |
|||
Porthcawl |
1 |
|||
Suffolk |
4 |
The c++ source code used to produce these results can be downloaded at https://www.rhydlewis.eu/resources/busCode.zip. Compilation and usage constructions are also contained in this resource.
Please direct any questions to Rhyd Lewis: LewisR9@cf.ac.uk, www.RhydLewis.eu.
Last Updated Tuesday, 13 November 2018