羅義學(xué)

(1.北京科技大學(xué)機(jī)械工程學(xué)院，北京100083；2.南寧市公安局交通警察支隊，廣西南寧530022)

0 引 言

送貨時間是衡量物流配送水平的一個非常重要標(biāo)準(zhǔn)。物流配送的目標(biāo)是準(zhǔn)時、準(zhǔn)確和快速，因此路徑優(yōu)化是物流配送的關(guān)鍵環(huán)節(jié)。其作用是高效地計算出配送車輛到目的地的最佳路徑，實現(xiàn)對配送車輛出行路徑的優(yōu)化，引導(dǎo)車輛沿最優(yōu)路徑到達(dá)目的地。物流配送路徑優(yōu)化，對物流企業(yè)提高服務(wù)水平、降低物流成本、提高競爭力和增加經(jīng)濟(jì)效益具有十分重要的理論和現(xiàn)實意義。

物流配送路徑優(yōu)化的關(guān)鍵是最優(yōu)路徑(SP)算法，Dijkstra算法是解決最優(yōu)路徑問題中的經(jīng)典算法[2]。在實際物流配送網(wǎng)絡(luò)，各個路段的行駛時間及交叉口延誤共同組成的交通阻抗將直接影響配送車輛的路徑選擇[3]。調(diào)查表明車輛在交叉口的時間延遲占整個出行時間的20%-40%[4]。因此在配送網(wǎng)絡(luò)中距離最短路徑并不一定是最優(yōu)路徑，車輛受交叉口時間延誤的影響，最優(yōu)路徑可能是距離相對較長而用時最短的一條路徑[5]。對于物流配送網(wǎng)絡(luò)來說，配送車輛在交叉口處的時間延誤與其在路段上的行駛時間相比同樣重要。因此建立一種考慮實際交通阻抗的物流配送路徑優(yōu)化算法，使求解的最優(yōu)路線符合實際交通情況，具有重要的理論和現(xiàn)實意義。

Petri網(wǎng)是一種圖形化的建模工具，它不僅可以刻畫系統(tǒng)結(jié)構(gòu)，而且可以描述系統(tǒng)的動態(tài)行為，它能精確地描述事件之間的順序、并發(fā)、同步等關(guān)系，適合于描述離散事件的動態(tài)過程[6-7,9]。Petri網(wǎng)模型是目前離散事件動態(tài)系統(tǒng)建模中最活躍的技術(shù)之一。物流配送路徑選擇是典型的離散事件系統(tǒng)，所以選擇Petri網(wǎng)對物流配送路徑選擇進(jìn)行模擬比較合適。

1 基于智能Petri網(wǎng)的物流配送路徑優(yōu)化算法

物流配送網(wǎng)絡(luò)是相對復(fù)雜且處在動態(tài)變化中的系統(tǒng)，因此需要在基本Petri網(wǎng)的基礎(chǔ)上進(jìn)行擴(kuò)展，建立一種可以描述物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)，并通過制定一些簡單的運行規(guī)則來建立最優(yōu)路徑的選擇方法。本文給出的物流配送路徑優(yōu)化算法主要由物流配送網(wǎng)絡(luò)智能Petri網(wǎng)和路徑優(yōu)化運行規(guī)則兩部分組成。

1.1 物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)描述

