周炳海 谭芬

摘 要：考虑将电动小车用来进行基于厂内循环配送策略的汽车装配线的物料配送，提出了汽车装配线电动车配送路径及换电站选址问题，以最小化系统总成本为优化目标建立了数学规划模型.针对这一复杂的混合优化问题，对该问题的性质进行了分析，提出了两阶段动态规划算法获取小规模问题的最优解；对于中、大规模问题，通过种群分割技术并在Lévy飞行中融入深度邻域搜索算子构建了改进型离散布谷鸟算法.最后，进行了仿真实验，分别对比了两阶段动态规划算法，实数遗传算法及改进人工蜂群算法在解决该问题方面的性能，结果表明改进型离散布谷鸟算法的有效性以及在算法稳定性、搜索深度以及收敛性三个方面的较大优势.

关键词：厂内物料配送；超市；电动小车；换电站；Lévy飞行；深度邻域搜索

中图分类号：TP391 文献标志码：A

Abstract：Considering employing the electric vehicles to deliver parts to stations for automotive assembly lines based on inplant milkrun delivery strategy， an electric vehicle delivery routing and battery swap station location problem was presented， and a mathematical programming model with an objective function of minimizing total cost of the system was set up. To tackle this complicated problem， the property was analyzed， and a twophase dynamic programming method was adopted to obtain the global optimum for small scale problems. For medium and large scale problems， both the population decomposition strategy and the depth neighborhood search operator based on Lévy flight were applied to develop an improved discrete cuckoo search algorithm. Finally， through the comparison of the twophase dynamic programming method， real genetic algorithm and modified artificial bee colony algorithm， the simulation experiments were carried out to illustrate the effectiveness and great advantages in stability， deep searching ability and convergence of the algorithm.

Key words： inplant material delivery； supermarket； electric vehicles； battery swap station； Lévy flight； depth neighborhood search

隨着经济的不断发展，能源危机和环境污染的问题日益凸显，发展绿色生产物流成为制造业发展的必然趋势[1].电动小车（Electric Vehicle， EV）由于其清洁、节能等优点逐步被用来取代传统燃料小车进行厂外“最后一公里”以及厂内的物料配送[2].如何采用EV进行汽车混流装配线的物料配送对制造企业的节能减排、降成本增效益具有重要意义.

近年来，许多国内外学者对汽车混流装配系统中的物料准时化配送调度问题进行了较深入的研究.Emde等[3]对基于物料超市的循环配送问题进行了建模分析，分别研究了路径和配送次数问题，并在多项式时间内求解；Fathi等[4]由此构建了循环配送问题的多目标配送调度模型，并提出了融合优先级规则算法以优化配送次数和线边库存.Golz等[5]以德国某汽车制造商为例，以最小化小车司机为目标研究了其路径、调度和装载问题.上述文献都是考虑传统小车的物料配送，而EV配送的不同点在于一是节能减排，二是由于其电量有限、可行驶里程较传统燃料车较短，需要考虑到电量的补给工作.

而关于EV配送的电动车辆路径问题（Electric Vehicle Routing Problem， EVRP）多是对厂外物料进行配送.Artmeier等[6]第一次引进了EV并考虑小车的能耗成本，通过改进经典的最短路径法来研究“最优能耗”路径；Schneider等[2]提出了带时间窗的可充电车辆路径问题，小车采用在客户点充电方式补给电量.Yang等[7]采用更换电池方式补给电量，随之而来的便是换电站（Battery Swap Station， BSS）选址问题.目前有两种充电方式：直接充电和换电池.从效率和成本方面考虑，本文选择换电池的方式来补给电量.上述文献中每个客户仅被访问一次，不同于装配车间需要进行多次物料配送.

为此，本文在上述文献的基础上，提出了汽车装配线电动车配送路径优化及换电站选址优化问题，通过决策EV的配送路径及BSS位置来构建优化模型，提出了两阶段动态规划算法和改进型离散布谷鸟算法以最小化配送系统的总成本.

1 数学建模

1.1 问题描述

对于汽车混流装配车间的工位段S，物料超市负责暂存和分拣S所需的物料.考虑到车间突发情况多，为了使得小车的柔性更高，EV由人员驾驶操作，根据配送列表将各工位所需的物料在需要的时间送达，实现对工位段S多频次、小批量的物料配送.装配线不允许缺货，EV的电量不允许降为0，即需在BSS对小车补给电量.在超市附近有一系列换电站BSSs的备选点，需要决策的就是在备选BSSs中选择合适的BSS进行换电池操作以及EV的配送路径使得系统的总成本最小.

