基于混合果蠅優(yōu)化算法的現場服務調度問題

吳 斌，王 超，董 敏

(南京工業(yè)大學 經濟與管理學院，南京 211816)

0 引言

現場服務通常指在顧客指定的地理位置，滿足顧客需求而進行的一系列活動?，F場服務廣泛存在于各個行業(yè)，如電力、通信系統(tǒng)的維護保障，家電、家具行業(yè)的售后安裝維修、醫(yī)療健康領域的家庭看護，制造企業(yè)的維護、維修、運行設備(Maintenance, Repair & Operations, MRO)服務等。據統(tǒng)計，僅上海市2010年的家電行業(yè)服務產值已達20億元。2014全球航空企業(yè)的MRO的服務產值超過50億美元。隨著大數據、移動互聯(lián)網等信息技術的發(fā)展，線上到線下(Online To Offline, O2O)等商業(yè)模式的興起，顧客的個性化需求和定制化服務需求的日益增多，現場服務的作用愈發(fā)重要?，F場服務的效率和質量與服務人員的合理配置及線路規(guī)劃密切相關[1]。不合理的任務及線路安排，容易出現員工在途時間長、顧客等待時間長、員工技能與任務不匹配等問題，從而影響服務質量和服務效率，進而影響顧客的滿意度，最終導致企業(yè)利潤的下降，因此，現場服務調度問題至關重要。

現場服務調度是一個新興的研究課題，國內外相關的文獻較少。Lesaint等[2]針對英國電訊公司通信網絡維護中員工的任務與線路安排問題，首次提出了現場服務調度的概念；但他們并沒有給出問題的模型和求解算法。Xu等[3]考慮服務任務的類型、優(yōu)先級以及顧客時間窗等約束條件，以服務任務數量最大、員工工作時間最短為優(yōu)化目標，建立了現場服務調度的模型，提出自適應貪婪隨機搜索算法進行優(yōu)化求解。在此基礎上，Akjiratikarl等[4]將員工的旅行距離最短作為優(yōu)化目標進行研究，提出粒子群算法進行優(yōu)化求解。Goel等[5]以電網停工時間和人員旅行時間最短為優(yōu)化目標，研究了電網維修人員的現場服務調度問題，提出了爬山法、大鄰域搜索等多種優(yōu)化算法。江俊杰等[6]除了將員工的旅行時間和等待時間作為優(yōu)化目標外，還將客戶滿意度作為優(yōu)化目標，提出了基于分段染色體編碼的遺傳算法(Genetic Algorithm, GA)。Xu等[7]強調了員工的綜合技能和團隊合作等約束條件，提出了改進的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)。Borenstein等[8]采用分區(qū)的方法，研究了英格蘭電信的動態(tài)現場服務調度問題，提出基于規(guī)則的算法進行優(yōu)化求解。Kovacs等[9]研究了需要團隊合作的現場服務調度問題，同時考慮對不能完成的任務采用外包，將旅行線路和外包費用作為優(yōu)化目標，提出自適應大鄰域搜索算法進行優(yōu)化求解。Damm等[10]基于文獻[3]的模型，以最大化完成任務的優(yōu)先級為主要優(yōu)化目標，提出偏置隨機關鍵遺傳算法(Biased Random Key Genetic Algorithm)進行優(yōu)化求解。Pillac等[11]分析了現場服務調度問題(Field Service Scheduling Problem, FSSP)與帶時間窗車輛路徑問題(Vehicle Routing Problem with Time Windows, VRPTW)的區(qū)別，提出并行自適應大鄰域搜索算法優(yōu)化求解該問題。此外，Cortes等[12]采用分支定價算法(branch-and-price)求解了一個實際公司維修數碼設備的現場服務調度問題。Tang等[13]、曹永榮等[14]以M/G/m排隊模型為基礎，通過仿真的方法研究了現場服務調度問題。

