范家佳，劉洪星，李勇華，楊麗金

(1.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430063； 2.交通物聯(lián)網(wǎng)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室(武漢理工大學(xué))，武漢 430070)

0 引言

港口是水陸運(yùn)輸?shù)臉屑~，吞吐能力與港內(nèi)車輛集疏效率息息相關(guān)[1]。海港規(guī)模大，交通設(shè)施完善路況良好，港內(nèi)貨物轉(zhuǎn)運(yùn)方式主要為船到火車，道路擁堵概率低。與海港不同，內(nèi)河港口相對(duì)規(guī)模較小，港內(nèi)交通設(shè)施建設(shè)落后，貨物轉(zhuǎn)運(yùn)的主要交通工具為貨車，在港作業(yè)車輛多且進(jìn)出頻繁，但對(duì)作業(yè)車輛的引導(dǎo)卻不夠智能化[2]。主要面臨以下幾個(gè)方面的挑戰(zhàn)：1)機(jī)械設(shè)備利用率不高。作業(yè)車輛需要港內(nèi)機(jī)械輔助完成作業(yè)，因此不能只簡(jiǎn)單考慮車輛的行駛時(shí)間。2)港區(qū)路網(wǎng)復(fù)雜和港方監(jiān)管困難。司機(jī)對(duì)港內(nèi)道路、作業(yè)流程不熟悉，加之作業(yè)過程中信息傳遞不及時(shí)，極易導(dǎo)致?lián)矶?，交通高峰期車輛在港內(nèi)通行往往需2倍于暢通狀態(tài)下的時(shí)間[3]。3)作業(yè)車輛間選路相互影響。若多輛車同時(shí)分配到相同路徑，則會(huì)導(dǎo)致新的擁堵。故減少車輛在港行駛時(shí)間，緩解港區(qū)道路擁堵、提高港方資源利用率成為港口智能化研究的重點(diǎn)。目前國(guó)內(nèi)外對(duì)內(nèi)河港口車輛擁堵的研究較少，對(duì)城市交通擁堵的研究較多。

隨著全球定位系統(tǒng)(Global Positioning System，GPS)和車輛識(shí)別等技術(shù)的引進(jìn)，車輛導(dǎo)航系統(tǒng)的選路算法發(fā)展到了實(shí)時(shí)選路階段[4]。劉恒宇等[5]提出了考慮擁堵和工作量的選路問題，構(gòu)建了混合整數(shù)規(guī)劃模型，驗(yàn)證了算法的有效性，但方法適用范圍有限。De Souza等[6]基于實(shí)時(shí)信息在每個(gè)路口為車輛動(dòng)態(tài)選路，實(shí)現(xiàn)道路交通的負(fù)載平衡，但該方案的效果未在真實(shí)路網(wǎng)中進(jìn)行測(cè)試。Lin等[7]將路網(wǎng)中車輛分成不同集群，使用進(jìn)化博弈分析車輛選路，減少了交通擁堵，但未考慮交通管制的影響。

隨著智能導(dǎo)航設(shè)備的增多，越來(lái)越多的車輛根據(jù)實(shí)時(shí)路況選路，但大量車輛同時(shí)請(qǐng)求導(dǎo)航時(shí)，極有可能因選擇相同路徑導(dǎo)致新的擁堵，因此合理的選路算法應(yīng)考慮到車輛間的沖突。嚴(yán)麗平等[8]建立了城市動(dòng)態(tài)多路口選路模型，車輛通過自適應(yīng)學(xué)習(xí)進(jìn)行博弈得到最佳路徑，但未考慮車輛不服從系統(tǒng)推薦路徑的情況。吳黎兵等[9]將車輛選路對(duì)路況的影響量化，避免了個(gè)體車輛選路造成的道路擁堵，但未考慮路網(wǎng)中的突發(fā)事件。Amar等[10]將多車輛選路問題建模成討價(jià)還價(jià)游戲，提出的團(tuán)隊(duì)路徑規(guī)劃算法可得到有效解，但仍需進(jìn)一步研究以確定游戲的最佳參與者個(gè)數(shù)。

