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

羅義學

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

0 引 言

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

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

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

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

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

1.1 物流配送網絡的智能Petri網描述

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

圖1 智能Petri網

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

1.2 物流配送網絡的智能petri網

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

圖2 物流配送網絡的圖模型

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

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

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

圖3 物流配送網絡的智能Petri網模型

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

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

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

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

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

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

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

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

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

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

2 實例分析

本文采用文獻[8]中的算例，并與改進的Dijkstra算法求解進行對比，以此來論證算法的可行性、有效性。基于智能petri網的物流配送路徑優(yōu)化算法流程如圖4所示。

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

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

圖5 算例的物流配送網絡

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

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

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

(1)將算例的物流配送網絡轉化為智能Petri網模型，托肯運行的方向用箭頭表示。在第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中的托肯仍然處于“進入庫所中延時”狀態(tài)。變遷t6在第12時刻“路途耗時完成”，托肯進入庫所P7中處于“延時完成”狀態(tài)，實施變遷t10。變遷t3，t10沒有“路途耗時完成”，則繼續(xù)耗時。(如圖8(b)所示)。

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

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

圖8 不同時刻智能Petri網

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

3 結束語

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

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

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

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

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

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

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

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

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

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