基于最短路多种群遗传算法的物流园区内部布局研究

孙 焰，马 驰，郑文家 （同济大学 交通运输工程学院，上海201804）

SUN Yan, MA Chi, ZHENG Wen-jia (School of Traffic and Transport Engineering, Tongji University, Shanghai 201804, China)

0 引 言

物流园区是众多物流功能的载体，其内部功能模块的合理布局直接影响着物流园区的有效运作和功能发挥。物流园区内部布局方法源于工厂车间布局设计[1]。Richard Muther 提出的系统设施规划布置——SLP（Systematic Layout Planning） 设计方法使平面配置布局设计从定性阶段发展到了定量阶段。Lee R.C、Buffa 等设施规划和设计学者将计算机技术引入到平面布局中，如CRAFT、CORELAP、ALDEP、COFAD、Multi-PLE 等，对布局问题进行优化设计。之后，图论法，割树法等都逐渐应用到平面布局中，并用遗传算法、禁忌搜索等启发式算法来求解。

本文在前人研究基础上，采用分割树作为中间媒介，将遗传算法的染色体和配置布局的结果对应转化，保持染色体的合法性。创新性引入最短路距离，使模型更符合实际情况，解空间更自由。引入精英策略，加速最优解的搜索。选用多种群遗传算法，避免单个种群的遗传算法陷入局部收敛和早熟。

1 配置布局模型

物流园区内部配置布局的最主要目标是实现各功能模块之间货物搬运成本最小和邻接关联程度最大。以此建立多目标配置布局模型。

1.1 模型假设

为保证物流园区内部配置布局模型求解的可行性，本文做如下假设：

（1） 各个功能模块和所要布局的地块形状均为矩形。

（2） 分割到底。因为在编码时采用二叉树分割的方式，地块分割时会一分到底，故不考虑出现类似如图1 的情形。分割线相当于园区内的路网，一般路网到底也符合实际情况。（3） 已知以下数据：功能模块的数目；功能模块之间的关联度；功能模块之间的货物流动量；单位货物搬运成本；布局地块的总面积；各功能模块的面积。

1.2 模型建立

根据功能模块间货物搬运成本最小和邻接关联度最大模型的目标要求，构建如下的数学模型：

式中：F1——功能模块之间搬运的总成本函数；F2——功能模块之间邻接关联度函数；fij——功能模块i到功能模块j的货物流动数；cij——功能模块i到功能模块j的单位货物单位距离搬运成本；dij——功能模块i到功能模块j中心的路网最短距离，将在1.3 中详细介绍；bij——功能模块i与功能模块j的邻近度，将邻近度值分成六个等级，具体见表1；范围由来确定，dmax表示最大距离，等于总地块的长宽之和。

vij——功能模块i与功能模块j的关联度，表示功能模块之间关系的密切程度，类似系统布局设计的作业单位间关系密切程度，并分成六个等级，具体见表2。

表1 功能模块间邻近度

表2 功能模块间关联度

ak——功能模块k的面积；A——布局地块的总面积。

1.3 最短路引入

传统的计算模块i到功能模块j的距离dij的方法包括欧式距离方法和曼哈顿距离。即：

这两种距离的算法会影响配置布局的方案，甚至导致配置布局方案的错误，与实际不符。如图2 中所示，模块2 到模块6 的距离，不管是用欧式距离还是曼哈顿距离，算得结果即是图中蓝色线所示，而实际距离却是图中红色线表示的；正是蓝色线代表的两种计算方法导致布局图出现[2,3,5,6 ]累计长条形布局情况。

为了避免长条形布局的出现，张智文等[2]提出采用长宽比范围作为罚函数的方法。但这存在两点问题：首先合适的长宽比值的范围难以确定，其次长宽比值的限定会导致解空间的缩小，甚至达不到最优解。

为此，将布局图中每个模块的边界看作路网，引入最短路距离来计算模块i到功能模块j的距离dij，即图2 中红色表示，是完全符合实际又能避免上述问题的，同时也保证了解空间的自由性。本文采用Dijkstra 算法来求解模块之间的最短路。