當(dāng)前港口向著信息化、智能化的方向發(fā)展，但我國(guó)大部分內(nèi)河港口只實(shí)現(xiàn)了信息化，未能實(shí)現(xiàn)智能化[11]。在用智能化手段管理港口車輛時(shí)，本文研究影響車輛作業(yè)效率的各個(gè)環(huán)節(jié)，結(jié)合生產(chǎn)作業(yè)指令，為作業(yè)車輛優(yōu)化在港內(nèi)行駛路徑。現(xiàn)有選路算法幾乎沒有考慮車輛路彼此間的沖突，為解決這一問題，本文建立港口作業(yè)車輛協(xié)同選路模型，將車輛間的交互建模為不完全信息博弈，采用“滿足均衡(Satisfaction Equilibrium, SE)”[12]的概念分析博弈。從港口總體收益出發(fā)，兼顧車輛間合作的同時(shí)最大化系統(tǒng)收益。

1 港口作業(yè)車輛協(xié)同選路模型

港口作業(yè)車輛協(xié)同選路模型用來(lái)描述港口路網(wǎng)中大量作業(yè)車輛同時(shí)請(qǐng)求導(dǎo)航的情況，采用基于不完全信息的博弈描述車輛間的交互，能更準(zhǔn)確地表示多車輛選路時(shí)的沖突。

1.1 模型要素

模型中包括對(duì)港口路網(wǎng)的表示、路徑選擇博弈的參與者、相應(yīng)參與者的策略空間及效用函數(shù)。

1.1.1 港口交通路網(wǎng)

港口路網(wǎng)表示為有向圖G=(V,E)。V={Vi|i=1,2,…,v}為節(jié)點(diǎn)集合，v為節(jié)點(diǎn)數(shù)，Vi中包括節(jié)點(diǎn)的基本信息如名稱、屬性(如地磅、堆場(chǎng))。E={Ei|i=1,2,…,e}為路段集合，e為路段總數(shù)，Ei中包含路段的基本信息如名稱、長(zhǎng)度、寬度。

1.1.2 參與者

N={Ni|i=1,2,…,n}為同時(shí)請(qǐng)求導(dǎo)航的n個(gè)作業(yè)車輛集合，是博弈參與者。?Ni∈N都有可承受的成本上限，t_Mi、d_Mi、o_Mi、v_Mi分別為車輛i從起點(diǎn)到終點(diǎn)的時(shí)間、距離、耗油量和等待作業(yè)機(jī)械時(shí)間的閾值。

1.1.3 策略空間

1.1.4 效用函數(shù)

作業(yè)車輛選路最關(guān)心成本，將車輛i的效用記作Ui(h)，為路徑成本的負(fù)值，如式(1)所示：

(1)

1.2 效用計(jì)算

車輛在路徑上行駛付出的成本代價(jià)有時(shí)間ti、距離di、油耗oi及等待作業(yè)機(jī)械時(shí)間vi，將它們進(jìn)行權(quán)重組合計(jì)算路徑的成本值，如式(2)所示：

(2)

其中：c1～c4表示相應(yīng)參數(shù)對(duì)應(yīng)的權(quán)值，它們和為1。成本值越大，對(duì)應(yīng)的路徑越不易被選中。

ti、di、oi的計(jì)算方法與文獻(xiàn)[8]中2.2節(jié)的方法相同，下面給出vi的具體計(jì)算方法。

M={Mi|i=1,2,…,d}為港口作業(yè)機(jī)械集合。車輛到達(dá)堆場(chǎng)后由調(diào)度員指定的機(jī)械為其作業(yè)。引入指示變量Xi, j，當(dāng)Xi, j=1時(shí)表示指定機(jī)械j為車輛i作業(yè)，為0時(shí)則相反。

每個(gè)作業(yè)機(jī)械都擁有一個(gè)車輛排隊(duì)隊(duì)列，K為在車輛i前等待機(jī)械j的車輛集合；ηj為機(jī)械j的作業(yè)速度；wi為車輛i的待作業(yè)貨物量；ti為車輛i到達(dá)目的地的預(yù)期行駛時(shí)間，則機(jī)械j為車輛i作業(yè)所需時(shí)間oi, j=ηj×wi，車輛i等待機(jī)械j的時(shí)間如式(3)所示：

