title: Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem.
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.
authors.affiliation: Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng, Henan 475004, China; College of Computer and Information Engineering, Henan University, Kaifeng, Henan 475004, China.
authors.forename: Xiaopan
authors.initials: X
authors.lastname: Chen
authors.affiliation: Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng, Henan 475004, China.
authors.forename: Yunfeng
authors.initials: Y
authors.lastname: Kong
authors.affiliation: Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng, Henan 475004, China; College of Computer and Information Engineering, Henan University, Kaifeng, Henan 475004, China.
authors.forename: Lanxue
authors.initials: L
authors.lastname: Dang
authors.affiliation: Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions, Ministry of Education, Henan University, Kaifeng, Henan 475004, China; College of Computer and Information Engineering, Henan University, Kaifeng, Henan 475004, China.
authors.forename: Yane
authors.initials: Y
authors.lastname: Hou
authors.affiliation: Department of Geography, Kent State University, Kent, OH 44242, United States of America.
authors.forename: Xinyue
authors.initials: X
authors.lastname: Ye
mesh_terms: D000465:Algorithms; D001071:Appointments and Schedules; D003198:Computer Simulation; D000066506:Heuristics; D006801:Humans; D018986:Motor Vehicles; D012574:Schools / Q000458:organization & administration*