目前關于現場服務調度問題的求解算法多基于經典算法，如遺傳算法等，缺少對新型算法的挖掘和優(yōu)選。果蠅優(yōu)化算法(Fruit fly Optimization Algorithm, FOA)是一種新型的群智能優(yōu)化算法，具有算法簡單、參數少、收斂速度快等優(yōu)點，已經在函數優(yōu)化[15]、神經網絡[16]、背包問題[17]、車間調度問題[18]等領域成功應用，但還未在現場服務調度問題中應用。本文基于果蠅優(yōu)化算法，提出求解現場服務調度問題的算法框架，設計了編碼方法和優(yōu)化算子，為現場服務調度問題的求解提供了新思路，既豐富了現場服務調度的求解算法，又擴展了果蠅優(yōu)化算法的應用領域。

1 現場服務調度問題的模型

現場服務調度問題可以描述如下：將n個分散在不同地點的客戶服務任務分配給m個工人。每個服務任務有時間窗和工人的技能要求。工人從不同的地點出發(fā)，巡回服務，結束后返回各自地點；每個工人掌握的技能不同，需要和服務任務匹配。該問題的優(yōu)化目標是工人的旅行時間、任務的完成時間和工人的等待時間最短。建立的混合整數規(guī)劃模型如下。

對于一個網絡G={V,E},其中集合V={D,C}，包含工人集合D={0,1,…,m-1}和任務集合C={0,1,…,n-1}。E={(i,j)},i,j∈V表示連接結合，cij表示i到j的旅行時間，且cij=cji。di表示任務i的標準服務時間，λki∈(0,M]表示工人k服務任務i的熟練程度，λki越小表示熟練程度越高，完成時間越短；λki>M則表示無法完成該任務。[Ei,Li]表示任務i的時間窗；ti表示任務i開始服務的時間；wi(ti)表示工人在任務i的等待時間。xijk=1,i,j∈V,k∈D表示工人k從節(jié)點i到j；否則xijk=0。yik=1,i∈C,k∈D表示任務i被工人k服務；否則yik=0。

(1)

(2)

(3)

(4)

tj=max{Ej,ti+λkidi+cij}

(5)

tj

(6)

wj(tj)=max{0,Ej-tj}

(7)

式(1)表示目標函數，由三部分組成：第1部分是旅行時間，第2部分是任務的完成時間，第3部分是工人的等待時間，通過加權使三者之和最小。約束式(2)保證每個任務點僅被1個工人服務。約束式(3)保證每個任務僅被服務1次，且工人進入節(jié)點并從該節(jié)點離開。約束式(4)表示工人需從自己的出發(fā)地出發(fā)。約束式(5)和(6)表示時間窗的約束，約束式(7)表示等待時間的計算。

2 基本果蠅優(yōu)化算法

果蠅優(yōu)化算法(FOA)是一種基于果蠅覓食行為的群智能優(yōu)化算法[19]。果蠅有很好的嗅覺和視覺器官，能夠依靠嗅覺感覺到40 km外的食物源，然后在鄰近食物源時，依靠敏銳的視覺發(fā)現食物的具體位置。果蠅算法模擬該過程，基于嗅覺和視覺行為進行迭代搜索，通過對果蠅種群位置中心的優(yōu)化，最終獲得問題的優(yōu)化解。果蠅算法的基本流程如下。

步驟1 初始化種群中個體的位置。

步驟2 嗅覺搜索。由個體的當前位置隨機選擇方向和位置進行搜索。

步驟3 個體評價。對個體搜索到的新位置，計算其味道濃度。

步驟4 視覺搜索。選擇味道濃度最大的位置，個體根據視覺向該位置搜索。

步驟5 判斷算法是否結束：是，則輸出最優(yōu)解；否，則轉步驟2進行迭代。

3 混合果蠅優(yōu)化算法求解現場服務調度問題

基本的果蠅算法主要用于函數優(yōu)化，將其應用于現場服務調度問題，需要在編碼方法、初始化方法、嗅覺搜索和視覺搜索等方面進行改進。

3.1 編碼方法

現場服務調度問題是組合優(yōu)化問題，果蠅優(yōu)化算法在求解這類問題時，如何進行編碼是關鍵。本文提出一種基于矩陣的編碼方式表示現場服務調度的解，這種編碼方法可以將任務分配與工人旅行線路同時表達出來，方便果蠅優(yōu)化算子的設計。其編碼方式如下：

(8)

步驟1j=0。

步驟2 選擇第行所有的非0元素組成的向量(ajl,ajm,…,aji)，則其對應的任務為(l,m,…,i)。

