A mixed load rural school bus routing problem with heterogeneous fleet: a study for the Brazilian problem

Abstract

The underdevelopment of Brazilian rural families is largely explained by their historical process of formation and by their poor access to a functional education and transportation systems. In the last decade, the federal government has been encouraging the nucleation of rural schools to offer better structured schools to the rural students. Multi-grade rural schools, often located closer to the rural families but with students of different grades being taught by the same teacher at the same class, are being shutdown and transfered to bigger, better installed facilities located near to the counties downtown area. The success of such endeavor relies on offering a transportation system for the rural students. Hence the Brazilian federal government has been making a great effort to support local administrators to provide better transport to rural students. One of such efforts gave rise to a central decision support system which solves the mixed load capacitated rural school bus routing problem with heterogeneous fleet. The mixed load feature allows students from different schools to ride the same bus during at the same time. This is an important but neglected problem in vehicle routing literature. In this thesis, four based meta-heuristic algorithms are devised and embedded into the support system. The computation performance of the proposed algorithms was assessed on solving four different datasets, including a real case from Brazil. The proposed methods were also compared with one known method from the literature. The attained cost savings and reduction of the number of buses required to serve the rural students showed the suitability of the mixed load approach over the single load one for the Brazilian rural context. Furthermore four based meta-heuristic based multi-objective algorithms to solve the multi-objective capacitated mixed load rural bus routing problem with heterogeneous fleet were also devised. The three involved objectives were the routing costs, the average weighted riding distances and the routes balance. The proposed multi-objective methods were compared with one from literature adapted for the problem and evaluated by assessing the metrics of cardinality, coverage and hyper-volume, followed by a statistical analyses. The work also introduces a new approach to help decision makers to selected a suitable solution from a Pareto set. All of the four devised multi-objective heuristics outperformed the literature procedure.