在石油资源短缺的情况下，为了提高国际市场的竞争力，炼油企业必须降低加工成本、提高炼油厂的利润^[1]。为了实现这一目标，炼油厂通常采用3个层次的分级方式运行，包括生产计划、短期调度和过程控制，这些层次之间的关系密不可分。生产计划是以经济效益最大化为目标的决策层，决定炼油厂在未来几个月内需要生产哪些产品以及生产这些产品所需的原油。短期调度是为实现生产计划而制定的调度决策层，通常具有较短的周期，如几天或一周，需要考虑实际生产中的具体情况，安排详细的调度。过程控制是执行短期调度决策的操作层，是炼油厂实现高效、稳定生产的关键环节之一。

1.   文献综述

目前，对炼油长期生产计划优化的研究已较为成熟，主要采用线性规划 (linear programming，LP) 进行建模求解，并且已有商业软件用于解决炼油长期生产计划优化问题。然而，原油短期调度问题呈现出不确定、约束复杂等特性，是典型的组合优化问题，属于NP-hard问题^[2]，到目前为止还没有成熟的技术和软件求解，仍依赖调度员根据经验制定详细调度计划。因此，寻求一种有效的方法制定短期详细调度计划，对于降低生产成本、提高生产效率具有重要意义^[3]。

数学规划是一种传统的优化技术，具有成熟的建模和求解方法。许多现有工作通过建立数学规划模型来优化短期调度问题^[4-6]。这些模型根据不同的时间表示方式分为离散时间模型和连续时间模型。无论使用哪种时间表示方式，都是利用状态任务网和资源任务网建立混合整数线性规划模型 (mixed integer linear programming，MILP) 和混合整数非线性规划模型 (mixed integer non-linear programming, MINLP)。为了提高模型求解的精度，基于离散时间表示的数学模型需要划分足够小的时间间隔，导致出现大量的离散变量，很难在有效的时间内求解。基于连续时间表示，文献[7]把原问题分解为3个子问题建立MILP模型，对原问题中出现的非线性约束线性化，可能会对解的可行性造成影响。文献[8]结合原油调度问题实际生产操作特性建立基于连续时间的MINLP模型，用分支定界法得到最优解。尽管采用基于连续时间表示的数学规划模型能够大大减少模型中出现的离散变量，但是产生的非线性约束使得求解极其困难。为了确保数学规划模型可以求解，在建模过程中往往会忽视一些重要约束，这就意味着获得的解不能直接应用到实际生产中。

因此，为了确保解的可行性，Wu等^[9]基于控制理论提出一种新方法，即把原油一次加工过程分为上下两层，上层采用线性规划方法求解出一个炼油计划，同时优化最大化生产率等目标；下层在可调度性条件的约束下安排详细调度计划以实现上层炼油计划。文献[9-10]对原油短期调度问题建立混合Petri网模型，分析并证明不同初始状态下的可调度性条件，并且给出一种通过递归求解获得详细调度计划的方法。但是该方法仅保证解的可行性，对详细调度过程涉及的多个目标的优化效果并不理想。

为了优化下层详细调度计划，Hou等^[11]将原油短期调度问题转换为资源指派问题，使得该问题能够使用启发式和元启发式算法求解。在求解过程中对包括管道混合成本、罐底混合成本、蒸馏塔切换供油罐成本和供油罐使用成本在内的4个目标利用遗传算法进行优化，取得了较好的优化效果。但是在该研究中，为了最大化生产率，在转运原油时假设采用最大转运速率，这会消耗大量能源。实际上，有些原油被转运到炼油厂后并没有马上被使用，而且原油的转运速率是可变的，取决于输油管道上开启油泵组的数量。开启油泵组的数量越多，转运速率就越大，所消耗的能量也就越高，它与能耗成正比，但是与转运速率却是非线性关系。为了响应国家节能减排的号召，Wu等^[12]基于控制理论方法获得一个详细调度，并使用线性规划方法对能耗这一目标进一步优化，但是该方法对能耗优化得并不彻底，仍然存在优化空间。文献[13]则对原油短期调度问题建模并使用NSGA-III 算法^[14] (reference-point-based non-dominated sorting genetic algorithm-III) 对包括能耗在内的5个目标进行优化，表现出良好的优化效果，但是能耗目标仍有进一步优化的空间。对于多目标优化问题，进化算法和群智能算法表现出良好的优化求解能力。以下是一些经典的多目标优化算法。

非支配比较是多目标优化算法中评估解常用的算子。文献[15]提出一种使用非支配排序和拥挤度距离的经典多目标遗传算法 (non-dominated sorting genetic algorithm-II, NSGA –II)。它通过非支配排序将种群划分为不同的层次，同时使用拥挤度距离来保持种群的多样性，避免过早收敛。NSGA-III在NSGA-II的基础上进行改进，引入参考点的概念，通过这些参考点对种群进行划分，能够更好地解决高维多目标优化问题。基于分解的多目标优化算法 (multi-objective evolutionary algorithm based on decomposition, MOEA/D) ^[16]将多目标优化问题转化为多个单目标优化子问题，通过交叉变异等操作使得个体在这些子问题上得到较好的优化效果。文献[17]提出一种基于参考向量的多目标算法 (reference vector guided evolutionary algorithm, RVEA)，其核心思想是利用参考向量引导搜索方向，避免在搜索过程中出现局部最优解的问题。文献[18]提出自适应权重多目标优化算法 (adaptive weighted genetic algorithm, AWGA)，该算法通过自适应调整权重的方式实现多目标优化，表现出较好的收敛性。

对于优化求解原油短期调度问题，尽管以上算法能够得到不错的优化解，但是在求解过程中仍然会出现局部最优、收敛较慢和能耗优化不彻底的情况。因此，本文在通过分析原油短期调度问题特点的基础上提出一种两阶段求解方法，如图1所示。第1阶段使用NSGA-III-ACMO算法优化原油短期调度问题所涉及到的5个目标，同时为了提高算法性能和求解能力，改进种群进化所用的交叉算子和变异算子；第2阶段对于第1阶段优化后得到的非支配解集，提出一个混合整数线性规划模型 (记为MILP-1) ，进一步优化能耗目标。

图  1  两阶段优化方法

Figure  1.  A two-stage optimization approach

下载: 全尺寸图片 幻灯片

2.   原油短期调度问题描述与建模

2.1   问题描述

原油短期调度问题是炼油调度问题中非常复杂、关键的问题。针对内陆型炼油厂，原油一次加工过程如图2所示。该过程包含原油卸载、原油转运和原油蒸馏3个阶段：1) 油轮抵达港口时将原油卸载到港口的储油罐中；2) 根据炼油需要，原油经管道转运到炼油厂内的供油罐；3) 最终提供给蒸馏塔进行炼制。本文研究原油一次加工过程的详细调度计划。

图  2  原油一次加工过程

Figure  2.  Crude oil operations

下载: 全尺寸图片 幻灯片

在原油处理过程中，短期调度问题既包含离散变量，也包含连续变量，具有加工过程复杂和多约束的特性。例如，1) 在一个调度周期内，为了保证生产效率，蒸馏塔必须保持连续不间断地运行；2) 在任何时刻，油罐不能同时充油和放油；3) 管道也只能被一个储油罐和一个供油罐同时使用；4) 为了保证原油的成分满足要求，原油在供油罐中需静置一段时间分离杂质，称之为驻留时间约束。一旦任何约束被违反，都会导致调度不可行，对炼油厂生产计划造成严重的影响。本问题要求在满足各项约束的同时，做出原油转运、炼制等详细决策，并且在求解过程中优化多个目标。

2.2   数学模型

基于分层的思想，最大利润率等目标已经由上层优化并得到一个炼油计划。本研究需要在下层找到一个详细调度计划来实现上层炼油计划，并且同时优化包括能耗成本在内的5个目标，建立原油短期调度计划的数学模型如下所示。

2.2.1   目标函数

在一个调度周期内，炼油厂通常会炼制不同种类的原油，不同类型的原油由于成分组成有差异，混合后会降低原油品质，造成原油混合成本。一种原油在管道转运完后会切换其他种类原油继续转运，导致原油混合，因此会产生管道原油混合成本，如式 (1) 所示。另外，供油罐给蒸馏塔供油后，会在油罐底部遗留小部分原油 (称为罐底) 无法全部排出，当该油罐再次被充入其他类型原油时，同样会导致原油混合，从而产生罐底混合成本，如式 (2) 所示。

其中，$\varTheta$为原油类型数；${\pi }_{ij}$为原油i和原油j在管道的混合成本；${\varpi }_{ij}$为原油i和原油j在罐底的混合成本；${\alpha }_{ij}$为调度周期内原油i和原油j在管道的混合次数；${\beta }_{ij}$为调度周期内原油i和原油j在罐底的混合次数。

蒸馏塔在蒸馏过程中会切换供油罐保证不间断运行，每次切换同样会产生一定成本，称为蒸馏塔换罐成本，如式 (3) 所示。

其中，K为炼油厂在调度期间运行的蒸馏塔数量；$\chi$为每次切换供油罐的成本系数；${\gamma }_{i}$为调度期内蒸馏塔i切换供油罐的次数。

供油罐作为炼油厂的重要资源，每个使用过的供油罐都需要清洁维护。式 (4) 表示供油罐的使用成本。

其中，$\delta$表示每个供油罐清洁维护成本；R表示调度期内使用供油罐的总个数。

原油在管道中流动是由管道周围的油泵提供动力，开启不同数量的油泵组，对应不同的转运速率，同时所消耗的能量也不同，能耗成本如式 (5) 所示。

其中，M为转运任务的数量；${\varepsilon }_{i}$为任务i所对应转运速度的能耗系数；${\varsigma }_{i}$为任务i所转运的原油体积。

原油短期调度问题是多目标优化问题，式 (1) ~ (5) 所描述的5个目标相互冲突、矛盾，优化某一目标可能对其他目标产生负面影响。比如，要降低管道混合成本，就需要安排相同类型的原油连续转运。然而，由于蒸馏塔的加工速率小于管道转运速率，这会导致该类型原油长时间占据供油罐，增加油罐的使用成本。而且，当再次使用该供油罐时，转运的是不同类型的原油，从而增加了罐底混合成本。另一方面，要降低蒸馏塔换罐成本，需要在对供油罐充油时尽可能充满，在有限时间内尽可能多地充油，这需要增大转运速率，从而增加能耗成本。供油罐中充入的原油体积会影响该罐的释放时间，因此在选罐阶段选择刚释放的供油罐，而不是从未使用的空罐，也可以降低使用油罐成本。事实上，原油调度过程极为复杂多变，微小的决策变动可能会导致调度结果的显著变化，因此，原油短期调度问题是一个典型的多目标优化问题。