(3)

機(jī)械j等待車輛i的時(shí)間如式(4)所示：

(4)

1.3 車輛選路的滿足均衡

因不完全信息博弈的納什均衡難以分析，本文采用滿足均衡的概念來(lái)分析博弈均衡。下面先給出滿足式表述，然后再給出本文追求的滿足均衡。

1.3.1 滿足式表述

不考慮車輛間相互影響的情況下，將車輛策略集中路徑的最大效用作為其理想效用，車輛i的理想效用如式(5)所示：

(5)

通常最優(yōu)的理性效用很難得到[14]，假設(shè)每個(gè)車輛對(duì)推薦路徑的效用有一個(gè)低于最優(yōu)值的預(yù)期，該值為車輛理想效用的τi倍，如式(6)所示，τi的值可通過多次實(shí)驗(yàn)探索得到。

(6)

fi(r-i)={ri∈Ri:ui(ri,r-i)≥Γi}

(7)

基于上述討論，本文用式(8)中所示的三元組描述所建立的博弈模型，稱為博弈的滿足式表述。

G=(N,{Ri}i∈N,{fi}i∈N)

(8)

1.3.2 滿足均衡

與滿足式表述對(duì)應(yīng)的均衡稱為滿足均衡(SE)，SE的定義[12]如下。

1.4 模型求解目標(biāo)

1)車輛選路目標(biāo)。

車輛選路的目標(biāo)是成本不超過閾值且選路效用超過期望值。?Ni∈N的求解目標(biāo)如式(9)所示：

s.t.ti≤t_Mi

di≤d_Mi

oi≤o_Mi

vi≤v_Mi

(9)

2)港口交通規(guī)劃系統(tǒng)路徑誘導(dǎo)目標(biāo)。

港口交通規(guī)劃系統(tǒng)期望所有車輛效用和最大，如式(10)所示；且裝卸機(jī)械能耗最小，如式(11)所示，包括機(jī)械作業(yè)狀態(tài)及空閑狀態(tài)下的能耗。機(jī)械能耗為其運(yùn)行時(shí)間乘以單位時(shí)間柴油能耗。

(10)

(11)

其中：Ej為機(jī)械設(shè)備j單位時(shí)間柴油能耗。

定義2 設(shè)w1、w2為相應(yīng)參數(shù)對(duì)應(yīng)的權(quán)值系數(shù)，二者和為1，所有車輛的效用和與機(jī)械能耗的帶權(quán)和稱為系統(tǒng)收益，記作Q=w1×U-w2×E。

顯然，任意博弈階段的系統(tǒng)收益均小于理想系統(tǒng)收益，Qt為t時(shí)刻獲得的系統(tǒng)收益，則Qt

港口交通規(guī)劃系統(tǒng)的決策目標(biāo)為最大化系統(tǒng)收益，如式(12)所示。

max:Q

(12)

該模型考慮了作業(yè)車輛的特性，即車輛與機(jī)械之間存在等待關(guān)系，同時(shí)考慮了車輛之間的相互影響。模型的求解在于找到滿足式(9)和(12)的行動(dòng)組合，同時(shí)模型中存在多個(gè)系數(shù)，可以通過多次實(shí)驗(yàn)探索總結(jié)得出滿足實(shí)際情況的值。

2 港口作業(yè)車輛協(xié)同選路模型求解

本文構(gòu)建的模型主要針對(duì)內(nèi)河港口作業(yè)車輛，具有領(lǐng)域適用性，在求解過程中需結(jié)合領(lǐng)域特性，模型服務(wù)于港口交通規(guī)劃系統(tǒng)。港口交通規(guī)劃系統(tǒng)與車輛的交互過程如圖1所示，主要過程如下：

圖1 交通規(guī)劃系統(tǒng)與車輛的交互Fig. 1 Interaction between traffic planning system and vehicles

