Abstract: Neighborhood search is one of the key issues in the algorithm design for solving mixed-load school bus routing problem (SBRP).For saving the execution time of neighborhood search,this paper introduced the concepts of spatiotemporal distance and spatiotemporal connectivity index to reduce the size of searching space.The spatiotemporal distance between stop nodes was defined as the weighted sum of normalized spatial distance and temporal distance.Moreover,the spatiotemporal connectivity index,a number indicating the feasible connectivity between two SBRP nodes,is determined according to spatiotemporal distance and constraints such as school bus capacity,school time window and maxi-mum riding time.The spatiotemporal connectivity indexes are sorted in a descending order for each node,and the neighborhood lists for all nodes are prepared for neighborhood search operators.In the following step of node moves,the neighborhood node with higher index value will be examined preferentially.Thus the effective node will be accepted as earlier as possible,and the size of neighborhood lists can be reduced substantially.The test of a set of large-scale mixed-load SBRP instances shows that the spatiotemporal neighborhood search is capable of reducing the neighborhood search space and saving the solution time dramatically.

Key words: School bus routing problem,Mixed-load,Neighborhood search,Spatiotemporal distance,Spatiotemporal connectivity index