Exact and metaheuristic approaches for a bi-objective school bus scheduling problem

Xiaopan Chen, Yunfeng Kong, Lanxue Dang, Yane Hou, Xinyue Ye

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

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.

Original languageEnglish (US)
Article numbere0132600
JournalPloS one
Volume10
Issue number7
DOIs
StatePublished - Jul 15 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Biochemistry, Genetics and Molecular Biology(all)
  • Agricultural and Biological Sciences(all)
  • General

Fingerprint

Dive into the research topics of 'Exact and metaheuristic approaches for a bi-objective school bus scheduling problem'. Together they form a unique fingerprint.

Cite this