考虑流量约束的碳存储管道运输网络优化

尹宇起，李　清，杨　斌，胡志华

(上海海事大学科学研究院，上海 201306)



考虑流量约束的碳存储管道运输网络优化

尹宇起，李清，杨斌，胡志华

(上海海事大学科学研究院，上海 201306)

针对实现碳存储技术的大规模应用问题，提出以管道网络为基础的碳存储网络设计模型.通过将管道运输的特点与最小生成树方法相结合，提出考虑节点流量的连续节点最小树方法，建立对应的碳存储网络设计模型.对连续选址的收集点进行编码，采用遗传算法求解模型得到添加连续节点的最小树网络.通过以上海市为背景的碳存储网络设计实验可知，考虑节点流量的连续节点最小树网络优于一般最小生成树网络，而且针对遗传算法中交叉概率及收集节点编码长度分别设置实验，分析了算法中参数的选取对求解结果的影响.

碳捕获与封存；碳存储；最小生成树；遗传算法；管道网络

0　引言

温室气体增加所产生的温室效应导致全球变暖的现象已成为国际社会关注和讨论的热门问题.碳捕集与封存(Carbon Dioxide Capture and Storage，CCS)作为减少温室气体排放的重要手段成为全球研究热点，管道运输是该技术得以实施的关键环节[1].由于碳源与碳汇在区域分布上的不均衡，在碳存储网络的设计过程中如何实现节点间液态CO2的管道物流成为碳存储网络设计的重点.

碳存储网络中碳源点的特点：CCS网络中的热电厂、水泥厂、化肥厂、钢铁厂等碳源的数目较大且多分布在工业园区和城市周边.每个碳源的CO2排放量巨大，如一个装机容量为500 MW的发电厂每年需要输送4～5 Mt的CO2[2].液态CO2需要在特定条件下运输，如文献[3]通过对离岸碳存储链CO2运输的研究得出整个系统的最优运输条件.

本文设计的碳存储网络指在管道网络的基础上，增加碳捕获和碳封存环节构成的能够完成碳存储完整流程的网络系统.管道网络结构的决策成为碳存储网络设计问题的关键，本文采用节点流量的连续节点最小树网络，即在最小生成树(Minimum Spanning Tree，MST)网络的基础上，构建满足管道网络设计的新型网络结构.针对影响管道网络建设成本的管道长度和管道直径2个主要因素，在连续节点最小生成树网络问题中增加节点的流量，约束优化管道路径的选取.在最小生成树模型的基础上建立满足问题要求的新型最小树网络模型，采用遗传算法进行求解，得到优于一般最小生成树模型的管道网络.

1　碳存储与管道网络

根据NETL(National Energy Technology Library)的统计资料，世界上正在运行和计划建设的CCS项目(包括单纯的碳捕获项目)已有247项.由于CCS技术的目标是实现CO2永久性或半永久性隔离，而且海洋封存技术目前还不成熟，且涉及海底生态、法律等诸多方面的问题[4]，因此上述已经实施的CCS项目中CO2的封存方式主要是地质封存.

CO2的管道运输技术已经成熟，通过改进管道技术压缩成本的空间不大，因此优化碳存储网络，设计高效的运输网是降低网络成本的关键.国内外相关研究人员已经开始进行碳存储网络设计和优化的研究.[5-12]将该源汇匹配问题归结为一个具有多背包性质的组合最优化问题，建立CCS源汇匹配数学模型，采用结合贪婪算法的混合遗传算法求解模型.J.Morbee等人[6]在网络设计过程中，首先使用k-均值聚类法减少网络中节点数，然后应用Delaunay三角网得到运输管道的预选方案，最后运用InfraCCS工具以新确定管道成本为目标设计最优网络.M.K.Chandela等人[8]讨论了干线管道的潜在经济性，由于地理位置影响封存成本，通过主干线管道运输CO2到一个成本低的封存点使网络更经济.由于碳存储网络建设的资金限制及经济最优化，一些学者运用动态网络规划的思想研究碳存储网络.孙亮等人[11]提出基于GAMS的源汇匹配动态规划模型，借鉴Delaunay三角网来构造潜在运输路径，将源汇匹配问题简化为混合整数规划问题，应用GAMS/CPLEX进行建模求解.R.S.Middletona等人[12]通过对网络的成本、建设和环境问题进行详细全面的建模，构建了考虑时空优化的SimCCSTIME模型，研究如何以及何时部署大规模CCS的基础设施.上述文献主要从数学规划及动态规划的角度研究CO2运输管道网络问题.

设计管道网络也可以应用图论中的最小生成树方法[7，13-14]，运用模拟退火算法和最小支撑树算法对潜在CO2汇点进行离散选址决策，并确定最优网络布局.本文在已有最小生成树文献基础上选址新节点并考虑节点的流量，从而通过设计管道网络，优化管道路径的选取及管道直径的确定.

2　问题定义

2.1问题描述与分析

本文所设计的碳存储网络是以管道网络为基础结合碳捕获和碳封存环节构成的网络系统.针对管道网络设计问题的要求，提出以下假设：(1)问题中将碳源点及碳汇点确定为图中节点，其中碳源点捕获并输出CO2，碳汇点作为管道的终端节点(根)封存CO2；(2)节点间管道的衡量指标包括长度和直径，管道网络设计的目标是实现管道网络的权重值(与管道长度及直径有关)最小化；(3)每个碳源点只有一条输出管道，但可以有多条输入管道；(4)在建成管道网络中，CO2总是由各碳源点发出沿着所在路径输送到碳汇点，即网络中的边(弧)方向，然而初始连通图中这种方向性并不存在；(5)添加的收集点本身的输出量为0.

在管道网络的建设中，管道的长度与直径决定工程建设的投入.由于碳源点的分布具有区域广泛性及无规律性，大规模的碳存储网络中管道网络建设的投入巨大，如何选择管道路径及确定管道直径、优化管道网络建设成本成为碳存储网络设计的关键问题.本文管道路径的选择可由最小树模型网络确定，并且各段管道的直径由流经管道的CO2流量确定，因此管道的长度与直径在路径选取后即可确定.此时问题的目标是管道网络建设成本最优，即管道的长度与直径成为管道路径选取的目标.

图1　最小生成树转化为连续节点最小树示意图

通过上述的问题描述可知，此时最小树网络中的赋权值包括边的长度(管道长度)和节点的输出量(碳捕获量).为了设计最优的碳存储管道网络，本文在最小生成树网络模型[M1]的基础上，考虑节点的输出量构建最小树模型[M2].通过选址新节点更新管道网络的可选路径，构建连续节点最小树模型[M3].本文采用了函数w(d，f)量化问题目标，即碳存储管道网络建设成本最小化，其中d表示管道长度，f表示管道流量.

2.2符号定义

假设无向图以G=(V，E)表示，有向图以T=(V，A)表示.模型涉及的参数与变量符号如下.

2.2.1集合与索引

(a)i，j=1，2，…，n，表示碳源的索引；

(b)k=1，2，…，m，表示添加的连续节点的索引；

(d)GN=(VN，EN)，表示扩展后图的无向图.

2.2.2参数

(c) (Xi，Yi)，i∈V，表示碳源点所在位置的坐标；

(d)Ci，i∈V，表示碳源点i需要运输的二氧化碳量；

(e)Dij，(i，j)∈E，表示碳源点i与j间的距离；

(f)AS表示图S的边集，其中S为图G=(V，E)的任意子图.

2.2.3变量

(a)xij，(i，j)∈EN，变量为0～1，边(i，j)∈EN被选则为1，否则为0；

(b)yij，(i，j)∈AN，变量为0～1，弧(i，j)∈AN被选则为1，否则为0；

3　模型

3.1一般最小树模型

求解以管道距离为权重的最小生成树模型[M1]，其中根据生成树网络的性质——边数等于节点数减1且不含圈，确定一般最小生成树模型的约束.

(1)

(2)

(3)

xij∈{0，1}，∀(i，j)∈E.

(4)

模型中：(1)式表示管道总长度最短；约束(2)式表示最小生成树网络中连通的边数为n-1条；约束(3)式表示最小生成树网络中不含圈；约束(4)式表示变量xij为0～1的变量.

3.2节点流量最小生成树模型

由问题假设(4)可知，在树形管道网络构建完成后，无向的树形图G=(V，E)可以看做有向树形T=(V，A)图(弧的方向与CO2的流向一致)，其中弧的选取yij，(i，j)∈A与边的选取xij，(i，j)∈E的关系为

(5)

s.t.(2)与(3)式

(6)

wij=fi·Dij，∀i，j∈V；

(7)

∀i，j∈V；

(8)

xij，yij∈{0，1}，∀i，j∈V.

(9)

模型中：(5)式为目标函数表示考虑节点流量的最小生成树网络赋权值最小；约束(6)式表示节点流量的累加公式；约束(7)式表示赋权值函数公式；约束(8)式表示无向图与有向图最小树间边(弧)的关系；约束(9)式表示变量xij与yij变量为0～1.

3.3连续节点最小生成树模型

(10)

(11)

(12)

(13)

wij=fi·dij，∀i，j∈VN;

(14)

∀i，j∈VN;

(15)

∀i，j∈VN;

(16)

(17)

xij，yij∈{0，1}，∀i，j∈VN;

(18)

(19)

模型中：约束(10)式为目标函数表示考虑节点流量的最小生成树网络赋权值最小；约束(11)式表示最小生成树网络中连通的边数为n+m-1条；约束(12)式表示最小生成树网络中不含圈；约束(13)表示节点流量的累加公式；约束(14)式表示赋权值函数公式；约束(15)式表示无向图与有向图最小树间边(弧)的关系；约束(16)式表示添加节点后碳源点i与j间的距离；约束(17)式表示添加节点的数目；约束(18)式表示变量xij与yij变量为0～1；约束(19)式表示ak与bk取值连续.

4　算法

4.1遗传算法的整体流程

Procedure：添加连续节点的最小生成树;

Input：碳源的数目及坐标、添加节点的数目、遗传算法参数;

Output：添加节点坐标及最小树的长度;

Begin

t←0，

基于实数编码的方法初始化P(t)，

基于实数编码的方法评价P(t)，

While(不满足终止条件)do

使用交叉算子以P(t)产生交叉子代C(t)，

使用变异算子以P(t)产生变异子代C(t)，

求解最小树的长度，以此评价C(t)，

使用轮盘赌规则从P(t)和C(t)中选择染色体组成P(t+1)，

t←t+1；

Output：添加节点坐标及最小树的长度;

End.

4.2编码和解码方法

图2　遗传算法中编码示意图

4.3交叉算子

分散交叉算子伪代码如下：

Procedure:分散交叉算子；

Input：父代p1[]，p2[]，编码长度L；

Output：交叉子代c[]；

Begin

i←0，

Whilei≤Ldo，

If rand(i)=1，

c(i)←p1(i)，

else

c(i)←p2(i)，

i←i+1；

Output：交叉子代c[]；

End.

交叉算子求解过程见图3.

4.4变异算子

均匀变异算子伪代码如下：

Procedure:均匀变异算子；

Input：父代p[]，编码长度L，变异概率MR，编码取值范围(Low，Up)；

Output：交叉子代c[]；

Begin

Span=Up-Low；//实数编码区间长度，

Fori=1 toL，

生成随机数R，

IfR>MR，

生成随机数Rs，

c(i)=Low+Rs·Span，

Else，

c(i)=p(i)；

Output：交叉子代c[]；

End.

图4　变异算子求解示意图

变异算子的求解示意图见图4，其中第3个基因被选择为变异基因.

5　实验部分

