石油海运领域运筹优化方法应用研究综述

王 薇，郑澜波

（武汉理工大学 物流工程学院，湖北 武汉 430063）

1 引言

化学品生产体量较大，且属危险品必须以安全方式运输，因此化学品相关行业供应链成本在所有行业中排名最高。作为全球化学品供应链重要组成部分，石油的海洋运输物流成本高达采购成本的20%。石油海上运输涉及油轮作业、航线制定等决策问题，都直接影响石油运输成本，这些问题大多涉及多类型资源且具备多种约束，是决策复杂性高的组合优化问题。随着运筹技术的发展，运筹优化技术在调度及路由问题上有着丰富的实际应用与研究成果，同样适用于石油海上运输的优化场景。越来越多的学者借助运筹优化方法解决石油海运优化问题，提升海运效率和经济效益。

2 文献检索及场景划分

通过知网、万方等搜索引擎进行检索，得到国内有关石油海上运输优化的研究较少，研究多数集中在内陆运输领域，对石油海运缺乏关注。通过谷歌学者数据库检索同时包含“运筹优化”和“石油海上运输”关键字的文献，发现1980 至2019年相关研究数量增势明显。以搜索词“石油”、“海上运输”和“运筹优化”识别文档标题、摘要和关键字，通过连接运算符与“油船”、“港口”以及“调度”等检索词进行组合筛选，创建各短语的文献数据集后整合为本文的目标文献集。具体如图1所示。

图1 谷歌学者库术语包含“石油海上运输”和“运筹优化”的文章数

以是否涉及石油运输船舶调度为标准，包括针对石油运输船舶的调度以及船舶与其他衔接资源的联合调度，定义石油海上运输优化的范围，将对象相同、约束类似的优化问题进行归纳划分。得到运筹优化方法在石油海上运输方向的应用场景划分如下：石油运输船舶调度及路由、石油在港作业调度及油轮海上驳运。以原油为例，对应场景如图2所示。

图2 原油海上运输流程及对应优化场景

3 石油运输船舶调度及路由

石油运输船舶调度及路由问题中，船队需决策执行哪些订单，以及港口的访问顺序，期间装载容量不得超过船舶容量。该问题的理论基础为车辆路径问题（VRP），车辆路径问题自 1959年被 Dantzig 和Ramser[1]提出以来，一直是优化调度研究中的热点，并衍生出诸多分支，取送货车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pickup，VRPSDP)与需求可分割的车辆路径问题(Split Delivery Vehicle Routing Problem，SDVRP)是很重要的两个分支。

3.1 石油船舶取送货路径问题

VRPSDP 问题由Min[2]首次提出，大部分石油海运问题都是取送货问题，油船根据长期合同订单，将石油从取货港运输到目的港，如何分配船舶、制定航线使得费用最小、效率最高是决策的难点。此外，为了平衡高额运输成本，船舶公司在完成合同订单同时，会根据船舶情况承接市场现货订单。因此，在满足车辆容量条件下，需进一步决策组合运输哪些市场订单使得盈利最大。

相关研究较多采用混合整数线性规划（MILP）模型或者网络流模型。两种模型可以相互借鉴转化，达到优化模型表达的效果，但需要根据实际问题具体分析。早在1987年，Brown 等[3]便提出原油海上运输是一个油轮路由调度问题，首次将基础的单舱单型油轮运输多种原油的航线制定问题表述为一个弹性集合分割问题。随着多船型选择，多种货物协同运输等条件出现，问题逐渐复杂，常见处理方式是将复杂问题通过D-W 分解、Benders 分解等算法，拆分为主问题、子问题进行求解。Kobayashi等[4]提出将带时间窗的船舶取送货问题拆分为两个子问题：

（1）任务划分子问题：将订单分配给各船舶，划分子问题的结果为路由子问题的输入。

（2）路由子问题：制定最佳的单个船舶访问港口的航线顺序。

基于集合划分的思想建立模型，将路由子问题转化为最短路问题求解。最终利用列生成算法求解，带来了5%-16%的成本改进。

精确算法在大规模航线规划中表现欠佳的情况下，可基于问题特征添加合适的启发式规则来加速算法求解。Cóccola等[5]将带时间窗的多船型多种原油运输航线制定问题拆分为单船问题和多船问题，开发了一种迭代算法，单船—多船迭代启发式规则如图3所示。

图3 单船-多船迭代启发式规则

该算法在求解性能上同时对比了Jetlund[6]所提出的启发式算法和Daniel[7]提出的精确算法。对比Jetlund 的实验结果，迭代MILP 算法能获得40%的利润提升。求解速度方面也有极大改进，与Daniel的精确算法对比，求解结果虽然只提升了0.31%，但求解时间从62 067s 缩减到了764s。在大规模算例中，群智能算法求解也是有效途径之一。应用群智能算法的关键在于确定合适参数。Chan 等[8]通过灵敏度分析得到了改进的多目标蚁群优化算法的最佳参数组合。

3.2 需求可拆分的石油船舶取送货路径问题

