基于多目標(biāo)遺傳算法的電梯維保路徑規(guī)劃方法研究

關(guān)鍵詞：電梯;多目標(biāo)優(yōu)化;維保路徑規(guī)劃;優(yōu)先級;多維保站點

中圖分類號：TP18 文獻標(biāo)志碼：A

0 引言（Introduction）

近年來，隨著電梯數(shù)量的迅速增長，電梯維保人員短缺問題愈發(fā)嚴(yán)重，導(dǎo)致電梯安全運行和維保難題日益顯現(xiàn)[1-2]。在當(dāng)前的電梯維保路徑規(guī)劃工作中，維保站點的人員在接到任務(wù)后，需獨立規(guī)劃前往各臺電梯的路線，而在不同電梯間轉(zhuǎn)移的時間消耗較長，因此維保人員每日能完成的電梯維保數(shù)量并不理想。在長期工作中，維保人員工作負荷分布不均，時而空閑時而忙碌，這種情況會導(dǎo)致團隊協(xié)作受阻、績效下滑，進而影響整體工作效果[3]。除此之外，單個維保站點擁有的維保資源只能為有限范圍內(nèi)的電梯提供維保服務(wù)，為了對所有待維保的電梯做好服務(wù)，需要整合多個維保站點的資源。因此，開展各個待維保電梯之間的路徑規(guī)劃及保證各個維保站點之間的協(xié)同工作，具有重要意義。

本文首先剖析了電梯維保路徑問題，并構(gòu)建了一個多目標(biāo)優(yōu)化模型，旨在實現(xiàn)總維保成本最小化、維保人數(shù)最少化，以及員工工作時長標(biāo)準(zhǔn)差最小化。其次針對該模型提出了一種基于非支配排序遺傳算法Ⅱ （Non-dominated Sorting GeneticAlgorithm Ⅱ，NSGA-Ⅱ）的電梯維保路徑規(guī)劃方案;在算法編碼階段采用雙染色體編碼，解決傳統(tǒng)單染色體編碼無法考慮任務(wù)優(yōu)先級和維保任務(wù)歸屬站點的問題，并修改交叉和變異算子，以適應(yīng)雙染色體編碼。最后將分解法[4]、全局法[5]和本文所提方案結(jié)合，使用Solomon標(biāo)準(zhǔn)測試數(shù)據(jù)集和實際案例進行對比驗證，選出合適的方案為電梯維保路徑規(guī)劃提供有益參考。

1 研究現(xiàn)狀（Research status）

目前，一部分學(xué)者圍繞路徑規(guī)劃開展了大量的研究，HANNAN等[6]采用一種改進粒子群算法處理具有容量約束的垃圾回收路徑問題;HUANG 等[7]使用蟻群優(yōu)化算法解決無人機配送服務(wù)的車輛路徑問題。學(xué)者對各類路徑規(guī)劃問題進行了研究，但鮮有針對電梯維保路徑規(guī)劃的研究。BLAKELEY等[8]通過解決周期性車輛調(diào)度問題（PeriodicVehicle Routing Problem， PVRP）創(chuàng)建高效的電梯維保日間路線，但僅考慮了周期性維保任務(wù)，而電梯的維保任務(wù)中不僅包含需要周期進行的預(yù)防性維護，還包括發(fā)生計劃外故障的糾正性維護[9]。