5.1算例数据与算法参数

(1) 算例数据

以上海市为背景设计碳存储网络，选取46个碳排放企业作为碳源点且在沿海区域选取1点作为虚拟汇点以便于扩展为离岸碳存储.节点流量在区间[5，15]内随机生成.源汇点坐标已知，节点间直线距离表示需要建设管道的长度，连续节点的选取数目根据实验要求选取.

(2) 算法参数

遗传算法中主要参数：种群规模为20；迭代次数为200；实验过程中交叉概率与变异概率若无实验设置说明，则选取交叉概率为0.8、变异概率为0.10.

5.2实验设计与结果

为了验证模型及其对应遗传算法的可行性，本文设计的实验见表1，实验1求解后的结果见表2.

表1　实验目的及实验设计

表2　实验1求解后的结果

5.3实验分析

(1) 实验1中求解[M2]得到覆盖全部碳源的管道网络的权值为44 257.采用遗传算法对[M3]求解10次，发现添加新的节点作为管道网络中的收集点优于未添加节点最小生成树的实验结果，见表2.此次实验中[M2]的实验结果的平均值为35 475，最小与最大的差值为3 528，然而在现有遗传算法设置条件下，无法确定何种因素影响[M3]的实验结果的波动.在模型的求解结果中我们可以发现并非每一添加的收集点都是有效的，如图5所示.

图5　实验1中[M3]的求解结果

(2) 根据实验2求解结果得到图6，首先添加节点数目不同使得实验结果的中位值呈现波动性趋势，添加5个节点时实验结果的中位值最优；其次，添加节点数目的不同对应的实验结果的范围相似，添加5个节点时的优势解分布密集.

(3) 根据实验3求解结果得到图7，首先交叉概率的变化使得各概率条件下的多次实验的中位数呈现类似抛物线的形状，交叉概率为0.9时取得较优实验结果的概率更高；其次，实验结果中位数的变化趋势也是实验结果取值范围的变化趋势.

图6　实验2求解得到关于网络赋权值箱形图

图7　实验3求解得到关于网络赋权值箱形图

综上可知，由添加连续节点的最小树模型[M3]得到的管道网络优于一般最小生成树模型[M2]，因此[M3]具有可行性.由于添加的节点中存在无效收集点，在[M3]的最小树基础上将无效添加点剔除后才会得到最终的管道网络.在使用遗传算法求解[M3]的过程中，算法设置极为重要.通过算例实验发现：(1)交叉概率与实验结果间存在近似凸性，通过调整交叉概率可以使实验结果更优，如上述算例中采用0.9的交叉概率；(2)添加节点数目对实验结果的范围影响不大；(3)增加添加节点数目的改变使得求解值呈现波动型变动.

6　结语

为实现碳存储技术的大规模应用，需要构建完整的碳存储网络.本文以管道网络为基础构建碳存储网络，其中将碳捕获环节和碳封存环节抽象为碳存储网络的节点，采用考虑节点流量的连续节点最小树模型与遗传算法相结合的方法求解新型的管道网络.在新型的管道网络中，通过添加连续的收集点使得管道网络的柔性增加，并且考虑碳源点的CO2输出量量化管道直径，最后由算例实验可知，考虑节点输出量的连续节点最小树模型得到优于一般最小生成树模型的管道网络，验证了连续节点最小树模型的可行性.同时，通过算例实验对遗传算法中的设置进行相应的讨论，为模型与算法的结合及应用提供了理论上的支持.然而求解后发现添加的节点中存在无效收集点，文中并未考虑碳汇点的选择问题.

[1]李昕. 二氧化碳输送管道关键技术研究现状[J]. 油气储运，2013，32(4)：343-349.

[2]拉克利，李月.碳存储与封存[M]. 北京：机械工业出版社，2010:278.

[3] NAM H，LEE T，LEE J，et al. Design of carrier-based offshore CCS system：plant location and fleet assignment[J]. International Journal of Greenhouse Gas Control，2013，12：220-230.