2.2.2   约束条件

在调度期间，首先要保证蒸馏塔的不间断运行，如式 (6) 所示。

其中，K为蒸馏塔个数；$[{\tau }_{{\rm{s}}},{\tau }_{{\rm{e}}}]$表示调度的开始时间和结束时间；$[{\theta }_{{\rm{s}}}^{k,i},{\theta }_{{\rm{e}}}^{k,i}]$表示蒸馏塔${D}_{k}$的第i个蒸馏任务的开始时间和结束时间。

油罐在使用过程中只能单向输油，充油和放油操作不能同时进行，如式 (7) 所示。

其中，${{C}}_{{\rm{in}},i}\left (t\right)$为0−1整型变量，值为1表示供油罐i在$t$时刻充油，反之，为0；同样，${{C}}_{{\rm{out}},i}\left (t\right)$为0−1整型变量，值为1表示供油罐i在$t$时刻放油，反之，为0。

另外，管道在同一时间只能被一个储油罐和一个供油罐使用，如式 (8) 所示。

其中，$\varOmega$为港口储油罐的数量；${\mathrm{\varLambda }}_{{\rm{out}},j}\left (t\right)$为0−1整型变量，值为1表示储油罐j在t时刻向管道输油，反之，为0；R为炼油厂中供油罐的数量。

驻留时间约束是对详细调度安排影响极大的约束，为了保证原油蒸馏时的品质达标，在经管道转运充入供油罐之后，需静置一段时间分离杂质，如式 (9) 所示。

其中，$\varPsi$表示驻留时间；${\omega }_{i}$表示第i个转运任务的结束时间；${\varphi }_{i}$表示第i个转运任务的原油被蒸馏塔使用的开始时间。

3.   问题转换与特点分析

由于短期调度问题规模庞大、目标多以及约束复杂，基于数学规划方法得出的数学模型求解困难，难以应用于实际生产；另一方面，原油短期调度不仅需要定义操作，同时还需要对这些操作进行排序，而启发式方法的前提是被调度的作业事先已知，故又无法直接使用启发式方法求解。为此，文献[11]把原油短期调度问题转换为供油罐到蒸馏塔的指派问题，转换后可以使用启发式或智能算法求解该问题，解决了使用数学模型求解所面临的计算复杂性问题。本文工作正是在此基础上展开的。

3.1   基于指派的求解过程

为了方便描述原油短期调度问题的详细调度计划，对原油操作${\varDelta }$做出如下定义。

定义1 $\varDelta = (o,\varsigma ,v,{u_{\rm{f}}},{u_{\rm{t}}},[{\rho _{\rm{s}}},{\rho _{\rm{e}}}])$，其中，$o$表示被操作的原油类型；$\varsigma$表示原油体积；$v$表示原油流动速度；${u}_{{\rm{f}}}$表示原油的来源；${u}_{{\rm{t}}}$表示原油的去处；$[{\rho }_{{\rm{s}}},{\rho }_{{\rm{e}}}]$表示该任务执行的时间区间。

原油处理过程，即一次加工过程分为3个阶段：原油卸载、原油转运和原油蒸馏，对应的原油操作决策分别用${{\varDelta }}^{{\rm{U}}}$、${{\varDelta }}^{{\rm{T}}}$和${{\varDelta }}^{{\rm{F}}}$表示。实际上，炼油厂会根据以往的数据和市场需求预先对原油进行采购，存储在储油罐中。因此，本文假设在港口储油罐中的原油足够当前调度使用，即不考虑${{\varDelta }}^{{\rm{U}}}$。那么，原油短期调度问题的详细调度可以表示为

${\varPi }=\{{{\varDelta }}_{1}^{{\rm{T}}},{{\varDelta }}_{2}^{{\rm{T}}},\cdots ,{{\varDelta }}_{M}^{{\rm{T}}},{{\varDelta }}_{1}^{{\rm{F}}},{{\varDelta }}_{2}^{{\rm{F}}},\cdots ,{{\varDelta }}_{Z}^{{\rm{F}}}\}$。

本问题的关键也就是获得一系列的${{\varDelta }}^{{\rm{T}}}$及其对应的${{\varDelta }}^{{\rm{F}}}$。

基于文献[11]提出的资源指派思想，从蒸馏塔集合选择一个未完成蒸馏任务的蒸馏塔${D}_{i}$，从空罐集合中选择一个供油罐${C}_{i}$，以及从原油在管道的转运速率集合中选择一个速度${v}_{i}$。于是，一个原油操作${{\varDelta }}^{{\rm{T}}}= (o,\varsigma ,v,{u}_{{\rm{f}}},{u}_{{\rm{t}}},[{\rho }_{{\rm{s}}},{\rho }_{{\rm{e}}}\left]\right)$将被确定。$o$根据蒸馏塔${D}_{i}$所需炼制的原油类型即可确定，转运速度为${v}_{i}$，来源${u}_{{\rm{f}}}$为装有$o$类型原油的储油罐，去处${u}_{{\rm{t}}}$为接收原油的供油罐${C}_{i}$，该操作的持续时间可以根据$\varsigma /{v}_{i}$求得。因此，只需要确定此任务转运的原油体积，那么该操作${{\varDelta }}^{{\rm{T}}}$也随之被确定。考虑到供油罐自身的容量和驻留时间约束，待转运原油体积可以通过式 (10) 计算。

