An Ant System for Bus Driver Scheduling

This paper reports on one of a number of parallel investigations being undertaken into alternative approaches to solving part or the whole of the bus driver scheduling problem. An artificial ant system is set up, with ants following trails through a network, each trail representing a complete bus driver schedule. Initial schedules are set up by drawing from shifts generated by other systems available in the University of Leeds. Each trail receives an allocation of pheromone related to the quality of the relevant schedule. As new ants are introduced to the system they are encouraged to follow the more intensive pheromone trails, and the poorer trails gradually lose their intensity. Thus successive ants are likely to follow better trails, and to yield better schedules. We report on our investigations. 1 Introduction In this paper a meta-heuristic known as the Ant System (AS), as created by Marco Dorigo et al [1], is applied to the problem of scheduling drivers of buses. The heuristic ca..