计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 240-246.doi: 10.11896/j.issn.1002-137X.2018.04.040

• 人工智能 • 上一篇    下一篇

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

侯彦娥,孔云峰,党兰学   

  1. 河南大学计算机与信息工程学院 河南 开封475004,河南大学黄河中下游数字地理技术教育部重点实验室 河南 开封475004,河南大学计算机与信息工程学院 河南 开封475004
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金项目(41401461)资助

Greedy Randomized Adaptive Search Procedure Algorithm Combining Set Partitioning for Heterogeneous School Bus Routing Problems

HOU Yan-e, KONG Yun-feng and DANG Lan-xue   

  • Online:2018-04-15 Published:2018-05-11

摘要: 针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。

关键词: 多车型校车路径问题,集合划分,贪婪随机自适应,混合元启发

Abstract: 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.

Key words: Heterogeneous school bus routing problem,Set partitioning,Greedy randomized adaptive search procedure,Hybrid meta-heuristic

[1] NEWTON R M,THOMAS W H.Design of school bus routes by computer[J].Socio-Economic Planning Sciences,1969,3(1):75-85.
[2] PARK J,KIM B I.The school bus routing problem:A review [J].European Journal of Operational Research,2010,202(2):311-319.
[3] DANG L X,CHEN X P,KONG Y F.Review of School BusRouting Problem:Concept,Model and Optimization Algorithms [J].Journal of Henan University(Natural Science),2013,43(6):682-691.(in Chinese) 党兰学,陈小潘,孔云峰.校车路径问题模型及算法研究进展[J].河南大学学报(自然科学版),2013,3(6):682-691.
[4] KE X.School bus selection,routing and Scheduling [D].Canada,Windsor:University of Windsor,2005.
[5] RIPPLINGER D.Rural school vehicle routing problem [J].Transportation Research Record:Journal of the Transportation Research Board,2005,1992(1):105-110.
[6] DE SOUZA L,SIQUEIRA P H.Heuristic Methods Applied to the Optimization School Bus Transportation Routes-A Real Case[C]∥23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems.2010:247-256.
[7] THANGIAH S R,FERGANY A,WILSON B,et al.School Bus Routing in Rural School Districts[C]∥Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport.Spring,2008:209-232.
[8] PARK J,TAE H,KIM B I.A Post-improvement Procedure for the Mixed Load School Bus Routing Problem [J].European Journal of Operational Research,2012,217(1):204-213.
[9] HOU Y E,DANG L X,KONG Y F,et al.GRASP Algorithmwith Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem [J].Computer Science,2016,43(8):233-239.(in Chinese) 侯彦娥,党兰学,孔云峰,等.求解多车型校车路径问题的带参数选择机制的GRASP算法[J].计算机科学,2016,3(8):233-239.
[10] HOU Y E,KONG Y F,DANG L X,et al.Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem [J].Computer Science,2016,43(12):234-240.(in Chinese) 侯彦娥,孔云峰,党兰学,等.车辆数限制的多车型校车路径问题模型及算法研究[J].计算机科学,2016,3(12):234-240.
[11] PISINGER D,ROPKE S.A general heuristic for vehicle routing problems[J].Computer & Operations Research,2007,34(8):2403-2435.
[12] SUBRAMANIAN A,PENNA P H V,UCHOA E,et al.A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem [J].European Journal of Operational Research,2012,221:285-295.
[13] SUBRAMANIAN A,UCHOA E,OCHI L.A hybrid algorithm for a class of vehicle routing problems [J].European Journal of Operational Research,2013,40:2519-2531.
[14] VIDAL T,CRAINIC T,GENDREAU M,et al.A unified solution framework for multi-attribute vehicle routing problems [J].European Journal of Operational Research,2014,234:658-673.
[15] ROCHAT Y,TAILLARD E D.Probabilistic diversification and intensification in local search for vehicle routing [J].Journal of Heuristics,1995,1:147-167.
[16] ALVARENGA G,MATEUS G,DE TOMI G.A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows [J].Computers and Operations Research,2007,34(6):1561-1584.
[17] HANSEN P,MLADENOVIC N.Variable Neighborhood Search:Principles and Applications [J].European Journal of Operations Research,2001,130(3):449-467.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .