## Using Ants for Driver Scheduling

##### Paul Forsyth, Computer Science, University Of Leeds, Leeds LS2 9JT, United Kingdom

Email: paulf@scs.leeds.ac.uk

Antony Wren, University Of Leeds, Leeds LS2 9JT, United Kingdom

The Ant System (AS) as used by Dorigo et al is applied to the Bus Driver
Scheduling Problem (BDSP), and its applicability analysed. The BDSP
consists of vehicles that each have a number of Relief Opportunities (ROS)
where drivers can change or take a break. A solved BDSP must ensure that
each piece of work - defined as being the time between each RO on a
vehicle - has been visited by the chosen drivers. Optimal schedules arise
from minimising the number of drivers and/or the cost of the schedule.

While it may appear natural to let ants build drivers shifts which between
them cover the whole bus schedule, this would lead in practice to an
unwieldy system in which each ant would have to evaluate the feasibility
of each potential move. In practice the rules regarding feasibility of a
drivers shift may be very complex. We therefore take advantage of the fact
that an existing solution method for the BDSP starts by generating many
thousand potential shifts. We have devised an AS in which ants follow
complete potential shifts , moving between them to complete a schedule.

Datasets in use are real-world problems and we will show comparisons with
our group's current algorithms that include Integer Linear Programming,
Genetic Algorithms and Constraint Programming.