TY - JOUR

T1 - Solving urban transit route design problem using selection hyper-heuristics

AU - Ahmed, Leena

AU - Mumford, Christine

AU - Kheiri, Ahmed

N1 - This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 274, 2, 2019 DOI: 10.1016/j.ejor.2018.10.022

PY - 2019/4/16

Y1 - 2019/4/16

N2 - The urban transit routing problem (UTRP) focuses on finding efficient travelling routes for vehicles in a public transportation system. It is one of the most significant problems faced by transit planners and city authorities throughout the world. This problem belongs to the class of difficult combinatorial problems, whose optimal solution is hard to find with the complexity that arises from the large search space, and the number of constraints imposed in constructing the solution. Hyper-heuristics have emerged as general-purpose search techniques that explore the space of low level heuristics to improve a given solution under an iterative framework. In this work, we evaluate the performance of a set of selection hyper-heuristics on the route design problem of bus networks, with the goal of minimising the passengers’ travel time, and the operator’s costs. Each selection hyper-heuristic is empirically tested on a set of benchmark instances and statistically compared to the other selection hyper-heuristics to determine the best approach. A sequence-based selection method combined with the great deluge acceptance method achieved the best performance, succeeding in finding improved results in much faster run times over the current best known solutions.

AB - The urban transit routing problem (UTRP) focuses on finding efficient travelling routes for vehicles in a public transportation system. It is one of the most significant problems faced by transit planners and city authorities throughout the world. This problem belongs to the class of difficult combinatorial problems, whose optimal solution is hard to find with the complexity that arises from the large search space, and the number of constraints imposed in constructing the solution. Hyper-heuristics have emerged as general-purpose search techniques that explore the space of low level heuristics to improve a given solution under an iterative framework. In this work, we evaluate the performance of a set of selection hyper-heuristics on the route design problem of bus networks, with the goal of minimising the passengers’ travel time, and the operator’s costs. Each selection hyper-heuristic is empirically tested on a set of benchmark instances and statistically compared to the other selection hyper-heuristics to determine the best approach. A sequence-based selection method combined with the great deluge acceptance method achieved the best performance, succeeding in finding improved results in much faster run times over the current best known solutions.

KW - Transportation

KW - optimisation

KW - routing

KW - Meta-heuristics

U2 - 10.1016/j.ejor.2018.10.022

DO - 10.1016/j.ejor.2018.10.022

M3 - Journal article

VL - 274

SP - 545

EP - 559

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -