基于Petri 網的拖車到達調度優化模型與仿真

蔡文學， 鐘冠恒， 胡清浩， 鐘慧玲

(華南理工大學經濟與貿易學院，廣東 廣州510006)

珠三角內河集裝箱碼頭進口集裝箱必須經過海關全部查驗后才能集中放行，由于堆場容量限制，集中到達的大量進港拖車只能在閘口外等待，導致城市交通要道阻塞. 以佛山三水港為例，進港拖車從下午5 點開始大量到達，1 h 后等待進港拖車的數量最多達60 輛，直到下午8 點才開始緩解.此問題在珠三角內河碼頭普遍存在.原因是珠三角城鎮一體化顯著，內河碼頭一般位于城鎮區域甚至接近城鎮中心的位置，大量等待進港的拖車阻礙了城市交通，由此產生的城市交通管制又影響了拖車運輸，進一步降低了物流效率.

解決港口等待拖車過多的方法，一是港口閘口設計優化，確定最優閘口通道量，文獻［1］使用排隊系統建立港口大門的作業模型，并仿真得到滿足通行量的港口最小通道數量;文獻［2］通過仿真測試港口閘口有效通行量確定閘口性能，分析港口最佳閘口數量，增加閘口單位時間內的通過量，從而減少等待進港拖車的數量. 二是港內堆場調度優化，通過提升港口堆場作業效率，縮短拖車在港內停留時間.文獻［3］通過優化拖車在港作業路徑，提高了堆場作業效率;文獻［4］提出港口內拖車調度的混合策略，通過離散事件仿真對混合策略的評價函數進行了優化，加快了港口內部運作速度. 三是拖車到達調度優化，緩解到達高峰. 文獻［5］用BCMP(Baskett Chandy Muntz Palacios)排隊網絡優化集卡到達調度，并用算例驗證了有效性;文獻［6］分析了拖車到達信息對港口利潤的影響，仿真證明拖車有序到達能減少港口運作成本.

珠三角內河集裝箱碼頭多屬于中小型碼頭，由于地理位置限制，碼頭面積有限. 隨著區域經濟的高速發展，多數港口的年吞吐量早已超過10 萬標準箱，港口堆場容量與閘口通道基本處于滿負荷狀態.因此，通過優化閘口設計和堆場作業調度難以解決等待拖車過多的問題.本文對進港拖車到達調度模式進行優化，將拖車隨機集中到達變為分批定量有序到達，緩解高峰時段拖車到達過多的問題，是解決目前珠三角內河集裝箱碼頭進港拖車交通擁堵和物流效率低下的可行方法.

基于拖車到達作業過程的離散隨機性與并發性的特點，建立了拖車到達作業過程的混合Petri網模型，對模型中庫所令牌的數量與時間戳屬性進行統計，分析進港拖車的到達數量、等待時間、最大隊長等參數，然后，利用Arena 仿真確定拖車調度方案，量化拖車調度優化效果.

1 拖車到達作業過程的Petri 網模型

1.1 拖車到達作業過程

拖車到達作業過程屬于線性流程. 具體流程如下:

(1)拖車到達:在港口閘口外等待堆場資源.

(2)入閘流程:堆場容量允許其進入后，拖車經過港口閘口進入堆場，拖車進入港口閘口、海關閘口交單驗單過程.

(3)堆場作業:拖車進入指定堆場，按業務類型完成提卸箱作業，完成作業后離開.

(4)出閘流程:拖車駛出港口閘口、海關閘口交單驗單過程.

(5)拖車離開:拖車完成作業后，經過海關閘口與港口閘口離開港口.

閘口通行取決于兩個條件:

(1)工作時間，以海關閘口工作時間為準.

(2)堆場能力，為避免堆場內拖車堵塞，影響作業效率，只有在堆場能力滿足時才能進港.

拖車到達港口屬于離散隨機事件，通過到達速率或到達間隔分布可以模擬港口拖車的到達規律.根據珠三角內河碼頭集中放行的特點，拖車到達速率隨時間改變，用變化的到達速率比單一間隔時間分布能更好地體現拖車到達規律，而非平穩泊松過程對車輛到達之類的多發獨立隨機事件有較好的模擬效果［7-8］.因此，采用用非平穩泊松過程模擬拖車的到達規律.

非平穩泊松過程中一次只有一個事件發生，且事件的發生互相獨立，在時間間隔［τB，τE］內事件發生量服從速率函數λ(τ)的泊松分布，因此，時段內事件發生期望數是與時間間隔τB-τE和速率函數λ(τ)有關的泊松隨機變量.

