郭麗　劉磊　緱西梅

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

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

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

0引言

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

路徑優(yōu)化是物流配送中的核心問(wèn)題。路徑優(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ù)，例如等級(jí)、長(zhǎng)度、類別、行程時(shí)間或延誤時(shí)間等；還具有空間屬性數(shù)據(jù)，例如空間位置。本項(xiàng)目將路網(wǎng)信息使用圖來(lái)進(jìn)行表達(dá)，表示方式如下：

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

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

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

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

本文將物流配送網(wǎng)絡(luò)使用有向圖G=（V，E，W）來(lái)表示。其中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（簡(jiǎn)稱OSM）是一個(gè)網(wǎng)上地圖協(xié)作計(jì)劃， OSM地理數(shù)據(jù)文件既包含了地理數(shù)據(jù)，又包含了對(duì)元數(shù)據(jù)的描述。每一個(gè)地理元素都擁有對(duì)應(yīng)的元數(shù)據(jù)，用于記錄數(shù)據(jù)修改的額時(shí)間、修改帳號(hào)和作者名稱等等。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通過(guò)經(jīng)緯度定義了一個(gè)地理坐標(biāo)點(diǎn)。同時(shí)，通過(guò)place=* and name=*來(lái)表示對(duì)象的名稱。其他一些可選信息，如name等，在tag子標(biāo)簽中表示。

1.1.2 Way路線

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

1.1.3 Realation關(guān)系

是有序列表nodes，ways和relations（合起來(lái)稱為members成員）組成的，每一個(gè)成員可以選擇擁有一個(gè)role角色，相互的關(guān)系通過(guò)role來(lái)定義。關(guān)系用來(lái)表示已經(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ù)一樣，存儲(chǔ)關(guān)系和邏輯關(guān)系是一種矢量關(guān)系，組成的點(diǎn)線面對(duì)象同樣包括有對(duì)象的外在屬性、對(duì)象的拓展與對(duì)象的空間位置。因此本項(xiàng)目中路網(wǎng)數(shù)據(jù)的拓樸關(guān)系是對(duì)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ù)格式如下所示。

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

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

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

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

2.1行駛距離

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

2.2平均行程時(shí)間

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

2.3擁堵程度

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

物流配送路徑選擇時(shí)，首先需要預(yù)定配送時(shí)間，行駛距離，當(dāng)前時(shí)段的擁堵程度等綜合情況。因此本項(xiàng)目設(shè)計(jì)了綜合路阻函數(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)間的最短距離時(shí)，將通過(guò)上一節(jié)所示方法求得任意兩路段間的路徑長(zhǎng)度、擁堵程度以及行駛時(shí)間，并通過(guò)綜合路阻函數(shù)求得任意兩路段間的出行費(fèi)用，具體格式如下：

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

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

4總結(jié)

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

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

參考文獻(xiàn)

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

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

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