王 翔 李艷冰 徐克林

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

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

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

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

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

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

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

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

在維修保養(yǎng)路徑規(guī)劃時(shí)僅考慮路程，沒(méi)有考慮交通擁堵。主要是因?yàn)閲?guó)內(nèi)維修保養(yǎng)工的主要交通工具是電動(dòng)助力車。基本不受交通擁擠的影響。雖然不一定能獲得全局最優(yōu)解，但相對(duì)于人工安排，在效率上和結(jié)論上都會(huì)大有改善，并為維修保養(yǎng)現(xiàn)場(chǎng)管理帶來(lái)了新的理念。

2 用蟻群算法求解TSP問(wèn)題的方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用MATLAB進(jìn)行計(jì)算：

在MATLAB中按序號(hào)順序把表2中的每一個(gè)工地的坐標(biāo)位置輸入矩陣jobsites。

jobsites =[ 121.436516 31.173949

121.463666 31.228802

…… ……

121.482089 31.222105]

%% 計(jì)算各個(gè)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è)定該計(jì)算的迭代次數(shù)的最大值為200。計(jì)算后得到的維修保養(yǎng)路徑按工地序號(hào)的順序依次為: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)路徑圖見(jiàn)圖2所示，各代最短距離與平均距離的對(duì)比見(jiàn)圖3所示。維修保養(yǎng)路徑計(jì)算耗時(shí)約26s。

圖2 最佳的路徑示意圖

圖3 各代最短距離與平均距離對(duì)比圖

4 結(jié)語(yǔ)

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