從時刻τB到時刻τE，業務類型x 拖車的到達期望值為

λ(τ)為某時段內某種業務類型拖車的到達速率函數，與業務類型x 及時間τ 有關，λx(τ)越大，在時間間隔［τB，τE］內事件發生次數越多.上述隨機變量可以在Petri 網中利用變遷的隨機發生來模擬拖車的隨機到達.

1.2 混合Petri 網模型

Petri 網具有簡單、描述并發事件能力強、過程直觀等特點，常用于描述異步的、并發的系統模型，并發展出多種高級Petri 網模型. 利用Petri 網描述配合仿真驗證的方法，在不同領域特別是港口物流研究中得到了廣泛應用［9-12］.

根據珠三角內河港口進港拖車的作業特點，本文通過對受控Petri 網、有色Petri 網、時延Petri 網以及隨機Petri 網的分析［13-15］.

令牌token 是Petri 網中流動的實體，表示實際作業的拖車.采用混合Petri 網模型

Σ= (P，T，F，M，C，B，K，I，H)

進行建模，其中:

(P，T，F)是基本Petri 網，P 為有限庫所集，T 為有限變遷集，F 為庫所集到變遷集的有向流集合.

Pq∈P 為隊列庫所集，表示拖車隊列的庫所.

Pd∈P 為時延庫所集，表示令牌在庫所中隨機逗留一段時間后才能離開.

Pc∈P 為選擇庫所集，表示令牌在庫所中按規則集R 選擇即將發生的變遷，用于表達拖車在作業過程中對不同路徑或閘口的選擇.

Ta∈T 為隨機變遷集，變遷隨機發生的期望值Λ(tB，tE)(式(1))與速率函數λ(t)有關. 用于表示各業務拖車的隨機到達.

Tr∈T 為時延變遷集，用□表示，即變遷需要通過一個隨機時延才能完成，每個時延變遷可看成兩個瞬時變遷與一個時延庫所的集合.

Tc∈T 為受控變遷集.

Tu∈T 為非受控變遷集，表示閘口或堆場作業的隨機時延.

M 為網的標識集;

C 為控制庫所集，

C∩P=?;

B 為從控制庫所影響可控變遷的有向弧集，它的元素稱為控制弧，表示受堆場容量限制的拖車放行條件，

B?C×Tc;

K 為令牌顏色集，用于標記拖車業務類型與到達時間、離開時間等時間戳，

K={k1，k2，…};

H 為全局時鐘，作為時間戳的記錄標準;

I 為抑止弧集，

I?P×T， I∩F=?.

若

(1)?p∈P∶(p，t)∈F→M(p)≥1，

(2)?p∈P∶(p，t)∈I→M(p)=0.

對t 有M［t ＞.即當抑止弧前端庫所存在令牌時，阻止抑止弧末端的變遷執行，用以表達拖車進入的優先級.

1.3 變遷使能條件

?p∈·t，若(p，t)∈F，且M(p)≥W(p，t)，則對t∈T，t 具有發生權，稱t 標識M 下使能.而對混合網Σ，當且僅當M(p)≥W(p，t)且控制u 使能時，變遷t∈Tc才能發生.對于控制u 的使能狀態，由某庫所令牌總數ΣM(pi)與當前時刻τ 共同決定，設z 為令牌總數的上限，τbeg、τend分別為仿真時鐘的時間上限與時間下限，當

控制u 使能.例如，當

時，庫所p1與p2的令牌總數≤4，且仿真時鐘在6 點到8 點之間，變遷t 有發生權.

1.4 基本性質檢驗

有界性:設港口每天作業拖車總量為O，一天中任一時刻系統中的拖車數m，必有m≤O. 通過觀察Σ 知，任取可達標識Mi都必有

Mi(p)≤m≤O，因此，Σ 為結構有界.

活性:對Σ 的運行進行分析可以看出，每個變遷在特定的變遷序列下都能重獲發生權，因此，Σ 為活網.

死鎖:為了保證不出現庫所永遠無令牌的情況，必須檢驗網Σ，證明其中不包含死鎖.根據Petri網死鎖的定義，對于庫所P，不存在任何庫所子集滿足·pi?p·

i ，因此，Σ 不存在死鎖.

1.5 模型假設

通過對港口作業的實際調研發現:

(1)進港拖車一般只執行單一業務，極少出現拖車空箱進港，重箱離港等混合業務.

(2)港口在海關集中放行后，大量拖車到港進行提取重箱業務造成拖車阻塞問題.

