A Multi-Objective Simulated Annealing for Bus Driver Rostering

Citation

Peng K, Shen Y & Li J (2015) A Multi-Objective Simulated Annealing for Bus Driver Rostering. In: Gong M, Pan L, Song T, Tang K & Zhang X (eds.) Bio-Inspired Computing -- Theories and Applications: 10th International Conference, BIC-TA 2015 Hefei, China, September 25-28, 2015, Proceedings. Communications in Computer and Information Science, 562. 2015 International Conference on Bio-inspired Computing: Theories and Applications (BIC-TA2015), Hefei, China, 25.09.2015-28.09.2015. Berlin: Springer, pp. 315-330. http://link.springer.com/chapter/10.1007/978-3-662-49014-3_29; https://doi.org/10.1007/978-3-662-49014-3_29

Abstract
This paper presents a Multi-Objective Simulated Annealing (MOSA) approach for noncyclic bus driver rostering. A heuristic is first devised to construct an initial solution. Next, a SA-based feasibility repairing algorithm is designed to make the solution feasible. Finally, a SA-based non-dominated solution generating algorithm is devised to find the Pareto front based on the feasible solution. Differing from previous work on the problem, the MOSA provides two options to handle user preferences: one with a weighted-sum evaluation function encouraging moves towards users’ predefined preferences, and another with a domination-based evaluation function encouraging moves towards a more diversified Pareto set. Moreover, the MOSA employs three strategies, i.e. incremental evaluation, neighbourhood pruning and biased elite solution restart strategy, to make the search more efficient and effective. Experiments show that the MOSA can produce a large number of solutions that reconcile contradictory objectives rapidly, and the strategies can enhance the computational efficiency and search capability.

Keywords
Public transit; Bus driver rostering; Multi-objective optimization; Simulated annealing