求解多车型校车路径问题的带参数选择机制的GRASP算法

doi:10.11896/j.issn.1002-137X.2016.08.047

摘要/Abstract

摘要： 考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。

关键词: 校车路径问题,多车型,贪婪随机自适应搜索过程,参数选择机制,可变邻域搜索

Abstract: This paper dealt with the heterogeneous fleet school bus routing problem,in which students are served by a heterogeneous fleet of buses with various capacities,fixed and variable costs.A GRASP (greedy randomized adaptive search procedure) algorithm with probability selection mechanism was proposed to solve the problem.In the initial solution construction phase,a set of threshold parameters with selection possibility is designed to control the size of restric-ted candidate list (RCL).The threshold parameter is selected by roulette-wheel selection method.The initial solution is then improved by variable neighborhood search (VNS).The selection probabilities for threshold parameters are equally set at first and periodically updated when certain iterations are finished.Each threshold parameter is evaluated by its historical performance records and its selection probability value is adjusted according to its performance.This parameter selection mechanism aims to find better average solution gradually.Our experiments are executed on a set of benchmark instances with different bus types.The results confirm that the proposed GRASP algorithm is more effective compared with classical GRASP algorithm.In addition,the proposed algorithm gives better results than existing algorithms for heterogeneous fleet school bus routing problem.

Key words: School bus routing problem,Heterogeneous fleet,Greedy randomized adaptive search procedure,Parameter selection mechanism,Variable neighborhood search

侯彦娥,党兰学,孔云峰,谢毅. 求解多车型校车路径问题的带参数选择机制的GRASP算法[J]. 计算机科学, 2016, 43(8): 233-239. https://doi.org/10.11896/j.issn.1002-137X.2016.08.047

HOU Yan-e, DANG Lan-xue, KONG Yun-feng and XIE Yi. GRASP Algorithm with Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem[J]. Computer Science, 2016, 43(8): 233-239. https://doi.org/10.11896/j.issn.1002-137X.2016.08.047

参考文献

[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:311-319
[3] Dang Lan-xue,Chen Xiao-pan,Kong Yun-feng.Review of SchoolBus Routing Problem:Concept,Model and Optimization Algorithms [J].Journal of Henan University(Natural Science),2013,3(6):682-691(in Chinese) 党兰学,陈小潘,孔云峰.校车路径问题模型及算法研究进展[J].河南大学学报(自然科学版),2013,3(6):682-691
[4] Xu Wen-long,Li Xiao-juan,Gong Hui-li,et al.An algorithm for school bus optimal path planning [J].Geospatial Information,2011,9(4):67-71(in Chinese) 许文龙,李小娟,宫辉力,等.校车最优路径规划算法[J].地理空间信息,2011,9(4):67-71
[5] Euchi J,Mraih R.The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm [J].Swarm and Evolutionary Computation,2012,2:16-17
[6] Zhang Fu,Zhu Tai-ying.Optimization Design for the School Bus Stations and Routing [J].Mathematics in Practice and Theory,2012,2(4):141-146(in Chinese) 张富,朱泰英.校车站点及线路的优化设计[J].数学的实践与认识,2012,2(4):141-146
[7] Dang Lan-xue,Hou Yan-e,Kong Yun-feng.Spatiotemporal Nei- ghborhood Search for Solving Mixed-load School Bus Routing Problem[J].Computer Science,2015,2(4):221-225(in Chinese) 党兰学,侯彦娥,孔云峰.基于时空相关的混载校车路径问题邻域搜索[J].计算机科学,2015,2(4):221-225
[8] Hoff A,Anderson H,Christiansen M,et al.Industrial aspectsand literature survey:Fleet composition and routing [J].Computers and Operations Research,2012,37(12):2041-2061
[9] Golden B,Assad A,Levy L,et al.The fleet size and mix vehicle routing problem [J].Computers and Operations Research,1984,11(1):49-66
[10] Taillaid E D.A heuristic column generation method for the he-terogeneous fleet VRP [J].RAIRO,1999,33:1-34
[11] 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(2):285-295
[12] Brando J.A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem [J].European Journal of Operational Research,2009,195(3):716-728
[13] Liu S.A hybrid population heuristic for the heterogeneous vehicle routing problems[J].Transportation Research Part E,2013,54:67-78
[14] Matei O,Pop P C,Sas J L,et al.An improved immigrationmemetic algorithm for solving the heterogeneous fixed fleet vehicle routing problem [J].Neurocomputing,2015,150:58-66
[15] Li X,Leung S C H,Tian P.A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem [J].Expert Systems with Applications,2012(39):365-374
[16] Liu F H,Shen S Y.The fleet size and mix vehicle routing problem with time windows [J].Journal of the Operational Research Society,1999,50(7):721-732
[17] Jiang J,Ng K M,Poh K L,et al.Vehicle routing problem with a heterogeneous fleet and time windows[J].Expert Systems with Applications,2014,41:3748-3760
[18] Li L Y O,Fu Z.The School Bus Routing Problem:A Case Study [J].The Journal of the Operational and Research Society,2002,53(5):552-558
[19] Fu Zhuo.The Open Vehicle Routing Problems and Their Applications[D].Changsha:Central South University,2003(in Chinese) 符卓.开放式车辆路径问题及其应用研究[D].长沙:中南大学,2003
[20] 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
[21] Ripplinger D.Rural school vehicle routing problem [J].Transportation Research Record:Journal of the Transportation Research Board,2005,1992:105-110
[22] Ke X.School bus selection,routing and Scheduling[D].Canada,Windsor:University of Windsor,2005
[23] Thangiah S R,Fergany A,Wilson B,et al.School Bus Routing in Rural School Districts[J].Computer-Aided Systems in Public Transport,2008,600:209-232
[24] Luzia V D S,Paulo H S.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(IEA/AIE).2010,3:247-256
[25] Braca J,Bramel J,Posner B,et al.A computerized approach to the New Yoke City school bus routing problem[J].IIE Transactions,1997,9:693-702
[26] Gendreau M,Potvin Jean-Yves.Handbook of Metaheuristics(2nd Edition)[M].New York:Springer-Verlag New York Inc.,2010
[27] Martí R,Resende M G C,Ribeiro C C.Multi-start methods for combinatorial optimization [J].European Journal of Operational Research,2013,226:1-8
[28] Prais M,Celso R.Reactive GRASP:An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment [J].INFORMS Journal on Computing,2000,12(3):164-176
[29] Alvarez-Valdes R,Parreo F,Tamarit J M.Reactive GRASP for the strip-packing problem [J].Computers & Operations Research,2008,35(4):1065-1083
[30] Hansen P,Mladenovi′N.Variable Neighborhood Search:Principles and Applications [J].European Journal of Operations Research,2001,0:449-467
[31] Vidal T,Crainic T G,Gendreau M,et al.Heuristics for multi-attribute vehicle routing problems:A survey [J].European Journal of Operational Research,2013,231(1):1-21

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed