A real geographical application for the School Bus Routing Problem

Author

Fonseca Faraj, Marcelo ; Machry Sarubbi, JoaÌƒo Fernando ; Silva, Cristiano M. ; Franco Porto, Marcelo ; Ramos Nunes, Nilson Tadeu

Author_Institution

Comput. Dept., Fed. Center of Technol. Educ., Belo Horizonte, Brazil

fYear

2014

fDate

8-11 Oct. 2014

Firstpage

2762

Lastpage

2767

Abstract

This work presents our research and implementation of the School Bus Routing Problem applied to the rural area of a Brazilian city. We use a complete set of real georeferenced data containing a sample of 944 students, 23 schools, and the full road network of a city of population of 280,000 inhabitants occupying an area of 2,348 km². Our goal is to optimize the daily transportation of students considering the real publicly available fleet composed of heterogeneous vehicles. As our solution is being evaluated for application over the entire country, we have included some ´quality´ parameters for tunning the application to distinct economic/social realities. A mixed integer linear programming model and a GRASP based algorithm are proposed to solve the routing problem.

Keywords

graph theory; greedy algorithms; integer programming; linear programming; search problems; vehicle routing; Brazilian city; GRASP based algorithm; SBRP; city population; daily transportation optimization; greedy randomized adaptive search procedure; heterogeneous vehicles; mixed integer linear programming model; quality parameters; real geographical application; real georeferenced data; real publicly available fleet; road network; rural area; school bus routing problem; Convergence; Educational institutions; Heuristic algorithms; Roads; Routing; Vehicles;

fLanguage

English

Publisher

ieee

Conference_Titel

Intelligent Transportation Systems (ITSC), 2014 IEEE 17th International Conference on

Conference_Location

Qingdao

Type

conf

DOI

10.1109/ITSC.2014.6958132

Filename

6958132