基于Floyd算法的城市配送最快路徑選擇

唐克生，錢 民，段麗梅，王 濱

（昆明冶金高等?？茖W校，云南 昆明 650033）

基于Floyd算法的城市配送最快路徑選擇

唐克生，錢 民，段麗梅，王 濱

（昆明冶金高等專科學校，云南 昆明 650033）

提出了一種基于車輛通行時間大數(shù)據(jù)選擇最快路徑的方法，充分考慮道路擁堵和交叉路口紅綠燈等待時間的因素，用通行時間代替距離，采用改進的Floyd算法來發(fā)現(xiàn)最快的配送路徑，研究發(fā)現(xiàn)該方法可以提高城市配送的效率，降低時間成本，具有較高的應用價值。

大數(shù)據(jù)；城市配送；最快路徑；時間成本；Floyd算法

1 引言

目前“最后一公里”的城市配送的效率問題已成為影響物流業(yè)發(fā)展的一個重要因素。配送路徑的選擇對配送的效率和成本起著關鍵的作用。過去，我們會選擇一條最短路徑作為配送路徑，最短路徑算法主要有Dijkstra廣度搜索算法、Floyd算法、A*啟發(fā)式算法以及在搜索節(jié)點時加入蟻群算法和遺傳算法以提高搜索的效率[1]?，F(xiàn)在，隨著城市交通擁堵的加劇，人們意識到最短路徑并不等于最快路徑，基于對配送效率和時間成本的考慮，傾向于在配送時選擇一條最快路徑。類似的研究成果主要有對交通擁堵可能發(fā)生進行提前預測[2]、建立考慮天氣狀況、道路容量等動量的動態(tài)交通網(wǎng)絡對出行道路進行規(guī)劃和中途調整[3]、引入道路擁堵因子的基于動態(tài)規(guī)劃法的配送路徑動態(tài)選擇[4]、基于交通信號的路口延遲和時間最短路徑(TLBSP)的計算模型實現(xiàn)交通信號控制下各車最短時間路徑的計算[5]、基于CapeCod方法計算最短時間路徑的最優(yōu)出發(fā)時間[6]等。

Dijkstra廣度搜索算法，是一種貪心算法，能夠搜索出一條單源最短路徑，即在圖中求出給定節(jié)點到其它任一節(jié)點的最短路徑。其計算復雜度為o(n2)。Floyd算法，能夠搜索出圖上的所有節(jié)點對的最短路徑。其計算復雜度為o(n3)，可以一次求解無向圖和有向圖。

本文提出了一種基于道路通行時間大數(shù)據(jù)來選擇最快配送路徑的方法，即通過記錄自有配送車輛在配送過程中所經(jīng)過的每條道路的通行時間，區(qū)分通行時段、天氣條件、交通信號路口數(shù)量等影響通行時間的因素，以道路的通行時間代替距離，使用Floyd算法計算完成一趟配送任務的最快路徑，即得出一條從配送中心到一次配送任務的多個客戶且返回配送中心的最快路徑。

2 影響道路通行時間的因素

2.1 天氣條件

一些特殊的天氣條件會直接影響到道路的通行速度，比如能直接導致能見度降低的大霧和沙塵天氣，導致路面濕滑的雨雪天氣。在城市道路的通行實例中，由于特殊天氣條件導致道路通行速度降低而發(fā)生擁堵的情況較為常見。

2.2 通行時段

機動車輛的通行速度直接和該時段的交通流量直接相關。比如高峰時段，由于交通流量增大，道路寬度等條件不足以容納，往往造成通行緩慢，直至發(fā)生擁堵；正常時段，交通流量沒有達到擁堵所需的量，則會道路通暢，不易發(fā)生擁堵。

2.3 交通路口數(shù)量

機動車行駛到路口需要降低速度通過，且由于交通信號燈等待延誤時間，常導致車輛的通行時間直接增加。由于交通信號燈的紅綠燈顯示是動態(tài)變化的，不能提前預測，也不能加以控制，故每個路口的等待時間取值紅燈等待時間的一半較為合適。如果紅燈等待時間為1min，則路口延誤時間取30s，具體的取值可以視不同的城市而有所不同。

本文中，天氣條件、通行時段對通行的影響可以通過該種條件下通行時間的長短得到反映，交通路口的等待時間則單獨標記。

3 最快路徑選擇

隨著城市擁堵的加劇，城市配送時選擇一條最短路徑已經(jīng)不具有現(xiàn)實意義，為了提高效率和降低配送的時間成本，往往需要選擇一條最快路徑來進行配送。