電梯維保路徑規(guī)劃涉及的優(yōu)化目標(biāo)眾多，電梯公司擁有的維保站點眾多，每個維保站點的維保人員人數(shù)有限，各個維保任務(wù)對應(yīng)的優(yōu)先級也各不相同。因此，本文將電梯維保路徑規(guī)劃抽象為一個集合多優(yōu)化目標(biāo)（Multi-Objective VehicleRouting Problem， MOVRP）、多車場調(diào)度（Multi-Depot VehicleRouting Problem， MDVRP）及任務(wù)優(yōu)先級（Vehicle RoutingProblem with Precedence Constraints VRP-PC）的車輛路徑規(guī)劃問題（vehicle routing problem， VRP）。針對上述VRP變體問題，現(xiàn)有研究中多采用啟發(fā)式算法求解，例如粒子群算法（Particle Swarm Optimization，PSO）、模擬退火算法（SimulatedAnnealing Algorithm，SAA）、自適應(yīng)大鄰域搜索算法（AdaptiveLarge Neighborhood Search，ALNS）等，也有不少學(xué)者采用遺傳算法進行求解[10-12]。

以上研究均取得較好的成果，但當(dāng)前的研究往往將多目標(biāo)優(yōu)化、多車場調(diào)度及任務(wù)優(yōu)先級等因素分別進行探討。然而，在電梯維保路徑規(guī)劃中，這些因素需要綜合考量，以實現(xiàn)更高效的規(guī)劃方案。因此，本文以VRP為基礎(chǔ)，綜合考慮多目標(biāo)優(yōu)化、多車場調(diào)度、任務(wù)優(yōu)先級3個因素，旨在解決電梯維保中存在的人員緊缺問題，均衡維保人員的工作時長，并降低公司維保成本。

2 問題描述和模型建立（Problem descriptionand model construction）

電梯涉及的維保任務(wù)眾多，可以大體劃分成3類維保任務(wù)：①電梯機械主要構(gòu)件;②電梯電氣部分的維護檢修任務(wù);③電梯的常規(guī)清潔。定期維護任務(wù)以第1類和第3類維保任務(wù)為主，而電梯電氣部分的故障更具偶發(fā)性。以上3類維保任務(wù)的緊急程度各不相同，其中以電梯機械主要構(gòu)件的維保任務(wù)最為重要，電氣維保次之，常規(guī)性維保緊急程度最低。任務(wù)緊急程度越高，對應(yīng)的維保時間越長，維保人員的工作負擔(dān)也越重，因此在進行維保調(diào)度時，每一位維保人員只能負責(zé)一個緊急程度最高的維保任務(wù)。本文采用優(yōu)先級表達任務(wù)的緊急程度，優(yōu)先級數(shù)字越小，表示緊急程度越高。

2.1 問題描述

電梯維保路徑規(guī)劃問題可描述如下：一家維保公司擁有多個維保站點，當(dāng)天要處理多個維保任務(wù)，但是每個維保站點的維保人員有限。不同的維保任務(wù)對應(yīng)不同的服務(wù)時間和優(yōu)先級;優(yōu)先級數(shù)字小的任務(wù)，需要在優(yōu)先級數(shù)字大的任務(wù)之前執(zhí)行;每位維保人員的工作時長不能超過額定工作時長。維保人員從各自維保站點出發(fā)，依次為待維保電梯提供服務(wù)，在完成維保任務(wù)后，需返回原維保站點。

已知維保站點和維保任務(wù)的位置，維保任務(wù)的服務(wù)時間和優(yōu)先級，以及維保人員的轉(zhuǎn)場速度，在滿足優(yōu)先級和工作時長約束的前提下，求解使總維保成本最低，參與維保人數(shù)最少，以及每位維保人員工作時長差異程度最小的調(diào)度方案。

2.2 數(shù)學(xué)模型

為清楚地表述電梯維保路徑規(guī)劃的數(shù)學(xué)模型，本文定義了相關(guān)符號參數(shù)，具體如表1所示。

