園區(qū)互連型公路貨運平臺的大規(guī)模魯棒運力資源分配問題研究

陳 玎 朱道立 楊 勇 趙 磊

(1.上海交通大學 中美物流研究院, 上海 200030; 2.上海交通大學 安泰經濟與管理學院, 上海 200030;3.交通運輸部科學研究院, 北京 100013; 4.上海交通大學 船舶海洋與建筑工程學院, 上海 200030)

0 引言

公路貨運是我國最重要的貨運方式之一,根據國家統(tǒng)計局資料顯示,2018年公路貨運量占我國貨運總量的76.9%,超過了美國71%的占比。從公路貨運總量角度看,2019年我國公路貨運量有望突破400億噸。但是,與龐大的貨運市場不相匹配的是,我國貨運行業(yè)始終面臨著公路貨運企業(yè)小、散、亂、差,行業(yè)集中度低的問題。以零擔運輸市場為例,我國公路零擔貨運行業(yè)集中度(concentration ratio top 10, CR10)僅有3%,而美國零擔運輸市場的行業(yè)集中度(CR10)高達75%,我國的整車運輸的行業(yè)集中度甚至低于3%。這意味著我國公路貨運市場的運力分散、運力資源浪費嚴重。“互聯網+公路貨運”模式是緩解這一局面,提高公路貨運集中度,促進公路貨運市場集約化發(fā)展的重要手段。隨著“互聯網+”的不斷發(fā)展,我國出現了一批“互聯網+”公路貨運平臺企業(yè),他們借助互聯網技術與平臺經濟思想整合物流資源,努力解決當前公路貨運行業(yè)運力分散、運力資源浪費等行業(yè)痛點問題。

“互聯網+” 公路貨運平臺的運營模式主要有交易撮合模式(輕資產化)和園區(qū)互連模式(重資產化)兩種。交易撮合模式主要指貨運平臺公司通過商業(yè)推廣將大量貨主企業(yè)貨運需求信息和運輸企業(yè)信息匯集于平臺。通過車貨匹配方法,向貨主企業(yè)推送滿足需求的承運人,同時向承運人推送適合其承接的貨運需求任務,達到交易撮合的目的。這一模式下平臺公司主要通過車后市場進行盈利(例如:加油費、輪胎等耗材費、車輛保養(yǎng)費等)。我國交易撮合型公路貨運平臺的代表企業(yè)有:滿幫、惠龍易通等。

另一種運營模式為園區(qū)互連模式。園區(qū)互連型平臺公司與全國多個物流園區(qū)建立園區(qū)托管關系,將原本相互獨立的園區(qū)日常運營標準化、規(guī)范化,并借此吸引各地依托物流園區(qū)的運輸需求企業(yè)與平臺簽訂運輸合約,保證平臺能向運輸端用戶提供充足穩(wěn)定的運輸需求。另一方面,平臺通過發(fā)展自營運力和吸引承運商(包括小物流企業(yè)、大小車隊甚至個體司機)加盟等方式,保證平臺的運力端能夠提供充足的運輸資源。在公路貨運市場供需兩端資源充足的情況下,這種公路貨運平臺能發(fā)揮整合優(yōu)勢,科學決策合理調配運力資源,實現干線運輸標準化、班列化運營,大力提高平臺的服務質量,從而較大改進了平臺雙邊用戶的平臺使用價值,提高了他們參與平臺服務的積極性,從而促進了貨運平臺的良性發(fā)展。如圖1所示。

圖1 園區(qū)互連模式Figure 1 Park interconnection mode

園區(qū)互連型公路貨運平臺運營管理系統(tǒng)主要由三部分組成:跨區(qū)域園區(qū)貨運管理系統(tǒng)、運力管理系統(tǒng)和干線貨運運營管理系統(tǒng),如圖2所示。其中,跨區(qū)域園區(qū)貨運管理系統(tǒng)主要負責各物流園區(qū)貨運運營管理、園區(qū)貨運大數據分析、平臺與園區(qū)合作模式設計等;運力管理系統(tǒng)主要負責運力狀態(tài)跟蹤維護、平臺與運力資源合作設計等;干線貨運運營管理系統(tǒng)則根據跨區(qū)域園區(qū)貨運管理系統(tǒng)提供的運輸需求信息和運力管理系統(tǒng)提供的可調配運力信息進行運力決策。通常,貨運平臺企業(yè)需要同時管理多個區(qū)域內物流園區(qū)及園區(qū)間干線運輸,且不同區(qū)域的貨運需求量和時效性要求不同。因此各區(qū)域的運輸任務難以統(tǒng)一調配,需要各區(qū)域運營團隊根據實時的運輸需求,自行安排車輛發(fā)運與任務分配。但是貨運平臺在保證各區(qū)域貨運任務的服務質量外,還需要考慮到各承運商利益平衡,各區(qū)域運力資源充足等因素。因此,目前園區(qū)互連型公路貨運平臺往往提前制定中長期貨運決策(模板路徑規(guī)劃、運力資源分配),以中長期貨運決策為指導與承運商簽訂相關合約,從而保證了承運商利益平衡和各區(qū)域運力資源充足。在中長期貨運決策基礎上,干線貨運運營管理系統(tǒng)根據運營過程中的實時需求信息,制定科學的短期貨運決策(日(周)路徑計劃、日(周)運輸車輛排班),上述系統(tǒng)還能夠利用運營過程中積累的數據進行大數據分析(決策效率/效益分析、運力資源評價、運價波動分析),并利用分析結果協(xié)助中長期運輸決策方案的調整,從而形成了數據驅動的閉環(huán)干線貨運決策系統(tǒng),保證了平臺決策的科學合理。在整個過程中,中長期貨運決策的任務是以平臺公司運營成本最低為目標,制定各路線運輸需求對不同承運商的分配,而短期貨運決策往往基于該“基礎運力分配”進行“實時分配調整”,因此中長期貨運決策的科學性極大的影響短期貨運決策的質量,因此本文主要研究干線貨運運營管理系統(tǒng)中運力資源分配這一中長期貨運決策問題。

圖2 園區(qū)互連模式運營管理系統(tǒng)Figure 2 Operation management system of park interconnection mode

貨運平臺企業(yè)主要利用雙邊平臺的網絡外部性,基于“互聯網+”,大數據技術和平臺經濟管理思想,努力有效地為平臺的運輸需求方和運輸服務方企業(yè)服務,從而提高平臺雙邊用戶的使用價值,吸引越來越多用戶加入平臺。如何科學運營平臺,為巨大規(guī)模的平臺雙邊用戶提供高質量服務,是園區(qū)互聯型公路貨運平臺管理者面臨的巨大挑戰(zhàn)。以我國某知名園區(qū)互連型公路貨運平臺為例,該平臺預期在2020年覆蓋千余條運輸路線;與兩萬個以上的物流企業(yè)和三十余萬個司機建立了加盟合作關系。根據國內公路貨運市場規(guī)模估計:每年約有3000萬貨車司機,在萬余條路線上承接共計343億噸公路貨運總量需求。巨大的市場規(guī)模意味著我國公路貨運平臺企業(yè)將面臨龐大的雙邊用戶規(guī)模,也意味著在公路貨運平臺企業(yè)運營中需要解決運力資源分配問題的規(guī)模龐大。此外,由于平臺注冊運力基數龐大、業(yè)務覆蓋地理空間廣闊,運輸市場波動和運價波動是影響平臺運力資源分配的關鍵因素。本文特研究具有規(guī)模巨大和運價信息不確定特征的運力資源分配問題。

本文的主要貢獻如下:

(1)根據園區(qū)互連型公路貨運平臺的運力資源分配問題的特點,分別建立了大規(guī)模運力資源分配問題模型和考慮運價波動的魯棒運力資源分配模型。

(2)針對考慮運價波動的魯棒運力資源分配模型為復雜半無限規(guī)劃的難點,給出了魯棒運力資源分配模型的等價確定性魯棒表達,將半無限規(guī)劃問題轉化為確定性非線性凸錐規(guī)劃問題,并證明了二者的等價性;

(3)針對魯棒運力資源分配模型的確定性魯棒表達模型規(guī)模巨大,現有商業(yè)求解器難以求解的難點,本文提出了一種原始對偶并行算法對該模型進行求解。

(4)通過仿真實驗,本文證明了魯棒運力資源分配模型得到的分配方案具有更好的抗價格波動的能力,并能幫助平臺科學設計保量合約策略;本文設計的算法能有效求解本文提出的魯棒運力資源分配問題。

本文結構如下:文章第一節(jié)綜述相關文獻研究。在第二節(jié),我們建立了運力資源分配模型,并在運力資源分配模型基礎上建立了考慮運價波動的魯棒運力資源分配模型,同時給出魯棒運力資源分配模型的確定性魯棒表達。在第三節(jié),我們提出了一種適應求解大規(guī)模問題魯棒運力資源分配模型的一階原始對偶并行算法。在第四節(jié),我們通過仿真實驗,論證了本文提出算法的有效性,以及本文提出的魯棒模型在科學決策的穩(wěn)健性和實施合約簽訂策略方面的應用價值;最后,第五節(jié)總結全文。

1 相關文獻綜述

目前對于運力資源分配問題的研究主要集中在兩個方向。第一個方向的研究主要是針對具體的貨主信息,向其推薦合適的運力資源。Yuan研究了如何通過乘客的出行方式和出租車出的GPS軌跡,利用推薦系統(tǒng)向出租車司機推薦合適的出租車[1],這類方法也應用在了車貨匹配問題中,Mallick使用強化學習的方法解決在線貨運平臺上,承運商如何作出運輸訂單決策的問題[2]。而賈艷麗等人通過設計考慮客戶綠色偏好的車貨匹配評價指標,并根據所建立的指標匹配體系以及所設權重建立多對多單邊匹配模型,判斷客戶和司機的匹配程度,并進行推薦[3]。Gale提出了經典的雙邊匹配問題模型[4],朱江洪基于經典雙邊匹配問題的模型,提出了考慮不確定性語言評價表征屬性信息的車貨匹配方法[5],Gheraibia和Gouin-vallerand[6]設計了考慮二氧化碳排放,燃料消耗和運輸擁堵程度等情況的貨運推薦系統(tǒng),為管理者提供能夠滿足客戶需求的更有效的車貨匹配方案。該類研究的成果也在滿幫等企業(yè)得到了一定的應用[7],但該類研究只能向貨主推薦運力資源信息,是否選擇推薦的運力資源由貨主決定而非平臺。第二個研究方向主要研究對于貨運車輛的指派問題,調度運輸企業(yè)內部的各類車輛,從而完成規(guī)定的貨運任務。Hoff在綜述了當運輸需求已知情況下,如何通過車輛路徑問題(vehicle routing problem, VRP)以及其變種進行路徑規(guī)劃,并給出了相應的算法[8]。李冰對多車型動態(tài)車輛調配問題進行了研究,并提出了利用限行函數來近似目標函數中未來時段部分,從而得到合理的車輛調配方案[9]。Zeimpekis考慮了動態(tài)隨機車隊管理,在制訂方案時考慮了當前的調度方案對未來各時段的影響,并綜述了相應的模型和算法[10]。余以勝等人提出了改進Balance算法的車貨匹配模型,引入了車貨匹配平衡函數定義各車型的匹配情況,并根據車貨之間的匹配關系對函數進行修正,使得決策結果相比貪婪算法在總收益上提高了18%[11],Powell研究了如何對于異質的大型卡車進行調度,并提出了相應的動態(tài)規(guī)劃算法[12],常連玉等研究了對于無車承運人,如何對當前的運力資源進行指派,從而能夠完成運輸車輛的最優(yōu)調度[13],Mu研究了如何對運力資源和運輸要求相似的貨源進行匹配[14]。該類指派調度問題雖然能夠達到運力資源分配的目標,但其決策者往往是擁有運輸車輛的運輸企業(yè),而非平臺企業(yè),并且其決策周期往往較短,數據規(guī)模也比較小。通過對運力資源分配問題的綜述,我們發(fā)現目前的研究主要集中在運力資源的推薦與短期的運力資源的指派,缺乏對于園區(qū)互聯型公路貨運平臺中長期運力資源分配問題的研究。

由于實際生活中很多問題都具有不確定性,自20世紀50年代左右出現了不確定優(yōu)化的研究,例如機會約束規(guī)劃[15],模糊規(guī)劃規(guī)劃[16],隨機規(guī)劃[17]等方式。模糊規(guī)劃是通過不確定參數的模糊隸屬函數來刻畫不確定性,但由于模糊隸屬度函數主要根據決策者的經驗得出,因此該方法具有較高的主觀性。隨機規(guī)劃是通過對數據進行分析,獲得不確定參數的分布模型,之后通過期望、機會約束等方式,使得到的解在大概率情況下是最優(yōu)的,該類方法在車隊的指派問題中也有著應用[10]。魯棒優(yōu)化則由Soyster于20世紀70年代提出[18],并由Ben-tal,Nemirovski等人發(fā)展成魯棒優(yōu)化理論[19-21]。相比于模糊規(guī)劃,魯棒優(yōu)化利用集合的方式對不確定變量進行描述,因此不需要不確定參數的模糊隸屬度函數和分布模型,同時,魯棒優(yōu)化的解考慮了不確定集合內最壞的情況,因此其結果較為穩(wěn)健,最優(yōu)決策方案對不確定因素波動的敏感性較低。近年來,魯棒優(yōu)化已被廣泛應用于供應鏈管理、項目管理等管理領域[22-24]。

2 園區(qū)互連型公路貨運平臺運力資源分配模型與考慮運價波動的魯棒運力資源分配模型

2.1 運力資源分配模型

貨主(運輸需求方)通過與平臺簽訂運輸合約,確保平臺能為其提供充分的運力資源,并保證運輸質量。而平臺的承運商(包括自營運力和加盟企業(yè)/司機)加盟平臺的目的是希望得到充足穩(wěn)定的運輸任務與合理運輸價格。在中長期決策之初,園區(qū)互連型公路貨運平臺通常根據貨主提出的運輸任務需求、貨運需求量預測以及平臺注冊運力對平臺運力資源進行分配。平臺在運力資源分配時,需要考慮平臺雙方用戶的價值需求,簽訂的運輸合約以及平臺自身發(fā)展需要,將貨主的不同區(qū)域的干線運輸任務,合理的分配給大量具有不同運輸范圍、運價特征、供給能力的運輸承運商,從而使得在中長期情況下,各類干線運輸任務能夠得到盡可能地滿足,同時最大程度的降低運輸成本。本節(jié)介紹運力分配問題的數學模型,首先給出如下定義:

