A multi-loading school bus routing problem

摘要

In this work we introduce the multi-loading school bus routing problem which extends the rural school bus routing problem with mixed loads by incorporating an innovative feature here referred to as multi-load. Whereas the mixed load variant allows students from different schools to ride the same bus at the same time, the multi-load model expands this definition by admitting students to be picked up and delivered simultaneously, regardless of their shift, commuting direction (going to or returning from school) or school, giving thus more flexibility to managers on lowering transportation costs. The multi-load feature has a great social and economic appeal, specially to developing countries that usually have double or triple shifts for schooling, and budget restrictions. The advantages and disadvantages of the new model are discussed and highlighted in our experiments which report the attained savings when compared with the mixed load approach for routing the students situated in rural areas of all 76 cities of the state of Espírito Santo, Brazil. To solve these large scale, real instances, different meta-heuristics were devised which combine an iterated local search with specialized neighborhood structures arranged in a variable neighborhood descent strategy enriched with a diversification scheme which relies on an elite set. The attained results demonstrate that the multi-loading approach can substantially reduce the solutions’ cost.