步驟3 將(ajl,ajm,…,aji)中的元素從小到大排序，得到(l,m,…,i)的任務排序，依次將客戶分配給工人，同時判斷是否滿足時間窗限制；如果不滿足，則將任務分配給距離最近或開始時間最早的工人。

步驟4 如果j=m-1，則結束程序；否則j=j+1轉步驟2。

例1 以3個工人、6個任務的現場服務系統(tǒng)為例，其編碼形式如下所示：

根據解碼算法，1號員工分配的任務是(2，4)，2號員工分配的任務是(1，5)。3號工人分配的任務是(3，6)。再根據客戶對應元素按照從小到大排序，同時考慮時間窗限制，得到員工的旅行線路是：1號的巡回線路是2—4；2號的巡回線路是5—1；3號的巡回線路是3—6。

3.2 種群初始化

隨機初始化的方法雖然簡單，但會產生一些非法解，影響求解質量。采用啟發(fā)式初始化的方法，可以在初始階段產生有效解，提高優(yōu)化的質量。本文基于最鄰近啟發(fā)式算法進行種群的初始化。該算法是求解旅行商問題(Traveling Salesman Problem, TSP)、車輛路徑問題(Vehicle Routing Problem, VRP)等的經典算法，其核心思想是在滿足一定的約束條件下，在未訪問的任務列表中逐步尋找與當前線路中距離最近的任務，然后將其插入線路中。本文由于實際窗的存在，在已經存在的線路中插入客戶任務，需要考慮兩方面的因素：第一，能力約束，即工人是否能完成該任務；第二，時間是否可行，即插入某一任務后，插入的任務和插入位置以后的任務的時間窗是否滿足要求。對于第二種因素，如果插入一個客戶，是否要依次檢查其后的所有客戶是否可行？對此問題，依據作者針對帶取送貨車輛路徑問題(Vehicle Routing Problem with Pickups and Deliveries, VRPPD)提出的可行性插入定理[20]，可以得到如下結論。

定理1 對于第f個工人已建立的可行線路i1,i2,…,ip，若在其第k個位置之后插入(ik和ik+1)之間插入一個任務h時，插入可行的充分必要條件是：

th

(9)

λfh≤M

(10)

其中：th表示到達任務h的時間；Lh表示任務h最晚允許達到的時間；Δt表示插入h后，車輛到達任務ik+1的時間比原來的推遲量；M表示預設的一個熟練程度值，在本文M=2，即當工人完成某項工作的時間大于標準時間的2倍時，認為工人不能勝任該任務，則該客戶不能分配給此工人。

在本文，鄰近任務的選擇需要考慮工人的等待時間、任務間的行駛時間等因素。設i表示當前線路中的最后一個任務，j表示未訪問的任務，cij表示i與j之間的行駛時間，ti表示在任務i處開始服務的時間，wj(tj)表示工人在任務j的等候時間。tj和wj(tj)由式(5)和(7)計算得到。Nij表示任務i與j之間的廣義費用，則選擇最鄰近任務的廣義費用可定義如下：

Nij=α1×cij+α2×wj(tj)

(11)

其中α1,α2為系數，且滿足α1+α2=1。通過計算未訪問任務的值，選出最小值對應的任務插入線路中。最鄰近插入算法的過程如下。

U表示任務集合，Rk表示第k條線路的集合，CLk表示第k條線路的旅行時間，Vj表示工人j的客戶集合。

步驟1 設置U=C,k=0,Rk=?,CLk=0，j=0。

步驟2 判斷任務集合U是否為空，如果是則轉步驟5。如果不是，則從U中選擇開始服務時間最早的任務i，如果其時間窗Li

并把任務i從集合中刪除。

步驟3 根據插入可行性定理1，從集合U中選擇未服務的可行任務。根據式(11)計算這些任務的插入值Nij，選擇最小的插入線路，更新CLk和集合U。重復上述過程，直至沒有可行客戶為止。

步驟4 計算Rk中任務的重心，選擇距離該重心最近的員工j，將Rk的元素插入Vj中。k=k+1，CLk=0，轉步驟2。

步驟5 將構造的初始解映射為果蠅優(yōu)化算法的編碼。

3.3 果蠅搜索策略

