Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Lewis, Rhyd ORCID: 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

[thumbnail of paper.pdf]
PDF - Accepted Post-Print Version
Download (2MB) | Preview


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: 06 Nov 2023 18:42

Citation Data

Cited 6 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics