[1]赵红梦,姜志侠*,曾 坤.一种用于公共自行车调度的改进 GA-SA 算法[J].计算机技术与发展,2021,31(10):184-189.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 031]
　ZHAO Hong-meng,JIANG Zhi-xia*,ZENG Kun.An Improved GA-SA Algorithm for Public Bicycle Scheduling[J].,2021,31(10):184-189.[doi:10. 3969 / j. issn. 1673-629X. 2021. 10. 031]
点击复制

一种用于公共自行车调度的改进 GA-SA 算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
31
期数:
2021年10期
页码:
184-189
栏目:
应用前沿与综合
出版日期:
2021-10-10

文章信息/Info

Title:
An Improved GA-SA Algorithm for Public Bicycle Scheduling
文章编号:
1673-629X(2021)10-0184-06
作者:
赵红梦; 姜志侠* ; 曾 坤
长春理工大学 理学院,吉林 长春 130022
Author(s):
ZHAO Hong-meng; JIANG Zhi-xia* ; ZENG Kun
School of Science,Changchun University of Science and Technology,Changchun 130022,China
关键词:
公共自行车; 车辆调度; 遗传算法; 模拟退火算法; 成本优化
Keywords:
public bicycle; vehicle scheduling; genetic algorithm; simulated annealing algorithm; cost optimization
分类号:
TP301. 6;U491. 225
DOI:
10. 3969 / j. issn. 1673-629X. 2021. 10. 031
摘要:
为解决公共自行车静态单调度路径优化问题,以成本最小化( 包括车辆固定成本和车辆行驶成本) 为目标建立优化模型,在此模型的基础上提出一种模拟退火算法融入遗传算法的混合启发式算法来求解该模型。 该算法在遗传算法中使用模拟退火算法进行判断选择, 从而增强全局或局部意义下的搜索效率和能力;并在遗传算法中提出三种改进的染色体交叉方式:基于关联度的两点交叉法、修正重复元素的两点交叉法、基于自适应的两点交叉法;利用实例和 MATLAB 软件编程分别对三种方法的性能进行验证。 结果表明:改进后的 GA-SA 算法的调度成本比 GA 算法的成本减少了 12. 17% ,比文献[6] 中算法的成本减少了 52. 11% ,说明该算法具有较高的可行性和有效性,是优化公共自行车调度问题的一种有效途径。
Abstract:
In order to solve the static single scheduling path optimization problem of public bicycles,an optimization model is established to minimize the? cost ( including vehicle fixed cost and vehicle running cost) . Based on this model,a hybrid heuristic algorithm with simulated annealing algorithm and genetic algorithm is proposed to solve the model. This algorithm uses simulated annealing algorithm to judge and select in genetic algorithm, so as to enhance the search efficiency and ability in the global or local sense. Three improved chromosome crossover methods are proposed in the genetic algorithm:two -point crossover method based on association degree,two-point crossover method based on correction of repeated elements,and two-point crossover method based on self-adaptive. The performance of the three methods is verified by examples and MATLAB software programming. The results show that the scheduling cost of the improved GA-SA algorithm is 12. 17% lower than that of GA algorithm and 52. 11% lower than that of the algorithm in reference [6] .It is showed that the improved GA-SA algorithm has higher feasibility and effectiveness,which is an effective path to optimize the public bicycle scheduling problem.

相似文献/References:

[1]檀庭方.基于自适应免疫遗传算法的VRP问题的研究[J].计算机技术与发展,2007,(06):74.
　TAN Ting-fang.Study on Optimization of Logistics Distribution VRP Based on Self - Adaption Immune - Genetic Algorithm[J].,2007,(10):74.
[2]殷龙,衡红军. 基于最邻近算法的机场特种车辆调度应用研究[J].计算机技术与发展,2016,26(07):151.
　YIN Long,HENG Hong-jun. Research on Application of Airport Special Vehicles Scheduling Based on Nearest Neighbors Algorithm[J].,2016,26(10):151.

更新日期/Last Update: 2021-10-10