需求不确定情况下沿海燃料油供应鲁棒优化

刘炬　钟铭　黄梦思　陈江涛　张宇涵

摘要：

針对沿海地区燃料油供应问题，制定燃料油配送方案，设计配送航线和配送量使运输成本和库存成本最小，同时考虑需求不确定的情况，使需求发生一定变动时原方案依旧可行。与不考虑需求不确定的供应方案相比，使用鲁棒优化方法得到的结果可靠性更强，发生缺货的可能更小。由于需求不确定情况下存在的二次约束严重影响模型的求解效率，提出一种两阶段求解方法来分解问题，使求解效率得到明显提高。对于存在需求不确定情况的供应系统，决策者使用该鲁棒优化模型时，可以根据风险偏好并通过调整参数最大限度地提高供应方案的可靠性。

关键词：

沿海燃料油供应; 库存路径; 鲁棒优化; 需求不确定; 可靠性

中图分类号：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.

（編辑 赵勉）