周晓玲,王　震,肖文涛

(1.中国石油大学中国能源战略研究院,北京 102249; 2.中国石油化工股份有限公司抚顺石油化工研究院,辽宁抚顺 113001)



原油远洋拼船运输方案优化研究

周晓玲1,王震1,肖文涛2

(1.中国石油大学中国能源战略研究院,北京 102249; 2.中国石油化工股份有限公司抚顺石油化工研究院,辽宁抚顺 113001)

分析当前运作模式下中国原油远洋运输优化的目标函数,总结供需平衡约束等7类运输优化限制条件,建立原油远洋拼船运输方案的优化模型,并应用改进差分进化算法求解。在模型求解过程中,对多种维度变量与约束因素数据进行有效整合,利用双染色体配对编码的方法实现供需平衡限制,通过配对染色体间的小概率交叉降低算法的早熟收敛概率,利用整体进化与个别进化相结合的方法回收潜在的优秀个体,最终加速算法的寻优速率。通过算法搜索方案与人工方案的比对结果发现,应用提出的改进差分进化算法能够降低原油远洋拼船运输方案费用,并有效提高优化方案的制定时效。

原油拼船运输; 运输优化; 差分进化算法; 供需平衡约束

引用格式:周晓玲,王震,肖文涛.原油远洋拼船运输方案优化研究[J].中国石油大学学报(自然科学版),2016,40(2):174-180.

ZHOU Xiaoling,WANG Zhen,XIAO Wentao.Optimization of ocean shipping schemes of LCL crude oil[J].Journal of China University of Petroleum(Edition of Natural Science),2016,40(2):174-180.

中国已经建成从原油远洋运输、原油管网转输、成品油管网运输到加油站罐车配送的综合能源运输体系。当前针对原油运输的研究大多集中在长输管道运输的水力、热力运行工艺方向[1],而对海上远洋运输关注相对较少。世界石油资源分布具有明显的不均衡性[2],使得大型油轮成为重要的原油运输方式。近年来在世界原油价格波动异常剧烈[3]的情况下,原油远洋运输方案的优化制定和高效执行事关能源供应体系的运行安全和运转效益,是保障炼厂资源供给、炼油装置生产安全及炼油业务经济效益的关键,同时对于开拓油气储运领域的研究方向也具有开创性意义。随着炼油化工企业对原油配送数量和配送质量的要求不断提高,中国原油远洋运输已经形成一种包含装港航程、卸港航程及船型选择等多种维度变量组合优化的NP(non-deterministic polynomial)难问题,现有以传统数学规划方法求解的远洋船运模型已经难以适用。中国石化2010年进口原油总量达1.65亿t[4],油轮运输费用高达一百多亿元人民币。为降低进口原油的远洋运输成本,经常将零散批次的油品拼装成大船运送回国。原油装港分布于世界不同地区,卸港分布于中国从南至北的不同地域,从而使得船运拼装方案呈指数倍增长。由于运输费用基数大,人工拼船优化效果差,因而原油远洋运输过程中存在较高的潜在优化效益。笔者分析当前运作模式下中国原油远洋运输优化的目标函数,总结供需平衡约束等7类运输优化限制条件,建立原油远洋运输优化模型,并应用改进的差分进化算法予以求解。

1　模型建立

1.1目标函数

原油远洋拼船运输方案优化的目标为:在满足运输需求的前提下,所有参与运输的油轮总费用最小。对于单船运输费用,计算方法为:基本费率×计费吨位×WS×航程。其中计费吨位及WS系数与船型相对应。船型选定后,若装油量小于等于计费吨位,则仍然按计费吨位收费;若装油量大于计费吨位,则超出计费吨位部分另外收费。综上所述,模型目标函数可以写为

(1)

1.2约束条件

原油远洋拼船运输方案优化的约束因素包含以下几类。