公式（3）和公式（4）表示維保人員k 的轉(zhuǎn)場時間和任務(wù)維保時間;公式（5）表示維保人員k 的總工作時長，由轉(zhuǎn)場時間和任務(wù)維保時間構(gòu)成;公式（6）和公式（7）表示本文的優(yōu)化目標(biāo)，其中維保成本由路線成本和人員成本兩個部分組成;公式（8）表示維保人員工作時間不超過額定工作時間;公式（9）和公式（10）表示進出平衡約束;公式（11）表示維保人員從維保站點出發(fā)，最后返回原先的維保站點;公式（12）表示單個維保站點參與維保的人員總數(shù)不超過其擁有的人員總數(shù);公式（13）表示維保人員不能從一個維保站點到另一個維保站點;公式（14）表示每個維保任務(wù)只能由一位維保人員負責(zé);公式（15）表示每位維保人員只能負責(zé)一個優(yōu)先級為1的任務(wù);公式（16）表示優(yōu)先級約束。

3 算法構(gòu)建（Algorithm construction）

在探討電梯維保路徑規(guī)劃問題，尤其是當(dāng)問題涉及多車場車輛路徑問題（MDVRP）時，選擇適當(dāng)?shù)那蠼夥椒ㄖ陵P(guān)重要。目前，針對MDVRP的兩種主流處理方法——分解法和全局法各有優(yōu)劣。為比較這兩種方法哪種更為合適，需要深入分析它們的特點和適用場景。本文將NSGA-Ⅱ和上述兩種方法結(jié)合，對公式（1）至公式（16）描述的多優(yōu)化目標(biāo)問題進行求解。以上兩種方法考慮問題的角度不同，同一種編碼和解碼方式無法滿足兩種方案的需求，因此本研究為分解法和全局法設(shè)計了不同的編碼和解碼方式，并修改遺傳算子以配合新的編碼方式。為了方便決策者做出選擇，引入模糊數(shù)學(xué)法在眾多最優(yōu)解中選取折衷最優(yōu)解作為最終的調(diào)度方案。

3.1 雙染色體編碼、解碼

各種VRP類型解決方案的標(biāo)準(zhǔn)編碼是以一維整數(shù)數(shù)組的形式出現(xiàn)的，即單染色體編碼，但其無法體現(xiàn)任務(wù)優(yōu)先級和任務(wù)的歸屬站點，因此本研究采用雙染色體編碼，該編碼方式可將任務(wù)優(yōu)先級和任務(wù)歸屬站點信息直接體現(xiàn)在編碼中。

3.1.1 全局法編碼

個體由2條染色體構(gòu)成，第1條染色體表示維保任務(wù)編號，第2條染色體表示維保人員編號。假定1家維保公司擁有2個維保站點，當(dāng)天需要處理8個維保任務(wù)，設(shè)置任務(wù)編號為1～8。每個站點有2位維保人員，1號站點的維保人員編號為1和2;2號站點的維保人員編號為3和4。將維保任務(wù)按優(yōu)先級進行劃分，每個優(yōu)先級的任務(wù)集合為Pi，P1 對應(yīng)任務(wù)編號為1和2;P2 對應(yīng)任務(wù)編號為3、4、5;P3 對應(yīng)任務(wù)編號為6、7、8。將任務(wù)按優(yōu)先級數(shù)字從小到大次序分布在第1條染色體中，將維保人員編號分布在第2條染色體中，維保任務(wù)和維保人員編號一一對應(yīng)，而維保人員編號又對應(yīng)不同的維保站點，從而實現(xiàn)維保任務(wù)和維保站點的對應(yīng)，全局法編碼如圖1（a）所示。

3.1.2 全局法解碼

將不同維保人員對應(yīng)的任務(wù)按其在染色體中出現(xiàn)的先后次序排列，從而得到每位維保人員的維保路徑。將每位維保人員的編號和其歸屬的維保站點對應(yīng)，最終得到每個維保站點的路徑規(guī)劃。雙染色體編碼不僅考慮了任務(wù)的歸屬站點信息，而且因其任務(wù)優(yōu)先級排序與維保人員路徑解碼方向一致，確保了每位維保人員的路徑滿足優(yōu)先級約束，從而有效地融合了任務(wù)優(yōu)先級和任務(wù)歸屬站點的考量。采用全局法解碼后的維保路徑如圖1（b）所示。

