西非—中国航线原油远洋运输方案优化

周晓玲， 王震， 肖文涛， 许国栋

(1.中国石油大学 中国能源战略研究院，北京 102249； 2.中国石油化工股份有限公司 抚顺石油化工研究院，辽宁 抚顺 113001； 3.中国石油集团工程设计有限责任公司北京分公司，北京 100085)

西非—中国航线原油远洋运输方案优化

周晓玲1， 王震1， 肖文涛2， 许国栋3

(1.中国石油大学 中国能源战略研究院，北京 102249； 2.中国石油化工股份有限公司 抚顺石油化工研究院，辽宁 抚顺 113001； 3.中国石油集团工程设计有限责任公司北京分公司，北京 100085)

为满足西非—中国航线的原油远洋运输方案的时效性要求，以油船运费、滞期费和靠港费之和最低为目标函数，以供需平衡、港口水深和装卸时间为约束条件，求解一个包含船型组合、装/卸港航线组合、油种替换、批次拆分等多决策变量的大规模NP(Non-deterministic Polynomial)难问题.采用差分进化算法进行求解.为提高求解速度，采用双染色体编码、基因组压缩编码、船型与拼装变量隐式联锁、配送油种比对解码等方法，进行供需平衡约束，降低问题规模，并缩减问题的“劣质解空间”，提高差分进化算法的搜索时效.利用提出的算法对中国石化某月度西非—中国航线实际原油远洋运输方案进行优化，得到优化方案平均用时约5 min，可节约运费50余万美元.

原油远洋运输； NP难问题； 差分进化算法； 数据降维

0 引 言

2015年我国从西非进口原油达4 000多万t，年度运输费用高达上亿美元，存在较高的优化空间.国内外学者针对原油远洋运输优化问题做了较多研究.冯高伟[1]建立了物流选址模型，设计了我国原油运输中心港口.陈飞儿等[2]采用非线性规划方法对进口原油典型航线的运输网络进行了优化.IAKOVOU[3]建立了以成本最低和风险最小为目标的原油海运网络模型.AL-OTHMAN等[4]提出多阶段随机规划模型，用于优化不确定性市场条件下的原油网络.初良勇[5]建立了以运输成本最低、运输风险最小为目标的多目标规划模型.陈超等[6]基于网络结构构建和运行控制一体化综合优化的解决思路，设计了我国原油进口海运网络优化模型.王尧等[7]对管道运输和海上运输的风险因素进行定性分析，建立了运输成本最低、风险最小的多目标规划模型.潘洹洹[8]基于运输与时间无关的假设建立了原油进口供应链网络优化模型，并采用动态规划方法求解.王廷林[9]采用线性规划方法建立了中东至美湾原油海运航线优化的数学模型，通过模型求解得出“VLCC模式与苏伊士模式相结合是最佳原油海运方案”的结论.

1 问题属性

原油远洋运输优化的最终目标是将从国际市场上采购的零散批次原油以最优的船型组合、拼装-配送航线组合运回我国卸港，以满足炼厂所提报的油品种类、需求量、到货港、到货期等要求.优化模型以油船运费、滞期费、靠港费之和最低为目标函数，决策变量包括：船型组合、装/卸港航线组合、油种替换、批次拆分等，约束条件包括供需平衡、港口水深和装卸时间等.由于决策变量及约束条件信息非结构化特点，本文以图文结合的形式阐述西非—中国航线原油远洋运输优化问题的属性.

西非—中国航线原油远洋运输问题描述见图1.根据炼厂需求情况和市场资源供应情况，以油船为纽带关联炼厂需求和市场资源，形成了“装港拼装—远洋运输—卸港配送”的三层运输过程.按航次租用油船，在“装港拼装—远洋运输—卸港配送”流程中不换船，也不在海上中途分卸.

图1 我国原油远洋运输业务示意图

炼厂提报需求时要指定油品种类、需求量、接收港、到货期等.需求油品允许用相同种类的其他名称的油品替换，到货期限为炼厂所指定的到货日前后10 d内.西非原油市场各批次资源都带有固定装期，供应量较为规整(约13万t).

我国原油远洋运输一般按航次租船，油船数量充足.西非市场的原油资源批次供应量较为规整，因而经济运输船型一般为VLCC(计费吨26万t)和SUEZMAX(计费吨13万t)两种.

