王 翔 李艳冰 徐克林

（同济大学 机械与能源学院工业工程所 上海200233）

在我国高速城镇化的今天，电梯已经成为日常生活中不可或缺的一部分。随之而来的则有各种因为电梯事故导致乘客被困甚至伤亡的新闻报导。相关数据显示在众多导致电梯安全隐患的因素中，制造质量占16%，安装占24%，而保养和使用问题高达 60%[1]。在 2017年，我国电梯的总保有量已到524.8万台[2]。市场的维修保养需求量增长极为迅速。

国内电梯市场上品牌众多，如奥的斯、三菱、通力、迅达、蒂森等，管理系统和模式照搬国外的体系。使用SAP数据库来统一设置工作任务清单，保养模块，保养频率，保养日期，保养时间平衡等。典型的电梯保养 SAP（System Applications and Products）系统如图1所示。但是工业工程的精益理念在电梯维修保养行业内的研究和运用基本属于空白状态。这个也和国内一线工地管理长期依靠工作经验有直接关系。

图1 典型的电梯保养SAP系统

我国地域广阔，城镇化发展迅速。现行的维修保养系统其实仅仅是表格化的分派工作，实际维修保养效果评估下来并不乐观。故障率和投诉率呈逐年上升的趋势，公众事故在行业内时有发生。

由表1可以发现由于交通原因导致的维修不及时所占的比例越来越大。从一个维修保养工地维修完成后转到另一个维修保养工地所需要的时间，目前在行业内的系统里没做考虑。维修路径安排由维修工自己决定。为了解决维修保养的路径不合理导致维修保养实际工作时间缩短、维修不及时的难题，本文对维修保养的行走路径规划进行了研究，通过将维修保养的路径规划转化为TSP (Traveling Salesman Problem）[3]问题。引入蚁群算法[4](AS) Ant System的概念[5-6]来解决维修保养路径的改善需求。

1 维修保养路径规划的改善

维修保养路径问题可以转化为TSP问题。该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。在维修保养任务不多，每天只需要拜访2～3个维修保养工地时，仅靠维修工的经验可以解决。而如果每天需要拜访10多个地点，就需要引入TSP的理论进行高效、快速的规划。

在维修保养路径规划时仅考虑路程，没有考虑交通拥堵。主要是因为国内维修保养工的主要交通工具是电动助力车。基本不受交通拥挤的影响。虽然不一定能获得全局最优解，但相对于人工安排，在效率上和结论上都会大有改善，并为维修保养现场管理带来了新的理念。

2 用蚁群算法求解TSP问题的方法

算法首先初始化结构图，定义TSP 问题的城市数量、连通情况、路径长度和信息素的初始值；算法的结束条件未能满足(结束条件包括：循环次数达到最大值、解在一定次数循环内没有改进、算法已经取得最优解等)使用算法定义的路径选择规则，选择蚂蚁下一步的走法；计算蚂蚁走过的路线的长度见式（1）；更新信息素，使用信息素的更新规则见式（2）。

其中，ηij=1/dij。dij是两个目的地之间的距离，Goed nodes是最大循环次数。

α和β分别是决定信息素和启发信息的权值；ρ是信息素的挥发率；τij是信息素数量；Δτij是信息素的增加量，计算方法是：

其中，Δτij（t）表示第k只蚂蚁一次搜索结束后路径（i,j）的信息素增量，在一开始时Δτij（t）=0 ，Q是一个固定的正数；Lm是第m只蚂蚁行走的路线长度。

1998年，Dorigo 和DiCargo 进一步发展了AS算法，强调了启发信息的重要性并使用了多种方法提高算法性能，形成 ACO 算法[7]，ACO 使用了ant- routing-table 来记录蚂蚁行走的过程。

3 用蚁群算法规划每日维修保养路径

给定一个有n个维修保养工地的TSP问题，人工蚂蚁的数量为m，每个人工蚂蚁的行为符合下列规律：

(1)根据路径上的信息素浓度以相应的概率来选取下一步路径。

(2)不再选取自己本次循环已经走过的路径为下一步路径，用一个数据结构来控制这一点。

(3)当完成了一次循环后根据整个路径长度来释放相应浓度的信息素并更新走过的路径上的信息素浓度。

用蚁群算法的实现步骤对维修保养路径规划的步骤如下：

（1）初始化相关参数, 设人工蚂蚁的数量为m。

（2）将人工蚂蚁用随机或者均匀方式分布到n个维修保养工地。

（3令每个人工蚂蚁在选择下一步的路径时，按照路径上的信息素浓度来决定相应的概率进行选择。

（4）每个人工蚂蚁在自己本次循环已经走过的路径将不会被选为下一步路径，通过路径记录表来进行控制。

（5）每一只蚂蚁在逐个前往各个维修保养工地后产生一个解，在访问的过程中，在i中保存已经访问过的维修保养工地。在维修保养工地i中，每只蚂蚁要在还没有访问的维修保养工地中，选出下一个要访问的维修保养工地j时，需要按照概率公式进行选择。如此进行循环，直到所有的蚂蚁最终访问完所有的n个维修保养工地。

（6）当每个人工蚂蚁完成了一次循环后，根据整个路径长度释放相应浓度的信息素，并对走过的路径上的信息素浓度做更新。

（7）对每只蚂蚁行走的总路径长度进行计算，并且保存其中的最优解。

维修工的交通工具是摩托车和电助动车，基本不受交通拥堵的影响。因此在这里使用地理坐标来设定工地的位置，可以在百度地图经纬度查询里获得坐标。例如以北纬 31.241633°， 东经121.508586°。为参考坐标，建立维修保养工地位置表，如表2所示。

使用MATLAB进行计算：

在MATLAB中按序号顺序把表2中的每一个工地的坐标位置输入矩阵jobsites。

jobsites =[ 121.436516 31.173949

121.463666 31.228802

…… ……

121.482089 31.222105]

%% 计算各个jobsite两两之间的距离

n = size(jobsites,1);

T = zeros(n,n);

for i = 1:n

for j = 1:n

if i ～= j

T(i,j) = sqrt(sum((jobsites(i,:) -

jobsites(j,:)).^2));

else

T(i,j) = 1e-4;

end

end

end

表2 维修保养工地位置表

设定蚂蚁数量为50，信息素重要程度因子为1，启发函数重要程度因子为5，信息素的挥发因子A为0.2；设定该计算的迭代次数的最大值为200。计算后得到的维修保养路径按工地序号的顺序依次为:14，28，13，8，19，4，10，1， 3，18，5，9，12，27，29，11，25，30，16，24，21，26，22，17，15，2，7，20，6，23，14。MATLAB 生成的维修保养路径图见图2所示，各代最短距离与平均距离的对比见图3所示。维修保养路径计算耗时约26s。

图2 最佳的路径示意图

图3 各代最短距离与平均距离对比图

4 结语

本文使用蚁群算法进行路径规划，可以快速地制定出合适的维修保养路径，高效地构建维修保养路径图。和现在完全凭维修人员的主观判断相比，有了很大的改进与提高。把电梯行业维修保养的现场管理从传统的仅凭经验的模式向依靠先进的理论工具的方向进行了改善，工作效率提高到仅需要26 s就可完成维修保养路径的计算。