顯然，不同的通行時段，同一條道路需要不同的時間，比如周末與工作日，高峰時段與正常時段所需時間都會不同。當然，不同城市的高峰時段和正常時段會有不同，需要根據(jù)具體的車輛通行時間大數(shù)據(jù)統(tǒng)計得來。接下來，我們給出選擇最快配送路徑的具體步驟。

步驟1 車輛通行大數(shù)據(jù)統(tǒng)計。物流公司的配送客戶通常是確定的，在配送時可選擇的路徑通常是有限的。在自有配送車輛上安裝GPS，按是否工作日、是否高峰時段、是否雨雪等特殊天氣來統(tǒng)計和記錄所經(jīng)過的每一條通行路段的時間，通常以1個月為統(tǒng)計數(shù)據(jù)區(qū)間，所得數(shù)據(jù)作為下個月決策的依據(jù)。

步驟2 數(shù)據(jù)處理。某路段某一時段的通行時間取該時段統(tǒng)計數(shù)據(jù)的平均值作為其時間權值。畫出交通網(wǎng)絡圖，其中，道路的通行時間標注在相應線段上，無向邊表示雙向通行時間無差異，單向邊表示單向通行，雙向邊表示同一條道路該時刻雙向通行時間不相同。節(jié)點標注交叉路口等待時間，通常取紅燈等待時間的一半，不考慮左轉、直行、右轉的區(qū)別。

步驟3 采用改進的Floyd算法來計算交通網(wǎng)絡圖中所有節(jié)點對之間的最短通行時間路徑。Floyd算法是一種基于迭代思想的動態(tài)規(guī)劃算法，本文中增加了交叉路口的等待時間，算法也相應地做出了改進。算法的主要部分如下：

聲明并初始化時間代價矩陣T(0)[i][j]，路口等待時間數(shù)組W[i]

其中，G.vnum()為節(jié)點數(shù)函數(shù)，T[i][j].time為節(jié)點Vi與節(jié)點Vj之間的時間代價，T[i][j].pre存儲節(jié)點Vi與節(jié)點Vj之間的前驅節(jié)點（跳節(jié)點）。

步驟4 使用全排列遞歸算法，計算一次配送所經(jīng)過的各個客戶的各種可能路徑的通行時間，通過比較得出其中一條最短時間路徑，算出最短時間，并給出本次配送的途經(jīng)節(jié)點順序，便于本次調度安排。全排列算法已經(jīng)非常成熟，在這里不再贅述。

4 算法仿真

Floyd算法是一種用于計算所有節(jié)點對的最短路徑的常用算法。在這里采用通行時間來代替距離，且在算法中增加了交叉路口等待時間，用來計算城市配送中的最快路徑。我們來看一個具體的例子。

例：圖1表示了一個城市交通的網(wǎng)絡圖，V1，V2，V3，V4，V5，V6分別表示6個交通節(jié)點，其中的數(shù)字表示路口等待時間，相連接的邊表示交通節(jié)點間的道路，權重表示通行時間，單位為分鐘。其中，雙向邊表示兩節(jié)點間的通行時間不同，單向邊表示單向通行，無向邊表示雙向通行的時間無差異。現(xiàn)實中，配送中心通常設在城市邊緣，其雙向通行時間會隨著出入城車輛數(shù)量的動態(tài)變化而有所不同，在圖中我們使用雙向邊來表示。假定配送中心位于V1處，現(xiàn)在需要完成一項配送任務，此次配送的兩個客戶分別位于V5、V6，我們該如何選擇最快配送路線，最快時間是多少？

圖1 城市配送網(wǎng)絡示意圖

步驟1 根據(jù)Floyd算法，得出初始時間代價矩陣T0(i,j)（見表1）、前驅節(jié)點矩陣P0(i,j)（見表2）、路口等待時間數(shù)組W[i]={0.5,0.5,0.5,0.5,0.5,0.5}。

表1 時間代價矩陣T0(i,j)

表2 前驅節(jié)點矩陣P0(i,j)

值得注意的是，時間代價矩陣是不對稱的，標明了有些路段雙向通行時間不相同，符號“∞”表示不可達。

步驟2 通過計算經(jīng)過中間跳點V1來更新時間代價矩陣為T1(i,j)（見表3）、前驅節(jié)點矩陣P1(i,j)（見表4）。更新原則：