(3)由于海關查驗需要貨箱單層平鋪，查驗堆場一般處于飽和狀態，因此，每天放行集裝箱量基本穩定.

(4)提取重箱業務不受其他業務活動干擾.根據上述實際作業特點，對拖車到達作業模型做以下假設:

(1)拖車業務單一性.

進港拖車只進行提取重箱或提取空箱等一種業務，且重點分析提取重箱拖車.

(2)堆場作業時間相對穩定.

由于查驗堆場處于飽和狀態，作業時間不受外部因素影響，可認為每輛拖車的堆場作業時間相對固定，符合一定的時間分布.

1.6 模型分析

網Σ 的運作如下，不同顏色令牌代表不同業務拖車隨機到達隊列庫所集合排隊，當控制u 使能即入閘條件允許，拖車通過閘口后，進入選擇庫所并根據規則發生不同時延變遷，拖車完成作業后離開網Σ.

用等待拖車最大數量與拖車等待時間評價拖車到達調度的效果.等待拖車最大數量是衡量拖車阻塞程度的指標，等待時間反映出擁堵的嚴重程度.通過對隊列庫所集合Pq中的令牌數進行統計，就可以得到一段時間內Pq中令牌的最大數量. 對進入與離開Pq的令牌建立時間戳，通過統計可得到一段時間內令牌在Pq中的逗留時間.

在時間［τB，τE］內，有輸入集:

通過輸入集X，在到達率λx(τ)下，統計時間［τB，τE］內M(Pq)與令牌的時間戳可以得到輸出集:

式中:f(X)為傳遞函數，通過Petri 網構建，利用Arena 仿真軟件實現，由到達批量與間隔時間的輸入集X，得到輸出集Y;

Lqmax為拖車等待隊列的最大長度;

τwaitavg為拖車平均等待時間;

τwaitmax為拖車最大等待時間.

通過輸出集可得拖車的最大等待時間、平均等待時間與等待隊長，根據這3 個指標分析港口拖車當前的阻塞程度，并衡量拖車調度優化后的效果.

2 拖車到達作業過程的Petri 網模型

2.1 三水港拖車到達作業過程簡介

佛山市三水港位于珠江三角洲的西北端北江與西江的匯流處，工作時間為每周6 d 早午晚3 時段制，其拖車業務主要包括提取和卸載重箱及提取和卸載空箱4 種，港內有2 個主要堆場，到達作業流程與1.1 節中的拖車到達作業過程相同.

2.2 拖車到達作業過程模型

建立拖車作業流程的混合Petri 網模型Σ，如圖1 所示.

圖1 三水港拖車到達作業過程Petri 網模型Fig.1 Trailer arrival and operation process Petri net model of Sanshui Port

式中:p1～p4分別表示卸載空箱、提取空箱、卸載重箱、提取重箱4 種業務拖車的等待隊列庫所.

式中:p5、p6、p7分別表示入閘海關是否查驗、進入重/空箱堆場、出閘海關是否查驗的3 個選擇庫所.

式中:t1～t4分別表示4 種業務拖車的隨機到達.

式中:t11～t15分別表示實際的作業環節，例如:海關入閘驗單、堆場裝卸箱、海關出閘檢查、港口出閘驗單.

以t11為例，一個時延變遷可以分解為兩個瞬時變遷與一個時延庫所的集合.

2.3 仿真建模

建立拖車到達作業過程的Petri 網模型后，將網Σ 中各個部分轉換為Arena 仿真系統中的相應模塊，即可得到拖車到達作業的仿真模型，其中:

使用Create 模塊替代隨機發生變遷集Ta的活動，實現作業拖車的隨機到達;

使用Assign 模塊中的Attribute 記錄顏色集K與時間戳，用于記錄拖車的不同業務與進出時刻;

使用Queue 模塊替代隊列庫所集合Pq的活動，并利用Queue 模塊中的Priority 屬性來體現抑止弧集I，抑止弧前端的隊列庫所優先級高;

使用Decide 模塊與Route 模塊替代選擇庫所集Pc的活動，實現實體的選擇活動;

使用Seize、Resource、Release 模塊替代控制庫所集C 的活動;

使用Process、Delayv 等模塊替代時延變遷集Tr的活動.

通過轉換后得到的Arena 仿真模型如圖2 所示，包括拖車到達、進入閘口、堆場作業、離開閘口4 個部分.

2.4 模型驗證

圖3 為三水港拖車離港記錄.

圖2 三水港拖車到達作業過程的Arena 仿真模型結構Fig.2 Arena simulation model structure based on trailer arrival and operation process of Sanshui Port