(1)集合

Γ(j)={i:(i,j)∈}:可分配給干線的承運商j∈集合;

Γ(i)={j:(i,j)∈}:表示在承運商運輸范圍內需求干線i∈的集合。

(2)參數

cj:貨運干線j∈上的平均單位運輸收入;

dj:貨運干線j∈上的運輸需求總量;

c′ij:承運商i∈在承接貨運干線j∈時的單位運輸成本;

Pj(yj):凸的光滑單調遞增函數,描述需求損失量與損失懲罰的關系,其中j∈;

si:承運商i∈能夠提供的運力資源上限;

hi:平臺在合約中向承運商i∈承諾提供的最低運輸需求;

ωi:平臺在合約中向承運商i∈承諾提供的最低運輸需求占承運商能提供運力資源上限的比例,即

(3)決策變量

大規(guī)模運力資源分配模型主要考慮如何在決策周期內對大量不同的承運商提供的運力資源進行分配,從而使其能夠滿足貨運干線運輸需求,因此設每個承運商在各干線上分配的干線運輸任務的比例為決策變量。即:

xij:向承運商i∈分配在貨運干線j∈的運輸任務的比例;

yj:當運輸需求無法被滿足時,貨運干線j∈的需求損失量;

由此,大規(guī)模運力資源分配問題可表示為如下的優(yōu)化模型:

其中,(1)為目標函數,由兩項組成,第一項表示了平臺的總的凈運輸成本,該成本由需要平臺支付給承運商的成本扣除運輸收入組成。第二項表示當無法滿足運輸任務時,需要承擔的懲罰成本為約束條件,約束(2)為需求滿足約束,即對于每條貨運干線,分配的運力資源的數量必須滿足干線的需求,yj則表示無法滿足貨運干線j上運輸需求的數量,該類約束共有m條。約束(3)為運力資源限制約束,即分配的運力資源的總量不能超過物流企業(yè)能夠承接的總量,該類約束共有n條。約束(4)為運力資源合約約束,即平臺通過與承運商簽訂合約的方式,保證承運商i至少能夠分配到一定量的運力資源,該類約束共有n條。約束(5)為非負性約束,一共有m×(n+1)條。

一般來說,當需求無法預期完成時,平臺需要按照與貨主之間的合約,向貨主進行賠償。由于不同運輸干線的貨物價值與服務水平不同,簽署的合約也有所不同,因此懲罰成本P(y)也會隨之不同,常見的懲罰函數可用一個單調函數來表示,例如eayi-1(a＞0)。運輸服務高的干線對應的懲罰函數的遞增率會更大。不失一般性,我們在這里用非線性光滑凸函數Pj(yj)(j∈)來刻畫不同合約情況下的需求損失的懲罰。

為方便魯棒模型的構建與推導,我們將問題(EP)等價地表達為矩陣向量形式問題(EP′)。令承運商集合為={1,…,n},平臺承接的貨運干線集合為={1,…,m},令運力資源分配問題需要決策的變量數為t=mn,1m表示m維1列向量,0m表示m維0列向量。則(EP′)需要引入如下向量參數:

lij:判斷承運商類別i∈是否為承運商業(yè)務范圍內的可運輸干線j∈,如果可以運輸則lij=1,否則lij=0。