智能Petri網(wǎng)(intelligent Petri net)是在基本Petri網(wǎng)基礎(chǔ)上的拓展，是可以描述系統(tǒng)組織結(jié)構(gòu)和系統(tǒng)狀態(tài)動態(tài)變化的一種系統(tǒng)模型[7]。它由庫所Pi(用圓圈表示)、變遷ti(用矩形方塊表示)以及連接庫所、變遷的線段和庫所中的托肯(用小黑點表示)構(gòu)成。如圖1所示給出的智能Petri網(wǎng)由5個庫所(Pi(i=1,2,…,5)、4 個變遷 ti(i=1,2,3,4)及 8 條連線構(gòu)成。

圖1 智能Petri網(wǎng)

對智能Petri網(wǎng)進(jìn)行賦時，即當(dāng)某一變遷的發(fā)生條件滿足時，延遲一段時間后從相應(yīng)的輸入庫所中移走相應(yīng)的托肯。智能Petri網(wǎng)中的庫所Pi標(biāo)上的時間值tpi稱為庫所時間，對應(yīng)的庫所稱為時間庫所。定義：①托肯運行方向集T：當(dāng)托肯處在某庫所時，通過變遷與該庫所直接連接的庫所組成的集合。②托肯經(jīng)過庫所集S：托肯達(dá)到目標(biāo)庫所經(jīng)過的庫所的集合。如：T3={P1,P2,P3,P4,P5}，S1={P1}，S5={P5}。

1.2 物流配送網(wǎng)絡(luò)的智能petri網(wǎng)

物流配送網(wǎng)絡(luò)由交叉口和路段組成。根據(jù)圖論可以將物流配送網(wǎng)絡(luò)抽象為節(jié)點、邊的元素集和他們相互關(guān)系描述的一張圖G，G=G(V,E,W)，其中V表示節(jié)點vi的集合；E為有向弧eij的集合；W為權(quán)值Wij的集合，表示配送車輛在路段上行駛的時間。物流配送網(wǎng)絡(luò)的圖模型如圖2所示，配送車輛在路段上的行程時間標(biāo)注于圖中弧段的旁邊。

圖2 物流配送網(wǎng)絡(luò)的圖模型

物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)描述：庫所Pi代表配送網(wǎng)絡(luò)的節(jié)點Vi；當(dāng)節(jié)點Vi與Vj之間有連線時，表示庫所Pi與Pj之間存在變遷tij，若無連線時表示庫所之間不存在變遷。配送車輛用托肯表示，配送車輛在路段上行駛的時間用庫所Pi與Pj間的變遷tij消耗值表示。物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)模型如圖3所示。

求配送車輛所在的節(jié)點Vi到目標(biāo)客戶所在節(jié)點Vj的最優(yōu)路徑問題，即轉(zhuǎn)化為時間庫所Pi經(jīng)過變遷到達(dá)時間庫所Pj的最小消耗。初始條件為托肯在庫所Pi，滿足的約束為托肯經(jīng)過變遷所用的時間消耗最小，托肯按照變遷的規(guī)則，使托肯逐步到達(dá)目標(biāo)庫所Pj，求得托肯經(jīng)過庫所集Sj，即求得最優(yōu)路徑。

相對于物流配送網(wǎng)絡(luò)圖模型，物流配送網(wǎng)絡(luò)智能Petri網(wǎng)模型可以實現(xiàn)配送過程的動態(tài)模擬。

圖3 物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)模型

1.3 智能Petri網(wǎng)路徑選擇運行規(guī)則

在描述物流配送網(wǎng)絡(luò)的智能petri網(wǎng)建立以后，需要對物流配送路徑的選擇進(jìn)行定義，以實現(xiàn)物流配送路徑選擇的優(yōu)化。以圖2為例，配送車輛位于節(jié)點Vi，目標(biāo)客戶位于節(jié)點Vj，配送車輛在路段上的行駛時間為定值，車輛在各交叉口的右轉(zhuǎn)、直行和左轉(zhuǎn)平均延誤的時間不同。求配送車輛所在節(jié)點Vi到目標(biāo)客戶所在節(jié)點 Vj的最優(yōu)路徑問題可以轉(zhuǎn)化為智能Petri網(wǎng)路中(如圖3所示)托肯在時間庫Pi經(jīng)過變遷到達(dá)時間庫所Pj的最小時間消耗。

因此最優(yōu)路徑的算法可以描述為，初始條件為托肯在庫所Pi，滿足的約束為托肯經(jīng)過變遷所用的時間消耗最小。以圖3為例，本論文定義最優(yōu)路徑選擇規(guī)則如下：

規(guī)則1：當(dāng)托肯在庫所P時，托肯的運行方向由可行方向集T'決定。T'區(qū)別于運行方向集T。當(dāng)托肯在庫所Pi時，變遷tik發(fā)生后，托肯到達(dá)庫所Pk，此時托肯的可行方向集為Tk'=Tk-{Pi}。

規(guī)則2：賦予時間庫所中的托肯兩種狀態(tài)：“進(jìn)入庫所中延時”狀態(tài)和“延時完成”狀態(tài)。當(dāng)托肯進(jìn)入時間庫所P，托肯處于“進(jìn)入庫所中延時”(用空心黑點來表示)狀態(tài)，庫所時間開始消耗，當(dāng)庫所時間耗時完成，托肯的狀態(tài)變?yōu)椤把訒r完成”(用實心黑點來表示)時，則實施某個變遷t，托肯將進(jìn)入輸出庫所。

規(guī)則3：托肯在庫所Pi“延時完成”后的運行方向由可行方向集Ti'決定；沿可行方向集Ti'分別實施變遷t，在變遷經(jīng)過“路途耗時完成”后，在對應(yīng)庫所集Ti'中的輸出庫所元素中放入一個托肯，并使托肯處于“進(jìn)入庫所中延時”狀態(tài)。輸入庫所Pi中的“延時完成”狀態(tài)的托肯被移出。

