王 翔 李艷冰 徐克林

（同濟大學(xué) 機械與能源學(xué)院工業(yè)工程所 上海200233）

在我國高速城鎮(zhèn)化的今天，電梯已經(jīng)成為日常生活中不可或缺的一部分。隨之而來的則有各種因為電梯事故導(dǎo)致乘客被困甚至傷亡的新聞報導(dǎo)。相關(guān)數(shù)據(jù)顯示在眾多導(dǎo)致電梯安全隱患的因素中，制造質(zhì)量占16%，安裝占24%，而保養(yǎng)和使用問題高達 60%[1]。在 2017年，我國電梯的總保有量已到524.8萬臺[2]。市場的維修保養(yǎng)需求量增長極為迅速。

國內(nèi)電梯市場上品牌眾多，如奧的斯、三菱、通力、迅達、蒂森等，管理系統(tǒng)和模式照搬國外的體系。使用SAP數(shù)據(jù)庫來統(tǒng)一設(shè)置工作任務(wù)清單，保養(yǎng)模塊，保養(yǎng)頻率，保養(yǎng)日期，保養(yǎng)時間平衡等。典型的電梯保養(yǎng) SAP（System Applications and Products）系統(tǒng)如圖1所示。但是工業(yè)工程的精益理念在電梯維修保養(yǎng)行業(yè)內(nèi)的研究和運用基本屬于空白狀態(tài)。這個也和國內(nèi)一線工地管理長期依靠工作經(jīng)驗有直接關(guān)系。

圖1 典型的電梯保養(yǎng)SAP系統(tǒng)

我國地域廣闊，城鎮(zhèn)化發(fā)展迅速。現(xiàn)行的維修保養(yǎng)系統(tǒng)其實僅僅是表格化的分派工作，實際維修保養(yǎng)效果評估下來并不樂觀。故障率和投訴率呈逐年上升的趨勢，公眾事故在行業(yè)內(nèi)時有發(fā)生。

