來遠為，楊錄峰

基于改進Floyd算法的物流運輸路徑規(guī)劃

來遠為，楊錄峰

（北方民族大學 數(shù)學與信息科學學院，寧夏 銀川 750021）

當站點較多時，物流運輸路徑規(guī)劃存在困難，傳統(tǒng)Floyd算法路徑規(guī)劃的時間復(fù)雜度過高．鑒于傳統(tǒng)Floyd算法規(guī)劃時間復(fù)雜度高是因節(jié)點數(shù)量過大導(dǎo)致，提出一種結(jié)合改進K-means聚類算法的Floyd算法，該算法在節(jié)點數(shù)量較大情況下，運用改進K-means聚類算法分割物流區(qū)域，降低規(guī)劃所需考慮節(jié)點數(shù)量，從而降低Floyd算法的時間復(fù)雜度．在復(fù)雜環(huán)境下進行傳統(tǒng)Floyd算法和改進算法的對比實驗，仿真分析結(jié)果表明，改進算法可以在更少的時間內(nèi)找到一條較優(yōu)的路徑．

K-means聚類算法；Floyd算法；時間復(fù)雜度；物流運輸路徑規(guī)劃

近年來，隨著網(wǎng)絡(luò)購物的興起，對于物流運輸行業(yè)的要求也越來越高，而大件商品的物流仍是一個難題，如運輸路徑、包裝費用等．現(xiàn)有的研究普遍忽略了大范圍物流運輸路徑規(guī)劃的時間復(fù)雜度．針對大件商品物流的路徑規(guī)劃問題[1-5]，本文將改進的K-means聚類算法與傳統(tǒng)的Floyd算法相結(jié)合，降低了路徑規(guī)劃問題所需的時間復(fù)雜度．

1　算法原理

1.1　改進的K-means聚類算法

相較于傳統(tǒng)的K-means聚類算法[6-7]，改進后的K-means聚類算法的聚類中心是固定的．聚類過程為：

Step3將所有普通物流地點依據(jù)其所最近的物流中心進行分區(qū)．

Step4對所有物流中心所劃分的物流區(qū)域內(nèi)的所有普通物流地點進行內(nèi)部檢查．提取出其中的異常點，重新進行聚類（此后的聚類排除以當前物流中心為聚類中心的情況）．

Step5將聚類結(jié)果存儲，以便之后使用Floyd算法時調(diào)用．

圖1　異常點說明

1.2　傳統(tǒng)的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　結(jié)合K-means聚類算法改進的Floyd算法

1.3.1前期準備前期準備過程為：

Step1通過改進的K-means聚類算法將各普通物流地點聚類到對應(yīng)的物流中心，并存儲以便反復(fù)調(diào)用；

Step2遍歷所有物流點，得到各個相鄰物流子區(qū)域的區(qū)域間相連點，用傳統(tǒng)Floyd算法[9]求出物流中心到物流子區(qū)域內(nèi)各相連點間的最短路徑和距離；

Step3利用Step2得到的物流中心、區(qū)域間相連點和兩者間最短距離以及區(qū)域間相連點的距離構(gòu)造鄰接矩陣，將所有物流點構(gòu)成的物流區(qū)域降維，使用傳統(tǒng)Floyd算法得到物流中心間的最短路徑．將得到的數(shù)據(jù)進行存儲，以便反復(fù)調(diào)用．

1.3.2物流子區(qū)域內(nèi)的路徑規(guī)劃在物流子區(qū)域內(nèi)進行路徑規(guī)劃時，僅需對該物流子區(qū)域內(nèi)的普通物流地點使用傳統(tǒng)Floyd算法進行路徑規(guī)劃即可．

1.3.3物流中心間的路徑規(guī)劃當物流運輸?shù)慕K點不在出發(fā)點所在物流區(qū)域時，需要提前計算各個物流中心間的最短路徑，并將得到的數(shù)據(jù)進行存儲，以用于跨區(qū)域路徑規(guī)劃．具體過程為：

2　規(guī)劃實例

圖2　物流運輸?shù)貓D

圖3　物流子區(qū)域劃分

圖4　物流中心間的最短路徑

2.1　物流子區(qū)域內(nèi)的路徑規(guī)劃

2.2　物流子區(qū)域間的路徑規(guī)劃

3　結(jié)語

[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中網(wǎng)絡(luò)場景與路由度量映射模型[J]．南京理工大學學報，2016（3）：290-296．

[3] 林琰，孫笑，楊碩．基于Floyd及KL-means聚類算法的交通運輸網(wǎng)絡(luò)設(shè)計[C]//中國公路學會，世界交通運輸大會執(zhí)委會，西安市人民政府，陜西省科學技術(shù)協(xié)會．世界交通運輸工程技術(shù)論壇（WTC2021）論文集（上）．北京：人民交通出版社股份有限公司，2021．

[4] 丁喬，李旭，王建春．結(jié)合DBSCAN聚類算法和粒子群算法的大規(guī)模路徑優(yōu)化方法研究[J]．物流科技，2020（4）：10-15．

[5] 劉文兵，王藝棟．多無人機協(xié)同搜索多目標的路徑規(guī)劃問題研究[J]．電光與控制，2019，26（3）：35-38，73．

[6] 楊俊闖，趙超．K-Means聚類算法研究綜述[J]．計算機工程與應(yīng)用，2019，55（23）：7-14，63．

[7] 袁方，周志勇，宋鑫．初始聚類中心優(yōu)化的k-means算法[J]．計算機工程，2007（3）：65-66．

[8] 田翠華，許衛(wèi)平，陳玉明．深度優(yōu)先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應(yīng)用[J]．河北北方學院學報（自然科學版），2013（3）：19-24．

[9] 惠慶華，張恒運，唐晨洋，等．基于Floyd算法和線性規(guī)劃的疫情防控物資配送方案[J]．青海大學學報，2022，40（4）：76-81．

[10] 程世輝，盧翠英．算法的時間復(fù)雜度分析[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

北方民族大學創(chuàng)新訓練項目（2022-XJ-SX-05）

來遠為（2002-），男，浙江杭州人，在讀本科生．E-mail：917408817@qq.com

楊錄峰（1980-），男，山東沂水人，講師，博士，從事偏微分方程數(shù)值解研究．E-mail：ylf-sd@163.com