HLFs細(xì)胞(編號GNHu28)從中科院細(xì)胞庫購買。試劑有DMEM培養(yǎng)液、0.25%胰蛋白酶、胎牛血清(美國 Gbico)，Tβ4(美國 RegeneRx)，DAPI、鼠抗人a-SMA抗體(美國Sigma)，兔抗人GAPDH、HI心標(biāo)記的羊抗兔、羊抗鼠IgG抗體(美國CST)，TRITC標(biāo)記的羊抗鼠 IgG(鼎國生物)，重組人TGF-β1(美國 R＆D)，BCA 蛋白濃度檢測試劑盒(美國pierce)，CCK-8試劑盒(日本同仁)。

規(guī)則4：當(dāng)一個庫所Pi存在一個托肯且該托肯處于“延時完成”狀態(tài)或者庫所Pi曾經(jīng)存在過托肯，而另外一個庫所Pj中的托肯經(jīng)過變遷t的輸出庫所為Pi，則變遷t不再實施，將庫所Pj的中托肯移出網(wǎng)絡(luò)。即每一個庫所只能接受唯一一個變遷的“延時完成”托肯。

規(guī)則5：當(dāng)一個庫所Pi存在一個托肯且該托肯處于“進(jìn)入庫所中延時”狀態(tài)或者庫所Pi曾經(jīng)存在過托肯，而另外一個庫所Pj的中托肯經(jīng)過變遷t的輸出庫所為Pi，則實施變遷，托肯進(jìn)入輸出庫所Pi，與其它托肯一起處于“進(jìn)入庫所中延時”狀態(tài)，Pi中最先處于“延時完成”狀態(tài)的托肯開始按照可行方向集Ti'運行，庫所Pi中的其余托肯移出網(wǎng)絡(luò)。

規(guī)則6：當(dāng)目標(biāo)庫所Pj中擁有托肯時，則計算終止，到達(dá)目標(biāo)庫所的托肯經(jīng)過的庫所集S，即為最優(yōu)路徑。

2 實例分析

本文采用文獻(xiàn)[8]中的算例，并與改進(jìn)的Dijkstra算法求解進(jìn)行對比，以此來論證算法的可行性、有效性?；谥悄躳etri網(wǎng)的物流配送路徑優(yōu)化算法流程如圖4所示。

圖4 基于智能petri網(wǎng)的物流配送路徑優(yōu)化算法流程

算例：如圖5所示物流配送網(wǎng)絡(luò)圖，配送車輛位于節(jié)點V1，目標(biāo)客戶位于節(jié)點V9。配送車輛在路段上的行駛時間標(biāo)注于圖中弧段的旁邊。配送車輛在各交叉口的右轉(zhuǎn)、直行和左轉(zhuǎn)平均延誤時間分別為0、2、3(時間單位：min)，計算配送車輛從V1到達(dá)目標(biāo)客戶V9的最優(yōu)路徑。

圖5 算例的物流配送網(wǎng)絡(luò)

基于經(jīng)典的Dijkstra算法求得在不考慮交叉口延誤時的最優(yōu)路徑，如圖6中粗實線所示：最優(yōu)路徑有3條V1V4V7V8V9，V1V4V5V8V9，和V1V4V5V6V9。然后根據(jù)文獻(xiàn)[8]的改進(jìn)的Dijkstra算法求得在考慮交又口延誤時的最優(yōu)路徑，如圖7中粗實線所示：最優(yōu)路徑為V1V4V5V8V9。

圖6 不考慮交又口延誤時的最優(yōu)路徑

圖7 考慮交又口延誤時的最優(yōu)路徑(改進(jìn)的Dijkstra算法)

(1)將算例的物流配送網(wǎng)絡(luò)轉(zhuǎn)化為智能Petri網(wǎng)模型，托肯運行的方向用箭頭表示。在第0時刻，庫所P1的庫所時間tp1=0，T1'={p2,p4}。P2和 P4中均沒有托肯，實施變遷 t1和 t2。(如圖8(a)所示)。

