之前没学过运筹学，最近又要用，因此找了一些”也许相关的论文“读读看。这里介绍的是一片 Chemical Engineering Research and Design 期刊上的文章 New model for large scale chemical industrial layout optimization。这篇文章研究的是化工厂环境中的布局问题，其中涉及了大规模管线布置的问题，符合我未来工作的需要。
论文作者在论述自己的核心贡献点的时候声称，“复杂的管道网络以及管架之前没有被充分讨论，且目前的算法尚无法高效地解决大规模布管问题。”这篇文章提出了一种解决一般的布局问题的新型模型以及对应的优化方法。在新模型中，管道模具以及管架被设计（定义）成不同的段（Segments），管道布局、管道连接以及管架的排布都可以同时进行优化。在优化的过程中还考虑， 安全性、地理性以及环境性限制条件。
1 背景介绍
布局问题的重要性不必多言。在研究问题，布局设计问题被称为 Facility Layout Problem (FLP)。FLP 问题是非常复杂的，是 NP-hard 的问题。对于化学工业企业的 FLP 问题，按照设施的范围可以分为两大类设计，如确定加工单元内的设备位置和确定工业区内的加工单元位置。它们分别被称为工厂布局 (plant layout) 和一般布局 (general layout) 问题。这里，一般布局也被称为全区布局 (area-wide layout.)。
在一个区域范围内的布局问题中，工厂的相对位置直接影响到材料处理成本、土地成本、能源损失和生产安全。大多数研究集中在土地成本和 FLP 的安全问题上。解决 FLP 问题的方法包括：
- 启发式方法 (heuristic method)
- 图论方法 (gragh-theoretic heuristics)
- 模拟退火方法 (simulated annealing algorithm)
- 分支和约束方法 (branch and bound method)
- MILP Solver
- 多目标混合整型线性规划模型 (multi-objective mixed-integer linear programming model)
- integrated fuzzy simulation-fuzzy data envelopment analysis (这 tm 什么名)
- 混合遗传算法 (hybrid genetic algorithm (GA))
一般来看遗传算法是最广泛使用的算法，这类算法的优点是鲁棒性以及可扩展性，不过 GA 算法的优化时间太长了。并行化算法可以加速 GA 的优化过程。OpenMP 是一个可用来实现并行化 GA (PGA) 算法加速的框架（这篇论文就是使用的这个框架）。
论文的核心贡献点包括：
- 在优化过程中考虑到了多设施的复杂管网，以及物质流的管网。
- 多层管架的设计被加入到全区布局的优化中，包括层数的确定和管架上管线的详细布局。
- 管子的隔热层厚度和每两根管子之间的空间都是可变的。根据管道中流体的物理和化学特性，管道的绝缘厚度和每两根管道之间的空间都是可变的。管道中流体的物理和化学特性而变化。
- 该方法可以解决现实生活中的大规模问题。研究了一个现实生活中的大规模化学工业区，以说明所提出的方法的有效性和适用性。
- 提出了一种结合 GeoSteiner 算法和 PGA 的新方法来优化包括厂房、管道和管架在内的全区布局问题 (general layout)。
2 问题建模
General Layout 问题可以划分成两阶段的优化问题
- 外层优化问题是确定设备的最佳位置；
- 在设备位置确定的前提下，确定最优的管线布置方案。
目标工业区域被划分成 的网格，每个网格可以放置一个设备 (Plant)。管线可以划分为两种不同的类型：
- 简单管线连接，即没有分支 (Branches)；
- 网络管线，即包含复杂分支结构；
由于管线结构的不同，这两类管线需要使用不同的模型来描述，其投资成本和能量开销的计算方式也不同，需要分开处理。
管线和管架之间存在互相影响的关系。例如为了支撑管子的重量，管架的建设成本需要随着管子数量的增加而增加。这两部分需要联合优化。可以通过管线布局均衡来平衡不同管架的层数。管架本身或者连接两个设备的管线会被视为一个段（Segment）。对于一个有 个设备的厂区中的段的数量是 。
最终问题建模如下：
2.1 假设条件
- 设施之间的距离是指设施的边界之间的水平或垂直长度；
- 相邻两个设备之的距离都是相同的，且不大于最小安全距离；
- 管道和管架只可以水平或者垂直放置；
- 水力和热力计算都是等温的 (Both hydraulic and thermodynamic calculations are isothermal)；
- 假设低粘度流体 () 位于阻力平方区域 (the resistance square area) 内，高粘度 () 位于层流区 (laminar flow area)；
- 管道架的高度是固定的；
- 通信线缆部署在地下，因此在管架上不会预留线槽；
2.2 已知
- 设施的数量；
- 用来部署设施的空网格的分布位置；
- 设施中的物料流及用量；
- 物料流之间的连接关系；
- 管道中传输的流体的物理化学特性；
- 厂区的地理位置和交通条件。
2.3 需要确定
- 设施的相对位置；
- 管线布局；
- 管子在管架上的布局；
- 管架的层数以及宽度；
2.4 规则
这里说的是管线布置需要符合一些国家标准，都是一些量化指标，这里不赘述了。
3 方法
3.1 目标函数定义
其中 是总成本， 是简单管道数量（无分支）； 是管道网络的数量， 是管道分支的数量， 是分段的数量。
论文花了大量的篇幅去描述各个成本项 的构成，但是这些细节问题是高度依赖于问题场景的，这些细节我不需要关注。
4 算法
文章使用的算法架构是 GeoSteiner 算法加上并行遗传算法（PGA），这套算法可以同时优化设施布局和管道布局。
4.1 PGA
遗传算法本身我已经很熟悉了，这里介绍算法本身特征的文字就不列举了；重要的是如何对问题建模，定义出遗传因子编码、交叉、变异等操作的形式，以及效用函数的定义。
论文使用 PGA 算法来优化设施位置。
4.2 GeoSteiner
GeoSteiner 算法是有专门的软件的包的。这是一个专门的问题（Steiner Tree Problem），因此我会单独调研一下。