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

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

0 引言（Introduction）

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

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

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

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

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

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

3.1 雙染色體編碼、解碼

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

3.1.1 全局法編碼

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

3.1.2 全局法解碼

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

3.1.3 分解法編碼

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

3.1.4 分解法解碼

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

3.2 交叉算子和變異算子

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

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

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

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

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

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

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

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

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

5 結(jié)論（Conclusion）

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

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

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

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

作者簡(jiǎn)介：

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

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