其中，${\epsilon }_{i}$表示供油罐${C}_{i}$的容量；${\zeta }_{i}$表示蒸馏塔${D}_{i}$还需要该类型原油的体积；${v}_{i}$为选择的管道转运速率；${\theta }_{{\rm{e}}}^{i}$表示目前蒸馏塔${D}_{i}$蒸馏任务${{\varDelta }}^{{\rm{F}}}$的结束时间，${\rho }_{{\rm{s}}}^{i}$表示转运任务i的开始时间。

一旦${{\varDelta }}^{{\rm{T}}}$被确定，那么只需将该${{\varDelta }}^{{\rm{T}}}$转运的原油安排给对应蒸馏塔加工，即${{\varDelta }}^{{\rm{F}}}$也随之被确定。通过对蒸馏塔、供油罐和转运速率的一次次指派，一系列的详细决策被生成，从而实现给定的炼油计划。

3.2   状态转移分析

通过选择生成指派的过程，可以看作是系统状态转移的过程，每当完成一次指派，系统会消耗一定的资源，转移到下一个状态。值得注意的是，资源是不同状态之间共享的，前一状态下对资源的不同选择，会导致下一状态可选资源的差异，也就会导致迥然不同的详细调度计划。因此，对于这样一个过程动态变化的系统进行调度并非易事。

图3为一个简化的系统状态转移过程，在此仅用可选供油罐的分配示意不同指派对调度的影响。每个节点S代表系统状态，${{U}}_{{\rm{C}}}$代表当前状态空罐的集合。假设在初始状态S₀，当前状态${{U}}_{{\rm{C}}}=\{{{C}}_{2},{{C}}_{5}, {{C}}_{8},{{C}}_{9}\}$，此时供油罐的选择有4种，选择不同供油罐完成指派后达到以下4种状态，分别为S₁、S₂、S₃和S₄。那么经状态S₁的供油罐指派有3种，分别为S₁₁、S₁₂和S₁₃，并且考虑到该过程中可能会有供油罐被蒸馏塔释放成为空罐，${{U}}_{{\rm{C}}}$也会加入新的空罐。此时可以看到状态S₁₁、S₁₂和S₁₃可选的空罐集合${{U}}_{{\rm{C}}}$相比其他状态已经发生较大变化。尤其是考虑到供油罐本身容量也不同，选择的蒸馏塔和原油转运速率也不同，那么不同状态到达的时间也不一样，所获得的详细调度更是差异很大。由此可见，一次指派选择的差异，就会产生完全不同的调度结果。

图  3  系统状态转移分析

Figure  3.  Analysis of system state transition

下载: 全尺寸图片 幻灯片

本文使用遗传算法进行优化求解，染色体变量对应不同的指派，假如一个变量发生改变，会导致该变量对应的指派改变，也就会影响到后续的调度安排。一个优秀的调度必然是由多个好的指派共同作用产生的，一旦其中一个指派被改变，那么该指派之后的指派也会随之改变，有可能导致这个调度变得非常差。所以，如何保留这些连续的优秀的指派组合是本文研究的重点之一。实际上，代表指派选择的染色体变量主要是在交叉算子和变异算子的作用下发生改变，文献[13,19-20]使用的模拟二进制交叉算子并不能成段保留染色体变量。因此，受单点交叉算子的启发，本文提出一种根据种群迭代过程自适应变化交叉点位的交叉算子和变异算子。其中，自适应变异算子是为了弥补交叉算子在交叉点之前损失的多样性，防止陷入局部最优。详情见本文3.3小节。

对于图3所示的不同指派导致系统进入不同状态，在选择过程中，也会有一些状态无法满足约束，无法做出下一次指派，称之为不安全状态，也就意味着此调度不可行。因此本文使用回溯策略处理这种不安全状态。假设系统从S₀经由S₁到达S₁₂状态，此时一些约束无法被满足，系统处于不安全状态，那么系统回溯至S₁做出其他指派选择，选择S₁₁或S₁₃继续安排调度计划，假设都不可行，那么系统返回到S₀，在状态S₂、S₃和S₄之间做出选择。由于该短期炼油计划是由上层求解得到的一个可行的计划，那么经过回溯一定会获得一个可行的详细调度计划。

3.3   能耗优化分析

由于智能算法不具备求解最优解的能力，只能获得近似最优解，在本问题中能耗目标通常没有达到最优。文献[12]采用线性规划模型在不影响其他目标的情况下对能耗进行优化求解，取得了良好的效果。但是，该模型在求解过程中固定了每一个转运任务中的原油量，一些暂时使用不到的原油预先以高速转运，导致能耗成本没有达到最优。

