Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem |
| |
Authors: | Xiaopan Chen Yunfeng Kong Lanxue Dang Yane Hou Xinyue Ye |
| |
Institution: | 1Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng, Henan 475004, China;2College of Computer and Information Engineering, Henan University, Kaifeng, Henan 475004, China;3Department of Geography, Kent State University, Kent, OH 44242, United States of America;Bangladesh University of Engineering and Technology, BANGLADESH |
| |
Abstract: | As a class of hard combinatorial optimization problems, the school bus routing problem has received considerable attention in the last decades. For a multi-school system, given the bus trips for each school, the school bus scheduling problem aims at optimizing bus schedules to serve all the trips within the school time windows. In this paper, we propose two approaches for solving the bi-objective school bus scheduling problem: an exact method of mixed integer programming (MIP) and a metaheuristic method which combines simulated annealing with local search. We develop MIP formulations for homogenous and heterogeneous fleet problems respectively and solve the models by MIP solver CPLEX. The bus type-based formulation for heterogeneous fleet problem reduces the model complexity in terms of the number of decision variables and constraints. The metaheuristic method is a two-stage framework for minimizing the number of buses to be used as well as the total travel distance of buses. We evaluate the proposed MIP and the metaheuristic method on two benchmark datasets, showing that on both instances, our metaheuristic method significantly outperforms the respective state-of-the-art methods. |
| |
Keywords: | |
|
|