多路径交互环形过道布置问题建模及改进蚁狮算法优化

王沙沙，张则强，刘俊琦，陈 凤

(西南交通大学 机械工程学院轨道交通运维技术与装备四川省重点实验室，四川 成都 610031)

1 问题的提出

系统的规划和布局对提高工业生产率和服务效率具有重要意义，同时科学合理的设施布局结构有助于提高物料搬运效率并降低物流成本。设施布局问题(Facility Layout Problem, FLP)为系统规划和布局的关键环节，其重要性日益凸显，作为FLP的一种，过道布置问题[1](Corridor Allocation Problem, CAP)因具有较高的搬运效率而被广泛应用在实际生产生活中，如行政办公楼的办公室[2]、医院走廊两侧诊室[3]和车间等布局问题。因此，CAP研究具有一定的实际应用价值和意义。

AMARAL[1]在2012年首次提出CAP，并建立以最小化加权物流成本为目标的混合整数规划模型，引起了学者们的广泛关注，CAP也被更加深入地研究，包括计算方法的改进和问题的进一步拓展。在计算方法方面，AHONEN等[4]、毛丽丽等[5]通过不同智能算法对该问题进行求解，均得到比较理想的计算结果；在问题拓展方面，KALITA等[6]将最小化过道长度加入CAP，不考虑相邻设施之间的间隙，提出无约束优化双目标CAP；KALITA等[7]加入新约束，即相邻设施之间不能有间隙，改进了其所提出的双目标CAP，并改进遗传算法(Genetic Algorithm，GA)对新的双目标CAP进行求解；管超等[8]将CAP扩展到双层设施布局规划，提出双层CAP，两层之间通过货梯连接，并对该问题建立了混合整数规划模型；管超等[9]在2019年又提出双层过道布置混合整数非线性规划模型；刘思璐等[10]提出考虑设施深度的CAP，并采用烟花算法进行求解；ZHANG等[11]将过道宽度的约束加入传统CAP中，利用改进分散式搜索算法进行仿真求解。上述文献求解问题时均假设过道为直线型，但许多建筑设计并非如此，首尾连通的环形布局同样广泛应用，其在大型医院和商场中最为常见。环形生产线也是常见的生产线布局类型之一[12]，生产线的环形布置适合于物流方向与工序方向相同、总物料进出口设置在一起的生产线(图1为环形生产线示意图)；另外，掘进机超宽带位姿检测基站、机动车检机构[13]也会采用环形布局。贾林等[14]在2019年首次提出环形过道布置问题(Annular Corridor Allocation Problem, ACAP)，将面积成本和物流总成本进行无量纲化处理，为环形设施布局的研究奠定了基础，但其将所有物流交互路径均设置在环形过道中线，并未考虑设施布置在过道同侧与不同侧时进行交互的区别，与实际生产情况存在一定差异。

蚁狮优化(Ant-Lion Optimizer, ALO)算法是Seyedali Mirjalili[15]于2015年提出的一种启发式算法，该算法模拟自然界中蚁狮的捕食机制，通过轮盘赌法构建陷阱、蚂蚁随机游走、蚂蚁掉进陷阱、蚂蚁滑向陷阱底部、捕获猎物和重建陷阱5个主要的捕食步骤来实现全局寻优，在改进搜索、避免局部最优和收敛性等方面具有良好的性能。该算法自提出以来，在热液与风力发电调度问题[16-17]、经济负荷分配[18]、无人机航迹规划[19]、配电网优化调度[20-21]等方面均有应用，而且计算结果较好。例如，黄长强等[19]针对基本ALO算法在解决三维航迹规划时能力不足的问题，引入混沌调节因子和反调节因子，提高了算法的探索能力和开发能力。

综上所述，为探究多路径交互对ACAP的影响，本文提出划分3条不同物流交互路径的多路径交互ACAP，从而进一步优化物流成本，减轻物流冲突。其次，鉴于改进蚁狮优化(Improved Ant-Lion Optimizer, IALO)算法在求解类似问题中显示出的优势，本文提出一种将随机行走机制与迭代机制融合，根据迭代次数增大动态化处理随机行走机制的IALO算法，对所提问题进行求解。

2 多路径交互环形过道布置问题的数学模型

2.1 问题描述