图4是文献[12]使用线性规划模型优化后得到的原油详细调度计划，称使用的线性规划模型为LP-12，管道转运任务即一系列${{\varDelta }}^{{\rm{T}}}$。LP-12的优化思想是在每一个${{\varDelta }}^{{\rm{T}}}$中尽可能多地使用低速率转运原油从而降低能耗。但是，文献[12]限定了详细调度的每个${{\varDelta }}^{{\rm{T}}}$优化前后转运的原油体积保持一致，就可能出现部分以高速转运的原油在调度前期没有用到，导致较高的能耗成本。实际上，这部分高速转运的原油可以与之后转运同种类型原油的${{\varDelta }}^{{\rm{T}}}$进行协调再优化，尽可能多地用低速转运原油。如图4中${{\varDelta }}_{3}^{{\rm{T}}}$的一部分原油使用高速转运，一部分使用低速转运，与之转运相同种类原油的${{\varDelta }}_{7}^{{\rm{T}}}$仅转运少量原油，所以${{\varDelta }}_{3}^{{\rm{T}}}$中的部分原油可以放到${{\varDelta }}_{7}^{{\rm{T}}}$用低速转运，因为都是转运#1类型原油，对其他目标不会产生任何影响。因此，本文提出一个新的混合整数线性规划模型从全局的角度协调多个转运相同类型原油的${{\varDelta }}^{{\rm{T}}}$对能耗进行优化。

图  4  LP-12优化后的详细调度计划

Figure  4.  A detailed schedule optimized by LP-12

下载: 全尺寸图片 幻灯片

本章节从基于指派的思想分析如何求解原油短期调度问题。通过选择未完成蒸馏任务的蒸馏塔、空闲的供油罐和管道转运速率完成一次指派，那么整个炼油计划由一系列的指派任务组成。然后，通过分析不同指派对后续调度结果产生的影响，提出一种改进的交叉和变异算子，保留一些指派组合，使得算法具有更好的收敛性以及跳出局部最优解的能力。最后分析文献[12]提出的数学模型对能耗优化不彻底的问题，提出一个新的混合整数线性规划模型，进一步对能耗进行优化。第4章将对本文使用的算法、提出的改进算子以及新的混合整数线性规划模型进行详细介绍。

4.   NSGA-III-ACMO算法

NSGA-III算法是由Deb等^[14]在2014年提出的多目标优化算法，相比NSGA-II算法，该算法引入基于参考点的选择机制，在求解高维目标时表现出良好的性能。本文提出NSGA-III-ACMO (adaptive crossover and mutation operator) 在NSGA-III的基础上对交叉和变异算子进行改进，在进化过程中均衡种群的多样性和收敛性。

4.1   染色体编码

在本文研究的问题中，一个染色体代表一个调度，染色体解码完成即可实现短期调度的所有操作。由2.1节可知，求解该问题需要完成若干次指派，每次指派需要选择一个供油罐、蒸馏塔和转运速率。因此，设计染色体

其中，${a}_{i}$代表选择蒸馏塔的变量；K为蒸馏塔的数量；${b}_{i}$代表选择供油罐的变量；R为供油罐总个数；${c}_{i}$代表选择管道转运速率的变量；L表示可选转运速率的数量；$\varGamma$代表最大指派次数；${a}_{i}、{b}_{i} \mathrm{和}{c}_{i}$均为整数。

由于不同调度对应的指派次数不同，并且为了优化其他目标允许管道停运，则最大指派次数为

其中，${\zeta }_{i,j}$表示蒸馏塔${D}_{i}$需要转运$j$类型原油的体积；${\epsilon }_{\min}$表示供油罐的最小容积；l为允许管道停运的次数；$\lceil \mathrm{*}\rceil$表示向上取整。

4.2   染色体解码

给定一条上述结构的染色体，可根据以下规则进行解码以完成指派。假设在调度过程中解码第i次指派的状态如下。未完成转运任务的蒸馏塔集合为${{U}}_{D}$，空的供油罐集合为${{U}}_{C}$以及转运速度集合${{U}}_{R}$，则根据染色体选择的蒸馏塔序号$a$和供油罐序号$b$如式 (12) 所示。速度则直接在${{U}}_{R}$中选择序号为${c}_{i}$的转运速度。

其中，|*|代表集合*中的元素个数，并且当${c}_{i}=0$时，表示管道处于停运状态，直到有一个供油罐被蒸馏塔释放才开始下一次指派。通过解码在${U}_{D}$中选择序号为$a$的蒸馏塔，在${U}_{C}$中选择序号为$b$的供油罐，在${U}_{R}$中选择序号为${c}_{i}$的转运速率。为了更加清晰理解该过程，给出以下例子。假设在某一状态，${U}_{D}=\{{{D}}_{1},{{D}}_{2},{{D}}_{3}\}$，${U}_{C}=\{{C}_{2},{C}_{5},{C}_{6}\}$，${U}_{R}=\{{v}_{1},{v}_{2}, {v}_{3}\}$，本次指派对应的染色体编码为${a}_{i}=2,{b}_{i}= 6,{c}_{i}= 2$，解码后$a=3,\;b=1$。因此，选择第2个转运速率${v}_{2}$；第3个蒸馏塔${{D}}_{3}$和第1个供油罐${C}_{2}$；即以速率${v}_{2}$向${C}_{2}$中转运${{D}}_{3}$所需原油。

4.3   自适应点位交叉和变异算子

一条染色体对应一组资源指派信息，解码后可以得到一个详细调度计划。由于指派过程相互关联，为了能够保留多个连续指派组合，就需要成段保留染色体基因，单点交叉算子可以成段保留染色体，但是会极大降低种群多样性。因此，本文结合单点交叉和模拟二进制交叉，以及多项式变异提出改进的交叉和变异算子。

