需求不確定情況下沿海燃料油供應魯棒優化

劉炬　鐘銘　黃夢思　陳江濤　張宇涵

摘要：

針對沿海地區燃料油供應問題，制定燃料油配送方案，設計配送航線和配送量使運輸成本和庫存成本最小，同時考慮需求不確定的情況，使需求發生一定變動時原方案依舊可行。與不考慮需求不確定的供應方案相比，使用魯棒優化方法得到的結果可靠性更強，發生缺貨的可能更小。由于需求不確定情況下存在的二次約束嚴重影響模型的求解效率，提出一種兩階段求解方法來分解問題，使求解效率得到明顯提高。對于存在需求不確定情況的供應系統，決策者使用該魯棒優化模型時，可以根據風險偏好并通過調整參數最大限度地提高供應方案的可靠性。

關鍵詞：

沿海燃料油供應;?庫存路徑;?魯棒優化;?需求不確定;?可靠性

中圖分類號：F550.5

文獻標志碼：A

收稿日期：?2018-09-29

修回日期：?2018-12-17

基金項目：

國家重點研發計劃（2017YFC0805309）;遼寧省交通科技項目（201704）;遼寧省高等學校教育教學改革研究項目（PI201527）

作者簡介：

劉炬（1993—），男，湖北隨州人，碩士研究生，研究方向為交通運輸工程，（E-mail）lj_931025@126.com;

鐘銘（1965—），男，遼寧大連人，教授，博導，博士，研究方向為交通運輸規劃與管理、物流工程與管理，（E-mail）zhongming_dlmu@126.com

Robust?optimization?of?short?sea?fuel?oil?distribution

under?demand?uncertainty

LIU?Jua，?ZHONG?Minga，?HUANG?Mengsib，?CHEN?Jiangtaoa，?ZHANG?Yuhana

（

a.?College?of?Transportation?Engineering;?b.?School?of?Maritime?Economics?and?Management，

Dalian?Maritime?University，?Dalian?116026，?Liaoning，?China）

Abstract：

Aiming?at?a?fuel?oil?distribution?issue?in?short?sea，?the?fuel?oil?distribution?scheme?is?developed，?the?distribution?route?and?distribution?quantity?are?designed?to?minimize?the?transportation?cost?and?inventory?cost，?and?the?uncertain?demand?is?taken?into?account?in?order?that?the?scheme?is?able?to?stay?feasible?when?the?demand?uncertainty?happens.Comparing?with?the?scheme?under?deterministic?demand，?the?scheme?developed?by?the?robust?optimization?method?is?more?reliable?and?less?likely?to?occur?out?of?stock.?Because?the?quadratic?constrain?under?the?demand?uncertainty?makes?the?solving?efficiency?terrible，?a?two-stage?solving?method?is?proposed?to?decompose?the?problem，?which?improves?the?solving?efficiency?greatly.?For?the?distribution?system?under?demand?uncertainty，when?decision?makers?adopt?the?robust?optimization?model，?the?reliability?of?the?distribution?scheme?can?maximize?according?to?their?risk?preference?and?through?adjusting?the?parameters.

Key?words：

short?sea?fuel?oil?distribution;?inventory?routing;?robust?optimization;?demand?uncertainty;?reliability

0?引?言