为有效描述要研究的优化问题，作如下基本假设：1）系统选用节拍时间作为基本的时间单位；2）计划期内的需求已知；3）不考虑EV负载对电池耗电量的影响；4） EV采用循环配送策略进行物料配送；5）各EV的配送路线不允许交叉（no overlapping）；6） EV可在各个备选换电站（Battery Swap Station， BSS）进行换电池操作，且在所负责工位段进行配送时不允许中断，即换电池操作只允许在到达第一个工位之前或离开最后一个工位之后进行；7）每辆EV最多进行一次换电池操作.

1.2 数学模型

为方便形式化描述，现定义符号，见表1～表4.

据上述问题描述、模型假设及符号定义，对汽车装配线电动车配送路径及换电站选址问题建模如下：

目标函数（1）表示最小化包括BSS建设成本、EV使用成本及运输成本的系统总成本；约束（2）～（4）表示每辆EV至少负责配送1个工位并且配送区域不重复；约束（5）表示每次配送不能超过EV的容量；约束（6）表示每辆EV最多进行一次换电池操作；约束（7）表示EV到达某节点的电量；约束（8）表示EV离开某节点的电量，其中，当EV离开BSS换完电池后变为满电量；约束（9）表示EV首次从超市出发的电量为Pk；约束（10）表示EV从超市离开的电量等于前一次配送到达超市的电量；约束（11） ～（12）表示变量的取值范围.

1.3 问题性质

为了进一步深入分析问题，针对上述构建的优化模型，给出了相关的引理、定理.

2 两阶段动态规划算法

由于各小车的配送路线不交叉，配送距离和需求仅与当前小车负责的配送区域有关，因此，提出两阶段动态规划法（Twostage Dynamic Programming， TSDP）来解决该问题：第一步确定最优工位划分方案，即解决EV配送路径的问题（Dynamic Programming Routing， DPR）；第二步解决相应小车的BSS站点问题（Dynamic Programming BSS， DPB）.

2.1 DPR问题

3 改进型离散布谷鸟算法

布谷鸟搜索算法（Cuckoo Search， CS）是由Yang等[8]在2009年提出的一种新兴的启发式群体智能优化算法.该算法基于布谷鸟寄生育雏的习性，并结合一些鸟类和果蝇Lévy飞行的行为.CS算法结构较简单、控制参数较少，且Lévy飞行的高随机性增强了算法探索解空间的性能.研究表明CS算法比粒子群算法（PSO）、遗传算法（GA）以及人工蜂群算法（ABC）等群体智能算法求解效率更高，目前已成功应用于多种工程优化问题的研究.因此，本文针对研究问题的特性提出改进型离散型布谷鸟算法（Improved Discrete Cuckoo Search， IDCS）.

本文實行种群分割技术，根据各鸟巢适应度的不同将布谷鸟分为三大种群，不同子群体中的鸟巢采用不同的搜索方法，从而保持种群搜索的多样性.对前Pd部分的优秀布谷鸟NPbest进行精英保留策略[9]；对前Pc部分的较优布谷鸟NPbetter在Lévy飞行中融入深度邻域搜索算子来获取新解，提高CS算法局部进行精细搜索的能力，提高收敛速度[10]；另外，对于种群中Pa部分的较差个体NPworse采取重建技术，利用其随机扰动性引导算法跳出局部最优.

3.1 鸟巢编码方式

鸟巢1，…，Npop采用变长三层混合编码方式，Npop为鸟巢的数量，也即种群规模的大小，编码长度表示该优化方案所采用的EV总数.编码的第一层为分区层，表示各EV负责配送区域的最后一个工位；编码的第二、三层为BSS层，第二层表示对应EV换电池的BSS所在备选点，其中0表示不需要换电池；第三层表示EV何时进行换电池操作，1表示EV在离开超市后换电池，0表示EV在到达超市前进行换电池.假设有|S|=12个工位、|F|=5个BSS备选点，如图2所示，给出了两鸟巢1、2的编码示意图.

3.4 基于Lévy飞行的深度邻域搜索