(1)供需平衡约束。任一种类油品的需求总量等于供应总量,任一油轮的装油量等于卸油量。t种类油品的供需平衡表示如下:

(2)

第i号油轮的装卸平衡表示如下:

(3)

(2)单船运量约束。每船的运输量都要小于该船所允许的最大运量。第i号油轮运输的所有种类的油品总量不超过该船所允许的最大载货量应满足下式:

(4)

(3)油品装期约束。签订购买某个批次油品合同的同时,油品的装船港口及装船日期也随之确定。油轮必须在装期之前赶至该港口进行油品拼装,否则属于严重违约。相反,若油轮过早地赶至该港口,则需等待装期,产生滞期费用。

dateiparr≤datejpload.

(5)

式(5)表示第i号油轮应在p装港的第j批次供应油品的装期之前抵达。式中,dateiparr为第i号油轮抵达p装港的时间;datejpload为p装港的第j批次供应油品的装期。

(4)港口水深约束。油轮出港时的总装油量应小于该港口的水深条件所允许的总船容。

(6)

(5)环保法规约束。由于某些批次的油品含硫量较高等原因,已装载部分该类油品的油轮不准驶入受相关法规保护的港口进行油品拼装。

d(pti-ptj)=∞ .

(7)

式(7)表示供应ti种类油品的港口pti与供应tj种类油品的港口ptj之间不通航或单向通航,也即已在港口装载部分ti种类油品的油轮不允许驶入ptj港口进行油品拼装tj种类油品。但应注意:虽然d(pti-ptj)=∞,然而有可能d(ptj-pti)≠∞。

2　模型求解

2.1选择求解算法

本文中通过改进差分进化(DE)算法求解原油远洋运输优化模型。DE[5-7]是一种基于群体差异的自启发式随机搜索算法,现已被广泛应用于交通运输、图像处理、电力输送、经济调度优化等研究领域[8-14]。DE算法具有较好的全局搜索能力,在寻优过程中可利用个体的局部信息和群体的全局信息引领搜索方向,在用于包含多种维度变量的原油远洋运输优化问题中时,能够有效地跳出局部最优解所在空间,增加搜索到全局最优解的概率。另外,DE算法所需调节的参数也较少,在用于时效性要求极强的原油远洋运输优化问题中时,可减少业务人员的建模与参数配置时间,能够及时响应国际原油市场信息的快速变化,以便利用算法搜索结果指导资源的采购选择。

2.2改进算法流程

原油远洋运输优化存在供需平衡约束。对于进化类算法,应用罚函数方法实现等式约束往往会导致无解假象[15-16]。本文中特采用供应/需求双染色体配对编码方式表达运输方案,通过编/解码规则来控制运输过程的供需平衡。算法实现步骤如下:

(1)确定双染色体配对编码规则,并指定染色体基因意义与基因附加属性。对出口港各批次供应油品以误差所允许的最小单位分解并编号,并标记各自的出口港、装期、港口水深所允许的最大船重等信息。对进口港各批次需求油品以相同的最小单位分解并编号,并标记各自的进口港编号。对可能参与运输的各种候选油轮编号,并标记其计费吨位、最大载重、基本费率、滞期费率、WS及航行速度等信息。装载方案由供应油品编号与油轮编号组合构成,卸载方案由需求油品编号组合构成。

(2)配置种群数量、交叉概率等算法参数。

(3)随机生成浮点编码的初始父代种群x、y。

(4)将初始父代种群中各浮点编码的染色体按基因大小排序,得到整数编码染色体,并解读出其所代表的运输方案。

(5)计算i号个体总适应值f(i)、装载方案半适应值fx(i)和卸载方案半适应值fy(i)。

(6)判断是否满足终止条件,若是,停止计算并解码输出方案;否则,转步骤(7)。

(7)对父代种群进行遗传操作,生成子代种群。

(8)将子代种群中各浮点编码的染色体按基因大小排序,得到整数编码染色体,并解读出其所代表的运输方案。