2 多种群遗传算法的模型求解

遗传算法是模拟Darwin 进化论和Mendel 遗传学说的自适应概率性搜索算法。但是单个种群的遗传算法容易陷入局部收敛和早熟，故选用多种群遗传算法。同时加入精英策略加速最优解的搜索。

单个种群的遗传算法由随机产生的一组初始解开始，通过模拟自然选择和遗传过程中的交叉、变异过程，代代进化，得到该种群的更优解。多种群遗传算法在此基础上，将每个种群的更优解带入到临近的种群中，作为其初始解的一部分，继续交叉变异迭代，最后得到问题的最优解，其一般流程示意图如图3 所示。

2.1 编码方案

合理合法的染色体编码是遗传算法设计的重要环节，本文选用实数编码和符号编码结合的编码方案：实数集合表示m个功能模块的编号；符号集合中的“+”表示垂直布局，“=”表示水平布局。一个合法的染色体包含m个不同的功能模块编号和（m- 1 ）个符号。

应用遗传算法求解实际问题的关键是如何进行编码空间与解空间的相互转换。本文采用分割树作为中间媒介，使染色体和配置布局达到对应互换。染色体转化成分割树后，从分割树的根部开始，自上而下分割，得到两个分支，先处理右分支，将其布局在离原点（即左下角的顶点） 最近的位置，再处理左分支；接着分别从各分割树的根部开始，继续从上而下分割，直到最后没有根节点，最终得到功能模块的配置方案，举例见图4。

2.2 构造初始解

用（m+ 1,m+2 ）表示符号｛+,= ｝，那么在Matlab 中就可用一个集合变量来表示一条合法的染色体。构造染色体时，按照从左向右的顺序依次放置，记模块编号个数为n，在染色体完成前保证符号的个数小于n-1；同时要保证模块编号的唯一性。

2.3 适应度函数与染色体评估

遗传算法在运行中基本不利用外部信息，主要以适应度函数（Fitness function） 为依据，充分利用种群中每个个体的适应度值来搜索。因此适应度函数的选取相当重要，影响到对遗传算法的收敛速度及能否找到最优解。

本文适应度函数由目标函数变换而成。由于物流园区功能模块配置优化模型中的是多目标函数，因此先将其归一化后，转化为单目标函数。转化后

新的目标函数为：

式中：F——新的目标函数；F1[ ],F2[ ]——对应目标函数的数量级；w——搬运总成本项权重值，权重值可由专家确定；V——功能模块i与功能模块j的最大邻接关联度，模型中取1。

由于遗传算法中按照适应度最大筛选染色体，故采用将目标函数进行倒数变换确定适应度函数。即有：

2.4 选择算子

选择时，采用精英策略，即当前最大适应度函数的染色体直接入选；其余染色体用轮盘赌进行选择，即适应度值为fi的染色体i，被选择的概率为：

2.5 交叉算子

交叉算子使两个父代随机地交换某些基因，产生新的基因组合，期望将有益基因组合在一起。本文采用位置的杂交，先将染色体分为编号部分和符号部分。当满足交叉概率时，两个父代染色体的符号部分参与交叉：随机选取一个位置，两个父代染色体符号部分从该位置开始交换，最后将新的符号部分和之前的编号部分组合，得到新的子代的染色体。举例说明如下：

随机所选位置：2

2.6 变异算子

变异算子是对个体染色体的某些基因值作变动。同交叉算子一样，先将染色体分为编号部分和符号部分，满足变异概率时，随机生成变异位置，将符号部分中对应该位置的符号置反，即“+”替换成“=”，将“=”替换成“+”，得到变异后的后代。

3 宁波陆港物流园区的实例验证

该部分使用前文所述的数学模型和算法原理，以宁波陆港物流园区为例，进行实例验证。

3.1 园区概况

宁波陆港物流园区位于宁波三江片北部进城门户，离中心城区距离适中，极易开展城市及区域配送；紧邻宁波城市工业功能区、江北高新技术产业园，极易开展工业第三方物流；此外还是镇海、北仑、舟山连接长三角上海、杭州、苏南地区通道的重要节点，极易形成区域性的物流集散中心。研究该物流园区的功能区的配置问题对拓展物流宁波区位优势、服务优势、战略优势都具有举足轻重的作用。

宁波陆港物流园区的园区类型定位：集公铁运输、生产服务和商业配送为一体的综合服务型物流园区。园区层次定位：全国重要的公路货运主枢纽、浙江省重点交通物流基地、宁波市级物流中心。园区功能定位：城市配送、第三方物流、货运交易和省际物流、商贸物流、配套商务与商业、配套住宅等六大功能。

3.2 功能模块划分

根据物流园区的功能定位，将该物流园区划分为12 个功能模块，由市场预测和功能模块单位处理能力计算得到各功能模块的占地面积，具体如表3 所示。

3.3 功能模块关系图

考虑物流园区的物流、行政、服务、事业等因素，可以判定各个功能模块之间的关系，绘制出宁波陆港物流园区的功能模块关系图，如图5 所示。

由图2 功能模块关系图和表2 的量化指标，可以得到物流园区功能模块配置优化模型中的Vij矩阵。如表4 所示。

3.4 功能模块货物流量流向表

通过对宁波陆港物流园区内部的运作流程分析，结合同等规模物流园区的资料，得到宁波陆港物流园区的功能模块之间的货物流量流向表，如表5 所示。

3.5 主要参数确定

种群数目100，种群规模100，迭代代数20。交叉概率选取0.95。变异概率选取0.01。搬运总成本项权重值w本文取0.8，则邻接关联度项权重值为0.2。

3.6 遗传算法求解结果

运行该遗传算法，得到迭代螺旋收敛图，如图6 所示。图中，俯视时共有100 个圆，每个圆代表一个种群的在迭代20 次过程中的更优解的变化，相当于一个单种群的遗传算法。明显看出，与单种群遗传算法相比，多种群遗传算法不会陷入局部最优解，其最终收敛的解更接近于问题的最优解。

表4 功能模块之间关联度量化表

表5 功能模块之间货物流量流向表 单位：吨/年

功能模块布局图，如图7 所示。

从图6 螺旋收敛图中可以认为目标函数最后达到近似最优解，收敛于1.0280。最终的染色体是：4 2 = 5 6+ 7 = 9 8 3 + = + 12 = + 1 11 + 10 + =。同时，得到对应的功能模块间货物搬运成本为1 276.6 万元/年，邻接关联度为89.68。

4 结束语

本文计算了物流园区内部路网最短距离，更贴近实际。在此基础上，应用分割树的方法，考虑物流园区内部各功能模块之间货物搬运成本最小和邻接关联程度最大，建立了物流园区内部功能模块配置布局模型。采用精英策略，设计了多种群遗传算法进行求解。应用实例证明，与单种群遗传算法相比，多种群遗传算法不会陷入局部最优解，其最终解更接近于物流园区内部布局问题的最优解，更好地兼顾了各功能模块之间货物搬运成本最小和邻接关联程度最大。

[1] AIELLO G, LA SCALIA G, ENEA M. A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding[J]. Expert Systems with Applications, 2012,39(12):103-105.

[2] 张智文. 基于遗传算法的物流园区功能区布局方法研究[D]. 北京：北京交通大学（硕士学位论文），2007.

[3] MELLER R D, GAU K-Y. The facility layout problem: recent and emerging trends and perspectives[J]. Journal of manufacturing systems, 1996,15(5):351-366.

[4] 刘训波，孙小明. 基于二叉树的遗传算法求解设施平面布局优化[J]. 数学的实践与认识，2011,41(21):76-82.

[5] 张超群，郑建国，钱洁. 遗传算法编码方案比较[J]. 计算机应用研究，2011(3):819-822.