欢迎访问昆明冶金高等专科学校学报官方网站,今天是 分享到:

昆明冶金高等专科学校学报 ›› 2024, Vol. 40 ›› Issue (6): 78-.DOI: 10.3969/j.issn.1009-0479.2024.06.013

• 电子信息技术 • 上一篇    

一种求解多目标校车路径问题的改进遗传算法8

谢显杰a ,何亚南a ,袁建明b ,朵云峰a ,刘发稳a    

  1. 昆明冶金高等专科学校 a计算机信息学院,b网络管理与信息中心,云南 昆明 650033)
  • 收稿日期:2024-04-07 出版日期:2024-07-04 发布日期:2025-09-24
  • 作者简介:作者简介:谢显杰 (1992-),男,云南腾冲人,讲师,工学硕士,主要从事智能优化、无线传感器网络、云计算等 研究。
  • 基金资助:
    昆明冶金高等专科学校科研基金项目 “校车多目标优化模型研究” (2021XJZK11); “群智混合激励机制研 究”(2020XJZK05)。 

An Improved Genetic Algorithm for Solving the Multi-0bjectiveSchool Bus Routing Problem#br# #br#

XlE Xianjieª, HE Yanan", YUAN Jianming" , DuO Yunfeng , Llu Fawen   

  1. (a. Faculty of Computer Information, b. Network Management and Information Center,Kunming Metallurgy College,Kunming 650033, China
  • Received:2024-04-07 Online:2024-07-04 Published:2025-09-24

摘要:  针对多目标校车路径优化问题的 NPhard和现有求解方法的不足,提出了一种新颖的 “站点—车辆” 两阶段编码策略,通过站点排序和车辆分配两个阶段生成个体,降低了编码冗余度,保证了解的合法性。设计 了一种新型的双序列交叉算子,在继承父代优良基因的同时,增加了种群的多样性,加快了算法的收敛速度。 在实验方面,选取 3组不同规模的基准测试数据,对算法的解质量和计算效率进行了评测,并与标准遗传算法 (SGA)、模拟退火算法 (SA)等经典启发式算法进行比较。实验结果表明,算法在解的质量和收敛速度方面均 优于其他算法,展现出了良好的求解性能和应用前景。

关键词: 校车路径优化, 多目标优化, 遗传算法, 两阶段编码, 双序列交叉

Abstract:  In response to the NP-hard nature of the multi-objective school bus routing optimization prob.lem and the shortcomings of existing solution methods, this paper proposes a novel “ stop-vehicle” two.stage encoding strategy. This strategy generates individuals through two phases: stop ordering and vehicleallocation, which reduces encoding redundancy and ensures the legality of the solutions. A new type ofdual-sequence crossover operator is designed to inherit the superior genes of the parents while increasingthe diversity of the population and accelerating the convergence speed of the algorithm. In terms of ex.periments, the paper selects three sets of benchmark test data of different sizes to evaluate the solutionquality and computational elficiency of the algorithm and compares it with classic heuristic algorithmssuch as the Standard Genetic Algorithm ($GA) and Simulated Annealing ( SA). The experimental re.sults show that the algorithm proposed in this paper is superior to other algorithms in terms of solutionquality and convergence speed, demonstrating good problem-solving performance and application prospects.

Key words: school bus routing optimization: multi-objective optimization: genetic algorithm, two-phaseencoding, dual sequence crossover

中图分类号: