时空相关的混载校车路径问题邻域搜索

Spatiotemporal Neighborhood Search for Solving Mixed-load School Bus Routing Problem

为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内。该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵。然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表。在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率。在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50%以上的求解时间。

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 maximum 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 mixedload SBRP instances shows that the spatiotemporal neighborhood search is capable of reducing the neighborhood search space and saving the solution time dramatically.