Fuzzy Evolutionary Approaches for Bus and Rail Driver Scheduling

Bus and train driver scheduling is a process of partitioning blocks of work, each of which is serviced by one vehicle, into a set of legal driver shifts. The main objectives are to minimise the total number of shifts and the total shift cost. Restrictions imposed by logistic, legal and union agreements make the problem more complicated.

The generate-and-select approach is widely used. A large set of feasible shifts is generated first, and then a subset is selected, from the large set, to form a final schedule by the mathematical programming method. In the subset selection phase, computational difficulties exist because of the NP-hard nature of this combinatorial optimisation problem. This thesis presents two evolutionary algorithms, namely a Genetic Algorithm and a Simulated Evolution algorithm, attempting to model and solve the driver scheduling problem in new ways.

At the heart of both algorithms is a function for evaluating potential driver shifts under fuzzified criteria. A Genetic Algorithm is first employed to calibrate the weight distribution among fuzzy membership functions. A Simulated Evolution algorithm then mimics generations of evolution on the single schedule produced by the Genetic Algorithm. In each generation an unfit portion of the working schedule is removed. The broken schedule is then reconstructed by means of a greedy algorithm, using the weight distribution derived by the Genetic Algorithm. The basic Simulated Evolution algorithm is a greedy search strategy that achieves improvement through iterative perturbation and reconstruction. This approach has achieved success in solving driver scheduling problems from different companies, with comparable results to the previously best known solutions.

Finally, the Simulated Evolution algorithm for driver scheduling has been generalized for the set covering problem, without using any special domain knowledge. This shows that this research is valuable to many applications that can be formulated as set covering models. Furthermore, Taguchi's orthogonal experimental design method has been used for the parameter settings. Computational results have shown that for large-scale problems, in general the proposed approach can produce superior solutions much faster than some existing approaches. This approach is particularly suitable for situations where quick and high-quality solutions are desirable.