周炳海 谭芬

摘 要：考虑将电动小车用来进行基于厂内循环配送策略的汽车装配线的物料配送，提出了汽车装配线电动车配送路径及换电站选址问题，以最小化系统总成本为优化目标建立了数学规划模型.针对这一复杂的混合优化问题，对该问题的性质进行了分析，提出了两阶段动态规划算法获取小规模问题的最优解；对于中、大规模问题，通过种群分割技术并在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]对基于物料超市的循环配送问题进行了建模分析，分别研究了路径和配送次数问题，并在多项式时间内求解；……