对于单点交叉算子，首先要确定交叉点位，然后进行交叉操作。本文通过种群当前的进化代数自适应确定交叉点位，如式 (13) 和 (14) 所示。

其中，X和Y是常数因子，$X\in \left (0,\mathrm{ }1\right) ,Y\in [1, +\mathrm{\infty })$；${G}_{{\rm{c}}}$表示当前的进化代数，${G}_{\max}$表示最大进化代数；$\varGamma$为最大指派次数；交叉点位${p}_{{\rm{c}}}$在[1,$\lfloor \varGamma *r\rfloor$]区间随机选取，$\lfloor *\rfloor$表示向下取整。随着交叉点位的确定，交叉操作如下。1) 交叉点位之前的变量，父代直接进行交换；2) 交叉点位之后的变量，采用模拟二进制交叉 (simulated binary crossover, SBX) 操作。图5展示了${p}_{{\rm{c}}}$=3时两个父代${P}_{1}$和${P}_{2}$的交叉过程。

图  5  交叉过程

Figure  5.  Crossover process

下载: 全尺寸图片 幻灯片

交叉操作产生的子代个体需要进行变异操作避免种群过早收敛。对于本文提出的自适应交叉算子，在交叉点位之前的染色体变量只交换而不改变，在一定程度上会导致种群多样性较差。因此，本文又提出自适应分配变异概率用来保持多样性，如式 (15) 和 (16) 所示。

其中，$\eta \in \left (\mathrm{0,1}\right)$为开始自适应变异的参数，当${G}_{{\rm{c}}} ＞ \eta {G}_{\max}$时，开始使用自适应变异算子，${p}_{{\rm{m}}}$为不同变异概率的分界点，在该点之前的染色体变量分配变异概率为$1/{p}_{{\rm{m}}}$，该点之后的变异概率为$1/\varGamma$；当${G}_{{\rm{c}}} ＜ \eta {G}_{\max}$时，该染色体的变异概率都为$1/\varGamma$。分配完变异概率之后，采用多项式变异操作进行变异。图6展示了变异点位等于4时的变异概率分配过程。

图  6  变异概率

Figure  6.  Mutation probability

下载: 全尺寸图片 幻灯片

4.4   NSGA-III-ACMO算法流程

基于以上提出的自适应进化算子，本文在NSGA-III的基础上提出NSGA-III-ACMO算法，具体流程如下。

1) 种群初始化。根据定义的染色体结构，随机生成N个个体作为初始种群P₀，并对该种群个体解码，获取各个体目标值；设$g=0$。

2) 交叉和变异操作。从种群P_g中随机选择两个个体进行自适应点位交叉和变异操作生成子代并放入子代种群Q_g中。重复此操作直到$\left|Q_g\right|=N$，然后对${{Q}}_{g}$中所有个体进行解码。

3) 环境选择。使R_g=P_g$\cup$Q_g，对R_g使用非支配等级划分和基于参考点的选择算子，选择N个优秀个体形成下代父种群P_g+1 。

4) 迭代。$g\leftarrow g+1$，重复步骤2) 和步骤3) 直到满足终止条件，得到R_g中的非支配解集。

5.   针对能耗目标的混合整数线性规划模型

与LP-12不同的是，本文提出的混合整数线性规划模型 (MILP-1) 不再按照管道空闲进行分组，目标函数和约束都不再出现代表组的变量。另外LP-12约束优化后每个${{\varDelta }}^{{\rm{T}}}$转运的原油体积与优化前一致，MILP-1则是在全局限定转运相同类型原油的${{\varDelta }}^{{\rm{T}}}$总的体积不变，并且要求满足罐容量约束和各种时间约束。在不影响其他目标的情况下具有更好的优化效果，MILP-1详细介绍如下。

1) 参数和集合。

${{U}}_{{\rm{T}}}$：完成原油短期调度转运任务${{\varDelta }}^{{\rm{T}}}$的集合，

${{U}}_{{\rm{R}}}$：管道周围每一泵站可开启油泵数量集合，

${{U}}_{{\rm{R}}}$ = {1, 2, $\cdots$, L}；

${{\varDelta }}_{i}^{{\rm{T}}}$：第i个原油转运任务；

${C}_{i}$：执行${{\varDelta }}_{i}^{{\rm{T}}}$所使用的供油罐；

${\epsilon }_{i}$：供油罐${{C}}_{i}$的容量；

${\varepsilon }_{h}$：每一泵站开启h组油泵时的能耗系数；

${v}_{h}$：每一泵站开启h组油泵时的转运速率；

${D}_{i}$：被${{C}}_{i}$供油的蒸馏塔；

${d}_{i}$：${{D}}_{i}$的蒸馏速率；

$\varPsi$：原油驻留时间；

O：需要转运的原油类型集合；

${W}_{t}$：调度初始状态下需要转运类型t原油的体积；

${\mu }_{i}$：初始状态下炼油厂原油可供${{D}}_{i}$蒸馏的时间。

决策变量如下所示。

${x}_{ih}$：在每一泵站运行h组油泵转运${{\varDelta }}_{i}^{{\rm{T}}}$原油的体积；