圖3 三水港拖車離港記錄對比Fig.3 Comparison of trailers departure records of Sanshui Port

為驗證模型的有效性，將仿真港口拖車離港分布與調研報告、港口提供的拖車離港分布進行對比.拖車離港的數量與時間由拖車到港數量、到港時間、等待時間、堆場處理能力、堆場處理時間、閘口處理時間等因素共同決定，能充分反映港口拖車的到達作業過程規律.

圖3 顯示仿真結果與調研記錄、港口記錄的拖車離港規律特別是高峰時段的到達規律高度吻合，且仿真得到的平均等待時間與最大隊長與調研報告中觀察到的基本相符，表明模型能夠反映港口拖車的到達作業過程.

3 拖車調度方案優化

進港拖車阻塞問題表現為進港拖車等待時間過長和等待隊長過長. 優化目標為:通過改變到達間隔τa與到達批量b 使等待時間與隊長最短，即令

代入X(λo，τB，τE)中，使下式成立，

式中:τao為最佳時間間隔;

bo為最佳批量;

λo為τao與bo下最佳到達率.

三水港重箱堆場作業平均費時

τavg=38 min.

理論上，當

時，拖車等待時間最短. 為便于港口計劃，簡化問題，設定到達間隔時間為30 min.令

代入X(λo，τB，τE)中，使式(4)成立.

檢驗以下兩個基本到達調度方案.

(1)方案1

不改變各工作時段提箱拖車到達的數量，但改變時段內到達的批量，令拖車到達數量適應時段內的堆場作業能力.

(2)方案2

在方案1 的基礎上，改變各時段拖車到達量的比例，使拖車到達量適應該時段港口堆場作業能力.拖車的到達調度，主要改變了拖車的到達規律，實現批量到達，建模重點在于確定不同時段內時間間隔τa與拖車到達批量b.

假設所有車輛都能準時到達，且所有車輛到達時間誤差服從三角分布，即Tri(-5 min，0 min，5 min)，提早或延遲時間均不超過5 min.以到達高峰的晚上時段為例，設

τa= 30 min， b ∈［15 輛，25 輛］，

利用PAN(process analyzer)的分析結果見表1.

晚上時段作業時間均值為195 min，最大等待時間超過195 min 則表示超出作業時間而在堆場內過夜的車輛.當間隔時間為30 min，批量為21 輛時，等待時間、最長等待隊長、超時車輛都相對較少，因此，選擇為晚上時段分析到達規律，用同樣的方法可得到所有時段的到達批量，如表2 所示.

表1 方案1 的PAN 仿真報告Tab.1 PAN simulation report of solution 1

表2 方案1 到達調度批量Tab.2 Scheduled arrival quantity of solution 1

4 仿真結果分析

改進前與兩種方案的30 次仿真結果見表3 和表4(仿真時間長度為6 d).

表3 最大隊長、平均等待時間與最長等待時間的比較Tab.3 Comparison of the maximum queue length，the average waiting time，and the maximum waiting time

(1)方案1 對工作時段內拖車到達進行調度，平均等待時間從原來的32 min 減少至9 min，最大等待時間從133 min 減少至96 min.最大的等待車輛數從原來的56 輛減少至41 輛.由表4 的等待時間分布比較可知，到達調度后拖車等待時間80%以上集中在30 min 內，表明到達調度能減少大部分拖車的等待時間.

(2)方案2 對全天內的拖車進行到達調度，可進一步減少平均等待時間與等待車輛數，并有效增加堆場利用率，減少過夜車輛.

表4 等待時間分布比較Tab.4 Comparison of waiting time distribution

圖4 為30 次仿真拖車等待時間均值的比較.

圖4 30 次重復仿真拖車等待均值比較Fig.4 Comparison of average waiting time based on 30 replications

由表3 和表4 可見:

(1)方案1 對工作時段內拖車到達進行調度，平均等待時間從原來的32 min 減少至9 min，最大等待時間從133 min 減少至96 min.最大的等待車輛數從原來的56 輛減少至41 輛.由表4 的等待時間分布比較可知，到達調度后拖車等待時間80%以上集中在30 min 內，表明到達調度能減少大部分拖車的等待時間.

(2)方案2 對全天內的拖車進行到達調度，可進一步減少平均等待時間與等待車輛數，并有效增加堆場利用率，減少過夜車輛.

5 結束語

