基于改进Floyd算法的物流运输路径规划

来远为，杨录峰

基于改进Floyd算法的物流运输路径规划

来远为，杨录峰

（北方民族大学 数学与信息科学学院，宁夏 银川 750021）

当站点较多时，物流运输路径规划存在困难，传统Floyd算法路径规划的时间复杂度过高．鉴于传统Floyd算法规划时间复杂度高是因节点数量过大导致，提出一种结合改进K-means聚类算法的Floyd算法，该算法在节点数量较大情况下，运用改进K-means聚类算法分割物流区域，降低规划所需考虑节点数量，从而降低Floyd算法的时间复杂度．在复杂环境下进行传统Floyd算法和改进算法的对比实验，仿真分析结果表明，改进算法可以在更少的时间内找到一条较优的路径．

K-means聚类算法；Floyd算法；时间复杂度；物流运输路径规划

近年来，随着网络购物的兴起，对于物流运输行业的要求也越来越高，而大件商品的物流仍是一个难题，如运输路径、包装费用等．现有的研究普遍忽略了大范围物流运输路径规划的时间复杂度．针对大件商品物流的路径规划问题[1-5]，本文将改进的K-means聚类算法与传统的Floyd算法相结合，降低了路径规划问题所需的时间复杂度．

1　算法原理

1.1　改进的K-means聚类算法

相较于传统的K-means聚类算法[6-7]，改进后的K-means聚类算法的聚类中心是固定的．聚类过程为：

Step3将所有普通物流地点依据其所最近的物流中心进行分区．

Step4对所有物流中心所划分的物流区域内的所有普通物流地点进行内部检查．提取出其中的异常点，重新进行聚类（此后的聚类排除以当前物流中心为聚类中心的情况）．

Step5将聚类结果存储，以便之后使用Floyd算法时调用．

图1　异常点说明

1.2　传统的Floyd算法

那么，令

Floyd算法代码为：

import math

D= Distance矩阵

S=Sequence矩阵

for k in range（n）：

for i in range（n）：

for j in range（n）：

if D[i][k]+D[k][j]

D[i][j]=D[i][k]+D[k][j]

S[i][j]=S[i][k]

1.3　结合K-means聚类算法改进的Floyd算法

1.3.1前期准备前期准备过程为：

Step1通过改进的K-means聚类算法将各普通物流地点聚类到对应的物流中心，并存储以便反复调用；

Step2遍历所有物流点，得到各个相邻物流子区域的区域间相连点，用传统Floyd算法[9]求出物流中心到物流子区域内各相连点间的最短路径和距离；

Step3利用Step2得到的物流中心、区域间相连点和两者间最短距离以及区域间相连点的距离构造邻接矩阵，将所有物流点构成的物流区域降维，使用传统Floyd算法得到物流中心间的最短路径．将得到的数据进行存储，以便反复调用．

1.3.2物流子区域内的路径规划在物流子区域内进行路径规划时，仅需对该物流子区域内的普通物流地点使用传统Floyd算法进行路径规划即可．

1.3.3物流中心间的路径规划当物流运输的终点不在出发点所在物流区域时，需要提前计算各个物流中心间的最短路径，并将得到的数据进行存储，以用于跨区域路径规划．具体过程为：

2　规划实例

图2　物流运输地图

图3　物流子区域划分

图4　物流中心间的最短路径

2.1　物流子区域内的路径规划

2.2　物流子区域间的路径规划

3　结语

[1] IFTIKHAR H．Cluster Formation and Cluster Head Selection Approach for Vehicle Ad-hoc Networks Using K-Mean and Floyd-Warshall Techniques[D]．辽宁：大连理工大学，2018．

[2] 秦珍珍，王玉皞，吴婷婷．DTN中网络场景与路由度量映射模型[J]．南京理工大学学报，2016（3）：290-296．

[3] 林琰，孙笑，杨硕．基于Floyd及KL-means聚类算法的交通运输网络设计[C]//中国公路学会，世界交通运输大会执委会，西安市人民政府，陕西省科学技术协会．世界交通运输工程技术论坛（WTC2021）论文集（上）．北京：人民交通出版社股份有限公司，2021．

[4] 丁乔，李旭，王建春．结合DBSCAN聚类算法和粒子群算法的大规模路径优化方法研究[J]．物流科技，2020（4）：10-15．

[5] 刘文兵，王艺栋．多无人机协同搜索多目标的路径规划问题研究[J]．电光与控制，2019，26（3）：35-38，73．

[6] 杨俊闯，赵超．K-Means聚类算法研究综述[J]．计算机工程与应用，2019，55（23）：7-14，63．

[7] 袁方，周志勇，宋鑫．初始聚类中心优化的k-means算法[J]．计算机工程，2007（3）：65-66．

[8] 田翠华，许卫平，陈玉明．深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J]．河北北方学院学报（自然科学版），2013（3）：19-24．

[9] 惠庆华，张恒运，唐晨洋，等．基于Floyd算法和线性规划的疫情防控物资配送方案[J]．青海大学学报，2022，40（4）：76-81．

[10] 程世辉，卢翠英．算法的时间复杂度分析[J]．河南教育学院学报（自然科学版），2007（4）：20-23．

Logistics transportation path planning based on improved Floyd algorithm

LAI Yuanwei，YANG Lufeng

（School of Mathematics and Information Science，North Minzu University，Yinchuan 750021，China）

Logistics transportation path planning is difficult when there are many stations，and the traditional Floyd algorithm has a high time complexity for path planning．Considering that the traditional Floyd algorithm has high planning time complexity due to the large number of nodes，a Floyd algorithm combined with an improved K-means clustering algorithm is proposed．This algorithm divides the logistics area by improving the K-means clustering algorithm in the case of a large number of nodes，reduces the number of nodes required for planning consideration，thereby reduces the time complexity of the Floyd algorithm．The comparative experiments between traditional Floyd algorithm and improved algorithm is conduct in complex environments，simulation analysis results show that the improved algorithm can find a better path in less time.

K-means clustering algorithm；Floyd′s algorithm；time complication；logistics transportation path planning

1007-9831（2023）12-0022-05

O29

A

10.3969/j.issn.1007-9831.2023.12.004

2022-11-20

北方民族大学创新训练项目（2022-XJ-SX-05）

来远为（2002-），男，浙江杭州人，在读本科生．E-mail：917408817@qq.com

杨录峰（1980-），男，山东沂水人，讲师，博士，从事偏微分方程数值解研究．E-mail：ylf-sd@163.com