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.