Visualisations of School Bus Routes in Real-World Cities

The school bus routing problem involves compiling a list of eligible school children and then efficiently organising their transport to school. This process requires the selection of a suitable set of pick-up points (bus stops), the assignment of students to these pick-up points, and the design of bus routes that visit these stops while getting students to school on time. In doing this, a number of factors should be considered:

· We should try to reduce economic costs by minimising the number of vehicles used;

· Bus journeys should not be too long for students;

· Pick-up points should be close to people’s houses;

· Buses have limited seating capacities.

The links in the table below show ten problem instances and solutions for a variety of locations in Australia and the UK. Clicking on the links in the rightmost column leads to a scatterplot for each problem instance where a range of solutions can then be accessed. Further information including links to code, tables of results, and downloads of this problem instance set can be found here,

Location	Country / State	Num. Bus Stops	Num. Addresses	Minimum Eligibility Distance (km)	Maximum Walk Distance (km)	Links to Solutions
Adelaide	South Australia	1188	342	1.6	1.6	View Solutions
Bridgend	Wales	633	221	4.82	1.6	View Solutions
Brisbane	Queensland	1817	438	3.2	1.6	View Solutions
Canberra	ACT	331	296	4.8	1	View Solutions
Cardiff	Wales	552	90	4.8	1.6	View Solutions
Edinburgh-1	Scotland	959	409	1.6	1.6	View Solutions
Edinburgh-2	Scotland	917	190	1.6	1.6	View Solutions
Milton Keynes	England	579	149	4.8	1.6	View Solutions
Porthcawl	Wales	153	42	3.2	1.6	View Solutions
Suffolk	England	174	123	4.8	1.6	View Solutions

A number of points should be made about these problem instances and their solutions.

· The second and third columns in the table give the number of bus stops and the number of student addresses in each problem instance.

· The column labelled Minimum Eligibility Distance indicates the minimum distance that students should live from the school to qualify for school transport. Consequently, no address should be within this distance (walking) from the school. Similarly, the column Maximum Walk Distance, gives the maximum distance that a student should be expected to walk to get to a bus stop. These values are roughly in the ranges of those given in government guidelines of the respective countries and territories

· In all cases, names and locations of real-world bus stops are used. These are taken from publically available government datasets. A bus stop is only included in the problem instance if it has at least one address within walking distance. Similarly, each address is also required to have at least one bus stop within walking distance.

· Names and GPS coordinates of real schools are used in each case. However, names and addresses of students have been generated at random and do not correspond to real people. Where such information is publically available, these addresses occur in areas roughly corresponding to the catchment areas of the schools.

· Driving times and distances between bus stops have been calculated using Bing Maps. Similarly, walking times and distances between addresses and bus stops have been taken from either Google Maps or Bing Maps. The driving routes shown in the solutions correspond to shortest driving times.

· For all problem instances, in-vehicle journey times are required to be less than 45 minutes and buses are assumed to have seventy seats. Note that in all cases, the solutions presented here use the minimum number of buses, which is equal to the number of students divided by the bus capacity, rounded up to the nearest whole number.

· Solutions also take into account the time it takes buses to slow down at a stop, students to board, and buses to re-join the traffic stream. For each stop on a route, this is calculated using 5 seconds for each student, plus a further 15 seconds. So, for example, if a bus picks up 10 students at a stop, this will lead to a dwell time of (5 x 10) + 15 = 65 seconds.

· In the scatter-plots, two quality measures are used: (a) the average walking time of the students, and (b) the average length of the bus routes (in minutes). Note that by reducing one of these, the other tends to rise. Consequently, solutions with very short walks tend to lead to more stops being used (and therefore longer routes). Similarly, longer walks tend to lead to fewer bus stops being used (and therefore shorter routes). The solutions have been produced using algorithms designed by Rhyd Lewis, as described 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.

Please direct any questions to Rhyd Lewis: LewisR9@cf.ac.uk, www.RhydLewis.eu.

Last Updated Friday, 15 December 2017