车辆数限制的多车型校车路径问题模型及算法研究

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

计算机科学 ›› 2016, Vol. 43 ›› Issue (12): 234-240.doi: 10.11896/j.issn.1002-137X.2016.12.043

车辆数限制的多车型校车路径问题模型及算法研究

侯彦娥,孔云峰,党兰学,谢毅

河南大学黄河中下游数字地理技术教育部重点实验室开封475004;河南大学计算机与信息工程学院开封475004,河南大学黄河中下游数字地理技术教育部重点实验室开封475004,河南大学计算机与信息工程学院开封475004,河南大学黄河中下游数字地理技术教育部重点实验室开封475004;河南大学计算机与信息工程学院开封475004

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金项目:大规模混载校车路径问题多目标优化算法研究(41401461),河南省教育厅自然科学重点项目(15A520009)资助

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

摘要： 为适应校车路径规划中校车有多种车型且每种车型数量受限的需求,建立车辆数限制的多车型校车路径问题(HFSBRP)的数学模型,并提出一种迭代局部搜索算法进行求解。该算法借助邻域随机选择的变邻域下降搜索(VND)算法完成局部提升。局部提升过程中,首先调整车型,然后再混合使用缩减路径数和提高车辆利用率的邻域解接受策略以提高算法的寻优能力,为保证解的多样性,允许接受一定偏差范围内的邻域解。此外,为避免算法过早陷入局部最优,设计了多点交换和移动的扰动规则。基于国际基准测试案例进行模型验证和算法测试,实验结果表明了模型的正确性和算法的有效性。

关键词: 多车型校车路径问题,车辆数限制,迭代局部搜索,随机邻域选择

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

侯彦娥,孔云峰,党兰学,谢毅. 车辆数限制的多车型校车路径问题模型及算法研究[J]. 计算机科学, 2016, 43(12): 234-240. https://doi.org/10.11896/j.issn.1002-137X.2016.12.043

HOU Yan-e, KONG Yun-feng, DANG Lan-xue and XIE Yi. Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem[J]. Computer Science, 2016, 43(12): 234-240. https://doi.org/10.11896/j.issn.1002-137X.2016.12.043

参考文献

[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

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

车辆数限制的多车型校车路径问题模型及算法研究

Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0