${A}_{i}$：改变转运速率之后${{\varDelta }}_{i}^{{\rm{T}}}$任务执行的开始时间；

${B}_{i}$：改变转运速率之后${{\varDelta }}_{i}^{{\rm{T}}}$任务执行的结束时间；

2) 目标函数。

3) 约束条件。

目标函数 (17) 表示通过调节原油流速后的最小总能耗，${\varepsilon }_{h}$表示输送一吨原油的能耗；约束 (18) 和 (26) 表示非负要求；约束 (19) 保证${{\varDelta }}_{i}^{{\rm{T}}}$中的原油不超过${\mathrm{C}}_{i}$的容量；约束 (20) 表示${{\varDelta }}_{i}^{{\rm{T}}}$和${{\varDelta }}_{i-1}^{{\rm{T}}}$的操作在时间上不冲突；约束 (21) 表示计算每个${{\varDelta }}_{i}^{{\rm{T}}}$改变转运速率之后的执行完成时间；约束 (22) 和 (23) 保证了在使用供油罐给蒸馏塔供油之前，供油罐中的原油准备就绪，即满足原油驻留时间约束；约束 (24) 保证了调度中每种原油需求量满足要求；约束 (25) 保证${{\varDelta }}_{i}^{{\rm{T}}}$使用了供油罐${{C}}_{i}$，当${{\varDelta }}_{j}^{{\rm{T}}}$再次使用该供油罐时，${{C}}_{i}$已经被释放。

对于一个已知的详细调度计划，本文提出了MILP-1，在不影响其他目标成本的情况下，对能耗进一步优化。因此，对于NSGA-III-ACMO算法得出的非支配解集，本文使用MILP-1继续进行能耗优化，进而得到更优的调度。

6.   工业实例

本节给出一个工业实例对提出的算法进行性能评估，图7展示了在上层使用线性规划得到的一个为期10 d的短期炼油计划。在炼油厂中，有3个蒸馏塔${D}_{1}\sim {D}_{3}$，其炼油速率分别为375.0、230.0和500.0 t/h。表1展示了炼油厂9个供油罐${C}_{1}\sim {C}_{9}$的初始信息。管道周围每个泵站有3组油泵，开启1组、2组和3组油泵对应的转运速率分别为${{U}}_{{\rm{R}}}=\left\{\mathrm{833.3,1\,250,1\,375}\right\}$ (t/h)，每种速率转运每吨原油所对应的能耗系数分别为$0.001\,2，0.001\,6\mathrm{和}0.002\,2$。另外，原油驻留时间$\varPsi =6$h。

图  7  一个10 d的炼油计划

Figure  7.  A ten-day refining plan

下载: 全尺寸图片 幻灯片

表  1  供油罐初始信息

Table  1.  Initial information of charging tanks

编号	容量/t	原油类型	已有原油/t
C1 #129	34000	#3	27000
C2 #128	34000	#2	30000
C3 #116	34000	#4	27000
C4 #117	34000	#5	30000
C5 #115	34000	#5	25000
C6 #127	34000
C7 #182	20000
C8 #180	20000
C9 #181	20000

下载: 导出CSV 

| 显示表格

根据蒸馏塔的炼油计划和炼油厂内供油罐的初始信息，可以计算出为完成炼油任务还需要经管道转运的原油体积，分别为#1原油63000 t、#2原油25200 t和#6原油38000 t，供油罐的最小容量为20000 t，根据式 (11) 可以得到$\varGamma =\left\lceil {63\,000/20\,000} \right\rceil + \left\lceil {25\,200/20\,000} \right\rceil +\left\lceil {38\,000/20\,000} \right\rceil +5=13$，指定最大停运次数$l=5$。

不同类型原油发生混合会产生一定的混合成本，用${n}_{ij}$和${m}_{ij}$分别表示类型i与类型j的原油在管道和罐底混合一次的经济成本。

本文的实验环境为CPU，Intel i5-7300HQ 2.50 GHz，内存16 GB，Windows10笔记本电脑。为了测试所提出算法的有效性，本文选择5种多目标优化算法进行对比，分别是MOEA/D、RVEA、AWGA、NSGA-II和NSGA-III。在下面的实验中，种群大小分别设置为100、200和300，迭代次数分别为100、200和300，每种算法独立运行30次，交叉概率为0.7，分布指数为20，多项式变异的分布指数为20。由于原油短期调度问题的真实Pareto前沿是未知的，因此本文使用集合覆盖率C指标和超体积指标 (hypervolume, HV) 对算法的性能进行评估。

1) C指标。

该指标是二元指标，它是通过两个解集的相互覆盖率评估解集的优劣，定义为

其中，解集A、B分别为两个算法求得的Pareto集，${C}\left (A,B\right)$表示解集B中的解被解集A支配的比率。当${C}\left (A,B\right) ＞ {C}\left (B,A\right)$时，称解集A的质量比解集B的质量高。

图8展示了NSGA-III-ACMO与其他5种算法的C指标对比结果。其中，A为本文提出的算法NSGA-III-ACMO；B为其他对比算法，即对应横坐标轴标注的算法。综合看来，NSGA-III-ACMO效果更好，求得的解集质量更高。

图  8  NSGA-III-ACMO与其他算法$C$指标对比

Figure  8.  Comparison of indicator $C$ obtained by NSGA-III-ACMO and other algorithms

