计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (4): 320-328.DOI: 10.3778/j.issn.1002-8331.2109-0424

• 工程与应用 • 上一篇    

混合蚁群算法的实况路网低碳冷链路径优化

高英腾,廖志高   

  1. 广西科技大学 经济与管理学院,广西 柳州 545006
  • 出版日期:2023-02-15 发布日期:2023-02-15

Path Optimization of Low Carbon Cold Chain in Real Road Network Based on Hybrid Ant Colony Algorithm

GAO Yingteng, LIAO Zhigao   

  1. School of Economics and Management, Guangxi University of Science and Technology, Liuzhou, Guangxi 545006, China
  • Online:2023-02-15 Published:2023-02-15

摘要: 针对市区内交通车速变化频繁、备选路径多的特点,传统算法选择路径时计算量大导致无法有效收敛,提出一种蚁群与Dijkstra混合算法进行求解。首先利用高德地图API获取市区主要交通道路及其在不同时刻的车速,并运用BP神经网络对车速进行预测。在此基础上,综合考虑固定成本、时间变动成本、路程变动成本、时间窗惩罚成本及碳成本,以总成本最低为目标函数,利用贪心规则的Dijkstra算法搜索路径,通过不断调整蚁群算法留下的信息素来调整道路运输成本,建立修正成本地图,在路况发生变动时通过调用地图提高二次搜索速度,并使用Python编程进行验证。实例证明,混合算法结合了蚁群算法正反馈的特性以及Dijkstra算法全局搜索能力强的特点,缩短了应对路况变化所需的时间,并能有效根据当前交通实况规划出合理路径。

关键词: 冷链配送路径问题, 市区交通, 低碳, 混合蚁群算法

Abstract: In view of the characteristics of frequent changes in traffic speed and many alternative routes in urban areas, the traditional algorithm cannot converge effectively due to the large amount of calculation, a hybrid ant colony and Dijkstra algorithm is proposed. Firstly, Amap API is used to obtain the main traffic roads in the urban area and their speed at different time, and BP neural network is used to predict the speed. On this basis, considering the fixed cost, time variable cost, distance variable cost, time window penalty cost and carbon cost, taking the lowest cost as the objective function, the Dijkstra algorithm with greedy rules is used to search the path, and the road transportation cost is adjusted by constantly adjusting the pheromone left by the ant colony algorithm, a revised cost map is established, the map is called to improve the secondary search speed when the road condition changes, and the algorithm is verified with Python. The example shows that the hybrid algorithm combines the positive feedback characteristics of ant colony algorithm and the strong global search ability of Dijkstra algorithm, shortens the time required to deal with road conditions, and can effectively plan a reasonable path according to the current traffic situation.

Key words: cold chain distribution routing problem, urban traffic, low carbon, hybrid ant colony algorithm