1)當(dāng)港口路網(wǎng)中多個(gè)車輛試圖由起點(diǎn)駛向終點(diǎn)時(shí)，駕駛員向?qū)Ш较到y(tǒng)輸入目的地。結(jié)合GPS定位系統(tǒng)，車載導(dǎo)航設(shè)備將駕駛員輸入的信息轉(zhuǎn)換為起止點(diǎn)對(duì)，提交給港口交通規(guī)劃系統(tǒng)。

2)港口交通規(guī)劃系統(tǒng)收到多個(gè)車輛提交的請(qǐng)求后，根據(jù)道路信息管理系統(tǒng)中的道路信息，結(jié)合生產(chǎn)業(yè)務(wù)管理系統(tǒng)中的車輛作業(yè)信息，使用合適的選路策略，運(yùn)用選路算法為車輛規(guī)劃路徑并反饋。

2.1 車輛分組原則

定義4 每個(gè)博弈階段進(jìn)行的操作稱為趟迭代。

趟迭代時(shí)若所有車輛同時(shí)改變選路策略，會(huì)導(dǎo)致系統(tǒng)收益發(fā)生劇烈震蕩無(wú)法收斂，故在趟迭代階段將車輛分成多個(gè)組，在組內(nèi)進(jìn)行適應(yīng)性學(xué)習(xí)，使系統(tǒng)收益向著收斂的方向改變。

定義5 車輛集合稱為組。每次趟迭代時(shí)分成m個(gè)組，C={Ci|i=1,2,…,m}為組集合。對(duì)于?Ck∈C，組內(nèi)車輛集合記作Nk={Nki|i=1,2,…,n}。

第t次趟迭代的組大小，如式(13)所示：

(13)

2.2 車輛選路策略

定義6 每個(gè)組內(nèi)進(jìn)行的操作稱為適應(yīng)性學(xué)習(xí)。

Qt為第t趟迭代中所得系統(tǒng)收益，ht為對(duì)應(yīng)的選路結(jié)果；Qt,k為第t趟迭代中第k個(gè)組適應(yīng)性學(xué)習(xí)完成后所得系統(tǒng)收益，ht,k為對(duì)應(yīng)的選路結(jié)果；Qt,k,t′為第t趟迭代中第k個(gè)組在第t′次適應(yīng)性學(xué)習(xí)中所得系統(tǒng)收益，ht,k,t′為對(duì)應(yīng)的選路結(jié)果。

集群k在Const次適應(yīng)性學(xué)習(xí)中所得最大系統(tǒng)收益記作Qt,k=max{Qt,k,0,Qt,k,1,…,Qt,k,t′,…,Qt,k,Const}。

車輛在迭代交互的過程中按如下規(guī)則行動(dòng)。

1)初始選路。

2)趟迭代選路過程。

第t(t=1,2,…)趟迭代開始時(shí)，根據(jù)2.1節(jié)中提到的方法將所有車輛分成m個(gè)組。?Ck∈C分別進(jìn)行Const次適應(yīng)性學(xué)習(xí)。適應(yīng)性學(xué)習(xí)詳見下文3)，輸入是所有車輛上次迭代的選路結(jié)果及對(duì)應(yīng)系統(tǒng)收益，輸出為所有車輛新的選路結(jié)果及對(duì)應(yīng)系統(tǒng)收益。

對(duì)于第1個(gè)組：將第t-1趟迭代的選路結(jié)果作為適應(yīng)性學(xué)習(xí)的輸入，其學(xué)習(xí)后所得系統(tǒng)收益為Qt,1、對(duì)應(yīng)選路結(jié)果為ht,1；

對(duì)于第j+1(2≤j+1≤m)個(gè)組：將第j個(gè)組適應(yīng)性學(xué)習(xí)后的結(jié)果作為輸入，其學(xué)習(xí)后所得系統(tǒng)收益為Qt, j+1，對(duì)應(yīng)選路為ht, j+1。

所有組學(xué)習(xí)完成后，將最后一個(gè)組m得到的結(jié)果作為第t趟迭代的結(jié)果，即Qt=Qt,m，ht=ht,m。