針對珠三角內河集裝箱碼頭的進港拖車阻塞交通的問題，提出拖車到達過程的混合Petri 網模型，對佛山三水港進行建模，通過Arena 仿真確定拖車到達調度的間隔時間與到達批量，并驗證調度方案的優化效果. 仿真結果顯示，拖車等待時間最高減少87%，等待數量減少26%，證明拖車到達調度優化能有效降低閘口外進港拖車的等待時間與等待數量，對改善內河集裝箱碼頭運行效率具有實際應用意義.

致謝:本文工作得到佛山市港口引用RFID 技術試點項目(FSHL2012192G)的資助.

［1］ 金淳，于越，趙璐. 基于仿真優化的集裝箱港口大門作業調度研究［J］. 系統仿真學報，2008，20(8):1998-2001.JIN Chun，YU Yue，ZHAO Lu. Research on optimal scheduling on gate operation on container terminal based on simulation optimization method［J］. Journal of System Simulation，2008，20(8):1998-2001.

［2］ 金淳，沈劍峰. 基于仿真的港口大門服務系統性能測試［J］. 系統仿真學報，2008，20(9):2429-2432.JIN Chun， SHEN Jianfeng. Simulation-based performance test for service information system of gate operation on container port［J］. Journal of System Simulation，2008，20(9):2429-2432.

［3］ 王軍，徐曉雷. 集裝箱碼頭集卡作業的路徑選擇［J］.大連海事大學學報，2011，37(2):25-27.WANG Jun，XU Xiaolei. Route selection of container trucks in container terminal［J］. Journal of Dalian Maritime University，2011，37(2):25-27.

［4］ TAO Jinghui，CAI Han，ZHANG Xiaoping. A mixed scheduling method for vehicle dispatching in container terminals［J］. Operations Research Transactions，2009，13(3):10-22.

［5］ 曾慶成，張笑菊，陳文浩，等. 基于BCMP 排隊網絡的碼頭集卡預約優化模型［J］. 系統工程學報，2013，28(5):592-599.ZENG Qingcheng，ZHANG Xiaoju，CHEN Wenhao，et al. Optimization model for truck appointment based on BCMP queuing network［J］. Journal of Systems Engineering，2013，28(5):592-599.

［6］ ZHAO Wenjuan，GOODCHILD A V. The impact of truck arrival information on container terminal rehandling［J］. Transport Research Part E:Logistics and Transportation Review，2010，46(3):327-343.

［7］ ERHAN C. Introduction to stochastic processes［M］.［S. l.］:Prentice-Hall，Inc.，1975:94-101.

［8］ 許巧莉，孫麗君，胡祥培，等. 非平穩到達的碼頭集卡預約優化模型［J］. 大連理工大學學報，2014，54(5):589-596.XU Qiaoli， SUN Lijun， HU Xiangpei， et al.Optimization model for appointment of container trucks with non-stationary arrivals［J］. Journal of Dalian University of Technology，2014，54(5):589-596.

［9］ 李望，倪少權. 基于TPr/T-S 的客專車站通用模型及仿真［J］. 西南交通大學學報，2013，48(5):934-941.LI Wang，NI Shaoquan. General model and simulation research on passenger-dedicated line station based on TPr/T-S［J］. Journal of Southwest Jiaotong University，2013，48(5):934-941.

［10］ 張耀鴻，樊建才，廖曉林. 基于Petri 網的指揮控制流程仿真方法［J］. 系統仿真學報，2012，24(7):1418-1421.ZHANG Yaohong， FAN Jiancai， LIAO Xiaolin.Simulation method of command and control process based on Petri net［J］. Journal of System Simulation，2012，24(7):1418-1421.

［11］ 魯工圓，閆海峰，徐進. 基于TCPN 的鐵路客運站作業組合仿真模型［J］. 西南交通大學學報，2013，48(4):694-701.LU Gongyuan， YAN Haifeng， XU Jin. Railway passenger station operation combined simulation model based on TCPN［J］. Journal of Southwest Jiaotong University，2013，48(4):694-701.

［12］ 鄭文艷. 分層有色Petri 網在物流配送系統仿真建模中的應用［J］. 計算機系統應用，2014，22(4):164-168.ZHEN Wenyan. Modeling and simulation in logistics systems based on hierarchy coloured petri net［J］.Computer Systems and Applications，2014，22(4):164-168.

［13］ 吳哲輝. Petri 網導論［M］. 北京:機械工業出版社，2006:251-263.

［14］ JENSEN K. Coloured Petri nets-basic concepts，analysis methods and practical use，Vol. 1［M］. 2nd ed. Heidelberg:Springer，1996:1-234.

［15］ RAMCHANDANI C. Analysis of asynchronous concurrent system by timed Petri nets［D］.Cambridge:MIT，1974.