综上所述，西非—中国航线的原油远洋运输优化的最终目标是在油品种类、供应量、时间等限制下，以运费最低的方案将采购的资源配送给各炼厂，从而形成一种包含船型组合、装/卸港航线组合、油种替换、批次拆分等多决策变量的大规模NP难问题.现有方法不能满足实际方案制订过程的时效性要求.

2 求解方法

本文采用改进差分进化(Differential Evolution,DE)算法求解西非—中国航线的原油远洋运输方案优化问题.DE算法由STORN等[10-11]提出，是一种基于群体差异的自启发式随机搜索算法.当前自启发式算法已被广泛应用于交通运输领域.[12-14]DE算法流程见图2.

图2 DE算法流程

仅用DE算法难以解决大规模原油远洋运输方案优化问题，因而本文在采用DE算法的基础上，又附加了几种降低问题规模的子算法，包括双染色体供需平衡编码、基因组压缩编码、船型与拼装变量隐式联锁和配送油种比对解码.

2.1 双染色体供需平衡编码

X代表粗略的油品拼装方案，需与限制条件结合才能构成准确的拼装方案，主要用于控制拼装航线组合；Y代表粗略的油品配送方案，需通过X-Y的比对解码形成准确的配送方案，主要用于控制配送航线组合(每个完整运输方案须由X染色体、Y染色体以及X-Y染色体之间的映射关系联合确定).

2.2 基因组压缩编码

基因组压缩编码方案见表1,其特点是：不将各批次油品按所允许的油品供应量配送误差(例如1万t)拆分成基因，而是将油品批次作为具有相同性状的基因组进行编码.该编码方案将原油批次作为一个具有相同性状的基因组，将各批次油品的供应量/需求量、港口、种类、时间等作为基因组的属性.表1中装/卸港的水深见表2.

表1 基因组压缩编码方案

表2 装/卸港水深

2.3 船型与拼装变量隐式联锁

船型与拼装变量联锁是指拼装变量和约束条件可隐式决定船型变量的取值.西非原油资源各批次供应量都约为13万t，因而经济船型只有VLCC(26万t)和SUEZMAX(13万t)两种选择.因为西非—中国航程较远，VLCC的经济性远高于SUEZMAX的，所以只要能满足约束条件，用VLCC拼装运输的经济性必然高于用SUEZMAX单独运输的经济性.因此，可以将船型作为一种与拼装变量联锁的隐式决策变量.在解读X染色体生成精准拼装方案时，只要满足约束条件，就优先选择VLCC船型.该子算法流程见图3.

从第i号空载油船(默认为VLCC)开始，从前至后对X染色体中未被装载的资源进行拼船，方法为：若装载当前第j批次的资源油品后不违反油船

图3 船型与拼装变量隐式联锁流程

载重、油品装期、港口水深、环保法规等约束条件，则第i号油船装载第j批次的资源油品，否则用第i+1号未满载油船装载第j批次的资源油品，直至所有批次的资源都被船队装载为止.若有油船装载油品在13万t左右，则该船降级为SUEZMAX.

2.4 配送油种比对解码

比对解码的目的是将船载油品按油种和需求量配送给各炼厂，生成完整、有效的油品配送方案，进而计算“装港拼装—远洋运输—卸港配送”方案的适应值.在配送过程中，船载各批次油品可能被拆分以满足不同批次的供应量要求.若被拆分的船载某批次油品在供应某一批次的需求后仍有剩余，则继续配送给下一批次需求，直至被完全卸载.

比对解码可有效缩减由众多复杂限制条件构成的“无效解空间”，对离散的有效解空间进行有效的联通，将多种较差的方案映射为更加优秀的方案，可以有效避免过度依赖“罚函数”所导致的无解假象，提高DE算法的搜索效率.该子算法流程见图4.

按从前至后的顺序卸载船队，对需求染色体Y进行油品配送.船舶卸载方法为：按从前至后的顺序比对Y染色体中需求原油的种类.若某批次需求油品的种类与某油船所载资源油品的种类相匹配，则该船航行至需求该油品的炼厂提报的到货港，并卸载相应种类的油品.若需求油品与船载油品的种类不匹配，则继续比对Y染色体中下一批次的需求油品的种类.当该船所装载的原油完全卸载后开始下一油船的卸载，直至所有油船油品按需配送完毕.

图4 油种配送比对解码方法流程

3 算例分析

3.1 模型假设

