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.

 

https://rhydlewis.eu/bus/index_files/image002.png

 

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)

Adelaide

South Australia

1188

342

565

1.6

1.6

Bridgend

Wales

633

221

381

4.82

1.6

Brisbane

Queensland

1817

438

757

3.2

1.6

Canberra

ACT

331

296

499

4.8

1

Cardiff

Wales

552

90

156

4.8

1.6

Edinburgh-1

Scotland

959

409

680

1.6

1.6

Edinburgh-2

Scotland

917

190

320

1.6

1.6

Milton Keynes

England

579

149

274

4.8

1.6

Porthcawl

Wales

153

42

66

3.2

1.6

Suffolk

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

View Solutions

View Solutions

View Solutions

Bridgend

6

View Solutions

View Solutions

View Solutions

Brisbane

11

View Solutions

View Solutions

View Solutions

Canberra

8

View Solutions

View Solutions

View Solutions

Cardiff

3

View Solutions

View Solutions

View Solutions

Edinburgh-1

10

View Solutions

View Solutions

View Solutions

Edinburgh-2

5

View Solutions

View Solutions

View Solutions

Milton Keynes

5

View Solutions

View Solutions

View Solutions

Porthcawl

1

View Solutions

View Solutions

View Solutions

Suffolk

4

View Solutions

View Solutions

View Solutions

 

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