基于运营和出行成本的校车路径问题研究
作者:
中图分类号:

U492.4

基金项目:

山东省自然科学基金(ZR2021QF110)


School bus routing considering operation and travel costs
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    为解决农村地区校车路网布局中校方运营成本过高,以及乘车站点分布散乱导致校车服务质量差的问题,建立混载与不混载场景下多目标校车路径规划问题(SBRP)模型.在不混载情景下,构建以学生出行成本和校方运营成本为优化目标的融合校车服务水平的SBRP数学模型;在混载情景下,构建考虑校车投入成本与运营成本的SBRP数学模型.通过对比多个启发式算法,确定基于模拟退火算法的求解流程和基于遗传算法求解结果的横向比对.最后,在国际基准案例上进行了测试,基于模拟退火算法引入不同搜索算子求解不同场景下构建的SBRP数学模型,应用于山东日照五莲县校车路径优化设计,结果表明不混载SBRP情景下,提出的方法较原校车运营方式,校车投入量、行驶里程、行程成本分别减少28.6%、37.8%、35.6%,考虑到学生的校车服务感知度,学生出行成本降低4.3%;由于混载情景的复杂性,难以有效兼顾出行成本,提出的方法较原校车运营方式的学生出行成本增加了0.5%,但校车投入量、行驶里程、行程成本分别减少37.5%、42.0%、35.8%,更好地验证了构建模型的有效性及模拟退火算法相较于遗传算法,能够更大程度提高农村地区校车服务质量和降低校方运营成本.

    Abstract:

    In order to solve the problems of high operating cost and poor service quality of school bus due to the scattered distribution of bus stops in rural areas, multi-objective SBRP (School Bus Routing Problem) models were developed for the mixed-load and non-mixed-load scenarios.In the non-mixed-load scenario, a model of the SBRP was developed to optimize the students' travel cost and school operating cost, while in the mixed-load scenario, another model of the SBRP was developed to consider the input cost and operation cost of the school bus.Several heuristic algorithms were compared, based on which the simulated annealing algorithm was selected to solve the models, and the horizontal comparison of the solution results based on genetic algorithm were determined.Tests were conducted on an international bench mark case and the constructed models were solved by introducing different search operators into the simulated annealing algorithm, then the proposed approach was applied to the optimal design of school bus routes in Wulian county, Rizhao, Shandong province.The results showed that in the non-mixed-load scenario, compared with the original school bus operation mode, the school bus input, mileage and travel cost were reduced by 28.6%, 37.8% and 35.6%, respectively, and students' travel cost was reduced by 4.3% considering the students' perception of school bus service.While in the mixed-load scenario, the proposed approach reduced the school bus input, mileage and travel cost by 37.5%, 42.0% and 35.8%, respectively;due to the complexity of the mixed-load scenario, it is difficult to take the travel cost into account, thus the students' travel cost was increased by 0.5%.The proposed SBRP models were verified to be effective and the simulated annealing approach can optimize service quality and reduce operation cost of rural school bus to a greater extent than the genetic algorithm.

    参考文献
    [1] Newton R M, Thomas W H.Bus routing in a multi-school system[J].Computers & Operations Research, 1974, 1(2):213-222
    [2] Jaradat A S, Shatnawi M Q.Solving school bus routing problem by intelligent water drops algorithm[J].Journal of Computer Science, 2020, 16(1):25-34
    [3] Calvete H I, Galé C, Iranzo J A, et al.A partial allocation local search matheuristic for solving the school bus routing problem with bus stop selection[J].Mathematics, 2020, 8(8):1214
    [4] 高巍, 陈泽颖, 李大舟.基于校车数量的无混载校车路线问题模型优化实现[J].沈阳化工大学学报, 2021, 35(1):82-89 GAO Wei, CHEN Zeying, LI Dazhou.Optimization of the model of unmixed school bus route based on the number of school bus[J].Journal of Shenyang University of Chemical Technology, 2021, 35(1):82-89
    [5] Hargroves B T, Demetsky M J.A computer assisted school bus routing strategy:a case study[J].Socio-Economic Planning Sciences, 1981, 15(6):341-345
    [6] Hou Y, Zhao N, Dang L, et al.A hybrid metaheuristic algorithm for the school bus routing problem with multi-school planning scenarios[J].Engineering Letters, 2021, 29(4):1-10
    [7] 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
    [8] Semba S, Mujuni E.An empirical performance comparison of meta-heuristic algorithms for school bus routing problem[J].Tanzania Journal of Science, 2019, 45(1):81-92
    [9] Braca J, Bramel J, Posner B, et al.A computerized approach to the New York City school bus routing problem[J].IIE Transactions, 1997, 29(8):693-702
    [10] 刘梦琪, 瞿何舟.基于轨道交通与常规公交组合的出行路径选择研究[J].交通运输工程与信息学报, 2018, 16(4):63-68 LIU Mengqi, QU Hezhou.Study on the route choice using the combination of rail and bus transit[J].Journal of Transportation Engineering and Information, 2018, 16(4):63-68
    [11] 冯焕焕, 邓建华.基于前景值和乘客最优理论的居民公交出行选择模型[J].科学技术与工程, 2019, 19(5):307-311 FENG Huanhuan, DENG Jianhua.Model of public transport choice based on prospect value and passenger optimal theory[J].Science Technology and Engineering, 2019, 19(5):307-311
    [12] Levin M W, Boyles S D.Practice summary:improving bus routing for KIPP charter schools[J].Interfaces, 2016, 46(2):196-199
    [13] 洪越, 殷利平.基于遗传算法的非高斯系统随机分布控制[J].南京信息工程大学学报(自然科学版), 2020, 12(4):504-509 HONG Yue, YIN Liping.Genetic algorithm-based stochastic distribution control for non-Gaussian systems[J].Journal of Nanjing University of Information Science & Technology (Natural Science Edition), 2020, 12(4):504-509
    [14] Minocha B, Tripathi S.Solving school bus routing problem using hybrid genetic algorithm:a case study[M]//Advances in Intelligent Systems and Computing.New Delhi:Springer India, 2014:93-103
    [15] 李燕, 季建楠, 沈葭栎, 等.基于改进蚁群算法的移动机器人路径规划方法[J].南京信息工程大学学报(自然科学版), 2021, 13(3):298-303 LI Yan, JI Jiannan, SHEN Jiali, et al.Mobile robot path planning based on improved ant colony algorithm[J].Journal of Nanjing University of Information Science & Technology (Natural Science Edition), 2021, 13(3):298-303
    [16] 邓绍强, 郭宗建, 李芳, 等.基于Metropolis准则的自适应模拟退火粒子群优化[J].软件导刊, 2022, 21(6):85-91 DENG Shaoqiang, GUO Zongjian, LI Fang, et al.Adaptive simulated annealing particle swarm optimization algorithm based on metropolis[J].Software Guide, 2022, 21(6):85-91
    [17] 李朝迁, 裴建朝.新型模拟退火遗传算法在路径优化的应用[J].组合机床与自动化加工技术, 2022(3):52-55 LI Chaoqian, PEI Jianchao.Application of new simulated annealing genetic algorithm in path optimization[J].Modular Machine Tool & Automatic Manufacturing Technique, 2022(3):52-55
    [18] Yu V F, Jewpanya P, Redi A A N P, et al.Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks[J].Computers & Operations Research, 2021, 129:105205
    [19] Li H B, Lim A.A metaheuristic for the pickup and delivery problem with time windows[J].Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2001).November 7-9, 2001, Dallas, TX, USA.IEEE, 2001:160-167
    [20] Bent R, Hentenryck P V.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J].Computers & Operations Research, 2006, 33(4):875-893
    [21] Liu W W, Li X, Qin X N, et al.A metropolis criterion based fuzzy Q-learning flow controller for high-speed networks[J].Applied Mechanics and Materials, 2012, 241/242/243/244:2327-2330
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李开雷,白翰,燕翔,朱漫兮,王修光.基于运营和出行成本的校车路径问题研究[J].南京信息工程大学学报(自然科学版),2023,15(3):293-303
LI Kailei, BAI Han, YAN Xiang, ZHU Manxi, WANG Xiuguang. School bus routing considering operation and travel costs[J]. Journal of Nanjing University of Information Science & Technology, 2023,15(3):293-303

复制
分享
文章指标
  • 点击次数:268
  • 下载次数: 1257
  • HTML阅读次数: 55
  • 引用次数: 0
历史
  • 收稿日期:2022-04-20
  • 在线发布日期: 2023-06-28

地址:江苏省南京市宁六路219号    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn

南京信息工程大学学报 ® 2025 版权所有  技术支持:北京勤云科技发展有限公司