A*估价函数在复杂配送路径优化中的改进

计算机工程与科学

A*估价函数在复杂配送路径优化中的改进

李世明1,2,王玉芬1,张秉桢1,李秋月1

(1.哈尔滨师范大学计算机科学与信息工程学院,黑龙江哈尔滨 150025;

2.上海市信息安全综合管理技术研究重点实验室，上海 200240)

收稿日期:2018-09-12 修回日期:2019-02-02 出版日期:2019-10-25 发布日期:2019-10-25
基金资助:
黑龙江省自然科学基金(F2016030，F2018023);黑龙江省教育厅科学技术研究项目(12511147);上海市信息安全管理技术研究重点实验室开放课题（AGK2015003）

Improvement of A* valuation function

in complex distribution path optimization

LI Shi-ming1,2,WANG Yu-fen1,ZHANG Bing-zhen1,LI Qiu-yue1

(1.College of Computer Science and Information Engineering,Harbin Normal University,Harbin 150025;

2.Shanghai Key Laboratory of Integrated Administration Technologies for Information Security,Shanghai 200240,China)

Received:2018-09-12 Revised:2019-02-02 Online:2019-10-25 Published:2019-10-25

摘要/Abstract

摘要：

随着城市交通日趋复杂，时间和路径成本直接决定路径规划的效果，但传统的A*算法已经不能满足复杂路径优化的需求。对此，提出了一种TWA*算法，在传统的A*算法基础上对其估价函数进行了改进。首先，通过时间参数建立时间因子归一化模型来提高节点被选择概率，节约时间成本；其次，结合时间因子与估价函数降低路程成本。实验采用北京市某一区域GPS数据，分别用A*算法和TWA*算法进行验证，结果表明，与传统A*算法相比，TWA*算法在时间及路径成本上分别提高了约6%和5%，达到了路径优化的目的，同时为企业物流的高效配送提供了较可靠的参考依据。

关键词: A*算法, 路径优化, 估价函数, 物流配送

Abstract:

As urban traffic becomes more and more complex, time and path cost directly determine the effect of path planning. The traditional A* algorithm cannot satisfy these needs any more. We thus propose a TWA* algorithm, which can improve its evaluation function on the basis of the original A* algorithm. Firstly, a time factor normalization model is established by time parameter to expand the probability of node selection and save time cost. Secondly, it is combined with the valuation function to reduce the distance cost. The A* algorithm and TWA* algorithm are respectively verified in the experiment using the GPS data of a region of Beijing. The results show that the TWA* algorithm improves the time and path cost by about 6% and 5% respectively, achieving the goal of path optimization and providing reliable reference basis for efficient delivery of enterprise logistics.

Key words: A* algorithm, path optimization, valuation function, logistics distribution

李世明1,2,王玉芬1,张秉桢1,李秋月1. A*估价函数在复杂配送路径优化中的改进[J]. 计算机工程与科学.

LI Shi-ming1,2,WANG Yu-fen1,ZHANG Bing-zhen1,LI Qiu-yue1.

Improvement of A* valuation function

in complex distribution path optimization

[J]. Computer Engineering & Science.

[1]	吕倩茹, 杨翔瑞, 蔡志平. 基于影响力地图的计算机兵棋推演路径规划[J]. 计算机工程与科学, 2024, 46(06): 1041-1049.
[2]	沈克宇, 游志宇, 刘永鑫. 基于拟合优先搜索的多场景自适应改进A*算法[J]. 计算机工程与科学, 2024, 46(01): 142-149.
[3]	李中华, 袁杰, 郭振宇. 基于信息启发的目标导向Bi-RRT机器人路径规划[J]. 计算机工程与科学, 2023, 45(12): 2237-2245.
[4]	张志远, 陈海进, 章一鸣. 基于局部障碍率预获取和双向父节点变更的A*算法优化[J]. 计算机工程与科学, 2023, 45(09): 1661-1669.
[5]	于家斌, 陈志豪, 邓维, 许继平, 赵峙尧, 王小艺. 一种无人巡航船遍历多目标点的路径规划算法研究[J]. 计算机工程与科学, 2023, 45(05): 840-848.
[6]	郭园园, 袁杰, 赵克刚. 基于改进A*算法和动态窗口法的机器人路径规划[J]. 计算机工程与科学, 2022, 44(07): 1273-1281.
[7]	张志远, 陈海进. 基于动态矩阵的未知环境地图构建与路径规划[J]. 计算机工程与科学, 2022, 44(03): 563-570.
[8]	宋阿妮, 包贤哲. 精英扩散蚁群优化算法求解运输无人机三维路径规划[J]. 计算机工程与科学, 2021, 43(10): 1891-1900.
[9]	袁也, 王刚, 刘晓光, 李雨森. 新型电路版图布局布线算法设计[J]. 计算机工程与科学, 2021, 43(07): 1185-1191.
[10]	李丹莲, 曹倩, 徐菲. 基于改进遗传算法的连锁便利店配送路径优化[J]. 计算机工程与科学, 2020, 42(11): 2096-2102.
[11]	苟平章，张芬，毛刚，贾向东. 基于AGNES聚类的能耗均衡WSNs优化路由算法[J]. 计算机工程与科学, 2020, 42(04): 620-627.
[12]	马贵平, 潘峰. 基于改进蚁群算法的物流运输路径研究[J]. 计算机工程与科学, 2020, 42(03): 523-528.
[13]	李玲玉,张昆. 快递配送路径的优化研究与软件设计[J]. 计算机工程与科学, 2019, 41(08): 1406-1412.
[14]	李楷，陈永府,金志勇，刘田，王振庭，郑迥之. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学, 2019, 41(07): 1227-1235.
[15]	刘国繁1,许多2. 基于非均匀分簇与路径优化的WSN路由协议[J]. J4, 2015, 37(08): 1492-1497.