基于綜合路阻函數(shù)的多源最短路徑計算

郭麗　劉磊　緱西梅

摘 要 路徑優(yōu)化是物流配送方案中最核心的問題。本文提出考慮行駛距離、擁堵程度及平均行駛時間的綜合路阻函數(shù)計算方法，并提取OSM地圖中路段數(shù)據(jù)構(gòu)建有向圖，基于Dijkstra算法求得最短路徑。

關(guān)鍵詞 路徑優(yōu)化 綜合路阻函數(shù) Dijkstra算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

0引言

高效率合理的配送是物流系統(tǒng)順利運(yùn)行的保證，配送線路安排的合理與否對配送速度、成本、效益影響很大。正確合理地安排車輛的配送線路，實(shí)現(xiàn)合理的線路運(yùn)輸，可以有效地節(jié)約運(yùn)輸時間，增加車輛利用率，從而降低運(yùn)輸成本，提高企業(yè)經(jīng)濟(jì)效益與客戶服務(wù)水平，使企業(yè)達(dá)到科學(xué)化的物流管理，？這也是企業(yè)提高自身競爭力的有效途徑之一。

路徑優(yōu)化是物流配送中的核心問題。路徑優(yōu)化總的解決思路如下：

（1）路網(wǎng)的表示

（2）道路權(quán)重的標(biāo)定

（3）最短路徑算法求解

（4）把圖中的最短路徑還原成現(xiàn)實(shí)路網(wǎng)中的路段集

1路網(wǎng)的表示

交通路網(wǎng)的構(gòu)成實(shí)體不僅具有非空間屬性數(shù)據(jù)，例如等級、長度、類別、行程時間或延誤時間等；還具有空間屬性數(shù)據(jù)，例如空間位置。本項(xiàng)目將路網(wǎng)信息使用圖來進(jìn)行表達(dá)，表示方式如下：

（1）頂點(diǎn)：代表道路的交叉口或者終點(diǎn)，Vertex記作V。

（2）邊：代表兩個結(jié)點(diǎn)之間的一條可以互通的有方向的道路，Edge記作E。

（3）權(quán)值：代表路段的某些特征屬性的量化，如路段長度、獨(dú)斷平均行程時間，即道路權(quán)重。Weight記作W。

一般來說，路段兩個方向的交通流情況并不一致，當(dāng)采用與交通流有關(guān)的擁堵計算時，采用有向圖更為合適，并且有向圖跟有利于處理單行線、轉(zhuǎn)向等特殊情況。所以本項(xiàng)目將路網(wǎng)抽象成為一個賦權(quán)有向圖，從而確定路網(wǎng)中某兩地間的最優(yōu)路線問題，轉(zhuǎn)化為圖論中的最短路徑問題。

本文將物流配送網(wǎng)絡(luò)使用有向圖G=（V，E，W）來表示。其中V為頂點(diǎn)集，V={Vi|i=1，2，…n}；E為邊集，E={e（Vi，Vj）|Vi，Vj∈V}；W為權(quán)值集W={W（Vi，Vj）|Vi，Vj∈V}。

1.1 OpenStreetMap

OpenStreetMap（簡稱OSM）是一個網(wǎng)上地圖協(xié)作計劃， OSM地理數(shù)據(jù)文件既包含了地理數(shù)據(jù)，又包含了對元數(shù)據(jù)的描述。每一個地理元素都擁有對應(yīng)的元數(shù)據(jù)，用于記錄數(shù)據(jù)修改的額時間、修改帳號和作者名稱等等。OSM地理數(shù)據(jù)的描述采用的是一種包含拓?fù)湫再|(zhì)的數(shù)據(jù)結(jié)構(gòu)，其中與道路相關(guān)的地理元素主要包括節(jié)點(diǎn)（Node）和道路（Way）以及關(guān)系（Relation）。

1.1.1 Node節(jié)點(diǎn)

Node節(jié)點(diǎn)包括經(jīng)緯坐標(biāo)和高度信息。node通過經(jīng)緯度定義了一個地理坐標(biāo)點(diǎn)。同時，通過place=* and name=*來表示對象的名稱。其他一些可選信息，如name等，在tag子標(biāo)簽中表示。

1.1.2 Way路線

Way表示地圖中的一條線路，通過2-2000個點(diǎn)（nodes）構(gòu)成。Way可表示如下3種。非閉合線，首尾不閉合的線路，通?？捎糜诒硎粳F(xiàn)實(shí)中的道路、河流、鐵路等。閉合線，首尾相連的線路，例如可以表示現(xiàn)實(shí)中的環(huán)線地鐵。區(qū)域，閉合區(qū)域，通常使用landuse=* 來標(biāo)示區(qū)域等。

1.1.3 Realation關(guān)系

是有序列表nodes，ways和relations（合起來稱為members成員）組成的，每一個成員可以選擇擁有一個role角色，相互的關(guān)系通過role來定義。關(guān)系用來表示已經(jīng)存在的nodes和ways之間的關(guān)系。

1.2數(shù)據(jù)解析及轉(zhuǎn)換

作為一種以研究和共享為目的的空間路網(wǎng)數(shù)據(jù)，OSM 數(shù)據(jù)基元的屬性值非常豐富，其盡可能地充分表達(dá)空間數(shù)據(jù)，以便不同領(lǐng)域的數(shù)據(jù)使用者方便提取。