(9)计算i号个体总适应值f(i)、装载方案半适应值fx(i)和卸载方案半适应值fy(i)。

(10)按总适应值优劣,将子代种群与父代种群中相应个体进行一对一竞争生存,更新父代种群,并转步骤(6)继续执行。

步骤(7)中,在对种群整体进行常见的遗传操作(通过差分变异生成子代种群vx、vy;父-子代间染色体交叉生成子代种群ux、uy等)之前,先进行局部进化操作,包括以下几个方面。

据fx(i)轮盘赌选择y(i),对卸油方案局部进化,更新fy(i)及f(i);据fy(i)轮盘赌选择x(i),对装油方案局部进化;对于fx(i)较高而fy(i)较低的方案,选取种群中其他个体的优秀y(j)与该个体的x(i)试匹配,看是否获得更好的运输方案;对于fy(i)较高而fx(i)较低的方案,选取种群中其他个体的优秀x(j)与该个体的y(i)试匹配,看是否获得更好的运输方案;选择部分f(i)较差的x、y染色体,令其x(i)、y(i)互换某一位置的基因。增加以上局部操作步骤的目的是回收潜在的优秀装载/卸载染色体,增加种群多样性,降低算法早熟收敛的概率,提高算法寻优效率。

3　算例分析

3.1算例设计

对于原油远洋运输优化这种包含多种维度变量组合优化的NP难题,已知最优解的验证实例很难寻找。本文中以具有代表性的简单算例检验算法求解的可行性。简单算例的优点是最优解可通过穷举方式获取,寻优结果可图形化,有助于识别与理解,可对比算法与人工的搜索能力的优劣。

算例:出口港1、2、3、4各有3万t原油出口,进口港1、2、3各有4万t原油待进口,按1万t为最小误差单位分解供/需油品。可能参与运输的油轮1、2、3、4、5、6,其最大运量分别为6、3、3、1、1和1万t。

供应/需求油品信息、油轮信息、装载方案、卸载方案表达规则参见图1。

图1　改进差分进化算法流程图Fig.1　Flow chart of improved differential evolution algorithm

3.2算例染色体解读方法

假设通过差分变异、交叉后生成某子代浮点编码染色体如表1所示。

经排序处理后得到整数编码染色体,如表2所示。

表1　某子代个体浮点编码染色体

表2　某子代个体整数编码染色体

其中解读油轮信息如表3所示。

表3　染色体油轮信息解读

1号船装载编号为1、2、3、7、6、5的油品运输并卸载至1、2、3、4、10、6。对应的航程为:出口港1>出口港3>出口港2>进口港1>进口港3>进口港2。其余船只航程计算与1号船类似。

6号船(x中的17基因)装载编号为8、9的油品运输并卸载至7、5。

2号船(x中的13基因)装载编号为10、11、12的油品并卸载至9、8、11。

4号船(x中的15基因)与3号船(x中的14基因)之间无油品编号,因而不参与运输。

3号船(x中的14基因)船装载编号为4的油品运输并卸载至12。

5号船(x中的16基因)后无油品,因而不参与运输。

3.3算法搜索能力分析

对于上述相对简单的示例,邀请6名做实际拼装优化的业务人员搜索到的“最优”计划如图2所示:2号船装载1、2、3(出口港)号油品卸载至1、2、3(进口港);3号船装载10、11、12(出口港)号油品卸载至10、11、12(进口港);1号船装载4、5、6、7、8、9(出口港)号油品卸载至9、5、6、7、8、4(进口港)。由于基本费率和WS点为常数,所以本文中以总航程来衡量方案经济性,方案总航程达到34.05 n mile。

通过算法搜索到的最优方案如图3所示:2号船

图3　改进差分进化算法搜索的最优方案的总航程Fig.3　Total navigation distance of optimization plan searched by improved differential evolution algorithm

