Adaptive Large Neighborhood search for school bus routing problem with mixed load effect

The school bus routing problem (SBRP) characterizes a variant of the well-known vehicle routing problem. The main objective of this study is to pick up students allocated to some bus stops and generate routes, including the selected stops, to carry the students to school while considering mixed load effect (the student of different school can be in one bus in the same time). In this paper, we propose two kinds of metaheurisitc configurations: simple Large Neighbourhood Search heuristic, called LNS, and Adaptive Large Neighbourhood Search heuristic, so called ALNS. The former only contains one removal and insertion heuristic while the latter includes set of removal and insertion operators. Both metaheuristics combine a nearest neighbourhood constructive heuristic to generate initial solution. Computational experiments are conducted on three data sets. The results reveal that ALNS is very competitive in comparison to optimal solution outperformed the LNS. Within the experimentations, we also perform further analysis to investigate the effect of mixed load effect on both the ALNS and the LNS heuristics.