文献[14]在提出ACAP时，假设其交互路径唯一。考虑到环形过道布置在优化过程中，多路径交互方式和环形过道宽度的动态性特点对物流总成本的影响，采用多路径交互来缓解单一路径拥堵的问题，可以使该问题的研究更符合实际生产情况。多路径交互ACAP可以描述为两个主要过程：①将n个设施分为两组，分别计算两组设施的长度，以设施长度较长的序列作为外圈，较短序列作为内圈；②将内外两圈设施序列从同一映射半径进行布置并首尾相连，组成同心圆环，完成对环形过道的布置。

由于环形过道布置过程中设施位置和长度的不确定性，其环形过道宽度随设施布置位置的变化而变化，即内外两圈设施长度变化时，过道宽度也随之变化；另外，由于ACAP的特点，过道宽度对物流成本有一定影响，在动态优化ACAP的基础上，根据同圈异圈划分两种不同的交互方式，如图2所示，设施序列为[1 2 3 4 5 6 7]，将其从位置4分为[1 2 3 4]和[5 6 7]两组设施序列，计算两组设施的长度，假设[1 2 3 4]序列较长，将两组设施以加粗虚线为环形过道设施布置起点，两组设施沿顺时针布置，最后在外圈增设外部交互出入口X。当两个设施处于同圈时，其设施之间的交互路径为过道边线，如图2中设施1和设施2之间的距离为d12，设施5和设施6之间的距离为d56；当两个设施位于异圈时，其设施之间的交互路径为过道中线，交互距离近似为两个设施投影到过道中线长度d15和过道宽度e之和，例如图2中设施1和设施5之间的距离为d15+e。

2.2 主要假设条件

(1)设施的长度和设施之间的单位加权物流交互成本为已知量。

(2)以环形过道中心加粗虚线所在位置为设施布置的起点位置。

(3)每个设施的物流交互点均处于过道边线中点，设施宽度暂不考虑。

(4)由于增设外部交互出入口X，将其设为布置起点，为便于对比计算，将其长度简化为0，而且所有物流交互不穿越布置起点。

(5)设施布置不受场地约束和限制。

2.3 数学模型

为了便于表达，给出数学模型中各个数学符号的定义，如表1所示。

表1 数学模型中参数的定义

对比CAP和ACAP，多路径交互ACAP要考虑物流交互路径的不同以及过道宽度的变化，在此基础上，以最小化物流成本为目标，建立基于动态过道的多路径交互ACAP的数学模型：

(1)

s.t.

-Xij+Xik+Xjk-Xji+Xki+Xkj≤1,

i,j,k∈N，i

(2)

-Xij+Xik-Xjk+Xji-Xki+Xkj≤1,

i,j,k∈N，i

(3)

Xij+Xik+Xjk+Xji+Xki+Xkj≥1,

1≤i

(4)

Yij=Xij+Xji,1≤i,j≤n，i≠j；

(5)

1≤i

(6)

1≤i

(7)

1≤i

(8)

(9)

(10)

Xij,Yij∈{0,1},1≤i,j≤n,i≠j。

(11)

其中：式(1)为目标函数，表示所有设施间的单位距离物流成本与实际运输距离乘积的最小值，位于不同圈设施间的实际运输距离包括过道宽度e，用1-Yij判断设施i和设施j是否在不同同圈，dij+e(1-Yij)表示设施间的实际运输距离；约束条件(2)～约束条件(5)用于确定决策变量Xij和Yij，Xij确保设施在排列时分成两圈，并确定排列时各个设施的相对位置；约束条件(6)～约束条件(8)计算各设施直线排列时的交互距离，用于近似表示设施间的弧线距离；约束条件(9)表示外圈设施的总长度，即设施交互距离矩阵中的最大值与其对应的两个设施长度一半之和；约束条件(10)计算过道宽度，与直线型过道布置问题不同，ACAP中的过道宽度会随布局变化而变化，因此需要计算过道宽度e，即外圈对应半径与内圈对应半径的差值，并限制其大于0，以保证两圈设施不会出现重叠；约束条件(11)为决策变量Xij和Yij的取值范围。

3 求解多路径交互环形过道布置问题的改进蚁狮算法

3.1 蚁狮算法介绍

ALO算法是一种用于分布式优化问题的新算法，其灵感来源于自然界中蚁狮捕食蚂蚁的行为。蚁狮在沙子里挖一个圆锥形的洞并躲在圆锥的底部，等待蚂蚁掉进洞里。当蚂蚁不幸掉到蚁狮洞里时，蚁狮向上喷沙子使蚂蚁掉到圆锥底部，然后将其吃掉。一次捕食行为结束后对坑进行修补，等待下一只猎物出现。陷阱和蚁狮的质量通过这样的过程不断提高。