由表1可以發(fā)現(xiàn)由于交通原因?qū)е碌木S修不及時所占的比例越來越大。從一個維修保養(yǎng)工地維修完成后轉(zhuǎn)到另一個維修保養(yǎng)工地所需要的時間，目前在行業(yè)內(nèi)的系統(tǒng)里沒做考慮。維修路徑安排由維修工自己決定。為了解決維修保養(yǎng)的路徑不合理導(dǎo)致維修保養(yǎng)實際工作時間縮短、維修不及時的難題，本文對維修保養(yǎng)的行走路徑規(guī)劃進行了研究，通過將維修保養(yǎng)的路徑規(guī)劃轉(zhuǎn)化為TSP (Traveling Salesman Problem）[3]問題。引入蟻群算法[4](AS) Ant System的概念[5-6]來解決維修保養(yǎng)路徑的改善需求。

1 維修保養(yǎng)路徑規(guī)劃的改善

維修保養(yǎng)路徑問題可以轉(zhuǎn)化為TSP問題。該問題是在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。在維修保養(yǎng)任務(wù)不多，每天只需要拜訪2～3個維修保養(yǎng)工地時，僅靠維修工的經(jīng)驗可以解決。而如果每天需要拜訪10多個地點，就需要引入TSP的理論進行高效、快速的規(guī)劃。

在維修保養(yǎng)路徑規(guī)劃時僅考慮路程，沒有考慮交通擁堵。主要是因為國內(nèi)維修保養(yǎng)工的主要交通工具是電動助力車?；静皇芙煌〒頂D的影響。雖然不一定能獲得全局最優(yōu)解，但相對于人工安排，在效率上和結(jié)論上都會大有改善，并為維修保養(yǎng)現(xiàn)場管理帶來了新的理念。

2 用蟻群算法求解TSP問題的方法

算法首先初始化結(jié)構(gòu)圖，定義TSP 問題的城市數(shù)量、連通情況、路徑長度和信息素的初始值；算法的結(jié)束條件未能滿足(結(jié)束條件包括：循環(huán)次數(shù)達到最大值、解在一定次數(shù)循環(huán)內(nèi)沒有改進、算法已經(jīng)取得最優(yōu)解等)使用算法定義的路徑選擇規(guī)則，選擇螞蟻下一步的走法；計算螞蟻走過的路線的長度見式（1）；更新信息素，使用信息素的更新規(guī)則見式（2）。

其中，ηij=1/dij。dij是兩個目的地之間的距離，Goed nodes是最大循環(huán)次數(shù)。

α和β分別是決定信息素和啟發(fā)信息的權(quán)值；ρ是信息素的揮發(fā)率；τij是信息素數(shù)量；Δτij是信息素的增加量，計算方法是：

其中，Δτij（t）表示第k只螞蟻一次搜索結(jié)束后路徑（i,j）的信息素增量，在一開始時Δτij（t）=0 ，Q是一個固定的正數(shù)；Lm是第m只螞蟻行走的路線長度。

1998年，Dorigo 和DiCargo 進一步發(fā)展了AS算法，強調(diào)了啟發(fā)信息的重要性并使用了多種方法提高算法性能，形成 ACO 算法[7]，ACO 使用了ant- routing-table 來記錄螞蟻行走的過程。

3 用蟻群算法規(guī)劃每日維修保養(yǎng)路徑

給定一個有n個維修保養(yǎng)工地的TSP問題，人工螞蟻的數(shù)量為m，每個人工螞蟻的行為符合下列規(guī)律：

(1)根據(jù)路徑上的信息素濃度以相應(yīng)的概率來選取下一步路徑。

(2)不再選取自己本次循環(huán)已經(jīng)走過的路徑為下一步路徑，用一個數(shù)據(jù)結(jié)構(gòu)來控制這一點。

(3)當(dāng)完成了一次循環(huán)后根據(jù)整個路徑長度來釋放相應(yīng)濃度的信息素并更新走過的路徑上的信息素濃度。

用蟻群算法的實現(xiàn)步驟對維修保養(yǎng)路徑規(guī)劃的步驟如下：

（1）初始化相關(guān)參數(shù), 設(shè)人工螞蟻的數(shù)量為m。

（2）將人工螞蟻用隨機或者均勻方式分布到n個維修保養(yǎng)工地。

（3令每個人工螞蟻在選擇下一步的路徑時，按照路徑上的信息素濃度來決定相應(yīng)的概率進行選擇。

（4）每個人工螞蟻在自己本次循環(huán)已經(jīng)走過的路徑將不會被選為下一步路徑，通過路徑記錄表來進行控制。

（5）每一只螞蟻在逐個前往各個維修保養(yǎng)工地后產(chǎn)生一個解，在訪問的過程中，在i中保存已經(jīng)訪問過的維修保養(yǎng)工地。在維修保養(yǎng)工地i中，每只螞蟻要在還沒有訪問的維修保養(yǎng)工地中，選出下一個要訪問的維修保養(yǎng)工地j時，需要按照概率公式進行選擇。如此進行循環(huán)，直到所有的螞蟻最終訪問完所有的n個維修保養(yǎng)工地。

（6）當(dāng)每個人工螞蟻完成了一次循環(huán)后，根據(jù)整個路徑長度釋放相應(yīng)濃度的信息素，并對走過的路徑上的信息素濃度做更新。

（7）對每只螞蟻行走的總路徑長度進行計算，并且保存其中的最優(yōu)解。

維修工的交通工具是摩托車和電助動車，基本不受交通擁堵的影響。因此在這里使用地理坐標(biāo)來設(shè)定工地的位置，可以在百度地圖經(jīng)緯度查詢里獲得坐標(biāo)。例如以北緯 31.241633°， 東經(jīng)121.508586°。為參考坐標(biāo)，建立維修保養(yǎng)工地位置表，如表2所示。

使用MATLAB進行計算：

在MATLAB中按序號順序把表2中的每一個工地的坐標(biāo)位置輸入矩陣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 維修保養(yǎng)工地位置表

設(shè)定螞蟻數(shù)量為50，信息素重要程度因子為1，啟發(fā)函數(shù)重要程度因子為5，信息素的揮發(fā)因子A為0.2；設(shè)定該計算的迭代次數(shù)的最大值為200。計算后得到的維修保養(yǎng)路徑按工地序號的順序依次為: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 生成的維修保養(yǎng)路徑圖見圖2所示，各代最短距離與平均距離的對比見圖3所示。維修保養(yǎng)路徑計算耗時約26s。

圖2 最佳的路徑示意圖

圖3 各代最短距離與平均距離對比圖

4 結(jié)語

本文使用蟻群算法進行路徑規(guī)劃，可以快速地制定出合適的維修保養(yǎng)路徑，高效地構(gòu)建維修保養(yǎng)路徑圖。和現(xiàn)在完全憑維修人員的主觀判斷相比，有了很大的改進與提高。把電梯行業(yè)維修保養(yǎng)的現(xiàn)場管理從傳統(tǒng)的僅憑經(jīng)驗的模式向依靠先進的理論工具的方向進行了改善，工作效率提高到僅需要26 s就可完成維修保養(yǎng)路徑的計算。