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

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

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

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

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

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

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

1 引言

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

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

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

2 影響道路通行時(shí)間的因素

2.1 天氣條件

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

2.2 通行時(shí)段

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

2.3 交通路口數(shù)量

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

本文中，天氣條件、通行時(shí)段對(duì)通行的影響可以通過該種條件下通行時(shí)間的長短得到反映，交通路口的等待時(shí)間則單獨(dú)標(biāo)記。

3 最快路徑選擇

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

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

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

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

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

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

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

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

4 算法仿真

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

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

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

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

表1 時(shí)間代價(jià)矩陣T0(i,j)

表2 前驅(qū)節(jié)點(diǎn)矩陣P0(i,j)

值得注意的是，時(shí)間代價(jià)矩陣是不對(duì)稱的，標(biāo)明了有些路段雙向通行時(shí)間不相同，符號(hào)“∞”表示不可達(dá)。

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

例如：在T0(I,j)里，V2→V3的時(shí)間權(quán)重為∞，經(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，同時(shí)在前驅(qū)節(jié)點(diǎn)矩陣中V2→V3的前驅(qū)節(jié)點(diǎn)標(biāo)記為1，即此時(shí)V2→V3需途經(jīng)V1中轉(zhuǎn)。

表3 時(shí)間代價(jià)矩陣T1(i,j)

表4 前驅(qū)節(jié)點(diǎn)矩陣P1(i,j)

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

表5 時(shí)間代價(jià)矩陣T6(i,j)

表6 前驅(qū)節(jié)點(diǎn)矩陣P6(i,j)

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

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

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

5 結(jié)束語

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

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

[2]錢民,唐克生.基于定性動(dòng)態(tài)概率網(wǎng)絡(luò)的交通狀態(tài)預(yù)測(cè)及改進(jìn)[J].云南大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,(2):165-168.

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

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

[5]李曉東,王東,曾凡智,陳俊健.城市交通時(shí)間最短路徑計(jì)算模型及應(yīng)用仿真[J].計(jì)算機(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

云南省教育廳項(xiàng)目（2015Y550）；昆明冶金高等?？茖W(xué)校項(xiàng)目（2016xjsk06）

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