A strategy for clustering students minimizing the number of bus stops for solving the school bus routing problem

In this work we tackle the bus stop selection step for the School Bus Routing Problem (SBRP). Our goal is to minimize the number of bus stops in order to assign all students to a bus stop respecting a home-to-bus-stop walking distance constraint. Our strategy creates a large number of possible bus stops points in a road network and uses a pseudo-random constructive heuristic algorithm to assign students to a bus stops. Our approach is tested on a real georeferenced data of a Brazilian city and is compared with a different methodology. Results demonstrate that the proposed approach is able to find good solutions for this optimization problem. Besides, the higher the number of possible points to install bus stops, the smaller is the number of bus stops required to attend all students.

I. Introduction

The School Bus Routing Problem (SBRP) [1]–[5] is a classical combinatorial optimization problem which, given a set of roads, schools, students, vehicles and garages, consists of generating an efficient schedule for a fleet of school buses. Each bus picks up students from various bus stops and delivers them to their designated schools while satisfying various constraints such as the maximum capacity of a bus, the maximum riding time of a student in a bus and the time window of a school. According to [2] the SBRP can be divided into five sub-problems: Data Preparation; Bus Stop Selection;Routes Generation; School Bell Time Adjustment and Route Scheduling. As far as we are concerned, only Desrosiers et al. [2], [6] address all five steps of the SBRP. Normally, the research works deal with the Route Generation and the Route Scheduling steps.