蚁狮算法模型主要分为5步：

(1)通过轮盘赌法构建陷阱

轮盘操作根据蚁狮的适应度值选择一只蚁狮。蚁狮的适应度值越高，其健康状况越好，所构建的陷阱也越好，因此有更高的几率捕捉到蚂蚁。蚁狮的位置和适应度值分别用矩阵表示如下：

(12)

(13)

式中：ALi,j表示第i只蚁狮在第j维上的位置；f表示适应度函数。

(2)蚂蚁随机游走

蚂蚁位置

(14)

式中Ai,j表示第i只蚂蚁在第j维上的位置。

用如下公式表示蚂蚁的随机行走：

Xt=[0,cumsum(2r(t1)-1),0,cumsum

(2r(t2)-1),…,0,cumsum(2r(tn)-1)]。

(15)

式中：cumsum表示累积和；t为迭代次数；n为蚂蚁数量；r(t)表示随机函数，当产生的随机数大于0.5时，r(t)=1，否则r(t)=0。

蚂蚁位置的优劣由适应度函数表示。蚂蚁的适应度值保存在矩阵MOA中。

(16)

(3)蚂蚁掉进陷阱

蚂蚁随机行走受蚁狮陷阱的影响，用式(17)和式(18)对此进行数学解释，表明蚂蚁被要求在一个由向量c和d定义的超球体内围绕选定的蚁狮移动。

(17)

(18)

(4)蚂蚁滑向陷阱底部

蚁狮一旦意识到陷阱里有蚂蚁，就会从陷阱中心向外喷射沙子，使蚂蚁滑向陷阱底部。

(5)捕捉蚂蚁并重建陷阱

(19)

表示第t次迭代中，第i只蚂蚁被第j只蚁狮捕食，即蚁狮种群更新。

ALO算法将每次迭代的精英蚁狮保存下来，若迭代未完成，则回到初始位置重新构建陷阱，重复进行捕捉操作，直到迭代结束。

3.2 改进蚁狮算法

原始ALO算法主要求解连续性问题，对离散问题的求解相对较少，为了将ALO算法应用到多路径ACAP中，在原始ALO算法的基础上对其结构进行调整，以求解所提问题，主要进行两部分结构改进，具体如下：

(1)蚁狮衍生蚂蚁种群

原始ALO算法随机产生初始ALO种群和初始蚂蚁种群，局部寻优能力相对较差。为了改善算法的局部寻优能力，IALO算法只生成初始蚁狮，不再同时生成蚂蚁。改进算法采用轮盘赌法选择一个较优蚁狮后，对其进行蚁狮衍生蚂蚁变异操作，产生局部蚂蚁种群，并更新蚁狮，进行蚁狮种群更新迭代。蚁狮衍生蚂蚁变异操作方式如图3所示，图中随机在(1，n)开区间内生成两个整数对应蚁狮位置MAL，将两个MAL的中间序列进行逆向排序来衍生蚂蚁，然后根据问题规模的不同设置蚂蚁种群Q组。

(2)动态化随机游走

根据迭代次数的取值范围选定随机游走操作次数。在进行初始求解时，为了提高算法的全局寻优能力，将随机游走次数和初始蚁狮种群设置为较大值，随着迭代次数的增大，得到的精英蚁狮越来越接近最优解，在该过程中，随着迭代次数的增加，逐渐减小蚂蚁随机游走的操作次数，以减少后期操作的计算量，提高计算速度与计算效率。在求解时，调整蚂蚁种群Q，以减少蚂蚁随机游走操作，实现动态化的随机游走过程。具体过程如下：将迭代次数分为(0,0.2Nmax]，(0.2Nmax,0.4Nmax]，(0.4Nmax,0.6Nmax]，(0.6Nmax,0.8Nmax]，(0.8Nmax,Nmax]5个阶段，在不同迭代阶段选择不同的衍生蚂蚁种群规模，随着迭代次数的增加，随机游走次数减小，将5个阶段分别对应的随机游走次数设置为Q，⌈0.8Q⌉，⌈0.6Q⌉，⌈0.4Q⌉，⌈0.2Q⌉。具体操作如图4所示。

3.3 改进蚁狮算法伪代码及步骤

IALO算法的伪代码如下：

Initialize the first population of ants and antlions randomly

Calculate the fitness of antlions for MOAL

Find the best antlions and assume it as the elite(determined optimum)

While i

for every ant

Select an antlion using Roulette wheel

Create a random walk around the selected antlion

Update the position of ant

End for

if(ant is fitter than antlion)then

