A mixed load capacitated rural school bus routing problem with heterogeneous fleet: Algorithms for the Brazilian context

• Brazil is improving its service level for its rural school transportation system.
• Five algorithms based on meta-heuristics are devised to address the problem.
• Two different transportation approaches are analyzed: single and mixed load plans.
• The mixed load plan has lower costs, number of buses and student riding distances.
• The mixed load approach shows to be more suitable for the Brazilian context.

A capacitated rural school bus routing problem featuring mixed loads, a heterogeneous fleet, and the same school starting time is here addressed. This is an important problem of the routing literature which has been attracting the attention of many researchers recently. The mixed load feature allows students from different schools to ride the same bus at the same time. Five meta-heuristic based algorithms were devised to solve the problem, and evaluated on solving four different datasets, one of them being based on a real case from Brazil. Four traditional local search neighborhood structures for vehicle routing problems were adapted and specialized to handle mixed loads and a heterogeneous fleet simultaneously. To the best of the authors knowledge, it is the first time that both features are treated jointly within an algorithm, and not as a post processing optimization step. The attained cost savings and reduction of fleet sizes suggest the suitability of a mixed load, heterogeneous fleet approach for sparsely populated rural areas. Moreover the devised framework has been embedded into a decision support system which is assisting several municipalities of the state of Minas Gerais, Brazil, to better plan their routes and reduce transportation costs.