如表1所示，假设在西非地区共采购8个批次的资源油品，依次编号1,2,…,8，供应量均为13万t，分别位于1，2，3，1，4，3，2，4号出口港，油品种类分别编号为0，0，1，0，2，0，3，3，油品装期分别为--0102，--0105，--0109，--0104，--0118，--0112，--0116，--0115.我国炼厂共需求7个批次的进口原油，各批次依次编号1,2,…,7，需求量分别为13万t，26万t，13万t，13万t，13万t，25万t，1万t，分别位于1，2，3，1，3，2，4号接收港，油品种类分别为0，0，1，2，0，3，3，油品到货期分别为--0204，--0205，--0209，--0214，--0211，--0217，--0216.可能参与运输的油船有VLCC和SUEZMAX两类，其计费吨位分别为26万t和13万t.假设算法计算过程中生成的某子代供-需染色体如表3所示.

表3 某子代供-需染色体

(1)对资源油品进行拼船装载.默认1号油船空载，船型为VLCC.利用1号油船装载X染色体中的6号原油，装载后还剩余13万t的运载能力，故可接着装载X染色体中的下一批次的1号资源油品(假设1号油船装载1号资源油品不违反约束条件).当1号油船装载完1号出口原油后达到其额定运载能力时就停止装载.接着用2号油船装载X染色体中的3号资源油品.依此类推，当5号油船装载完8号资源油品后，拼船装载过程结束.因为4号油船在拼装8号油品时出港船达到26万t，超出4号装港的允许船重，所以最终只装载13万t的7号资源油品，船型降级为SUEZMAX.最终形成的拼装方案见表4.

表4 某子代染色体所代表的拼装方案

(2)对需求油品进行分船配送.首先利用1号油船对Y染色体中的需求原油进行配送.Y染色体中第一位为1号需求原油，其 ytype为0，与1号油船上装载的6，1号资源油品类型相符，因此1号油船对1号需求供给13万t的6号资源油品，1号需求得到满足.Y染色体中的第二位为5号需求，其ytype为0，与1号油船上装载的1号原油类型相符，因此1号油船对5号需求供给13万t的1号资源油品，5号需求得到满足，1号油船完成“装港拼装—远洋运输—卸港配送”任务.接着用2号油船对Y进行配送.Y中未得到满足的第一位为2号需求，其ytype为0，与2号油船的2号资源油品相符,因此2号油船对2号需求供给13万t的2号资源油品.此时，2号需求剩余13万t等待配给.2号油船中剩余3号资源油品，其xtype为1，与Y中3号需求的原油类型相符,因此，2号油船对3号需求配给13万t的3号资源油品，3号需求得到满足.2号油船完成任务.依此类推，直至对Y中6，7号需求的原油配给完毕.最终生成的配送方案见图5.

图5 配送方案示意图

(3)解读航行路线组合.由以上的拼装和配送过程可得船队的航行路线组合.例如1号油船先后装载6，1号资源油品，而后配送给1，5号需求.对应着先后经过1，2号出口港和1，3号接收港.因此，其航行路线为：xport3(0,13/13)→xport1(0,13/13)→yport1(0,13/13)→yport3(0, 13/13).同理可得2，3，4，5号油船航行路线:2号船为xport3(1,13/13)→xport2(0,13/13)→yport2(0,13/26)→yport3(1,13/13);3号船为xport4(2,13/13)→xport1(0,13/13)→yport2(0,13/26)→yport1(2,13/13);4号船为xport2(3,13/13)→yport2(3,13/25);5号船为xport4(3,13/13)→yport2(3,12/25)→yport4(3,1/1).

3.2 算例应用

表5是2014年11月西非—中国原油远洋运输人工计划，其中C油、Q油所在港口水深允许最大船舶总载重量为15万t，已装载H油的油船不得拼装K油、N油、J油、E油、G油.拼装过程中，油船过早抵达港口需要等待装期，按等待时间长度缴纳滞期费用，而过晚抵达属于严重违约，是禁止发生的情况.

采用普通DE算法，以最小数量误差编码染色体，求解了超过24 h仍未获得可行方案.采用本文提出的降维方法后，在约10 min的时间内获得了优化方案(表6).经检验，比人工计划(表5)节省运费50余万美元.

表5 2014年11月西非—中国原油远洋运输人工计划

表6 2014年11月西非—中国原油远洋运输优化方案

4 结 论

西非—中国航线的原油远洋运输是一种包含船型组合、装/卸港航线组合、油种替换、批次拆分等多决策变量的大规模NP难问题.本文采用双染色体

编码的差分进化(DE)算法求解西非—中国航线原油远洋运输优化问题，并通过双染色体编码、基因组压缩编码、船型与拼装变量隐式联锁、配送油种比对解码等方法实现了对大规模远洋运输优化问题的有效求解.