3)第t趟迭代中組k(1≤k≤m)的適應(yīng)性學(xué)習(xí)。

適應(yīng)性學(xué)習(xí)初始階段t′=0，?i∈Nk使用輸入的選路結(jié)果作為試探性最佳路徑；

(14)

若當(dāng)前效用未達(dá)到預(yù)期，即vi(t′-1)=0，可能需要車輛i改變策略，也可能需其他車輛改變策略。由于其他車輛的行為策略不確定，一個(gè)理性的參與者希望此刻的行為在將來(lái)看來(lái)是最不后悔的選擇，因此行動(dòng)選擇概率可表示為式(15)的形式：

(15)

(16)

4)輸出最佳路徑選擇。

若在約定次數(shù)內(nèi)系統(tǒng)收益達(dá)到最大，即ns(ns>0)次迭代后，|Qt/Qt-1-1|<ε,ε>0；或算法迭代達(dá)到最大可接受次數(shù)maxTray，算法終止并輸出對(duì)應(yīng)的最佳路徑ht及系統(tǒng)收益Qt。

2.3 車輛協(xié)同選路算法描述

根據(jù)上面構(gòu)建的模型和模型求解的思路，本文提出一種車輛協(xié)同選路(Collaborative Route Selection, CoRS)算法來(lái)求解上述模型。

2.3.1 CoRS算法

CoRS算法初始階段車輛根據(jù)貪心策略完成初始選路，之后進(jìn)行多次趟迭代直至達(dá)到算法終止條件。其具體執(zhí)行步驟如下：

步驟1 輸入請(qǐng)求路徑規(guī)劃的車輛集合及各車的候選路徑集合。

步驟2 初始階段：每個(gè)車輛根據(jù)貪心策略選路，作為試探性最佳路徑選擇。

步驟3 趟迭代階段：將車輛分組，組內(nèi)進(jìn)行適應(yīng)性學(xué)習(xí)。

步驟4 判斷當(dāng)前選路結(jié)果是否滿足算法終止條件，若滿足則進(jìn)行步驟5；若不滿足則進(jìn)行步驟3。

步驟5 輸出車輛的試探性最佳路徑作為最佳選路。

2.3.2 時(shí)間復(fù)雜度分析

設(shè)車輛數(shù)為n、每個(gè)車輛的候選路徑個(gè)數(shù)為m。CoRS算法分兩部分實(shí)現(xiàn)：1)初始選路階段，每個(gè)車輛遍歷候選路徑集找出效用最大的路徑，時(shí)間復(fù)雜度為O(mn)；2)趟迭代階段，對(duì)每個(gè)組內(nèi)所有車輛進(jìn)行適應(yīng)性學(xué)習(xí)，車輛適應(yīng)性學(xué)習(xí)時(shí)間復(fù)雜度為O(m2)，則趟迭代時(shí)間復(fù)雜度為O(nm2)。綜上所述，本算法的時(shí)間復(fù)雜度為O(nm+nm2)。

2.3.3 收斂性分析

采用數(shù)學(xué)歸納法證明CoRS算法可使系統(tǒng)收益隨著迭代次數(shù)的增加逐漸增大，最終達(dá)到收斂。

初始選路階段：系統(tǒng)收益為Q0

趟迭代階段：

1)第1趟迭代。

將所有車輛分成m個(gè)組，C={Ci|i=1,2,…,m}為組集合，?Ck∈C進(jìn)行適應(yīng)性學(xué)習(xí)。

a)對(duì)于第1個(gè)組：

適應(yīng)性學(xué)習(xí)初始階段，使用h0作為初始路徑選擇，h1,1,0=h0，對(duì)應(yīng)系統(tǒng)收益為Q1,1,0=Q0；

第t′(t′=1,2,…,Const)次適應(yīng)性學(xué)習(xí)中，組內(nèi)車輛通過適應(yīng)性學(xué)習(xí)選定路徑，計(jì)算系統(tǒng)收益Q1,1,t′，對(duì)應(yīng)選路為h1,1,t′。