(2)在第13時刻，變遷t8的輸入庫所P5中的托肯處于“延時完成”狀態(tài)，實施變遷t8。由于P2、P5中都有托肯，且處于“延時完成”狀態(tài)，不實施變遷t4。變遷t9的輸入庫所P5中的托肯仍然處于“進(jìn)入庫所中延時”狀態(tài)。變遷t6在第12時刻“路途耗時完成”，托肯進(jìn)入庫所P7中處于“延時完成”狀態(tài)，實施變遷t10。變遷t3，t10沒有“路途耗時完成”，則繼續(xù)耗時。(如圖8(b)所示)。

(3)在第22時刻，由變遷t9進(jìn)入輸出庫所P8的托肯在P8中首先達(dá)到“延時完成”狀態(tài)，因此由變遷t10進(jìn)入輸出庫所P8的托肯被移出網(wǎng)絡(luò)。實施變遷t12，且t12沒有“路途耗時完成”，則繼續(xù)耗時。此時，P6中的托肯“延時完成”，實施變遷t11，變遷t11沒有“路途耗時完成”，則繼續(xù)耗時。由于P6中已經(jīng)有托肯，且處于“延時完成”狀態(tài)，不實施變遷t7，并將P3托肯移出網(wǎng)絡(luò)。(如圖 8(c)所示)。

(4)在第25時刻，變遷t12“路途耗時完成”，托肯進(jìn)入P9，且托肯處于“延時完成”狀態(tài)。因為P9就是目標(biāo)庫所，運行完畢。托肯經(jīng)過的庫所集合為S={P1,P4,P8,P9}，即最短路徑為V1V4V5V8V9。(如圖 8(d)所示)。

圖8 不同時刻智能Petri網(wǎng)

可見，應(yīng)用基于智能PETRI網(wǎng)的物流配送路徑優(yōu)化算法得出的最優(yōu)路徑與改進(jìn)的 Dijkstra算法得出的最優(yōu)路徑是一致的。運用該算法，可以得到配送車輛從出發(fā)點到城市中任何一個節(jié)點的最優(yōu)路徑。比如車輛從V1到達(dá)目標(biāo)客戶V6的最優(yōu)路徑為V1V4V5V6，耗用的時間為19個單位時間。

3 結(jié)束語

本文利用智能 Petri網(wǎng)在描述離散事件動態(tài)過程上的優(yōu)點，考慮配送車輛受交叉口時間延誤的影響，建立了物流配送網(wǎng)絡(luò)的智能Petri網(wǎng)，并通過定義運行規(guī)則，給出了基于智能Petri網(wǎng)的物流配送路徑優(yōu)化算法與計算流程。經(jīng)算例與改進(jìn)的Dijkstra算法相比，論文提出的算法不需要對物流網(wǎng)絡(luò)圖作任何修改，同時還可實現(xiàn)配送過程的動態(tài)模擬。實際上物流路徑的選擇過程是十分高智能、復(fù)雜的，本文給出的路徑選擇的規(guī)則，雖然較全面的考慮了路徑選擇的一些特性，但仍然需要在實際應(yīng)用過程中不斷修正和改進(jìn)。后續(xù)研究可以將該算法應(yīng)用到物流仿真技術(shù)之中。

[1]趙建有.道路交通運輸系統(tǒng)工程[M].北京:人民交通出版社,2004:199-201.

[2]王勇,池潔.物流配送路線及配送時間的優(yōu)化分析[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2008,27(4):647-650.

[3]邵春福.交通規(guī)劃原理 [M].北京:中國鐵道出版社,2004:174-183.

[4]何鵬,李文鋒.基于隨機(jī)Petri網(wǎng)的物流配送流程建模與分析[J].武漢理工大學(xué)學(xué)報·信息與管理工程版,2010,32(3):434-436.

[5]朱文興,賈磊,丁緒東,等.城市交通網(wǎng)絡(luò)中的路徑優(yōu)化研究[J].山東大學(xué)學(xué)報(工學(xué)版),2005,35(1):74-77.

[6]張梅青,周葉.Petri網(wǎng)理論在物流管理中的應(yīng)用研究綜述[J].物流技術(shù),2010(7):13-16.

[7]楊世強(qiáng),張海峰,李德信.基于Petri網(wǎng)的FMS物流系統(tǒng)建模與仿真[J].計算機(jī)工程與應(yīng)用,2008,44(22):226-228.

[8]樊月珍,江發(fā)潮,毛恩榮.車輛行駛最優(yōu)路徑優(yōu)化算法設(shè)計[J].計算機(jī)工程與設(shè)計,2007,28(23):5758-5761.

[9]石春玲,杜玉越.基于邏輯Petri網(wǎng)的物流配送系統(tǒng)建模[J].系統(tǒng)仿真學(xué)報,2007,19(1):114-117.