[1]冯高伟. 沿海石油物流方案设计[D]. 大连: 大连海事大学, 2004.

[2]陈飞儿, 张仁颐. 我国原油进口航线网络的优化[J]. 上海海事大学大学报, 2006, 27(2): 75-80.

[3]IAKOVOU E T. An interactive multi-objective model for the strategic maritime transportation of petroleum products: risk analysis and routing[J]. Safety Science, 2001, 39(S1): 19-29.

[4]AL-OTHMAN W B E, LABABIDI H M S, ALATIQI I M,etal. Supply chain optimization of petroleum organization under uncertainty in market demands and prices[J]. European Journal of Operational Research, 2008, 189(3): 822-840.

[5]初良勇. 我国水上石油物流系统与分拨运输网络研究[D]. 大连: 大连海事大学, 2007: 80-96.

[6]陈超, 李霏. 我国原油进口海运网络优化模型[J]. 油气储运, 2011, 30(2): 97-100. DOI: CNKI:13-1093/TE.20110130.1037.000.

[7]王尧, 吕靖. 中国原油进口运输通道安全研究[J]. 大连海事大学学报, 2014, 40(1): 109-116.

[8]潘洹洹. 中石化原油进口供应链运输成本优化模型研究[D]. 哈尔滨: 哈尔滨理工大学, 2012.

[9]王廷林. 中东至美湾原油海上运输模式比较研究[D]. 大连: 大连海事大学, 2010.

[10]STORN R, PRICE K. Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces[R]. California:International Computer Science Institute, 1995(8): 22-25.

[11]STORN R, PRICE K. Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359.

[12]蔡延光, 宋康, 张敏捷, 等. 自适应多目标混合差分进化算法在联盟运输调度中的应用[J]. 计算机应用, 2010, 30(11): 2887-2890.

[13]葛显龙, 辜羽洁, 王伟鑫. 供应链环境下的库存与运输整合优化模型及算法[J]. 系统工程, 2014, 32(1): 26-32.

[14]闫华, 高黎, 刘国勇, 等. 基于多时间窗的油料保障模型[J]. 计算机应用, 2015, 35(7): 2096-2100. DOI: 10.11772/j.issn.1001-9081.2015.07.2096.

(编辑 贾裙平)

Ocean crude oil shipping scheme optimization of West Africa-China shipping line

ZHOU Xiaoling1, WANG Zhen1, XIAO Wentao2, XU Guodong3

(1. Academy of Chinese Energy Strategy, China University of Petroleum, Beijing 102249, China; 2. Fushun Research Institute of Petroleum and Petrochemicals, SINOPEC, Fushun 113001, Liaoning, China; 3. China Petroleum Engineering Co., Ltd. Beijing Company, Beijing 100085, China)

To meet the timeliness and effectiveness of the crude oil shipping scheme of West Africa-China shipping line, a large scale NP (Non-deterministic Polynomial) hard problem with multiple decision variables including ship-type combination, loading/unloading port route combination, crude oil-type replacement and batch split is solved, where the objective is to minimize the sum of freight, demurrage and berthing fees, and the condition constraints are supply-demand balance, water depth of ports and loading/unloading time. The differential evolution algorithm is adopted to solve the problem. In order to improve the solving speed, the methods of the double chromosome coding, the genome compression coding, the implicit interlocking of ship-type and assembly variables, and the comparison and decoding of distributed oil types are adopted to realize the supply-demand balance constraint, reduce the scale and the inferior solutions of the problem, and improve the efficiency of the differential evolution algorithm. The proposed algorithm is used to optimize the actual ocean crude oil shipping scheme of West Africa-China shipping line of SINOPEC in a month, and the optimized scheme can be obtained in about 5 min at average and save about 500 000 USD.

ocean crude oil shipping; non-deterministic polynomial hard problem; differential evolution algorithm; data dimension reduction

10.13340/j.jsmu.2017.01.007

1672-9498(2017)01-0031-06

2016-07-05

2016-12-27

国家自然科学基金(71303258)

周晓玲(1980—)，女，陕西乾县人，博士研究生，研究方向为油船远洋运输方案规划，(E-mail)tinazhoujing@163.com； 王震(1969—)，男，甘肃会宁人，教授，博导，研究方向为能源金融与能源经济、跨国投资与并购，(E-mail)wangzhen@cup.edu.cn

F550.74;U695.21

A