CS算法运用Lévy飞行的高随机性来进行全局搜索.标准的CS算法是用来解决连续优化问题，通过Lévy分布产生随机数来确定搜索的距离.而在组合优化问题中，解空间比较复杂，解之间的距离也不能用数学形式很好地去刻画，因此，离散CS算法需要根据离散问题的特性来定义搜索的距离.所以，根据Lévy分布产生的随机数来确定搜索的步长或深度[11].在本文提出的IDCS中，在鸟巢之间增加信息交换即交叉操作以加快算法的收敛速度，此外，在Lévy飞行部分嵌入了结合问题特征的深度邻域搜索算子，提高算法的精细搜索能力，具体包括：交叉算子（Crossover）、BSS层交换算子（BSSswap）、BSS层插入算子（BSSinsert）、BSS层反转算子（BSSinverse）.

3.4.1 Crossover算子

3.5 重建鸟巢

在标准的CS算法中，n个巢中有Pa部分将会被新的鸟巢取代，这些鸟巢由于不够好，所以很容易被宿主鸟发现从而无法保留至下一代.因此，需要重建鸟巢，重建技术包括变异、合并、拆分算子，使得鸟巢的长度分别为保持不变，减1，加1，如图4所示.

由于试验参数为三因素四水平，因此选用L16（43）的正交表，如表6所示.对于每种试验方案，IDCS算法运行20次，选用其平均值作为评价指标，试验结果的统计分析见表7.

由表7可知，种群规模Npop对IDCS算法性能影响最大，Npop值偏大将会导致较多的计算时间，Npop值偏小又会使得搜索不充分；Pc和Pa值很好地平衡了算法搜索的深度和广度.

综上，当问题规模S=30时IDCS算法的参数设置如下：种群规模Npop=120，执行基于Lévy飞行的深度邻域搜索操作的种群比例Pc=0.6，执行变异操作的种群比例Pa=0.25.

4.3 算法有效性验证

由于TSDP算法具有指数级别的时间复杂度，随着问题规模|S|的扩大，所需的计算时间急剧增加，故用其来解决小规模问题.因此，为验证IDCS算法的有效性，首先将其与TSDP算法在小规模算例下进行比较，将计算时间设置为1 200 s，是可接受的TSDP算法运行的时间.针对每个算例，IDCS算法运行20次，问题规模参数和测试结果如表8所示（符号”-=”表示TSDP算法无法在规定时间内获取最优解或无法比较）.其中，C*、CPU1为TSDP算法所得的最优目标函数值和相应的运行时间，、CPU2为IDCS算法运行20次的平均值和平均运行时间.

由表8可知，IDCS算法可以有效地解決小规模问题.各算例求得结果的平均值与TSDP算法求得的最优值的绝对偏差Δ值虽然随着问题规模的扩大而增大，但各算例优化结果的百分比偏差（percentage deviation，PD）[12]在区间[0，0.23]内.

为了进一步验证本文构建的IDCS算法的搜索性能，利用IDCS算法求解中、大规模算例，并将其与文献[13]、[14]中的实数遗传算法（RGA）、改进人工蜂群算法（MABC）进行比较分析，包括不同问题规模下优化结果的百分比偏差PD值以及标准差σ值分析，其中，百分比偏差PD值可以反映算法的搜索深度，标准差σ值反映出了算法的稳定性，PD值越大，表明本文构建的IDCS算法的搜索深度较其他算法更优.σ值越小，表明算法的稳定性更好.三种算法的优化结果如表9所示.可以很明显地看出IDCS算法的搜索深度和稳定性均优于其它两种算法.

4.4 算法收敛性能分析

此外，本文根据文献[15]中提出的解的优度（performance ratio，PR）作为算法收敛性能的评价指标.PR=V（H，T，Y）Best（Y），其中V（H，T，Y）表示算法H在迭代T次后对算例Y的求解结果，Best（Y）表示对算例Y求解获得的参照最优值.由于上文已验证的本文构建的IDCS算法的有效性，因此，下文将IDCS算法对算例Y经过1 000次迭代后的结果作为Best（Y）.PR值能很好地反应出算法的收敛性能，其值越小，表明算法的收敛性能越好.图5给出了问题规模S=50时迭代次数对三种算法的PR值的影响.

5 结 论

1）提出了汽车装配线电动车配送路径及换电站选址问题，对企业的节能减排、降成本增效益具有重要意义；