沿海燃料油供應問題屬于海運庫存路徑問題（maritime?inventory?routing?problem，MIRP）。在經典的車輛路徑問題（vehicle?routing?problem，VRP）中，供應商使用不同的車輛將貨物配送到所有需求節點上，并返回供應節點，要求成本最小化。庫存路徑問題（inventory?routing?problem，?IRP）以VRP為基礎，是一類典型的運輸問題。VRP與IPR的區別在于：VRP只考慮運輸，而IRP中供應方既負責運輸又負責庫存。庫存的引入更適用于研究多階段、長周期運輸問題，而庫存成本與運輸成本間的“二律悖反”效應（即一種成本的降低必然導致另一種成本的增加）使得IRP的研究內容更加豐富。通常海上貨物運輸中，承運人只負責運輸階段，貨交收貨人即責任終止，一般不會考慮庫存問題。然而，燃料油、天然氣這類貨物的供應方會同時負責運輸和庫存成本，某些特殊貨物如水泥、化學品、瀝青等的運輸也符合MIRP的特點。與傳統班輪和雜貨運輸不同，MIRP中掛靠港數量通常是固定的，但運輸路徑和掛靠港順序是變動的。在研究內容上，MIRP與上述IRP相似，不同的是海運中由于港口掛靠成本高并且泊位限制和靠泊過程較長等問題，一個需求港通常只允許被掛靠一次（即不能使用多條船為同一港口服務）。MIRP通常研究單貨種、多周期、一對多（一個供應節點對應多個需求節點）的運輸，路徑規劃建立在各節點的需求量已知和各種參數均為確定參數的基礎上，而不確定參數問題近些年逐漸受到重視。最初MIRP主要以連續時間為主，后來離散時間被引入，AGRA等[1]研究了連續時間和離散時間下的沿海IRP，結果表明用離散時間容易取得更優的目標函數邊界，而用連續時間的求解速度更快。若需求是固定的，則適合使用連續時間;若需求是浮動的，則適合使用離散時間。對于需求確定的MIRP，船舶配置和航線選擇相對固定，適合研究多周期問題[2]，而在需求不確定或難以預測的情況下更傾向于研究單周期或短周期問題[3]。近年來多貨種MIRP逐漸顯現，主要以油品或化學品運輸作為研究對象[4]，因為多種液態貨物通常不能混合運輸，所以會使用多艙室船舶，因此一個航次同一艙室要求只裝一種貨物，甚至同一個艙室相鄰兩個連續航次只能裝同一種貨物。MIRP中貨物來源于單一供應港和多供應港，CHRISTIANSEN等[5]對多年來各類海運方面文獻做了總結和概述。

MIRP屬于NP難問題，精確算法通常用來求解小規模問題，分支定界法和分支切面法等精確算法[6]是求解混合整數規劃（mixed?integer?programming，?MIP）模型的主要方法，有效不等式和緊縮約束在模型改進方面有很重要的應用[7]。隨著模型規模的增加，精確算法很難在有限的時間內取得令人滿意的結果，因此變量鄰域下降搜索法[8]、滾動時域法[9]等啟發式算法的開發意義重大。實際上，需求和運輸時間兩個因素在特定的MIRP中具有很強的不確定性：需求沒有得到滿足容易產生很高的補貨成本;有的貨物需要在一定的期限內送達，否則會延誤船期，而船舶的航行受很多種因素的影響致使運輸時間往往難以保證。近年來，不確定性MIRP的研究逐漸受到關注，GUSTAVO等[10]使用魯棒優化方法研究了航行時間不確定時的MIRP，使得在航行發生一定延誤的情況下原方案仍然具有很強的可行性，并且局部搜索啟發式算法對魯棒優化問題也有很好的效果。AGRA等[11]首次使用隨機規劃方法研究了航行時間和在港時間不確定時的MIRP。ADULYASAK等[12]在公路運輸的VRP中針對運輸時間不確定情況，使用隨機優化和魯棒優化方法得到魯棒性更強的配送方案。MAGGIONI等[13]研究了需求和租車價格不確定情況下的運輸配車問題，發現隨機優化方法可以使成本更小，但魯棒優化方法對不確定的控制能力更強。LI等[14]研究了考慮運輸準備時間的IRP，其中庫存水平不確定但未來概率分布已知，屬于隨機優化的范疇。隨機優化是研究不確定問題的一種重要手段，但隨機參數需服從確定的概率分布，而現實問題中不確定因素往往不是嚴格服從某種分布發生的，因此很難得到分布函數;魯棒優化不需要知道參數的分布，更適合研究不確定性問題。SOYSTER[15]最早提出魯棒優化的概念，但由于所采取的盒式魯棒過于保守而被否定;BEN-TAL等[16]在SOYSTER的基礎上添加橢球約束，使得保守性大大降低，并且可以根據決策者風險偏好選擇合適的參數加以調節。隨后結合范數的概念，魯棒不確定集被泛化成Norm-ball不確定集，上述兩種不確定集也被納入這個范疇，盒式不確定集屬于無窮范數，而BEN-TAL橢球不確定集為2范數。使用不同的范數，不確定集具有不同的形狀，Norm-ball不確定集中使用最多最具有代表性的是2范數即橢球不確定集。BERTSIMAS等[17]從另一個角度出發，設計了通過控制不確定參數個數來調節保守性的魯棒優化，成為魯棒優化方法中具有代表性的一種。SOLYALI等[18]首次使用這種方法研究了需求不確定下的IRP，問題設定為一對多、單貨種、多周期的供應系統。這種魯棒形式只能考慮部分節點需求不確定性，而現實中所有節點的需求都具有不確定性。

本文聯系實際考慮燃料油供應中各節點需求不確定性，從而基于橢球不確定集的魯棒優化與隨機優化相比更貼近實際。這是因為隨機優化建立在概率分布已知的基礎上，確定一種概率分布本身就具有很強的主觀因素。基于需求發生變動的港口數量不確定的魯棒優化（另一類魯棒思想）總會忽視部分港口需求不確定，相比之下橢球不確定性集可以兼顧所有港口需求不確定，更符合經營實際。在考慮不確性參數時使用橢球不確定集并針對其中的二次約束對模型進行拆分，有以下優點：（1）避免模型過于保守，即過濾了所有港口需求都波動過大的情況;（2）可以兼顧所有港口的需求不確定;（3）可以針對不同的決策方案，根據決策者的風險偏好或者保守程度，通過調節參數θ的值控制模型的魯棒性。（4）求解中將原含有二次約束的混合模型拆分為一個線性模型和一個純二階錐優化模型，采用兩階段求解方法使求解效率得到明顯提高。

1?確定性模型

1.1?問題描述

燃料油公司有多個燃料油供應基地，每個基地有若干船舶，定期將燃料油配送到需求港以滿足未來時期各地區燃料油需求。燃料油公司承擔需求港的燃料油庫存成本和運輸成本，未來時期需求不確定，配送方案需要具有一定魯棒性，盡可能防止缺貨發生。由于需求不確定，本文進行單周期研究，采用多供應港對多需求港的供應模式，貨種為單貨種。運輸中每艘船從所屬供應港出發完成多個港口供應，并回到所屬港口，每個需求港只由一艘船服務，燃料油公司需要確定合適的船舶、配送量、運輸航線以安排配送。需求港庫存成本按燃料油的勻速消耗計算，不考慮供應港庫存量和成本，由于不考慮運輸時間的不確定，且燃料油配送對船期要求不高，故忽略船舶航行時間問題。

1.2?符號說明

N為所有節點的集合，i，j∈N;NS={1，2，…，m}為供應港集合，ND={1，2，…，n}為需求港集合，N=ND∪NS={1，2，…，m+n};Nv為由船舶v服務的港口集合，NvN;V為異構船隊集合，船舶v∈V。

di為港口i的需求量;d*i為港口i的需求量均值;σi為港口i需求量所在區間半徑，即di∈d*i-σi，d*i+σi;Wv為船舶v的最大載重噸;cijv為船舶v在弧（i，j）上的航行成本，與航線距離和船舶有關;Ii為港口i的最大庫存量，供應港庫存無限制;Hi為港口i在規劃期初原有庫存量;Ci為港口i的單位庫存持有成本，港口庫存成本與庫存量成正比;gi為港口i因未滿足需求而產生的單位缺貨損失成本（懲罰成本）;Fv為船舶v一個航次的固定成本;ziv為0-1變量，若v是供應港i的船舶則為1，否則為0;u（v，i）表示船舶v掛靠港i的序號（無實際意義僅用于消除子圈）。

xijv為0-1決策變量：若船舶v在有向弧（i，j）上航行，則為1，否則為0;i和j不能同時為供應港。yiv為0-1決策變量：若船舶v在港口i裝卸燃料油，則為1，否則為0;i可以是供應港也可以是需求港。ωjiv為供應港j通過船舶v向需求港i運輸的燃料油量。

[WTHX]x[WTBX]、

[WTHX]y[WTBX]、[WTHX]ω[WTBX]為以上3個決策變量的矩陣形式。

1.3?模型建立

先建立需求確定情況下的燃料油庫存路徑成本數學模型，其中除

特殊說明外，i∈N，j∈N，v∈V。目標函數為

式（1）為目標函數，為規劃期內總成本最小，包括規劃期內總運輸成本、總庫存成本。式（2）保證弧（i，j）上的兩港口不能同時為供應港。式（3）、（4）表示船舶v在弧（i，j）上航行的前提是船舶v在港口i、j都掛靠。式（5）～（7）為船舶流量平衡。式（8）為艙容限制。式（9）表示一個港口只能由一艘船服務。式（10）保證需求被滿足。式（11）表示供應港的船必須掛靠該船所屬供應港。式（12）表示船舶向港口供貨必掛靠港口，且掛靠必供貨。式（13）表示供應港的貨物必須由該供應港的船運輸。式（14）、（15）表示消除子圈。式（16）～（19）為0-1約束和非負約束。式（11）～（14）為一對多模型泛化到多對多模型的關鍵。

1.4?不確定性魯棒優化模型

由于每個港口的需求是未知的，但根據長期經營得來的數據可知，需求的變動并不是任意的，而是在一定范圍內變動的。假設需求以

在集合中存在十分極端的需求組合，如所有需求都波動到最大可能取值，但事實上即便從概率角度考慮，這種情形是極不可能出現的。如果將這個集合作為不確定集，則過于保守，因此需要通過約束去除保守組合。橢球不確定集[19]

[WTHX]d[WTBX]構成的n維橢球體，σi是港口i需求量所在區間半徑也是橢球體對應軸的半徑，θ2θ≥0用來控制橢圓大小，是調節保守性的參數。當θ=0時，不確定集縮小到一點，成為確定性問題;當0<θ<1時，

2?模型分解與轉化

上述模型中存在二次約束，這使得求解現實的小規模問題的時間依然很長，因此需要加以改進。式（10）和目標函數中都含有不確定參數，不利于計算，可以利用拉格朗日乘子法將約束以懲罰成本的形式轉移到目標函數中，同時懲罰成本允許缺貨的發生，但必須接受一定的懲罰，使模型更加靈活。寫成如下形式：

z

當約束被破壞即g（x）<0時，d，u無窮小，其中u>0為懲罰因子。算法步驟如下：（1）初始化懲罰因子u（0）>0，取接近于0的閾值e;（2）令k=0，在定義域內取初始值，計算*d（0），u（0）;（3）k=k+1，u（k）=cu（k-1），0

通過內點懲罰函數法求解式（25）得到worst-case下的需求量

[WTHX]d[WTBX]#，將其代入z得到z1的魯棒解。分解之后模型求解效率比直接求解效率高很多，對于求解現實規模大小的問題，效果明顯。

3?算例分析

3.1?算例介紹

選擇18個港口，其中2個供應港，16個需求港，其中{1，2，…，16}為需求港集合，{17，18}為供應港集合。共有供油船5艘，相關固定成本信息見表1。港口需求量和規劃期初庫存量見表2。假設港口不確定需求半徑為需求水平的25%（即

[3]MILORAD?V，?DRAEN?P，?BRANISLAVA?R.?Mixed?integer?and?heuristics?model?for?the?inventory?routing?problem?in?fuel?delivery[J].?International?Journal?of?Production?Economics，?2014，?147：?593-604.DOI：?10.1016/j.ijpe.2013.?04.034.

[4]RACHANIOTIS?N?P，?MASVOULA?M.?A?decision?tool?for?scheduling?fleets?of?fuel?supply?vessels[J].?Operational?Research：?An?International?Journal，?2018（9）：?1-15.?DOI：?10.1007/s12351-018-0377-2.

[5]CHRISTIANSEN?M，?FAGERHOLT?K，?NYGREEN?B，?et?al.?Ship?routing?and?scheduling?in?the?new?millennium[J].?European?Journal?of?Operational?Research，?2013，?228（3）：?467-483.?DOI：?10.1016/j.ejor.2012.12.002.

[6]GRNHAUG?R，?CHRISTIANSEN?M，?DESAULNIERS?G，?et?al.?A?branch-and-price?method?for?a?liquefied?natural?gas?inventory?routing?problem[J].?Transportation?Science，?2010，?44（3）：?291-428.DOI：?10.1287/trsc.1100.0317.

[7]AGRA?A，?CHRISTIANSEN?M，?DELGADO?A，?et?al.?Hybrid?heuristics?for?a?short?sea?inventory?routing?problem[J].?European?Journal?of?Operational?Research，?2014，?236：?924-935.?DOI：?10.1016/j.ejor.2013.06.042.

[8]AGRA?A，?CHRISTIANSEN?M，?HVATTUM?L?M，?et?al.?Robust?optimization?for?a?maritime?inventory?routing?problem[J].?Transportation?Science，?2018，?23：?1-17.DOI：?10.1287/trsc.?2017.0814.

[9]RAKKE?J?G，?STALHANE?M，?MOE?C?R，?et?al.?A?rolling?horizon?heuristic?for?creating?a?liquefied?natural?gas?annual?delivery?program[J].?Transportation?Research?Part?C，?2011，19（5）：?896-911.?DOI：?10.1016/j.trc.2010.09.006.

[10]GUSTAVO?S?D?S?D，?SILVIO?H，?FABRICIO?O.?Robust?optimization?for?a?maritime?inventory?routing?problem[J].?Flexible?Services?and?Manufacturing?Journal，?2018，?1：?1-17.DOI：?10.1007/s10696-018-9327-9.

[11]AGRA?A，?CHRISTIANSEN?M，?DELGADO?A，?et?al.?A?maritime?inventory?routing?problem?with?stochastic?sailing?and?port?times[J].?Computers?&?Operations?Research，?2015，?61：?18-30.DOI：?10.1016/j.cor.2015.01.008.

[12]ADULYASAK?Y，?JAILLET?P.?Models?and?algorithms?for?stochastic?and?robust?vehicle?routing?with?deadlines[J].?Transportation?Science，?2016，?50（2）：?608-626.

[13]MAGGIONI?F，?POTRA?F?A，?BERTOCCHI?M.?A?scenario-based?framework?for?supply?planning?under?uncertainty：?stochastic?programming?versus?robust?optimization?approaches[J].?Computational?Management?Science，?2017，?14（1）：?5-44.?DOI：?10.1007/s10287-016-0272-3.

[14]LI?Ming，?WANG?Zheng，?CHAN?F?T?S.?A?robust?inventory?routing?policy?under?inventory?inaccuracy?and?replenishment?lead-time[J].?Transportation?Research?Part?E，?2016，?91：?290-305.DOI：?10.1016/j.tre.2016.05.001.

[15]SOYSTER?A?L.?Convex?programming?with?set-inclusive?constraints?and?applications?to?inexact?linear?programming[J].?Technical?Notes，?1973，?21：?1154-1157.

[16]BEN-TAL?A，?NEMIROVSKI?A.?Robust?solutions?of?uncertain?linear?programs[J].?Operations?Research，?1999，?25（1）：?1-13.

[17]BERTSIMAS?D，?SIM?M.?The?price?of?robustness[J].Operations?Research，?2004，?52（1）：35-53.

[18]SOLYALI?O，?CORDEAU?J?F，?LAPORTE?G.?Robust?inventory?routing?under?demand?uncertainty[J].?Transportation?Science，?2012，?46（3）：?327-340.?DOI：?10.1287/trsc.1110.0387.

（編輯?趙勉）