装载4、5、6(出口港)号油品卸载至3、5、9(进口港);3号船装载1、2、3(出口港)号油品卸载至6、1、4(进口港);1号船装载7、8、9、10、11、12(出口港)号油品卸载至10、11、12、7、8、2(进口港)。方案总航程为34.012 5 n mile,优于人工计划。

4　结　论

(1)分析了当前运作模式下中国原油远洋运输优化的目标函数,总结了供需平衡约束等7类运输优化限制条件,建立了原油远洋运输优化模型,并应用改进的差分进化算法予以求解。

(2)在模型求解过程中有效地整合了各类运输数据间的逻辑关系,利用双染色体配对编码的方法实现了供需平衡限制,并通过配对染色体间的小概率交叉降低了算法的早熟收敛概率。

(3)在种群整体进化的过程中通过选择种群中某些“半适应值”较高的供应/需求染色体,对其相应的需求/供应染色体进行个别进化,实现了潜在优秀基因的有效回收,从而加速了算法寻优速率。

(4)对于中等规模的原油远洋运输优化问题,提出的改进差分进化算法能够获得全局最优解,并能够有效地辅助业务人员提高运输优化方案的制定时效。如何有效求解大规模原油远洋运输优化问题仍需进一步的研究探索。

[1]张劲军,何利民,宫敬,等.油气储运理论与技术进展[J].中国石油大学学报(自然科学版),2013,37(5):151-162.

ZHANG Jinjun,HE Limin,GONG Jing,et al.Theoretical and technological advances in petroleum storage and transportation engineering[J].Journal of China University of Petroleum(Edition of Natural Science),2013,37(5):151-162.

[2]仇鑫华,王震.基于委托-代理理论的国际石油合作财税体系比较[J].中国石油大学学报(自然科学版),2015,39(2):171-179.

QIU Xinhua,WANG Zhen.Comparison of international petroleum cooperation fiscal systems based on principle-agent theory[J].Journal of China University of Petroleum(Edition of Natural Science),2015,39(2):171-179.

[3]周德田,郭景刚.基于二元VAR-GARCH(1,1)-BEKK模型的金融市场与石油市场的溢出效应研究[J].中国石油大学学报(自然科学版),2014,38(1):177-185.

ZHOU Detian,GUO Jinggang.Spillover effect of financial market and oil market based on binary VAR-GARCH (1,1)-BEKK model[J].Journal of China University of Petroleum(Edition of Natural Science),2014,38(1):177-185.

[4]潘洹洹,王宇奇.中石化原油进口成本降低途径分析[J].科技与管理,2012,14(2):67-70.

PAN Huanhuan,WANG Yuqi.Cost reduction route analysis of sinopecs crude oil imports[J].Science-Technology and Management,2012,14(2):67-70.

[5]STORN R,PRICE K.Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces[J].Journal of Global Optimization,1995(8):22-25.

[6]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.

[7]周艳平,顾幸生.差分进化算法研究进展[J].化工自动化及仪表,2007,34(3):1-5.

ZHOU Yanping,GU Xingsheng.Development of differential evolution algorithm ITHM[J].Control and Instruments in Chemical Industry,2007,34(3):1-5.

[8]王翔,董晓马,阎瑞霞,等.改进DE/EDA算法在求解难约束优化问题中的应用研究[J].计算机应用研究,2010,27(11):4114-4117.

WANG Xiang,DONG Xiaoma,YAN Ruixia,et al.Improved DE/EDA algorithm for difficult COPs[J].Application Research of Computers,2010,27(11):4114-4117.

[9]CHANG C S,DU D.Further improvement of optimization method for mass transit signaling block-layout design using differential evolution[J].IEEE Proceedings on Electric Power Applications,1999,146(5):559-569.

[10]周辉仁,唐万生,王海龙.基于差分进化算法的多旅行商问题优化[J].系统工程理论与实践,2010,30(8):1471-1476.