Replace antlion with its corresponding ant

end

Update elite if an antlion becomes fitter than the elite

end while

Return elite and its fitness

IALO算法的具体操作步骤如下：

步骤1初始化参数。设置问题规模n、最大迭代次数Nmax、蚁狮初始种群规模M、动态游走步长最大值Q。

步骤2判断当前迭代次数i

步骤3对蚁狮种群进行轮盘赌操作，选择较优蚁狮，保留蚁狮位置和适应度值。

步骤4根据轮盘赌选择蚁狮位置、当前迭代次数、最大迭代次数，然后根据当前迭代次数i选择游走步长，蚂蚁在轮盘赌产生的蚁狮周围进行动态随机游走操作，产生蚂蚁种群。

步骤5更新当前蚂蚁位置MA和适应度值MOA。

步骤6蚁狮捕食蚂蚁，更新蚁狮种群的位置MAL和适应度值MOAL，以及精英蚁狮位置和适应度值。

步骤7转步骤2。

步骤8达到设置的最大迭代次数，停止循环并输出结果。

IALO算法流程图如图5所示。

4 计算结果与分析

本文所做的所有算例测试试验均在Window 10操作系统下进行，计算机硬件配置为：Intel(R)Core(TM)i5-8265U，主频1.8 GHz，内存8 GB。计算软件所用版本为Lingo 11和MATLAB R2016b。

为了验证混合整数规划模型的正确性，本文采用精确求解软件Lingo 11求解小规模多路径交互ACAP，结果对测试算例S5～S8均求得最优解，验证了模型的正确性。然后将精确求解结果与IALO算法计算结果进行对比，对于测试算例S5～S8，IALO算法均可求到与Lingo 11相同的解，证明了IALO算法的正确性。IALO算法的部分参数设置为：问题规模为n时，最大迭代次数Nmax随问题求解难度和最优解的稳定性而定，设置初始蚁狮个数为M，蚂蚁随机游走为(0, 0.2Nmax]，(0.2Nmax,0.4Nmax]，(0.4Nmax,0.6Nmax]，(0.6Nmax,0.8Nmax]，(0.8Nmax,Nmax]5个阶段，对应的游走向上取整次数分别为Q，⌈0.8Q⌉，⌈0.6Q⌉，⌈0.4Q⌉，⌈0.2Q⌉。对于不同规模问题，经过20次测试算例试验，IALO算法的具体参数设置如表2所示。

表2 IALO算法参数设置

采用Lingo 11和IALO算法求解中、大规模算例的比较如表3所示，可见对于8规模算例，IALO算法的求解时间为1.14 s，Lingo的求解时间为3 057 s，证明IALO算法具有明显的优越性；对于9～15规模算例，由于自身局限性以及问题的复杂程度，Lingo不能在较短时间内求得全局最优解，将其计算时间设置为3 600 s，求得局部最优解，与IALO的计算结果进行对比，11规模算例的Lingo局部最优解为4 169.296，IALO算法求解结果为3 570.105，求解时间为23.91 s，解偏差gap=14.37，说明采用精确软件Lingo求解较大规模问题时的精确求解质量和效率均已不能满足要求；对于25～49之间的大规模测试算例，Lingo软件在3 600 s内不能给出计算结果，IALO算法在合理的时间内均求得最优值或近似最优值。

表3 Lingo 11与IALO算法的求解结果比较

为了验证算法对ACAP的求解性能，采用IALO算法对文献[14]考虑面积成本的双目标ACAP 13组算例的不同规模问题进行10次求解，结果显示IALO算法均可求得最优值或近似最优值，而且对于30规模以内的10组算例，IALO算法的求解时间为0.04 s，0.22 s，0.64 s，1.67 s，6.39 s，7.07 s，11.47 s，22.67 s，235.67 s，446.73 s，均优于改进禁忌搜索(Improved Tabu Search, ITS)算法；对于40规模以上的3组算例，IALO算法的求解时间为989.25 s，903.24 s，2 108.36 s，其中在42规模算例，IALO算法的计算时间较短，在40规模和49规模算例，ITS算法的计算时间较短，即IALO算法和ITS算法对40规模以上算例的求解效率互不占优。总而言之，在兼顾求解质量和求解时间的前提下，采用IALO算法求解文献[14]中的问题具有一定优势，如表4所示。

表4 求解结果对比