SDVRP问题由Dror等[9]首次提出，并证明了在需求可拆分情况下分割运输，运输总距离和派车数都能得到优化。油船在港取送货且单个石油订单可拆分由多个油船满足，即为需求可分割的取送货问题（Vehicle Routing Problem with Split Delivery and Split Pickup，VRPSDSP）。该问题结合了VRPSDP 与SDVRP的特征。已知提货和交货数量，决策提、交货的分配以及装运数量，多艘船舶需协同一致满足同一订单的时间及数量要求，相较于单纯取送货问题，其求解难度进一步加大。

该问题约束较多，建模要充分考虑变量设置及约束表达，避免约束数量增长过快。Hennig等[10]在拓展Mckay[11]模型的基础上引入了路径流模型，与前者相比具有约束数不随生成的路由数增长的优势。模型求解上，Hennig等[12]进一步研究比较了两种替代路径流模型方法，并分析了它们在列生成设置中的适用程度。Nishi等[13]将石油船舶调度问题转化为需求可拆分的车辆路由问题，提出了一种基于列生成的高效算法，与启发式算法进行了比较并验证了算法有效性。随后，又提出了一种基于列生成的高效启发式算法，与分枝定界算法和人工算子性能比较效果更优[14]。

3.3 带库存约束的石油库存船舶路径问题

从是否考虑库存约束的角度，石油海运路由问题可进一步衍生出库存路由问题。Miller[15]等人提出了第一个海运库存航线问题。发货是确保收货点没有缺货而不由订单发起，这种交付环境下的问题称为库存路由问题。

Christiansen 等就同一个结合库存管理的带时间窗船舶航线问题建立了MILP 问题[16]和网络流模型[17]，结合D-W 分解与分枝定界解得了一致的结果。在此基础上，Al-Khayya[18]等人解决了涉及非线性约束的多类型船队航线制定问题，采用了Christiansen 的网络流公式开发了MILNP 模型，并证明该模型可重构为具有特殊结构的等价MILP模型，为非线性问题转化为线性问题求解提供了新的思路。Shen 等[19]开发了路径重链接方法增强的贪婪随机自适应搜索元启发式方法，该方法对于随机生成的中小型实例效果良好。在此基础上，Shen等[20]采用拉格朗日松弛方法求解近似最优解，与之前实验结果对比更优，特别是在较大规模算例情况下。

此外，有学者在多式联运场景下从系统网络层面优化石油运输。如Lakovou等[21]采用网络流模型替代传统最短路径公式，提出仅考虑起讫点的航线规划可能导致某些环节超载，应从多起讫点、多商品网络角度考虑。Li 等[22]解决了竞争性多式联运和多产品网络中的油流分配问题。还有一些特殊问题，例如周晓玲等[23]基于零散批次油品的拼船运输问题总结了7类运输优化限制条件，并应用改进差分进化算法求解。

综上，石油船舶路径问题多采用MILP 模型，非线性约束可转化为线性求解，有些转化可能会加大模型的求解难度。网络流模型在某些约束表达上具备优势，还可借鉴利用图论的相关算法框架。算法研究中，基于搜索的启发式算法较多，测试已知的启发式方法是否适合油轮海上运输的路径调度可能会是研究热点。基于列生成的精确算法较多，精确算法研究关键是开发有效解决定价问题的方法。

4 石油在港作业调度问题

石油在港调度包括原油从油轮卸载、原油在码头罐区存储、原油从码头罐区运送到装置罐区、原油在装置罐区存储、原油从装置罐区到生产装置的管道输送。

学术界主要还是采用数学规划建模解决石油在港作业调度问题。原油调度一般同时包含连续操作和离散决策变量，建模关键是时间约束的表达，分为离散时间和连续时间两大类。离散时间建模简单直观，但对时间的离散化近似降低了模型精度。连续时间表达模型更精确，在离散事件发生频率不高且具有一定规律性的问题中整数变量规模较小，求解更容易。

对原油调度问题的早期研究采用离散时间建模方法建立MIP 或MINLP 模型。早在1996年，Shah[24]开发离散时间MILP模型，将原油调度分为两个子问题，上游问题包括左舷油罐卸载，下游问题包括炼油厂储罐与原油蒸馏装置的连接，以及从港口泵送至炼油厂的顺序和数量。若出现港口子问题不可行的现象，则通过松弛子问题的约束条件后重新求解，直至港口子问题可行。同年，Lee 等人[25]提出的离散时间MIP 模型通过限定装置罐内原油关键组分浓度的上下限，将原油混合操作视为单独的原油组分流而规避非线性，但模型得到的解会出现浓度不一致的现象。随着油轮、油罐数目增加或调度周期延长，计算量骤然增大，出现求解时间过长甚至无法获得可行解的情况。为了能在合理时间内求解，可采用减少调度模型的最小调度单元数的办法，但会损失部分可行域。Li[26]为了避免直接求解MINLP问题，提出将模型分解成MIP 和NLP 两部分迭代求解，但这种方法可能会在最优解存在的情况下找不到解。Reddy等[27]针对沿海型炼油企业建立离散时间MINLP模型，并采用按时间轴滚动迭代求解MIP，一定程度上克服了非线性的问题。