例如：在T0(I,j)里，V2→V3的時間權重為∞，經(jīng)更新后為 20.5，通過判斷 T[2][3].time＞T[2][1].time+T[1][3].time+W[1]，即∞＞10+10+0.5，故將 T[2][3].time更新為20.5，同時在前驅節(jié)點矩陣中V2→V3的前驅節(jié)點標記為1，即此時V2→V3需途經(jīng)V1中轉。

表3 時間代價矩陣T1(i,j)

表4 前驅節(jié)點矩陣P1(i,j)

步驟3繼續(xù)更新時間代價矩陣和至T6(i,j)（見表5）和P6(i,j)（見表6），即分別計算經(jīng)過V2，V3，V4，V5，V6中轉的最快時間，從任一節(jié)點至任一節(jié)點。

表5 時間代價矩陣T6(i,j)

表6 前驅節(jié)點矩陣P6(i,j)

例如：V1→V6,最快時間為 38min，路徑為 V1→V3→V4→V6，總時間為10+0.5+15+0.5+12，表示經(jīng)過了兩個路口，等待時間為0.5+0.5。

步驟4 本次配送需要從配送中心V1出發(fā)一次送完兩個客戶V5、V6，然后返回配送中心V1，計算出最短時間和最快路徑。使用成熟的全排列遞歸算法，進行比較后得出最短時間。例如：按照全排列規(guī)則，需要計算和比較以下的路徑：V1V5V6V1、V1V6V5V1，它們所用的時間分別為83.5min、81min，由此可知，最短時間為81min，其路徑V1V6V5V1，它的具體路徑為V1→V3→V4→V6→V5→V4→V2→V1。值得注意的是，在該路徑中，節(jié)點V4經(jīng)過了兩次，這是根據(jù)實際情況而選定的。

至此，我們得出了此次配送的最短時間和最快路徑。

5 結束語

本文選擇Floyd算法來計算最快路徑，是因為該算法能夠滿足兩種情形：配送時，一次配送任務通常需要滿足不止一個客戶，也即一次計算可以得出一條包含往返的最快路徑；城市中通常會出現(xiàn)單行道路和通行時間不對稱道路。但是，F(xiàn)loyd算法的時間復雜度比其他算法復雜，我們可以將一條較長的道路作為一條通行路段來看，而不必按照交叉路口所分割的路段數(shù)量來計算，這與實際的配送情形是一致的，也即正常情況下，在確定了配送客戶后，我們可供選擇的路徑是有限的。

[1]趙青,朱樂天.基于ArcGIS的最短路徑算法在城市交通中的應用[J].航空計算技術,2014,(2):14-17.

[2]錢民,唐克生.基于定性動態(tài)概率網(wǎng)絡的交通狀態(tài)預測及改進[J].云南大學學報(自然科學版),2012,(2):165-168.

[3]楊浩雄,王丹,張敬蕤.基于蟻群算法的擁堵交通最短路徑研究[J].計算機仿真,2015,(32):186-191.

[4]趙慧娟,湯兵勇,張云.基于動態(tài)規(guī)劃法的物流配送路徑的隨機選擇[J].計算機應用與軟件,2013,(30):110-112.

[5]李曉東,王東,曾凡智,陳俊健.城市交通時間最短路徑計算模型及應用仿真[J].計算機仿真,2014,(31):172-175.

[6]E Kanoulas,Du Yang,Xia Tian,Zhang Donghui.Finding Fastest Paths on A Road Network with Speed Patterns[A].Proceedings of the 22nd International Conference on Data Engineering[C].2006．

Selection of Fastest Route in Urban Distribution Based on Floyd Algorithm

Tang Kesheng,Qian Min,Duan Limei,Wang Bin
(Kunming Metallurgy College,Kunming 650033,China)

In this paper,we proposed a method for the selection of the fastest route based on the big data on vehicle travelling time,then having fully considered road congestion and the waiting time at crossroads and traffic lights,substituted distance with travelling time and at the end,used the improved Floyd algorithm to identify the fastest distribution route.

big data;urban distribution;fastest route;time cost;Floyd algorithm

F224.0;F252.14

A

1005-152X(2017)09-0101-04

10.3969/j.issn.1005-152X.2017.09.023

2017-08-03

云南省教育廳項目（2015Y550）；昆明冶金高等?？茖W校項目（2016xjsk06）

唐克生（1974－），男，云南華寧人，講師，工學碩士，主要研究方向：物流工程技術、智能數(shù)據(jù)處理。