Computer Science ›› 2016, Vol. 43 ›› Issue (12): 234-240.doi: 10.11896/j.issn.1002-137X.2016.12.043

Previous Articles     Next Articles

Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem

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

  • Online:2018-12-01 Published:2018-12-01

Abstract: In practice of school bus route planning,the bus fleet usually consists of a limited number of buses with different capacities,purchase costs and operation costs.However,the heterogeneous fixed fleet school bus routing problem (HFSBRP) has not been well investigated.In this paper,we introduced a mathematical model for HFSBRP and also proposed an iterated local search (ILS) algorithm to optimize the total cost.The ILS is combined with a variable neighborhood descent (VND) algorithm with random neighborhood selection.In local search,the bus type for one or more routes will be adjusted to reduce the costs.Two acceptance rules are used to accept the solution while satisfying the rules.In addition,some worst solutions within the scope of cost deviation are accepted to keep the diversification of the search.Moreover,a perturbation mechanism with multiple points swap or shift is used to avoid local optima.The experimental results demonstrate the correctness and effectiveness of the proposed model.

Key words: Heterogeneous school bus routing problem,Fixed fleet,Iterated local search,Random variable neighborhood search

[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 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] 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
[5] Kinable J,Spieksma F C R,Berghe V G.School bus routing-acolumn generation approach [J].International Transactions in Operational Research,2014(21):453-478
[6] 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
[7] Dang Lan-xue,Hou Yan-e,Kong Yun-feng.Spatio temporal 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] Kusuma S,Anan M,Gerrit K J,et al.Heterogeneous VRP Review and Conceptual Framework [J].Lecture Notes in Engineering and Computer Science,2014,2210(1):1052-1059
[9] Ripplinger D.Rural school vehicle routing problem [J].Transportation Research Record:Journal of the Transportation Research Board,2005,1992:105-110
[10] Ke X.School bus selection,routing and Scheduling[D].Canada,Windsor:University of Windsor,2005
[11] 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
[12] 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,3:247-256
[13] 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
[14] 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
[15] Penna P H V,Subramanian A,Ochi L S.An iterated local search heuristic for the heterogeneous fleet vehicle routing problem [J].Journal of Heuristics,2013,19(2):201-232
[16] Hansen P,Mladenovic N.Variable Neighborhood Search:Principles and Applications [J].European Journal of Operations Research,2001,130(3):449-467
[17] Dang Lan-xue,Wang Zhen,Liu Qing-shong,et al.Heuristic Algorithm for Solving Mixed Load School Bus Routing Problem[J].Computer Science,2013,0(7),248-253(in Chinese) 党兰学,王震,刘青松,等.一种求解混载校车路径的启发式算法[J].计算机科学,2013,0(7):248-253

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .