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

摘要：

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

關鍵詞：

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

中圖分類號：F550.5

文獻標志碼：A

收稿日期：?2018-09-29

修回日期：?2018-12-17

基金項目：

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

作者簡介：

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

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

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

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

1?確定性模型

1.1?問題描述

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

1.2?符號說明

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

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

xijv為0-1決策變量：若船舶v在有向?。╥，j）上航行，則為1，否則為0;i和j不能同時為供應港。yiv為0-1決策變量：若船舶v在港口i裝卸燃料油，則為1，否則為0;i可以是供應港也可以是需求港。ωjiv為供應港j通過船舶v向需求港i運輸?shù)娜剂嫌土俊?/p>

[WTHX]x[WTBX]、

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

1.3?模型建立

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

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

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

1.4?不確定性魯棒優(yōu)化模型

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

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

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

2?模型分解與轉(zhuǎn)化

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

z

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

通過內(nèi)點懲罰函數(shù)法求解式（25）得到worst-case下的需求量

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

3?算例分析

3.1?算例介紹

選擇18個港口，其中2個供應港，16個需求港，其中{1，2，…，16}為需求港集合，{17，18}為供應港集合。共有供油船5艘，相關固定成本信息見表1。港口需求量和規(guī)劃期初庫存量見表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.

（編輯?趙勉）