Const次適應(yīng)性學(xué)習(xí)后，從中選出最大系統(tǒng)收益Q1,1=max{Q1,1,0,Q1,1,1,…,Q1,1,t′,…,Q1,1,Const}，對(duì)應(yīng)選路為h1,1。有Q0=Q1,1,0≤Q1,1

b)對(duì)于第j+1(2≤j+1≤m)個(gè)組：

設(shè)第j個(gè)組適應(yīng)性學(xué)習(xí)完成后，所得系統(tǒng)收益為Q1, j，對(duì)應(yīng)選路為h1, j。

適應(yīng)性學(xué)習(xí)初始階段，將h1, j作為初始路徑選擇，h1, j+1,0=h1, j，對(duì)應(yīng)系統(tǒng)收益為Q1, j+1,0=Q1, j；

第t′(t′=1,2,…,Const)次適應(yīng)性學(xué)習(xí)中，組內(nèi)車輛通過適應(yīng)性學(xué)習(xí)選定路徑，計(jì)算系統(tǒng)收益Q1, j+1,t′，對(duì)應(yīng)選路為hi, j+1,t′。

Const次適應(yīng)性學(xué)習(xí)后，從中選出最大系統(tǒng)收益Q1, j+1=max{Q1, j+1,0,Q1, j+1,1…,Q1, j+1,t′,…,Q1, j+1,Const}，對(duì)應(yīng)選路為hi, j+1。有Q1, j≤Q1, j+1,0≤Q1, j+1

系統(tǒng)收益的關(guān)系為Q0≤Q1,1≤…≤Q1, j≤Qi, j+1≤…≤Q1,m

2)第i+1趟迭代。

設(shè)第i趟迭代后所得系統(tǒng)收益為Qi，選路為hi。

將所有車輛分成m個(gè)組，C={Ci|i=1,2,…,m}為組集合，?Ck∈C進(jìn)行適應(yīng)性學(xué)習(xí)。

a)對(duì)于第1個(gè)組：

適應(yīng)性學(xué)習(xí)初始階段，使用hi作為初始路徑選擇，hi+1,1,0=hi，對(duì)應(yīng)的系統(tǒng)收益為Qi+1,1,0=Qi；

第t′(t′=1,2,…,Const)次適應(yīng)性學(xué)習(xí)中，組內(nèi)車輛通過適應(yīng)性學(xué)習(xí)選定路徑，計(jì)算系統(tǒng)收益Qi+1,1,t′，對(duì)應(yīng)選路為hi+1,1,t*。

Const次適應(yīng)性學(xué)習(xí)后，從中選出最大的系統(tǒng)收益Qi+1,1=max{Qi+1,1,0,Qi+1,1,1,…,Qi+1,1,t′,…,Qi+1,1,Const}，對(duì)應(yīng)選路為hi+1,1。有Qi=Qi+1,1,0≤Qi+1,1

b)對(duì)于第j+1(2≤j+1≤m)個(gè)組：

設(shè)第j個(gè)組適應(yīng)性學(xué)習(xí)完成后，所得系統(tǒng)收益為Qi+1, j，對(duì)應(yīng)選路為hi+1, j。

適應(yīng)性學(xué)習(xí)初始階段，將hi+1, j作為初始路徑選擇，hi+1, j+1,0=hi+1, j，Qi+1, j+1,0=Qi+1, j為對(duì)應(yīng)系統(tǒng)收益；

第t′(t′=1,2,…,Const)次適應(yīng)性學(xué)習(xí)中，組內(nèi)車輛通過適應(yīng)性學(xué)習(xí)選定路徑，計(jì)算系統(tǒng)收益Qi+1, j+1,t′，對(duì)應(yīng)選路為hi+1, j+1,t′。

Const次適應(yīng)性學(xué)習(xí)后，從中選出最大系統(tǒng)收益Qi+1, j+1=max{Qi+1, j+1,0,Qi+1, j+1,1,…,Qi+1, j+1,t′,…,Qi+1, j+1,Const}，對(duì)應(yīng)選路為hi+1, j+1。有Qi+1, j=Qi+1, j+1,0≤Qi+1, j+1≤Q*。