[4]王建秀，吴远斌，于海鹏. 二氧化碳封存技术研究进展[J]. 地下空间与工程学报，2013，9(1)：81-90.

[5]李永，陈文颖，刘嘉. 碳收集与封存的源汇匹配模型[J]. 清华大学学报(自然科学版)，2009，49(6)：894-896.

[6]MORBEE J，SERPA J，TZIMAS E. Optimized deployment of a European CO2transport network[J]. International Journal of Greenhouse Gas Control，2012，7：48-61.

[7]刘巍，董明. 碳封存网络的规划模型及求解算法研究[J]. 工业工程与管理，2011，16(6)：128-132.

[8]CHANDELA M K，PRATSONB L F，WILLIAMS E. Potential economies of scale in CO2transport through use of a trunk pipeline[J]. Energy Conversion and Management，2010，51(12)：2825-2834.

[9]MIDDLETONA R S，KUBYB M J，BIELICKIC J M. Generating candidate networks for optimization：The CO2capture and storage optimization problem[J]. Computers，Environment and Urban Systems，2012，36(1)：18-29.

[10]MIDDLETONA R S，BIELICKIB J M. A scalable infrastructure model for carbon capture and storage：SimCCS[J]. Energy Policy，2009，37(3)：1052-1060.

[11]孙亮，陈文颖. 基于GAMS的CCUS源汇匹配动态规划模型[J]. 清华大学学报(自然科学版)，2013，53(4)：421-426.

[12]MIDDLETONA R S，KUBYB M J，WEIB R，et al. A dynamic model for optimally phasing in CO2capture and storage infrastructure[J]. Environmental Modelling & Software，2012，37：193-205.

[13]ANDRÉ J，AURAY S，WOLF D D，et al. Time development of new hydrogen transmission pipeline networks for France[J]. International Journal of Hydrogen Energy，2014，39(20)：10323-10337.

[14]WANG Y，DUAN M，FENG J，et al. Modeling for the optimization of layout scenarios of cluster manifolds with pipeline end manifolds[J]. Applied Ocean Research，2014，46：94-103.

(责任编辑：石绍庆)

Carbon storage pipeline transport network optimization considering flow constraints

YIN Yu-qi，LI Qing，YANG Bin，HU Zhi-hua

(Scientific Research Academy，Shanghai Maritime University，Shanghai 201306，China)

The paper offers to the pipeline network-based carbon storage network design problems. By combining the characteristics of the pipeline with the minimum spanning tree(MST) method，the paper establishes the carbon storage network design model with using a continuous-node MST method considering the node output. Encoding the continuous-node of location，and adopting genetic algorithm to solve our model，we can achieve the minimum spanning tree with adding new node. The experiment，designing Shanghai’s carbon storage network，shows that the MST network with continuous-node is better than that without continuous-node. The experiment about the crossover probability，mutation probability and the collection node length coding of genetic algorithms，shows respectively influence on the results from them.

CCS；carbon storage；minimum spanning tree；genetic algorithm；pipeline network

1000-1832(2016)03-0067-07

2015-03-17

国家自然科学基金资助项目(71471109)；交通运输部科技项目(2015328810160)；上海市科委科研计划项目(14DZ2280200，14511107402)；上海市教委科研创新项目(14YZ100)；上海市曙光计划项目(13SG48)；上海市科委科技创新行动计划项目(14170501500)；上海市自然科学基金资助项目(15ZR1420200)；教育部人文社会科学研究青年基金资助项目(15YJC630145，15YJC630059)；上海海事大学研究生创新基金资助项目(2014ycx013).

尹宇起(1991—)，男，硕士研究生，主要从事绿色物流、管道运输研究；胡志华(1977—)，男，博士，副教授，主要从事港航与物流运作优化、社会科学计算实验、计算智能研究.

U 172[学科代码]520·60

A

[DOI]10.16163/j.cnki.22-1123/n.2016.03.013