l∈?t:承運商的運營范圍判斷向量,l=(l11,…,l1m,

x∈?t:決策變量xij(i∈,j∈)向量,x=(x11,…,

y∈?m:決策變量yj(j∈)向量

c∈?t:承運商的單位凈運輸成本,j∈),其中

d∈?m:貨運干線j∈上的需求向量,d=(d1,…,

ω∈?n:平臺提供給承運商i∈最低運力需求占承運商運力上限比例向量

s∈?t:承運商能夠提供的運力資源參數si(i∈)向量,

同時,我們還引入如下參數矩陣:

這樣,運力資源分配問題(EP)可以表示為如下矩陣向量的等價形式。

其中⊙為矩陣的哈達瑪積運算。

2.2 考慮運價波動的魯棒運力資源分配問題模型

在中長期決策過程中,往往需要參考一些基于歷史數據分析的輔助決策系統(tǒng)給出的信息(如圖2所示)。在實際情況下,隨著運輸市場的不斷變化,運輸價格往往會產生波動,因此,在進行長期決策時,通過參考不同承運商的運價波動情況,會獲得更優(yōu)的資源分配決策。如平臺企業(yè)在不考慮運輸價格波動的情況,就可能會青睞運價較低的運輸企業(yè),在決策時向這些企業(yè)分配較多的運輸任務。但實際情況下,由于承運商與平臺簽訂的合約中明確規(guī)定,加盟商能夠按照市場情況對運價進行調整。因此若該類承運商在承接大量運輸任務后,在決策周期內上浮運價,則會造成平臺企業(yè)的運輸成本的大幅上升,嚴重甚至會導致資金鏈斷裂等風險,因此本文通過考慮分析不同承運商的歷史運價數據,從而制定出能夠一定程度上抵御價格波動特性的運力資源分配計劃,進而幫助平臺減少上述損失風險。

魯棒優(yōu)化作為一種不確定性最優(yōu)化方法,能夠基于歷史運價數據,通過構建不確定集合的方式描述參數的不確定性,管理者是基于該不確定集合進行科學決策。如考慮了不確定集合中最壞的情況,就能得到具有穩(wěn)健性的決策。由此,本節(jié)提出了基于價格波動的魯棒運力資源分配模型。在決策時通過參考所有承運商的運價的歷史信息,進而構造運價的不確定集合,由此幫助平臺制定更符合平臺服務環(huán)境和平臺風險承擔能力的運力資源分配計劃。

令運輸價格c的不確定集合為表示為U={c∈?t,其中為期望運輸價格向量,即通過歷史數據獲得的不同加盟承運公司在不同干線上的成本的期望,A∈?t×t為通過歷史數據獲得的不同加盟承運公司之間運價的協(xié)方差矩陣,ρ≥0為決策穩(wěn)健程度的系數。令為波動因素,取模。 這種對價格的刻畫方式,將運價的波動納入了對運輸價格的表達,使得模型能比期望運價模型更綜合的考慮運價均值和運價波動情況,更合理的選擇對應的承運商,從而增強了模型的抗運輸價格波動能力。考慮運輸價格波動的魯棒運力分配問題(RP)具體如下。

由于(RP)問題是一個復雜的半無限規(guī)劃,它包含無限個約束條件,直接求解十分困難,因此本文根據Ben-Tal提出的魯棒對等轉換理論(robust counterpart)[20],將其轉化為確定性魯棒表達。

命題1假設不確定集合‖ζ‖∞≤ρ},其中,A∈?t×t,ζ∈?t,則有

根據命題1,可以得到魯棒運力資源分配問題模型的確定性魯棒表達如下:

根據一階錐的定義,可以將(RPC)轉為非線性凸錐約束問題 :

3 求解魯棒運力資源分配模型的一階原始對偶并行算法

對于問題(EP′)與(RPC′),其變量數隨著承運商和貨運干線數量增加直線上升,同時,由于決策周期較長,園區(qū)互連型公路貨運平臺需要進行決策的承運商規(guī)模和貨運干線的數量都非常之大,這就導致了該類運輸資源分配問題的規(guī)模十分大。例如,按照國內目前某企業(yè)給出的規(guī)模數據,該企業(yè)每月需要制定近兩萬承運商在千余條路線上的運力資源分配計劃。則問題(EP′)與(RPC′)將會有千萬級別的決策變量與約束條件。更進一步,隨著平臺經濟的不斷發(fā)展,如果公路貨運平臺企業(yè)能夠承接全國1%的公路運輸需求,則代表著平臺企業(yè)每月需要制定面向幾十萬承運商的幾千條路線上運輸的資源分配計劃,此時問題(EP′)與(RPC′)的決策變量更是趨近十數億。對于這類復雜的大規(guī)模問題,常見的算法由于數據量過大,計算資源要求高的限制,很難甚至無法進行求解;同時,由于模型中會有錐約束,目標函數中Pj(yj)是非線性凸函數,導致CPLEX等常見的商業(yè)求解器也無法進行求解。因此,本文基于Zhao和Zhu[25]提出的一般非線性凸錐約束規(guī)劃的VAPP算法,提出一種求解大規(guī)模資源分配問題的一階原始對偶算法對本文提出的大規(guī)模魯棒資源分配問題進行求解。該方法通過將問題分解為多個能夠并行求解的子問題,分別求解后,通過對偶進行協(xié)調,進而迭代得到最終的計算結果(如圖3(a)所示)。該方法不同于順序迭代求解的串行算法(如圖3(b)所示)需要在每個子問題上都要使用全部的數據帶來的對高性能計算資源要求。VAPP算法的每個子問題相互獨立,因此只需要通過增加求解子問題計算資源的數量,便可提高運算的效率,因此具有更好的橫向延展性,更適合于大規(guī)模優(yōu)化問題的求解。

圖3 VAPP算法和串行算法迭代流程Figure 3 VAPP algorithm and serial algorithm iterative process

下面,我們將根據Zhao和Zhu[25]提出的有效求解非線性錐規(guī)劃的VAPP方法,給出求解(RPC′)的一階原始對偶算法。為了簡化表達,我們可以將模型(RPC′)寫成如下形式:

根據增廣Lagrangian的對偶理論,模型(15)的增廣Lagrangian函數可表示為:

其中,Lagrangian乘子p∈?m+3n+1,φ(Ω(u),p)=為在的共軛錐*上的投影。本文涉及的一階錐的共軛錐為,而

{?m+}和{?n+}共軛錐為其本身,其投影為投影對象的本身。Zhao和Zhu在[25]中提出求解問題(14)的原始對偶迭代方法:

在上一次迭代獲得的uk和pk基礎上求解原始子問題,得到uk+1:

在原始子問題解uk+1和上一次迭代獲得的乘子pk基礎上求解對偶子問題,通過投影得到pk+1:

該方法在原始方向上采用了線性化和規(guī)則化處理,因而原始優(yōu)化子問題(17)可分解為各變量的獨立優(yōu)化問題。對偶問題(18)是投影計算。

具體算法流程如下:

算法1=0m,λ02=λ03=0n,λ04=0n+1 :設置參數:α為一個足夠小的參數,最大迭代次數K for k=1,…,K計算原始方向子問題: xk+1=arg min初始化:x0=0t,y0=0m,z=0,λ0〈ˉc,l⊙s⊙x〉+〈qk1,B(l⊙x)〉+〈qk2,D(l⊙x)〉-〈qk3,D(l⊙x)〉+〈ˉqk4,A⊥(l⊙s⊙x)〉+1 2α‖x-xk‖2(19) yk+1=arg min x∈?t+y∈?m+〈▽P(yk)-qk1,y〉+1 2α‖y-yk‖2 (20) zk+1=arg min z≥0(1-^qk4)z+1 2α‖z-zk‖2 (21)計算對偶方向子問題: λk+1 1+(d-B(l⊙xk+1)-yk+1)) (22) λk+12=Π?n+(λk 1=Π?m+(λk 2+(D(l⊙xk+1)-1n)) (23) λk+1 3+(D(l⊙xk+1)+ω)) (24)3=Π?n+(λk 4+Θ(xk+1,zk+1)) (25)End for輸出:xK,yK λk+1 4=Πimages/BZ_178_460_2667_484_2698.pngn+1(λk∞

特別需要指出的是:通過對原始方向優(yōu)化問題(23～25)的分析,各個子問題均存在如下閉合表達式:

可以看到,VAPP算法在原始問題上的x,y,z的求解是相互獨立的,即可以分別利用計算資源,通過閉合表達式(19～21)在原始方向上對x,y,z的進行并行迭代求解。同時,對于向量x,y,z的求解,由于向量的每個元素的更新均相互獨立,因此對于x,y,z的每個元素也能夠進行并行求解。通過這種并行求解的方式,將計算任務分攤到多個計算資源上,解決了大規(guī)模資源分配問題中,計算資源無法存儲和計算大規(guī)模變量的問題。

此外,通過分析我們不難得到問題(RPC′)為非線性凸錐規(guī)劃問題,根據凸分析理論,凸問題(RPC′)的KKT點即為問題的最優(yōu)解。算法迭代點wk=(xk,yk,zk,λk1,λk2,λk3,λk4)給出KKT映射如下:

定義1(問題(RPC′)的ε-近似解)如果點滿足如下不等式

我們稱w*為凸問題(RPC′)的ε-近似解。如果ε=0,w*則為問題(RPC′)的最優(yōu)解。

命題2假設序列{wk}由算法1生成,則有存在δ＞0,使得如下不等式成立

RCP′滿足Zhao和Zhu給出的定理1中[25]給出的所有條件,因此算法產生序列{wk}有界,并收斂到問題的KKT點,即‖wk-wk+1‖→0。根據命題2,‖wk-wk+1‖≤ε′可作為算法的終止條件,其中ε′=ε/δ,δ為一個不隨算法迭代變化的正數。如果‖wk-wk+1‖≤ε′,算法的迭代點wk+1可看作問題(RPC′)的ε-解。

4 仿真實驗

4.1 仿真環(huán)境設置

由于計算資源的限制,本文仿真實驗中設置運輸路線為10條,承運商為100家,則具有一千多個決策變量和兩千多條約束。對線路和承運商的仿真數據設置如下:

由圖1可知,平臺會將承運商根據其企業(yè)規(guī)模、風險等級及簽約要求等信息進行分類并簽訂不同類型的合約。因此,本實驗將承運商分為4類:臨時承運商、短期合約承運商、中期合約承運商以及長期合約承運商,每類承運商25家,每類承運商能夠提供的運力為1.357萬噸,所有承運商能夠提供的運力為5.428萬噸?？偟倪\輸需求為3.6187噸。每家承運商的運輸能力以及營運范圍由仿真系統(tǒng)隨機生成。

一般來說,平臺與臨時承運商不簽訂保量合約。因此臨時承運商價格受市場影響較大,運輸市場的淡旺季等因素會對臨時承運商的價格造成很大的影響。臨時承運商雖然運價均值較低,但運價的波動性較大,平臺將與其他三類承運商簽訂不同期限的運力合約。合約時間越長,平臺向承運商提供的運力報價也會相應提高,同時承運商的運價波動也會相應減小。仿真系統(tǒng)按照上述原則生成了100家承運商20天內的運輸價格數據集。其中承運商運價均值越高,對應的方差越高,代表運價的波動性越大。將100家承運商20天內的運輸價格數據集按照承運商類型進行匯總,得到表1的運價均值數據。根據表1得到的運價數據,結合設定的平臺利潤率情況,仿真系統(tǒng)生成每條路線上對貨主方面的運輸價格cj。

表1 運輸路線上各類承運商及平臺對貨主的運價均值(單位:元/噸)Table 1 The mean freight rate of various kinds of carriers and platform income on the transport route (in yuan/ton)

4.2 算法有效性分析

4.2.1 實驗目標

算法有效性分析實驗通過對算法迭代的相對誤差進行分析,證明算法的有效性。

4.2.2 實驗方案

定義相對誤差ek=‖wk-wk+1‖,由于問題(RPC′)滿足Zhao和Zhu給出的定理1中[25]給出的所有條件,因此算法產生序列{wk}有界,并收斂到問題的KKT點。則根據命題2,ek可以作為算法有效性的表征。

圖4 算法有效性分析Figure 4 Effectiveness analysis of the algorithm

4.2.3 實驗結論

由圖4可以看到,隨著算法的逐漸迭代,相對誤差ek逐漸減小并趨近于0,說明算法正逐漸收斂到問題的KKT點。由此,圖4證明了本文提出的算法能夠有效的求解 (RPC′)魯棒資源分配問題。

4.3 魯棒模型決策有效性分析

4.3.1 實驗目標:

魯棒模型決策有效性分析實驗主要通過對運力資源分配模型(EP′)和魯棒運力資源分配模型(RPC′)計算結果進行比較,證明魯棒運力資源分配模型(RPC′)對于抵抗運價波動上的有效性。

4.3.2 實驗參數設計:令表示為干線i上無法滿足的貨運量的單位懲罰成本,令懲罰項為仿真所需的運力數據來源于4.1中的仿真環(huán)境。其中運力資源分配模型(EP′)運輸價格為仿真環(huán)境中每家承運商的運價均值,魯棒運力資源分配模型(RPC′)的運價信息與運價波動信息來源于仿真環(huán)境4.1中的承運商運價數據集。根據仿真數據的特點,取三種不確定集合:ρ=0.001,ρ=0.0005,ρ=0.0001,產生三種魯棒模型:(RPC′-1),(RPC′-2),(RPC′-3)。

4.3.3 實驗方案:

按照仿真環(huán)境中得到的運價均值數據以及運力數據,得到問題(RPC′-1),(RPC′-2),(RPC′-3),(EP)的運力資源分配計劃。而后按照仿真環(huán)境中給出的不同承運商的運價均值和方差,生成實時運價,進而能夠得到不同運力資源分配計劃的運輸成本。將上述過程重復100次,則可以得到長期運行情況下,問題(RPC′-1),(RPC′-2),(RPC′-3),(EP)的運力資源分配方案成本的均值和方差情況,實驗結果如表2。

表2 魯棒有效性分析中不同決策模型多次仿真實驗系統(tǒng)成本結果(單位:萬)Table 2 System cost of simulation experiments with different decision-making model in robust effectiveness analysis (in ten thousand)

4.3.4 實驗結論

根據實驗計算和分析,我們能夠得到如下結論:

(1)魯棒運力資源分配模型具有更好的抗價格波動能力,而運力資源分配問題(EP′)受價格波動的影響較大。在100次的隨機價格波動中,問題(RPC′-1)和(RPC′-2)的方差,最大值以及最小值均沒有發(fā)生太大的變化;問題(RPC′-3)的方差相比前兩者較大,并且最小值發(fā)生了比較明顯的變化;問題(EP′)的方差最大,并且其最大值和最小值的差異也比較明顯,說明其會根據價格的波動產生比較明顯的變化。

(2)魯棒運力資源分配模型得到的運輸成本的均值高于運力資源分配問題(EP′)。相比于問題(EP′),魯棒運力資源分配模型的運輸成本較高。隨著決策穩(wěn)健性的提升,其運輸的成本也會相應增加。

4.3.5 管理建議

由魯棒模型決策有效性分析實驗我們發(fā)現,更強的抗價格波動能力往往會導致運輸成本的提升。因此企業(yè)需要根據其發(fā)展階段與自身的發(fā)展策略,對決策策略進行調整,制定出符合企業(yè)發(fā)展階段的運力資源分配計劃,使得企業(yè)能夠有效應對運輸市場的價格波動,保證企業(yè)的健康發(fā)展。

本文提出魯棒運力資源分配模型,不僅能夠在運營層面上幫助企業(yè)制定長期運力資源分配策略,同時能夠通過對ρ的調整實現對決策穩(wěn)健性進行調整,進而幫助企業(yè)理解不同決策策略下的抗價格波動能力與運輸成本之間的關系,從而能夠在戰(zhàn)略層面上指導企業(yè)制定出更符合企業(yè)發(fā)展階段的長期運力資源分配決策。

4.4 保量合約設計分析

4.4.1 實驗目標:

揭示平臺合約策略對運力資源分配的作用,為平臺管理者提供設計保量合約策略的科學思路。

4.4.2 實驗參數設計:

本次實驗設計了四類合約策略,不同的合約策略表示平臺對不同類型運力的偏好程度。其中,合約策略1表示平臺對四類運力均不簽署運力合約;合約策略2表示與短期合約承運商簽訂較大的保量合約,而對長期合約承運商簽訂較小的保量合約;合約策略3表示與三類合約運力簽訂同樣大小的保量合約;合約策略4則表示對長期合約承運商簽訂比較大的保量合約,而對短期合約承運商簽訂比較小的保量合約。具體的保量合約簽訂情況如表3所示。

表3 保量合約設計分析中不同合約策略下每類運力的保量合約簽訂情況Table 3 The signing status of the volume contract of each type of capacity under different contract strategies in the analysis of the volume contract design

4.4.3 實驗方案:

按照仿真環(huán)境中得到的運價均值數據以及運力數據,分別得到四種合約策略下的運力資源分配計劃。而后按照仿真環(huán)境中給出的不同承運商的運價均值和方差,生成實時運價,進而計算能夠得到不同合約策略下的運輸成本。將上述過程重復100次,則可以得到長期運行情況下,四種合約策略下的運力資源分配方案成本的均值和方差情況,實驗結果如表4所示。

表4 保量合約設計分析中不同合約策略多次仿真實驗系統(tǒng)成本結果(單位 萬)Table 4 System cost of simulation experiments with different contract design strategies (in ten thousand)

將不同合約策略下,各類承運商在分配結果中的運力資源占比情況進行統(tǒng)計,得到表5所示結果。

表5 保量合約設計分析中不同合約策略下運力資源占比情況(單位:萬)Table 5 The proportion of capacity resources under different contract strategies in contract designing analysis (in ten thousand)

4.4.4 實驗結論

根據上述實驗,我們能夠得到如下結論:

(1)合約簽訂策略會對運力分配抗價格波動能力產生影響。由表4我們可以看到,平臺與中長期運力類型承運商簽約較高運輸合約比例,會提升系統(tǒng)的抗價格波動能力,但同時也會增加系統(tǒng)運輸成本。

(2)合約簽訂策略也會對不同類型承運商的運力分配結果產生明顯影響。由表5能夠看到,當平臺與短期合約承運商簽訂較高的保量合約(合約策略2),將導致短期合約承運商運力占比明顯上升;而隨著向中長期合約承運商簽訂保量合約比例的上升(合約策略3,4),中長期合約承運商在整個運力資源分布中的占比明顯上升。

4.4.5 管理建議

合約的簽訂策略會導致運力分配決策結果抗運價波動能力的變化。平臺需要根據其發(fā)展階段,合理的選擇合約策略,才能夠保證其健康長效的發(fā)展。例如,在平臺發(fā)展初期,可能需要與短期合約承運商簽訂較大比例的合約,進而保證平臺能夠吸引到足夠的運力資源。而在平臺發(fā)展的穩(wěn)定階段,為保證平臺有更好的抗價格波動的能力,平臺需要適量降低對短期合約承運商的保量合約簽訂比例,提高對中長期合約承運商的保量合約簽訂比例。

本文提出的魯棒運力資源分配模型,能根據企業(yè)不同的合約策略,得出對應的運輸資源分配方案。因為企業(yè)能夠對不同合約策略的反應結果有直觀和科學的認識,從而能夠在戰(zhàn)略層面上,指導企業(yè)制定出符合自身發(fā)展的合約簽訂策略。

5 總結

本文研究了“互聯網+”模式下,園區(qū)互連型公路貨運平臺對運輸資源有效組織分配問題,針對平臺企業(yè)用戶規(guī)模大,價格波動敏感的特點,本文提出了考慮價格波動的魯棒運力資源分配模型,由于這一模型為復雜半無限規(guī)劃問題,因此本文利用對偶范數和一階錐的定義,給出了這一問題的可計算確定性魯棒表達,并應用Zhao和Zhu提出的VAPP算法框架,設計了能夠并行運算的且在多項式時間內收斂的求解算法。

最后,本文通過仿真實驗證明了本文算法的有效性。同時,實驗證明了本文提出的算法在戰(zhàn)略層面和運營管理層面均有很好的適用性。在戰(zhàn)略決策層面,本文提出的魯棒運力資源分配模型能夠對結合運力分配穩(wěn)健性策略和合約簽訂策略仿真,可幫助企業(yè)制定出符合自身發(fā)展期望的運輸分配方案,促進企業(yè)實現企業(yè)戰(zhàn)略決策智能化。在運營管理層面,本文提出的魯棒運力資源分配模型能夠結合企業(yè)實際的運營情況,制定出滿足雙邊用戶需求的最優(yōu)運力分配方案,提高企業(yè)的運營效率和質量。