由上可得，第i+1趟迭代中，各個(gè)組適應(yīng)性學(xué)習(xí)后得到的系統(tǒng)收益的關(guān)系為Qi≤Qi+1,1≤…≤Qi+1, j≤Qi+1, j+1≤…≤Qi+1,m≤Q*。第i+1趟迭代后各車選路結(jié)果為hi+1=hi+1,m，對(duì)應(yīng)系統(tǒng)收益為Qi+1，且Qi≤Qi+1,m=Qi+1

由上述推導(dǎo)過程歸納可得Q0≤Q1≤…≤Qt-1≤Qt≤…

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)先對(duì)CoRS算法的適用性進(jìn)行縱向分析，然后選取城市路網(wǎng)通用選路算法與其進(jìn)行橫向比較，主要比較系統(tǒng)收益及車輛平均行駛時(shí)間。

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文采用重慶某港口散貨堆場(chǎng)的交通路網(wǎng)，路網(wǎng)實(shí)際情況如圖2所示，涉及到的作業(yè)堆場(chǎng)為A～N共14個(gè)。路網(wǎng)中共包含223個(gè)節(jié)點(diǎn)，200條路段。港區(qū)內(nèi)限速30 km/h，道路通行能力為26 pcu/min(pcu/min表示每分鐘可通行車輛數(shù)的最大值)。

圖2 真實(shí)路網(wǎng)Fig. 2 Real road network

3.2 模擬結(jié)果及分析

存放在散貨堆場(chǎng)的貨物類型主要有煤炭、礦石，裝載機(jī)裝卸不同種類散貨的作業(yè)效率相差不大，故設(shè)定在港作業(yè)車輛作業(yè)類型為裝貨，貨物類型為鉻礦，載貨量為32 t，隨機(jī)指派機(jī)械為車輛作業(yè)。本文編寫了程序來(lái)模擬車輛協(xié)同選路過程。

1)組大小隨迭代次數(shù)變化情況。

設(shè)置請(qǐng)求路徑規(guī)劃的總車輛數(shù)目n為200(內(nèi)河港口通常會(huì)進(jìn)行港內(nèi)的交通管制，進(jìn)港車輛數(shù)會(huì)有所限制)，運(yùn)行算法進(jìn)行20次趟迭代。組大小隨迭代次數(shù)變化情況如圖3所示。由圖3可知，迭代次數(shù)在1到9間時(shí)，隨迭代次數(shù)的增加，組大小逐漸增加；迭代到第10次時(shí)，組大小為20，該值為多次實(shí)驗(yàn)后選取的經(jīng)驗(yàn)值；迭代次數(shù)在11到20之間時(shí)，隨著迭代次數(shù)的增加，組大小逐漸減小。

圖3 組大小隨迭代次數(shù)變化情況Fig. 3 Group size varying with the number of iterations

2)系統(tǒng)收益隨迭代次數(shù)的變化情況。

分別設(shè)置n為20、80、140、200，算法進(jìn)行10次趟迭代，所得系統(tǒng)收益隨迭代次數(shù)變化情況如圖4所示(系統(tǒng)收益實(shí)際為負(fù)值，本文在原始值的基礎(chǔ)上增加70 000，將結(jié)果處理為正值以便反映數(shù)據(jù)規(guī)律)。由圖4可知，當(dāng)路網(wǎng)中車輛較少時(shí)(n=20)，道路通行能力強(qiáng)，隨迭代次數(shù)的增加系統(tǒng)收益變化不大，算法迭代較少次數(shù)(約3次)即可達(dá)到系統(tǒng)最大收益；當(dāng)路網(wǎng)中車輛較多時(shí)(n=80、140、200)，若車輛都按貪心策略選路會(huì)導(dǎo)致?lián)矶掳l(fā)生，系統(tǒng)收益不高，CoRS算法通過調(diào)整車輛策略提高系統(tǒng)收益，使得隨著迭代次數(shù)的增加系統(tǒng)收益逐步增大，需迭代較多次(約7次)才可達(dá)到系統(tǒng)最大收益。