连续时间建模方面，Jia等[28-29]将连续时间建模方法应用于原油调度问题，建立基于事件的连续时间MIP模型，仍采用线性化方法处理原油混合操作带来的非线性约束，未解决浓度不一致问题。Moro等[30]建立了同步连续时间模型求解通过管线输油至厂区油库的原油调度问题，并比较了连续时间MINLP 模型和将储油罐库存体积离散化后形成的MIP 模型。考虑到连续时间表达方式的优势，Reddy等[31]在之前离散模型的基础上建立连续时间MINLP 模型，同样采用按时间轴滚动迭代求解MIP 的方法。后由Karimi所带领的研究小组对此模型做了一系列改进：为了解决迭代过程中出现不可行解的情况，讨论了当出现不可行解时按单个时间段往前回溯和按大的时间段块往前回溯的方法[32]；考虑到实际调度应用中油轮到期波动等异常事件[33]；设计启发式重调度方法快速获得高质量可行解[34]等。

综上，数学规划模型求解难度与整型变量和非线性约束关系密切，体现在：设置各工作单元的状态变量均为0-1变量，混输过程中原油的二次混合带来一些非线性因素。尽管线性规划对于解决收敛问题最优解有着无以伦比的优势，但在实际应用中仍有许多不足：

（1）通用性差，实际问题结构与运作情况互不相同，且问题规模大导致求不出解；

（2）MIP 虽能把非线性问题线性化，但非所有的非线性方程都能有理想的处理方法。

5 油轮海上驳运调度

超大型原油船、巨型油轮等运输船无法通过浅航道或浅港口码头，需通过小型船舶将原油从大型油轮转运至小型船舶，是石油供应链中的一个关键步骤。油轮驳运增加了原油供应灵活性并提高输送效率，并有助于减少大型油轮的定期租船成本或滞期费。

Daskin 等[35]为一个超大型油轮的一般过驳问题建立了一组排队模型，包括用于驳船操作的循环排队模型和用于油轮延误的近似排队模型。Lin等[36]开发了一种连续时间MILP数学模型，为每艘船舶引入一系列事件点，并定义0-1变量以确定船舶是否要在每个事件点开始一项任务，包括安装油轮、从油轮上泵油、拆卸油轮、行驶到炼油厂、停靠炼油厂、泵油、卸船、回到锚地。Huang 和Karimi[37]进一步研究利用不同的线性化方法开发了连续时间MILP模型，解决了油轮驳运的一般现实问题，弥补了Lin研究忽略一些实际问题特征的不足，包括多舱服务船在一次航行中提取不同的原油包裹，在一次航行中多次访问不同的超大型油轮，考虑原油密度、滞期费和时间租赁成本影响等。Huang和Karimi[38]为区域分销的一般驳运场景建立调度模型，采用大M 松弛法求解每艘接收船接收货物的顺序、侧面（左舷或右舷）和时间，在简单案例中降低成本6.3%。

综上，驳运调度的研究相对较少，不科学调度导致的拥堵会使得滞期费迅速增加，减少等待时间、提高驳船利用率至关重要。油轮海上驳运的优化目标往往设置为最小化成本，包括油轮滞期费和驳船作业费。

除了以上场景，一些细分问题的研究数量不多，但也为石油海上运输优化奠定了理论和实际研究基础。例如石油运输风险评估，风险评估量化模型作为构建海上石油运输多目标模型相当重要的部分，在过去很长一段时间里相关文献存在严重空白。前文提到的Li 和Lakovou 都旨在解决包括石油产品在内，考虑风险影响的危险品海上运输问题。

6 结论及建议

广大学者利用以线性规划为主的运筹优化方法，为石油海上运输实际应用带来了切实的好处。结合以上各场景的综述分析提出以下建议：

（1）拓展优化范围研究全局优化调度。目前已有一些将原油调度问题和炼油生产过程调度、成品油配送等集成的研究（如 Guyonnet 等[39]和 lee 等[40]）。但问题规模巨大，严格优化方法应用在全局调度还有困难，所以原油在港调度等局部优化问题仍是近几年的研究热点。随着计算技术的发展，基于全局的优化将是具有挑战性和前景的研究方向之一。

（2）根据实际添加特殊约束和设置变量。危险化学品的调度问题具备多种特殊约束，如货物/船货不兼容等。此外，当前研究常将船速简化为常量，但燃油消耗率其实是航速的非线性函数，加入有关船速的决策可限制油耗带来成本的进一步优化。

（3）利用约束规划、人工智能等方法弥补线性规划求解的不足。基于人工智能的约束规划方法可直接处理非线性问题，并根据变量的逻辑关系对问题进行建模和求解。且因搜索机制不同，可求解较大规模逻辑组合很强的问题。此外，以往研究方案通用性差，约束规划以其灵活的建模特点，有助于开发灵活的求解框架。

总的来说，石油海上运输优化是化工物流管理的重要研究领域，运筹规划拥有科学的理论及适合的工具方法来推动该领域向前发展。在国内研究相对较少的情况下，国内学者更应重视石油海运优化的相关课题，以带来更多有价值的研究成果。