Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem

• DOI: 10.1371/journal.pone.0132600
• Publication Date: 2015-07-15T14:36:28Z
• Authors: Xiaopan Chen; Yunfeng Kong; Lanxue Dang; Yane Hou; Xinyue Ye
• Keywords: Solver; Benchmark (surveying); Vehicle Routing Problem; School bus; Parallel metaheuristic

As a class of hard combinatorial optimization problems, the school bus routing problem has received considerable attention in last decades. For multi-school system, given trips for each school, scheduling aims at optimizing schedules to serve all within time windows. In this paper, we propose two approaches solving bi-objective problem: an exact method mixed integer programming (MIP) and metaheuristic which combines simulated annealing with local search. We develop MIP formulations homogenous heterogeneous fleet problems respectively solve models by solver CPLEX. The type-based formulation reduces model complexity terms number decision variables constraints. is two-stage framework minimizing buses be used as well total travel distance buses. evaluate proposed on benchmark datasets, showing that both instances, our significantly outperforms respective state-of-the-art methods.