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

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

Abstract

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

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.

References

[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

Comments

Recommended 0

No Suggested Reading articles found!

GRASP Algorithm with Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 0