ZHOU Huiren,TANG Wansheng,WANG Hailong.Optimization of multiple traveling salesman problem based on differential evolution algorithm[J].Systems Engineering-Theory & Practice,2010,30(8):1471-1476.

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

CAI Yanguang,SONG Kang,ZHANG Minjie,et al.Adaptive multi-objective hybrid differential evolution algorithm in union transport scheduling[J].Journal of Computer Applications,2010,30(11):2887-2890.

[12]段新涛,范晓艳,王婧娟,等.基于差分进化的插值置换混叠图像盲分离[J].视频应用与工程,2015,39(21):95-98.

DUAN Xintao,FAN Xiaoyan,WANG Jingjuan,et al.Blind separation method for interpolation permuted alias image based on differential evolution[J].Video Application & Project,2015,39(21):95-98.

[13]韩丽,孙望,罗朋,等.差分进化算法在变压器故障诊断中应用[J].电测与仪表,2015,52(16):38-42.

HAN Li,SUN Wang,LUO Peng,et al.Differential evolution algorithm in the application of the transformer fault diagnosis[J].Electrical Measurement & Instrumentation,2015,52(16):38-42.

[14]NIKNAM T,DOAGOU M H,FIROUZI B B.A new optimization algorithm for multi-objective economic/emission dispatch[J].Electrical Power and Energy Systems,2013,46:283-293.

[15]何家莉,宣士斌.含有等式约束优化问题的遗传算法[J].计算机工程与设计,2008,29(5):1253-1255.

HE Jiali,XUAN Shibin.Genetic algorithm of equation constrained optimization problem[J].Computer Engineering and Design,2008,29(5):1253-1255.

[16]胡宽,常新龙,宋笔锋,等.求解含等式约束优化问题的遗传算法[J].上海交通大学学报,2011,45(7):966-969.

HU Kuan,CHANG Xinlong,SONG Bifeng,et al.Genetic algorithm to solve optimization problem with equality constrains[J].Journal of Shanghai Jiaotong University,2011,45(7):966-969.

(编辑修荣荣)

Optimization of ocean shipping schemes of LCL crude oil

ZHOU Xiaoling1,WANG Zhen1,XIAO Wentao2

(1.Academy of Chinese Energy Strategy in China University of Petroleum,Beijing 102249,China;2.Fushun Research Institute of Petroleum and Petrochemicals,SINOPEC,Fushun 113001,China)

As an extension and development of oil and gas storage and transportation,the optimization of crude carrier co-loading scheme plays an important role in improving the profit and reducing loss in terms of crude oil logistics,which is of great importance in upgrading the overall competitive strength for the oil and petrochemical companies in China.The objection function on the optimization of long-distance crude oil transportation was analyzed,and seven constraints,such as the balance of supply and demand were concluded,which set limits on the extent to which the system will work.An optimization model of crude carrier co-loading scheme was established by using an improved differential evolution algorithm.The equation constrained was satisfied by the method of paired chromosomes.Some constraints were simplified by the form of additional distance.The crossover of small probability between paired chromosomes was used to prevent premature convergence.Finally,to recycle some potential excellent genes and to speed up the algorithm optimization,some chromosomes of high "semi-fitness" were selected for individual evolutions during the execution of differential evolution algorithm.Compared with manual searching plans,this improved differential evolution algorithm can not only significantly reduce the cost in long-distance crude oil co-loading and transportation,but also save the time in optimizing the crude carrier co-loading schemes.

LCL crude oil shipping; optimization of transportation; differential evolution algorithm; constraint of supply-demand balance

2015-11-26

国家自然科学基金项目(71303258)

周晓玲(1980-),女，博士研究生，研究方向为能源金融和原油油轮海上运输。E-mail:tinazhoujing@163.com。

1673-5005(2016)02-0174-07doi:10.3969/j.issn.1673-5005.2016.02.023

TE 832

A