侯彦娥,孔云峰,党兰学.求解多车型校车路径问题的混合集合划分的GRASP算法[J].计算机科学,2018,45(4):240-246
求解多车型校车路径问题的混合集合划分的GRASP算法
Greedy Randomized Adaptive Search Procedure Algorithm Combining Set Partitioning for Heterogeneous School Bus Routing Problems
投稿时间:2017-02-15  修订日期:2017-05-26
DOI:10.11896/j.issn.1002-137X.2018.04.040
中文关键词:  多车型校车路径问题,集合划分,贪婪随机自适应,混合元启发
英文关键词:Heterogeneous school bus routing problem,Set partitioning,Greedy randomized adaptive search procedure,Hybrid meta-heuristic
基金项目:本文受国家自然科学基金项目(41401461)资助
作者单位E-mail
侯彦娥 河南大学计算机与信息工程学院 河南 开封475004 houyane@henu.edu.cn 
孔云峰 河南大学黄河中下游数字地理技术教育部重点实验室 河南 开封475004  
党兰学 河南大学计算机与信息工程学院 河南 开封475004 danglx@foxmail.com 
摘要点击次数: 235
全文下载次数: 174
中文摘要:
      针对不同规划场景下具有不同优化目标的多车型校车路径问题(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 HSBRP algorithms.
查看全文  查看/发表评论  下载PDF阅读器