由于采用矩陣的編碼方式，現有果蠅算法的狀態(tài)更新方程不再適用。本文根據現場服務問題的特征，基于群智能理論和社會心理學原理，提出以下3種果蠅搜索策略。首先本文定義以兩種矩陣操作：posSwap(m,k)和valueSwap(m,k)。

1)posSwap(m,k)表示將矩陣A的第m行(或列)與第k行(或列)的元素互換，同時對于所有非零元素進行如下計算：

(12)

2)valueSwap(m,k)表示將矩陣A中第k列的第m行元素進行重新賦值。執(zhí)行該操作時，首先根據式(13)計算amk，然后將該列除此元素之外的所有元素置0，以保證解的合法性，即每個任務只能分配給一個工人：

(13)

3種果蠅搜索策略分別定義如下：

Move1m∈D,k∈D,posSwap(m,k)。表示兩個工人之間互換所有任務，同時任務的服務順序可能發(fā)生改變。

Move2m∈C,k∈C,posSwap(m,k)。表示將任務和互換，該操作可以使任務在工人之間交換，同時也可以改變任務在工人中的訪問順序。

Move3m∈C,k∈D,valueSwap(m,k)。表示將任務k分配給工人m，該操作可以改變任務的分配，同時改變任務在工人中的訪問順序。

在果蠅算法中：由于果蠅的嗅覺靈敏，可以在大范圍內搜索，因此嗅覺搜索主要負責解空間的開發(fā)探索(exploitation)，它的搜索范圍比較大；當距離事物源較近時，則轉為視覺搜索，視覺搜索主要負責解空間的精細搜索(exploration)。根據上述原理，本文所提算法在嗅覺搜索中，依次執(zhí)行Move1、Move2和Move3搜索，根據最好接受(Best Acceptance)策略，選擇搜索到的最好位置信息更新當前果蠅的狀態(tài)；在視覺搜索過程中，僅執(zhí)行Move2和Move3搜索，根據更好接受策略(Better Acceptance)，當搜索到比當前果蠅狀態(tài)更好的位置時，即進行更新。嗅覺搜索和視覺搜索的過程如圖1所示。

圖1 FOA的搜索過程

3.4 后優(yōu)化過程

在執(zhí)行完果蠅優(yōu)化算法的搜索過程后，為了提高優(yōu)化質量，使用局部搜索算法對每個解進行改進，此處主要采用兩種改進算法：2-Opt和OR-Opt。后優(yōu)化過程采用更好接受策略，當搜索到比當前解更好的解時，對果蠅的狀態(tài)進行更新?；旌瞎墐?yōu)化算法的流程如圖2所示。

4 實驗仿真

目前現場服務調度問題沒有測試實例庫，本文基于帶時間窗的多倉庫車輛路徑問題(Multi-Depot Vehicle Routing Problem with Times Windows, MDVRPTW)的實例庫[21]，構建現場服務調度問題的實驗數據。原有數據的坐標、時間窗、操作時間等信息不變，忽略其中的客戶需求量等信息。工人數量設定為與原實例中車輛數量相等，在將原有的倉庫位置設定為現場服務調度中工人位置的同時，還需要將一些客戶位置設定為工人位置。此外，對于每個實例還需要生成一個工人操作任務熟練度的矩陣，此矩陣隨機生成。其中：λki的取值范圍是[0.5,3]，λki越小表示完成任務所需要的時間越短，操作越熟練，λki>2表示工人無法完成此任務。

圖2 混合果蠅優(yōu)化算法求解現場服務調度問題的流程

對于實例中的PR01問題，原問題表示有4個倉庫、48個客戶、每個倉庫有2輛車的問題，在轉換成現場服務調度問題時，則是有8個工人、44個客戶的問題，其中4個工人的地址是原倉庫地址，其余4個工人地址是從原48個客戶中隨機選擇4個設定的。根據此方法，選擇10組實例進行測試，問題規(guī)模如表1所示。

表1 仿真實例描述

混合果蠅優(yōu)化算法用C++語言實現，運行在酷睿i5 2.5 GHz，4 GB內存的計算機平臺上。果蠅算法的種群規(guī)模P=100，迭代次數NC=1 000，目標函數的系數α=0.4，β=0.3，γ=0.3。針對每個實例，算法隨機運行20次，對其結果進行統(tǒng)計分析。首先對本文提出的初始化方法進行分析比較，最鄰近法的初始化參數α1=0.6，α2=0.4，將最鄰近算法和隨機初始化進行對比。針對PR01和PR02進行測試，優(yōu)化結果的均值和方差如圖3所示。

