求解多车型校车路径问题的混合集合划分的GRASP算法

摘要

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法.根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解.为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息.使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性.%In practice of school bus route planning,there are a variety of planning applications with different optimization objectives under the types of school buses constraints.This paper dealt with a class of heterogeneous school bus routing problem(HSBRP) with different objectives.A greedy randomized adaptive search procedure(GRASP) algorithm combining set partition(SP) procedure was proposed in this paper.First,the routes generated in the execution of GRASP are used to build the set partition model,and then the model is solved by the CPLEX optimization software.To keep the algorithm suitable for different HSBRP problems,the initialization solution generation procedure of GRASP is adapted for these problems to obtain a valid solution,and the routes of this initialization solution are put into the route pool.In the local search phase,the many neighborhood operators and variable neighborhood descent procedure are executed for improving the solution.At the same time,the routes of the solution that is improved and the best local optimization in every iteration are both put into the route pool.The test results on the benchmark datasets show that the SP procedure of the proposed algorithm can improve the quality and stability of the algorithm.The proposed algorithm can effectively solve two types of HSBRP with different objectives,and it is effective when compared with the existing HS-BRP algorithms.