下载: 全尺寸图片 幻灯片

2) 超体积指标。

该指标为一元指标，通过计算解集与参考点围成空间的超体积对不同算法求出的解集进行评估，多种算法对比时要保证是同一参考点。超体积指标可以评估解集的收敛性和多样性，超体积越大表示解集越靠近帕累托前沿，说明解集的质量更好，其定义为

其中，$\lambda$为勒贝格测度；F 为需要计算的解集；${\vartheta }_{i}$表示第i个解与参考点构成的超体积。

本文在计算超体积时所采用的参考点为 (1,1,1,1,1)，即当前解集中各目标最大值组成的向量进行归一化处理。图9展示了不同算法在不同的种群大小和迭代次数的超体积指标结果，可以看出NSGA-III-ACMO求得解集的超体积指标较其他都偏高，表示算法性能更好，算法的多样性和收敛性优于其它算法。

图  9  NSGA-III-ACMO与其他算法超体积指标对比

Figure  9.  Comparison of HV obtained by NSGA-III-ACMO and other algorithms

下载: 全尺寸图片 幻灯片

对于利用NSGA-III-ACMO算法得到的非支配解集，选取一些代表性的调度与文献[13]中的结果进行对比。如表2所示，+45%表示该目标优化效果提升45%。其中，调度1、3和6是文献[13]优化得到的结果，调度2、4、5和7是利用NSGA-III-ACMO算法得到的结果。可以看出调度2支配调度1，说明调度2 更优秀；调度4和调度5对比调度3也得到大幅度优化，但是在${J}_{\beta }$和${J}_{\delta }$目标上做出一点点牺牲；调度7与调度6相比优化了${J}_{\alpha }$目标，在${J}_{\beta }$和${J}_{\varepsilon }$目标上表现稍差，但是经过本文提出的MILP-1进一步优化能耗目标后得到的调度8 (表2中记为ACMO-MILP算法)，可以在其他4个目标不变的情况下，将${J}_{\varepsilon }$目标优化至最低。调度7的详细调度甘特图如图10所示，调度8的详细调度甘特图如图11所示。

表  2  NSGA-III-ACMO与文献[13]结果对比

Table  2.  Comparison of results obtained by NSGA-III-ACMO and the algorithm in Reference[13]

调度来源	编号	${J}_{\alpha }$	${J}_{\beta }$	${J}_{\gamma }$	${J}_{\delta }$	${J}_{\varepsilon }$
文献[13]	1	33	45	11	6	151
NSGA-III-ACMO算法	2	18 (+45%)	45	10 (+9%)	6	151
文献[13]	3	25	32	11	7	151
NSGA-III-ACMO算法	4	18 (+28%)	34 (-6%)	10 (+9%)	7	151
NSGA-III-ACMO算法	5	18 (+28%)	24 (+25%)	10 (+9%)	8 (-14%)	151
文献[13]	6	28	12	11	9	162
NSGA-III-ACMO算法	7	25 (+10%)	13 (-8%)	11	9	163 (-0.6%)
ACMO-MILP算法	8	25 (+10%)	13 (-8%)	11	9	151 (+6.8%)

下载: 导出CSV 

| 显示表格

图  10  调度7的甘特图

Figure  10.  Gantt chart for Schedule 7

下载: 全尺寸图片 幻灯片

图  11  调度8的甘特图

Figure  11.  Gantt chart for Schedule 8

下载: 全尺寸图片 幻灯片

图10中管道转运任务${{\varDelta }}_{2}^{{\rm{T}}}$的转运速度为1250 t/h，其他转运任务均为最低速度833.33 t/h。优化后的结果如图11所示，${{\varDelta }}_{2}^{{\rm{T}}}$使用低速转运，整个调度周期内的原油全都使用低速转运，管道转运的能耗目标已经优化到最低。之所以${{\varDelta }}_{2}^{{\rm{T}}}$可以低速转运，其重要原因是转运#2类型原油的${{\varDelta }}_{3}^{{\rm{T}}}$和${{\varDelta }}_{6}^{{\rm{T}}}$进行协调，${{\varDelta }}_{3}^{{\rm{T}}}$的部分原油交给${{\varDelta }}_{6}^{{\rm{T}}}$转运，为${{\varDelta }}_{2}^{{\rm{T}}}$争取更多时间使其能够低速转运。

在实际的生产过程中，炼油厂也需要根据实际情况选择不同的调度方案，多目标优化算法一次求解能获得多个解决方案，对炼油厂选择合适的调度方案有很大帮助。例如，当炼油厂内供油罐需要维护，空罐不足的情况下，选择调度2执行比较合适。本节给出一个真实的工业实例展现了所提出算法的优越性。

7.   结论

针对原油短期调度优化问题，本文采用两阶段优化求解策略。通过对问题特点的分析，提出自适应交叉和变异算子使得NSGA-III-ACMO算法具有更好的收敛性和多样性。首先使用NSGA-III-ACMO算法对5个目标进行优化，并在此基础上提出MILP-1模型对能耗目标进一步优化，表现出更好的优化效果。实验表明，本文提出的NSGA-III-ACMO算法和MILP-1模型在求解原油短期调度问题时具有更好的性能，与其他文献优化后的结果相比仍然可以不同程度降低成本，对炼油厂实现低能耗、低成本和高效益具有重要意义。