圖3 果蠅優(yōu)化算法初始化方法的比較

從圖3中可以看出，最鄰近法比隨機方法的均值有明顯降低(對于PR01問題，與隨機方法相比，最鄰近法均值了減小7%；對于PR02，減小6.9%)，并且算法的偏差更小，表明最近鄰算法能使果蠅算法更加穩(wěn)定。

下面對3種局部搜索算子的搜索能力進行比較。依然以PR01和PR02為例，分別單獨執(zhí)行Move1、Move2和Move3三種搜索策略，算法的進化曲線如圖4所示。從圖4中可以看出，在算法初期(200代以內)，3種搜索策略的效率相差不大，都能很快地搜索到比較好的結果；但在迭代后期，Move1算法比較早地進入停滯期，無法跳出局部極值點。這是因為Move1主要將客戶在工人之間交換，搜索得比較粗糙。Move2算子在3種搜索策略中優(yōu)化能力最強，這主要因為Move2操作在進行任務交換的同時，不僅改變了任務在工人間的分配，同時還改變了任務的訪問順序，是一個集成了線路內和線路間的2-Opt算子。Move3類似于一個插入算子，搜索能力比Move1強，但比Move2弱。

圖4 3種搜索算子的比較

對于嗅覺搜索和視覺搜索的搜索能力，本文也通過PR01和PR02兩個問題進行了驗證，結果如圖5所示。

圖5 搜索策略的比較

從圖5可以看出，僅執(zhí)行視覺搜索的結果最差，嗅覺和視覺都執(zhí)行的混合策略優(yōu)化結果最好。因為視覺搜索主要是由鄰域信息引導的局部搜索，采用更優(yōu)接受(better acceptance)策略。而嗅覺搜索是全局信息引導的搜索，并且3種搜索算子都執(zhí)行，采用最優(yōu)接受策略，因此，嗅覺搜索的優(yōu)化能力更強，當把兩種搜索策略混合，視覺的局部搜索能改進嗅覺搜索的優(yōu)化結果。

圖6顯示了后優(yōu)化過程對算法的影響。與沒有使用后優(yōu)化的算法相比，使用后優(yōu)化過程(兩種算子都用)可以將優(yōu)化的均值提高5%左右(PR01提高4.91%，PR02提高4.45%)。單獨使用一種后優(yōu)化算法子，OR-Opt比2-Opt稍有優(yōu)勢。

圖6 后優(yōu)化過程的比較

最后，將本文提出的混合果蠅優(yōu)化算法與Xu等[3]提出的貪婪隨機自適應搜索過程(Greedy Randomized Adaptive Search Procedure, GRASP)算法和江俊杰等[6]提出的遺傳算法進行了比較，結果如表2所示。從表2中數據可以看出，對于10個問題，混合優(yōu)化果蠅算法在均值和最優(yōu)值方面都優(yōu)于GRASP算法和遺傳算法，GRASP算法又比遺傳算法的優(yōu)化結果好。

表2 3種算法的均值與最優(yōu)值比較

5 結語

隨著互聯(lián)網經濟的發(fā)展，客戶的個性化服務需求日益凸顯?，F場服務進入飛速發(fā)展階段，為了提高服務質量和效率，現場服務調度至關重要。本文建立了現場服務調度問題的數學模型，分析了問題解的性質(插入可行性)。鑒于問題的復雜性，提出了混合果蠅優(yōu)化算法進行求解。設計了基于矩陣的實數編碼方案，基于群智能理論和社會心理學原理，定義了兩類矩陣操作算子，設計了3種搜索策略，進而重構了果蠅優(yōu)化算法的嗅覺搜索和視覺搜索過程。為了提高算法的性能，構建了基于最鄰近插入啟發(fā)式算法的初始化方法，并引入后優(yōu)化過程。通過實驗仿真，分析比較了各算子的優(yōu)化效果，并與其他算法進行了比較。結果表明，本文所提算法是求解現場服務調度問題的有效方法。