圖4 系統(tǒng)收益隨迭代次數(shù)變化情況Fig. 4 System profit varying with the number of iterations

3)與城市路網(wǎng)通用選路算法比較。

為突出CoRS算法特性，將其與SALA(Self-Adaptive Learning Algorithm)[8]和Dijkstra算法[15]進(jìn)行比較。分別設(shè)置n為20、80、140、200，將車輛的目的地隨機(jī)分散在各個(gè)堆場(chǎng)上。此外，選取2018年10月24日重慶某港口生產(chǎn)業(yè)務(wù)管理系統(tǒng)中的286輛車輛的作業(yè)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，即n為286。其中每個(gè)實(shí)驗(yàn)數(shù)據(jù)是20次重復(fù)實(shí)驗(yàn)結(jié)果的平均值。不同算法下系統(tǒng)收益、車輛平均行駛時(shí)間對(duì)比分別如圖5所示。

由圖5(a)可知，Dijkstra算法、SALA算法和本文算法中系統(tǒng)收益隨車輛數(shù)的增加而降低。隨著車輛數(shù)的增加，車輛在路段上行駛代價(jià)增大，同時(shí)排隊(duì)等待機(jī)械作業(yè)的車輛越多，使得車輛等待機(jī)械的時(shí)間越長(zhǎng)，最終使得車輛選路效用降低，系統(tǒng)收益降低。當(dāng)車輛數(shù)為286時(shí)，本文算法的系統(tǒng)收益分別比Dijkstra算法、SALA算法提高了51.7%和24.5%。

由圖5(b)可知，Dijkstra算法、SALA算法和本文算法中車輛的平均行駛時(shí)間隨著車輛數(shù)的增加而上升。隨著車輛數(shù)的增加，道路負(fù)載增大，道路通行能力降低，使得車輛的平均行駛時(shí)間增加。當(dāng)車輛數(shù)為286時(shí)，本文算法的車輛平均行駛時(shí)間分別比Dijkstra算法、SALA算法降低了50.8%和16.3%。

圖5 3種算法的性能對(duì)比Fig.5 Performance comparison of three algorithms

當(dāng)車輛較少時(shí)，道路暢通，車輛彼此間影響小，各算法差異不大；當(dāng)車輛較多時(shí)，尤其是達(dá)到200輛及以上時(shí)，使用Dijkstra算法選路會(huì)導(dǎo)致車輛集中選擇當(dāng)前暢通道路造成擁堵，算法性能低；SALA算法考慮了車輛間的相互影響，系統(tǒng)收益和平均行駛時(shí)間相比Dijkstra算法都有所提高，但該算法受選路時(shí)機(jī)的限制對(duì)性能改善效果不如CoRS算法明顯。CoRS算法考慮了車輛選路對(duì)道路狀態(tài)的影響，每次都基于全局最優(yōu)策略進(jìn)行選路，能夠加快車輛分流過程，算法性能高。

4 結(jié)語(yǔ)

針對(duì)內(nèi)河港口中大量車輛同時(shí)選路時(shí)彼此間路線沖突從而導(dǎo)致?lián)矶碌膯栴}，本文結(jié)合港口生產(chǎn)作業(yè)的特點(diǎn)，綜合考慮作業(yè)車輛的行駛時(shí)間和港方的作業(yè)效率，構(gòu)建了港口作業(yè)車輛協(xié)同選路模型，并采用本文提出的CoRS算法進(jìn)行模型求解。實(shí)驗(yàn)結(jié)果表明，相比于城市路網(wǎng)通用選路算法，CoRS算法可提高系統(tǒng)收益，并降低車輛平均行駛時(shí)間，能更好地適應(yīng)港口特性；但本文研究仍存在不足，目前還未考慮行駛車輛不遵循港口交通規(guī)劃系統(tǒng)路徑推薦的情況，且不能保證所有的車輛都能達(dá)到滿足，可能造成個(gè)別車輛的路徑推薦效果不理想。今后將深入研究車輛的博弈策略調(diào)整方法，進(jìn)一步提升車輛選路滿意度。