3.1.3 分解法編碼

分解法在每次規(guī)劃維保路徑時，只需要考慮單個站點對應(yīng)的任務(wù)，因此僅對單個維保站點內(nèi)的維保人員進行編號即可，其余編碼過程與全局法編碼過程一致。假定1號維保站點負責(zé)1、3、6、7號任務(wù);2號維保站點負責(zé)2、4、5、8號任務(wù)。分解法對應(yīng)的分解編碼圖如圖2（a）所示。

3.1.4 分解法解碼

分解法單次只考慮一個維保站點，參與維保作業(yè)的維保人員都屬于該站點，不需要考慮維保人員的歸屬站點劃分問題。因此，將不同維保人員對應(yīng)的任務(wù)按其在染色體中出現(xiàn)的先后次序排列，得到各維保站點的維保路徑。采用分解法解碼后的維保路徑如圖2（b）所示。

3.2 交叉算子和變異算子

由于雙染色體編碼的染色體數(shù)量與傳統(tǒng)編碼不同，因此需要對為傳統(tǒng)編碼設(shè)計的遺傳算子進行相應(yīng)的調(diào)整。本文的交叉算子采用部分匹配交叉，該算子可以有效地避免基因重復(fù)及保留親代的優(yōu)秀特征。變異算子采用隨機變異和互換變異兩類。圖3表示修改后的交叉、變異算子示意圖。圖3（a）表示部分匹配交叉，其適用范圍包括任務(wù)和維保人員，執(zhí)行交叉后為防止個別基因出現(xiàn)重復(fù)的情況，在交叉區(qū)域內(nèi)建立每個染色體的匹配關(guān)系，在交叉區(qū)域外對重復(fù)基因應(yīng)用此匹配關(guān)系以消除沖突;圖3（b）表示互換變異算子，其適用于任務(wù)和維保人員，隨機選中兩對任務(wù)和對應(yīng)的維保人員，置換選中的任務(wù)和維保人員的位置;圖3（c）表示隨機變異算子，其適用范圍僅為維保人員，將選中的人員進行隨機替換。

4 數(shù)值算例（Numerical example）

本文選取Solomon測試集中的C201、R201、RC201三種不同分布類型的算例，對提出的電梯維保路徑規(guī)劃模型和方案進行驗證，由于Solomon測試集無法直接應(yīng)用于電梯維保路徑規(guī)劃問題，因此對其做出如下修改。

以位置坐標(biāo)點（30，60）、（40，20）及（75，50）為維保站點，在每個算例中設(shè)立16個優(yōu)先級為1的維保任務(wù)，32個優(yōu)先級為2的維保任務(wù)，52個優(yōu)先級為3的維保任務(wù)。為了對比分解法和全局法在電梯維保路徑規(guī)劃中的效果，將NSGA-Ⅱ分別與分解法、全局法結(jié)合，組成2種不同的方案對不同算例進行求解。假定每位維保人員的調(diào)度費用為100元/位，單位出行費用為10元/千米，轉(zhuǎn)場速度為70 km/h;算法一共進化1 000代;算法對應(yīng)的交叉概率為0.7，變異概率為0.3。

表2記錄兩種方案對應(yīng)的折衷最優(yōu)解，從中可知分解法和全局法在標(biāo)準(zhǔn)差的表現(xiàn)上相近，均能保障員工工作時長均衡，并且分解法在C201和R201算例上優(yōu)于全局法;在總成本方面，分解法均優(yōu)于全局法。通過折衷最優(yōu)解無法直觀地看出兩種方案解集的優(yōu)劣，為此繪制各方案的Pareto前沿對比圖。