文献[14]采用单一路径交互方式计算物流成本，考虑到交互过程中可能出现拥堵，本文采用多路径交方式进行计算。为了验证多路径交互求解该问题的效果，编写文献[14]的单一路径物流交互程序，在相同参数设置下，采用IALO算法分别对单一路径交互方式和多路径交互方式进行计算，结果显示多路径交互比单一路径有明显的改善，其中对于30规模，单一路径的最优值为66 592.147，多路径交互的最优值为63 734.217，改善率为4.29%，如表5所示。

表5 环形单一路径交互与多路径交互对比

通过分析表3～表5可知，IALO算法对单一路径和多路径ACAP有良好的求解效率和质量，将其与GA和禁忌搜索(Tabu Search，TS)算法进行对比，进一步验证IALO算法的有效性和优越性，结果如表6所示。可见，在兼顾求解质量和时间的前提下：

表6 GA、TS算法和IALO算法的计算结果对比

(1)对比算法最优值偏差gapGA算法只有1组算例未出现最优值偏差，其求解S10算例的最优值偏差最大为5.04，TS算法和IALO算法均有3组未出现最优值偏差，TS算法在求解30规模算例时的最优值偏差最大为2.90，IALO算法在求解25规模算例时的最优值偏差最大为3.67，说明相对于GA，TS算法和IALO算法的求解稳定性相对较好。

(2)对比算法均值Avg14组对比算例中，GA中有13组算例的均值均大于TS算法和IALO算法。对比TS算法和IALO算法，14组算例中，IALO算法有9组算例的均值比TS算法优，有3组算例的均值和TS算法相同，有2组算例(S8和S9H)的均值比TS算法差。通过以上数据可以看出，GA的求解质量相对较差，TS算法的求解质量相对较好，IALO算法的求解质量最优。

(3)对比算法求解最优值或近似最优值Min针对14组对比算例，将3种算法求得的最小值作为最优值或近似最优值，GA有6组算例求得最优值或近似最优值，TS算法有8组算例求得最优值或近似最优值，IALO算法在14组算例均求得最优值或近似最优值，说明IALO算法相比GA和TS算法具有良好的寻优能力。

(4)对比算法求解时间t14组算例中，GA的求解时间均大于TS算法和IALO算法。对比TS算法和IALO算法，14组算例中，IALO算法有10组算例的求解时间比TS算法少，有4组算例的求解时间比TS算法长。在兼顾求解质量的情况下，GA对该问题的求解效率相对较差，TS算法的求解效率一般，IALO算法的求解效率良好。

综上所述，在求解多路径ACAP时，相比GA和TS算法，在求解效率和求解质量等方面，IALO算法均表现出良好的求解能力。

由表6的计算结果绘制GA、TS算法和IALO算法14组测试算例均值对比图，如图6所示。由表6和图6可见，IALO算法14组算例的求解结果均属最优值或近似最优值，其对应的14组均值为128.481，287.051，409.280，669.801，1 225.040，2 319.039，1 437.134，3 578.092，3 573.255，8 964.207，65 034.132，64 081.489，14 920.095，23 558.016，以上数据表明IALO算法在多路径交互ACAP上具有良好的求解性能。

根据表6的计算结果比较3种算法，由于GA的求解质量和时间相对较差，绘制TS算法和IALO算法箱型图，如图7所示。从图7和表6可见，IALO算法求解各种规模算例的平均偏差为0，0，0，1.18，0.79，0.19，1.75，0.95，1.15，3.67，2.03，1.59，1.33，0.93，而TS算法的平均偏差为0，0，0，0.54，1.40，0，1.97，1.35，1.62，2.42，2.90，2.04，0.68，0.72，说明TS算法和IALO算法均表现出良好的求解能力，但在兼顾求解时间的情况下，IALO算法具有更好的求解效率和质量。

5 结束语

针对现有ACAP中物流交互路径设置在过道中线，忽略设施位于环形过道同圈与异圈物流交互区别的不足，本文结合实际生产，研究了以最小化总物流成本为目标的多路径交互ACAP。

针对这一新问题建立混合整数规划数学模型，通过精确求解小规模算例验证了模型的正确性。然后设计了一种利用蚁狮衍生蚂蚁种群，并将随机行走机制和迭代次数进行关联和动态化处理的IALO算法，改进了原始算法的搜索能力。将该算法应用于不同规模实例，分别与精确方法和3种启发式方法进行比较，结果表明该方法具有良好的求解质量和效率。

本文并未考虑设施布置方向不同对布局的影响，未来研究可根据实际情况对ACAP进行进一步拓展，如设施方向可变的ACAP、多层ACAP、多约束ACAP等。