2）将该问题划分为两个子问题，并构建了TSDP算法以获得小规模问题的最优解，并证明该算法具有指数级别的复杂度；

3）构建IDCS算法求解中、大规模问题，通过在Lévy飞行中融入深度邻域搜索算子提高算法精细搜索的能力；

4）通过将IDCS算法与TSDP算法在小规模问题下进行比较，并与其它算法进行对比，验证其有效性.

参考文献

[1] 聂凯，谢丹凤，李巍.新能源汽车城市物流碳排放模型的构建与分析[J].湖南大学学报（自然科学版），2015，42（9）：134-140.

NIE K， XIE D F， LI W. Modeling and analysis of the carbon emission of new energy vehicle in urban logistics industry[J]. Journal of Hunan University（Natural Sciences）， 2015，42（9）：134-140.（In Chinese）

[2] SCHNEIDER M， STENGER A， GOEKE D. The electric vehiclerouting problem with time windows and recharging stations[J]. Transportation Science， 2014， 48（4）： 500-520.

[3] EMDE S， BOYSEN N. Optimally routing and scheduling tow trains for JITsupply of mixedmodel assembly lines[J]. European Journal of Operational Research， 2012， 217（2）： 287-299.

[4] FATHI M， RODRIGUEZ V， ALVAREZ M J. A novel memetic ant colony optimizationbased heuristic algorithm for solving the assembly line part feeding problem[J]. The International Journal of Advanced Manufacturing Technology， 2014， 75（1/4）： 629-643.

[5] GOLZ J， GUJJULA R， GüNTHER H O， et al. Part feeding at highvariant mixedmodel assembly lines[J]. Flexible Services and Manufacturing Journal， 2012， 24（2）： 119-141.

[6] ARTMEIER A， HASELMAYR J， LEUCKER M， et al. The shortest path problem revisited： Optimal routing for electric vehicles[C]//Annual Conference on Artificial Intelligence. Berlin Heidelberg： Springer， 2010： 309-316.

[7] YANG J， SUN H. Battery swap station locationrouting problem with capacitated electric vehicles[J]. Computers & Operations Research， 2015， 55： 217-232.

[8] YANG X S， DEB S. Cuckoo search via Lévy flights[C]//World Congress on Nature & Biologically Inspired Computing. IEEE， 2009： 210-214.

[9] 張 泉，杜亚星，张林峰，等.基于遗传算法的单U地源热泵钻孔内热阻研究[J].湖南大学学报（自然科学版），2014，41（9）：100-105.

ZHANG Q， DU Y X， ZHANG L F， et al. A study on the heat resistance of single U pipe in the ground source heat pump system based on genetic algorithm[J]. Journal of Hunan University（Natural Sciences）， 2014，41（9）：100-105.（In Chinese）

[10]何禹清， 彭建春， 文明， 等. 基于改进遗传算法的配电网动态无功优化[J]. 湖南大学学报（自然科学版），2010， 37（3）： 38-43.

HE Y Q， PENG J C， WEN M， et al. Dynamic reactive power optimization method for distribution network based on improved genetic algorithm[J]. Journal of Hunan University（Natural Sciences）， 2010， 37（3）：38-43.（In Chinese）

[11]WANG J， WANG L， SHEN J. A hybrid discrete cuckoo search for distributed permutation flowshop scheduling problem[C]//2016 IEEE Congress on Evolutionary Computation （CEC）. IEEE， 2016： 2240-2246.

[12]SINGH M R， MAHAPATRA S S. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks[J]. International Journal of Advanced Manufacturing Technology， 2011， 62（1/4）：267-278.

[13]ALNAHHAL M， NOCHE B. A genetic algorithm for supermarket location problem[J]. Assembly Automation， 2015， 35（1）： 122-127.

[14]周炳海， 刘子龙. 考虑衰退的流水车间生产与预防性维护集成调度方法[J]. 计算机集成制造系统， 2016， 22（5）： 1273-1279.

ZHOU B H， LIU Z L. Integrated scheduling method of production and preventive maintenance in flow shops with degradations[J]. Computer Integrated Manufacturing Systems， 2016，22（5）： 1273-1279. （In Chinese）

[15]QU P， MASON S J. Metaheuristic scheduling of 300mm lots containing multiple orders[J]. IEEE Transactions on Semiconductor Manufacturing， 2005， 18（4）： 633-643.