圖4（a）至圖4（c）表示分解法和全局法在C201、R201、RC201算例中的Pareto前沿對比圖。由Pareto前沿對比圖可知，分解法表現(xiàn)最優(yōu)，說明在迭代次數(shù)相同的情況下，分解法更具優(yōu)勢。該結(jié)果與各方案在折衷最優(yōu)解中的表現(xiàn)相吻合，證實了以折衷最優(yōu)解作為決策者選擇的可行性。

為驗證算法的實際應(yīng)用效果，選取某公司某時刻的維保任務(wù)，對提出的模型和方案進行驗證。任務(wù)分布情況如圖5（a）所示，一共有50個任務(wù)點，由3個維保站點完成;有3種任務(wù)優(yōu)先級類型，分別為8個優(yōu)先級為1的維保任務(wù)，16個優(yōu)先級為2的維保任務(wù)，26個優(yōu)先級為3的維保任務(wù)。在保留其他參數(shù)不變的情況下，由于各維保電梯之間距離較近，因此將轉(zhuǎn)場速度修改為40 km/h。表3記錄兩種方案的折衷最優(yōu)解在總成本、標(biāo)準(zhǔn)差和參與人數(shù)方面的表現(xiàn);圖4（d）記錄兩種方案對應(yīng)的Pareto前沿。

分析表3可知，相較于全局法，分解法在成本上節(jié)約了17.3%，在員工工作時長標(biāo)準(zhǔn)差上減少49.7%，在人力資源上節(jié)約了26.6%;結(jié)合圖4（d）所示的Pareto前沿對比圖可知，分解法結(jié)合NSGA-Ⅱ方案得到的解更優(yōu)秀，說明在迭代次數(shù)相同的情況下，采用分解法更適用于電梯維保路徑規(guī)劃問題。

圖5（b）至圖5（d）表示3個維保站點的維保路徑圖，維保人員從維保站點出發(fā)，首先對優(yōu)先級為1的任務(wù)提供服務(wù)，其次對優(yōu)先級為2和3的任務(wù)提供服務(wù)，并且每條路徑中只存在一個優(yōu)先級為1的任務(wù)，滿足優(yōu)先級約束條件。上述結(jié)果表明，本文所提方案可為電梯維保路徑規(guī)劃提供有益參考。

5 結(jié)論（Conclusion）

本文研究電梯維保路徑規(guī)劃任務(wù)，以總維修成本最低、維保人數(shù)最少及均衡員工工作負載為優(yōu)化目標(biāo)，求解電梯維保路徑規(guī)劃問題。首先，建立多目標(biāo)優(yōu)化模型，并考慮任務(wù)優(yōu)先級和多維保站的調(diào)度問題，其次，利用NSGA-Ⅱ?qū)?gòu)建的多目標(biāo)優(yōu)化模型進行求解，最后，通過Solomon算例和實例得到以下結(jié)論。

（1）雙染色體編碼解決了單染色體編碼未考慮任務(wù)優(yōu)先級和維保任務(wù)歸屬站點的問題，可以應(yīng)用于電梯維保路線調(diào)度問題。

（2）應(yīng)用NSGA-Ⅱ算法，實現(xiàn)了多維保站點的維保路徑規(guī)劃，通過Solomon測試集和實例驗證發(fā)現(xiàn)，在迭代次數(shù)相同的基礎(chǔ)上，分解法優(yōu)于全局法。在實例上的表現(xiàn)如下：采用分解法在成本上節(jié)約了17.3%，在員工工作時長標(biāo)準(zhǔn)差上減少了49.7%，在人力資源上節(jié)約了26.6%。因此，針對電梯維保路線調(diào)度問題，采用分解法更合適。

本文所提方法為電梯維保路徑規(guī)劃提供了一種可行的調(diào)度辦法。

作者簡介：

魏義敏（1986-），男，博士，副教授。研究領(lǐng)域：彈性波，故障診斷，路徑規(guī)劃。

豐煒（1996-），男，碩士生。研究領(lǐng)域：電梯維保路徑規(guī)劃。