A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems

Lewis, Rhyd and Smith-Miles, K. 2018. A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems. Journal of Discrete Algorithms 52-53 , pp. 2-17. 10.1016/j.jda.2018.11.001

Preview

PDF - Accepted Post-Print Version Download (2MB) | Preview

Abstract

This paper proposes a heuristic algorithm for designing real-world school transport schedules. It extends previously considered problem models by considering some important but hitherto overlooked features including the splitting and merging of routes, gauging vehicle dwell times, the selection of stopping points, and the minimisation of walking distances. We show that this formulation contains a number of interacting combinatorial subproblems including the time-constrained vehicle routing problem, set covering, and bin packing. As a result, a number of new and necessary algorithmic operators are proposed for this problem which are then used alongside other recognised heuristics. Primarily, the aim of this algorithm is to minimise the number of vehicles used by each school, though secondary issues concerning journey lengths and walking distances are also considered through the employment of suitable multiobjective techniques

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	1570-8667
Funders:	Cardiff University Seedcorn Fund
Date of First Compliant Deposit:	13 November 2018
Date of Acceptance:	1 November 2018
Last Modified:	10 Nov 2019 03:32
URI:	http://orca.cf.ac.uk/id/eprint/116689

Actions (repository staff only)

Edit Item