OSM 路網(wǎng)數(shù)據(jù)和其他 GIS 數(shù)據(jù)一樣，存儲關(guān)系和邏輯關(guān)系是一種矢量關(guān)系，組成的點(diǎn)線面對象同樣包括有對象的外在屬性、對象的拓展與對象的空間位置。因此本項(xiàng)目中路網(wǎng)數(shù)據(jù)的拓樸關(guān)系是對Node和Node、Node和Way、Way和Way之間的相關(guān)關(guān)系、Relation與Relation之間的關(guān)系屬性的數(shù)據(jù)描述。

首先，獲取需進(jìn)行配送的物流網(wǎng)絡(luò)中的節(jié)點(diǎn)列表，其中節(jié)點(diǎn)使用經(jīng)緯度表示，數(shù)據(jù)格式如下所示。

其中，每一行代表一個待配送網(wǎng)點(diǎn)的地址信息，第一個數(shù)字代表網(wǎng)點(diǎn)地址的經(jīng)度，第二個數(shù)字代表網(wǎng)點(diǎn)地址的緯度。

如圖1所示，在拿到待配送網(wǎng)點(diǎn)信息后，文件中的所有的點(diǎn)構(gòu)成了路網(wǎng)的初始點(diǎn)集V，通過循環(huán)讀取點(diǎn)集中的頂點(diǎn)，去ways表中查找是否有以該頂點(diǎn)為弧頭的邊，有則將該邊上存在的所有nodes加入到點(diǎn)集中，并建立對應(yīng)的邊集E。由此建立，獲取配送網(wǎng)點(diǎn)之間的詳細(xì)路網(wǎng)。

2路網(wǎng)邊權(quán)評價方法

路網(wǎng)的邊權(quán)代表了當(dāng)前兩點(diǎn)之間的出行代價，很多學(xué)者也稱之為路阻。對于路網(wǎng)邊權(quán)的評價，實(shí)際上就是路阻函數(shù)的設(shè)計過程，即出行費(fèi)用的計算過程。從可計量性和數(shù)據(jù)可獲得性方面考慮，在實(shí)際考慮出行費(fèi)用時，一般都采用被占用的時間或者能夠反映被占用時間長短的其他指標(biāo)，例如排隊(duì)長度、耗油量、擁擠程度等等。因此在路徑選擇中，我們設(shè)計了考慮出行時間、行駛距離和擁擠程度三方面的綜合路阻函數(shù)。

2.1行駛距離

行駛距離是靜態(tài)的路阻數(shù)據(jù)，用C1i=Li表示，其中Li是路段i的長度。單獨(dú)使用行駛距離作為路阻函數(shù)時，較適用于網(wǎng)絡(luò)道路質(zhì)量相近、交通流分布均勻的情況，這時指定OD對之間的最佳路徑是固定不變的。

2.2平均行程時間

平均行程時間是最常用的動態(tài)路阻形式，用表示。指在第k個時段，車輛在該路段上運(yùn)行時所用的平均時間，包括形式時間和停車延誤時間。endprint

2.3擁堵程度

在交通網(wǎng)絡(luò)中，“擁擠”是指道路上的車輛不能以正常速度行駛的現(xiàn)象，表現(xiàn)為行駛時間延長和停車延誤增加。一般可用排隊(duì)商都和路段的流量與同性能力之比來衡量。本項(xiàng)目定義反映擁堵程度的路阻函數(shù)為C3i（k）=ti（k）/t0。其中，ti（k是k時段i路段的平均運(yùn)行時間，而是車輛以規(guī)定的最高速度通過該路段所需要的時間，是固定值。C3i（k）越小，擁堵程度越低，C3i（k）越大，擁擠程度越嚴(yán)重。

物流配送路徑選擇時，首先需要預(yù)定配送時間，行駛距離，當(dāng)前時段的擁堵程度等綜合情況。因此本項(xiàng)目設(shè)計了綜合路阻函數(shù)為：

Ci（k）=h（C1i，C2i（k），C3i（k））

=b1C1i- +b2C2i- （k）+b3C3i- （k）

3基于Dijkstra算法的最短路徑算法

本項(xiàng)目將求解配送網(wǎng)絡(luò)任意網(wǎng)點(diǎn)間的最短距離時，將通過上一節(jié)所示方法求得任意兩路段間的路徑長度、擁堵程度以及行駛時間，并通過綜合路阻函數(shù)求得任意兩路段間的出行費(fèi)用，具體格式如下：

第一列和第二列代表路段出點(diǎn)的經(jīng)緯度，第三列和第四列代表路段入點(diǎn)的經(jīng)緯度，最后一列代表路段上的出行費(fèi)用。

Dijkstra算法是從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路求得任意配送點(diǎn)間的最短送貨線路。

4總結(jié)

本文基于OSM開源地圖數(shù)據(jù)，獲取物流配送點(diǎn)中，配有交叉路口信息的有向圖。提出一種以擁堵系數(shù)及路徑長度作為權(quán)值的最短路徑求解方法，有效的提高了在物流配送中最短路徑的精確度。

基金項(xiàng)目：本文為河南省科技攻關(guān)計劃項(xiàng)目（162102310580，162102310582，172102210526，172102210593），河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（15B520040，16A520099，17B520042）研究成果。

參考文獻(xiàn)

[1] 劉海燕，李宗平，葉懷珍.物流配送中心選址模型[J].西南交通大學(xué)學(xué)報，2000，35（03）：311-314.

[2] 楊弋，顧幸生.物流配送車輛優(yōu)化調(diào)度的綜述[J]. 東南大學(xué)學(xué)報：自然科學(xué)版，2003，33（z1）：105-111.

[3] 廖良才，王棟，周峰.基于混合遺傳算法的物流配送車輛調(diào)度優(yōu)化問題求解方法[J].系統(tǒng)工程，2008，26（08）：27-31.endprint