计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 240-246.doi: 10.11896/j.issn.1002-137X.2018.04.040
侯彦娥,孔云峰,党兰学
HOU Yan-e, KONG Yun-feng and DANG Lan-xue
摘要: 针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。
[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! |
|