吳 斌,王 超,董 敏
(南京工業(yè)大學(xué) 經(jīng)濟與管理學(xué)院,南京 211816)
現(xiàn)場服務(wù)通常指在顧客指定的地理位置,滿足顧客需求而進行的一系列活動。現(xiàn)場服務(wù)廣泛存在于各個行業(yè),如電力、通信系統(tǒng)的維護保障,家電、家具行業(yè)的售后安裝維修、醫(yī)療健康領(lǐng)域的家庭看護,制造企業(yè)的維護、維修、運行設(shè)備(Maintenance, Repair & Operations, MRO)服務(wù)等。據(jù)統(tǒng)計,僅上海市2010年的家電行業(yè)服務(wù)產(chǎn)值已達20億元。2014全球航空企業(yè)的MRO的服務(wù)產(chǎn)值超過50億美元。隨著大數(shù)據(jù)、移動互聯(lián)網(wǎng)等信息技術(shù)的發(fā)展,線上到線下(Online To Offline, O2O)等商業(yè)模式的興起,顧客的個性化需求和定制化服務(wù)需求的日益增多,現(xiàn)場服務(wù)的作用愈發(fā)重要?,F(xiàn)場服務(wù)的效率和質(zhì)量與服務(wù)人員的合理配置及線路規(guī)劃密切相關(guān)[1]。不合理的任務(wù)及線路安排,容易出現(xiàn)員工在途時間長、顧客等待時間長、員工技能與任務(wù)不匹配等問題,從而影響服務(wù)質(zhì)量和服務(wù)效率,進而影響顧客的滿意度,最終導(dǎo)致企業(yè)利潤的下降,因此,現(xiàn)場服務(wù)調(diào)度問題至關(guān)重要。
現(xiàn)場服務(wù)調(diào)度是一個新興的研究課題,國內(nèi)外相關(guān)的文獻較少。Lesaint等[2]針對英國電訊公司通信網(wǎng)絡(luò)維護中員工的任務(wù)與線路安排問題,首次提出了現(xiàn)場服務(wù)調(diào)度的概念;但他們并沒有給出問題的模型和求解算法。Xu等[3]考慮服務(wù)任務(wù)的類型、優(yōu)先級以及顧客時間窗等約束條件,以服務(wù)任務(wù)數(shù)量最大、員工工作時間最短為優(yōu)化目標(biāo),建立了現(xiàn)場服務(wù)調(diào)度的模型,提出自適應(yīng)貪婪隨機搜索算法進行優(yōu)化求解。在此基礎(chǔ)上,Akjiratikarl等[4]將員工的旅行距離最短作為優(yōu)化目標(biāo)進行研究,提出粒子群算法進行優(yōu)化求解。Goel等[5]以電網(wǎng)停工時間和人員旅行時間最短為優(yōu)化目標(biāo),研究了電網(wǎng)維修人員的現(xiàn)場服務(wù)調(diào)度問題,提出了爬山法、大鄰域搜索等多種優(yōu)化算法。江俊杰等[6]除了將員工的旅行時間和等待時間作為優(yōu)化目標(biāo)外,還將客戶滿意度作為優(yōu)化目標(biāo),提出了基于分段染色體編碼的遺傳算法(Genetic Algorithm, GA)。Xu等[7]強調(diào)了員工的綜合技能和團隊合作等約束條件,提出了改進的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)。Borenstein等[8]采用分區(qū)的方法,研究了英格蘭電信的動態(tài)現(xiàn)場服務(wù)調(diào)度問題,提出基于規(guī)則的算法進行優(yōu)化求解。Kovacs等[9]研究了需要團隊合作的現(xiàn)場服務(wù)調(diào)度問題,同時考慮對不能完成的任務(wù)采用外包,將旅行線路和外包費用作為優(yōu)化目標(biāo),提出自適應(yīng)大鄰域搜索算法進行優(yōu)化求解。Damm等[10]基于文獻[3]的模型,以最大化完成任務(wù)的優(yōu)先級為主要優(yōu)化目標(biāo),提出偏置隨機關(guān)鍵遺傳算法(Biased Random Key Genetic Algorithm)進行優(yōu)化求解。Pillac等[11]分析了現(xiàn)場服務(wù)調(diào)度問題(Field Service Scheduling Problem, FSSP)與帶時間窗車輛路徑問題(Vehicle Routing Problem with Time Windows, VRPTW)的區(qū)別,提出并行自適應(yīng)大鄰域搜索算法優(yōu)化求解該問題。此外,Cortes等[12]采用分支定價算法(branch-and-price)求解了一個實際公司維修數(shù)碼設(shè)備的現(xiàn)場服務(wù)調(diào)度問題。Tang等[13]、曹永榮等[14]以M/G/m排隊模型為基礎(chǔ),通過仿真的方法研究了現(xiàn)場服務(wù)調(diào)度問題。
目前關(guān)于現(xiàn)場服務(wù)調(diào)度問題的求解算法多基于經(jīng)典算法,如遺傳算法等,缺少對新型算法的挖掘和優(yōu)選。果蠅優(yōu)化算法(Fruit fly Optimization Algorithm, FOA)是一種新型的群智能優(yōu)化算法,具有算法簡單、參數(shù)少、收斂速度快等優(yōu)點,已經(jīng)在函數(shù)優(yōu)化[15]、神經(jīng)網(wǎng)絡(luò)[16]、背包問題[17]、車間調(diào)度問題[18]等領(lǐng)域成功應(yīng)用,但還未在現(xiàn)場服務(wù)調(diào)度問題中應(yīng)用。本文基于果蠅優(yōu)化算法,提出求解現(xiàn)場服務(wù)調(diào)度問題的算法框架,設(shè)計了編碼方法和優(yōu)化算子,為現(xiàn)場服務(wù)調(diào)度問題的求解提供了新思路,既豐富了現(xiàn)場服務(wù)調(diào)度的求解算法,又?jǐn)U展了果蠅優(yōu)化算法的應(yīng)用領(lǐng)域。
現(xiàn)場服務(wù)調(diào)度問題可以描述如下:將n個分散在不同地點的客戶服務(wù)任務(wù)分配給m個工人。每個服務(wù)任務(wù)有時間窗和工人的技能要求。工人從不同的地點出發(fā),巡回服務(wù),結(jié)束后返回各自地點;每個工人掌握的技能不同,需要和服務(wù)任務(wù)匹配。該問題的優(yōu)化目標(biāo)是工人的旅行時間、任務(wù)的完成時間和工人的等待時間最短。建立的混合整數(shù)規(guī)劃模型如下。
對于一個網(wǎng)絡(luò)G={V,E},其中集合V={D,C},包含工人集合D={0,1,…,m-1}和任務(wù)集合C={0,1,…,n-1}。E={(i,j)},i,j∈V表示連接結(jié)合,cij表示i到j(luò)的旅行時間,且cij=cji。di表示任務(wù)i的標(biāo)準(zhǔn)服務(wù)時間,λki∈(0,M]表示工人k服務(wù)任務(wù)i的熟練程度,λki越小表示熟練程度越高,完成時間越短;λki>M則表示無法完成該任務(wù)。[Ei,Li]表示任務(wù)i的時間窗;ti表示任務(wù)i開始服務(wù)的時間;wi(ti)表示工人在任務(wù)i的等待時間。xijk=1,i,j∈V,k∈D表示工人k從節(jié)點i到j(luò);否則xijk=0。yik=1,i∈C,k∈D表示任務(wù)i被工人k服務(wù);否則yik=0。
(1)
(2)
(3)
(4)
tj=max{Ej,ti+λkidi+cij}
(5)
tj (6) wj(tj)=max{0,Ej-tj} (7) 式(1)表示目標(biāo)函數(shù),由三部分組成:第1部分是旅行時間,第2部分是任務(wù)的完成時間,第3部分是工人的等待時間,通過加權(quán)使三者之和最小。約束式(2)保證每個任務(wù)點僅被1個工人服務(wù)。約束式(3)保證每個任務(wù)僅被服務(wù)1次,且工人進入節(jié)點并從該節(jié)點離開。約束式(4)表示工人需從自己的出發(fā)地出發(fā)。約束式(5)和(6)表示時間窗的約束,約束式(7)表示等待時間的計算。 果蠅優(yōu)化算法(FOA)是一種基于果蠅覓食行為的群智能優(yōu)化算法[19]。果蠅有很好的嗅覺和視覺器官,能夠依靠嗅覺感覺到40 km外的食物源,然后在鄰近食物源時,依靠敏銳的視覺發(fā)現(xiàn)食物的具體位置。果蠅算法模擬該過程,基于嗅覺和視覺行為進行迭代搜索,通過對果蠅種群位置中心的優(yōu)化,最終獲得問題的優(yōu)化解。果蠅算法的基本流程如下。 步驟1 初始化種群中個體的位置。 步驟2 嗅覺搜索。由個體的當(dāng)前位置隨機選擇方向和位置進行搜索。 步驟3 個體評價。對個體搜索到的新位置,計算其味道濃度。 步驟4 視覺搜索。選擇味道濃度最大的位置,個體根據(jù)視覺向該位置搜索。 步驟5 判斷算法是否結(jié)束:是,則輸出最優(yōu)解;否,則轉(zhuǎn)步驟2進行迭代。 基本的果蠅算法主要用于函數(shù)優(yōu)化,將其應(yīng)用于現(xiàn)場服務(wù)調(diào)度問題,需要在編碼方法、初始化方法、嗅覺搜索和視覺搜索等方面進行改進。 現(xiàn)場服務(wù)調(diào)度問題是組合優(yōu)化問題,果蠅優(yōu)化算法在求解這類問題時,如何進行編碼是關(guān)鍵。本文提出一種基于矩陣的編碼方式表示現(xiàn)場服務(wù)調(diào)度的解,這種編碼方法可以將任務(wù)分配與工人旅行線路同時表達出來,方便果蠅優(yōu)化算子的設(shè)計。其編碼方式如下: (8) 步驟1j=0。 步驟2 選擇第行所有的非0元素組成的向量(ajl,ajm,…,aji),則其對應(yīng)的任務(wù)為(l,m,…,i)。 步驟3 將(ajl,ajm,…,aji)中的元素從小到大排序,得到(l,m,…,i)的任務(wù)排序,依次將客戶分配給工人,同時判斷是否滿足時間窗限制;如果不滿足,則將任務(wù)分配給距離最近或開始時間最早的工人。 步驟4 如果j=m-1,則結(jié)束程序;否則j=j+1轉(zhuǎn)步驟2。 例1 以3個工人、6個任務(wù)的現(xiàn)場服務(wù)系統(tǒng)為例,其編碼形式如下所示: 根據(jù)解碼算法,1號員工分配的任務(wù)是(2,4),2號員工分配的任務(wù)是(1,5)。3號工人分配的任務(wù)是(3,6)。再根據(jù)客戶對應(yīng)元素按照從小到大排序,同時考慮時間窗限制,得到員工的旅行線路是:1號的巡回線路是2—4;2號的巡回線路是5—1;3號的巡回線路是3—6。 隨機初始化的方法雖然簡單,但會產(chǎn)生一些非法解,影響求解質(zhì)量。采用啟發(fā)式初始化的方法,可以在初始階段產(chǎn)生有效解,提高優(yōu)化的質(zhì)量。本文基于最鄰近啟發(fā)式算法進行種群的初始化。該算法是求解旅行商問題(Traveling Salesman Problem, TSP)、車輛路徑問題(Vehicle Routing Problem, VRP)等的經(jīng)典算法,其核心思想是在滿足一定的約束條件下,在未訪問的任務(wù)列表中逐步尋找與當(dāng)前線路中距離最近的任務(wù),然后將其插入線路中。本文由于實際窗的存在,在已經(jīng)存在的線路中插入客戶任務(wù),需要考慮兩方面的因素:第一,能力約束,即工人是否能完成該任務(wù);第二,時間是否可行,即插入某一任務(wù)后,插入的任務(wù)和插入位置以后的任務(wù)的時間窗是否滿足要求。對于第二種因素,如果插入一個客戶,是否要依次檢查其后的所有客戶是否可行?對此問題,依據(jù)作者針對帶取送貨車輛路徑問題(Vehicle Routing Problem with Pickups and Deliveries, VRPPD)提出的可行性插入定理[20],可以得到如下結(jié)論。 定理1 對于第f個工人已建立的可行線路i1,i2,…,ip,若在其第k個位置之后插入(ik和ik+1)之間插入一個任務(wù)h時,插入可行的充分必要條件是: th (9) λfh≤M (10) 其中:th表示到達任務(wù)h的時間;Lh表示任務(wù)h最晚允許達到的時間;Δt表示插入h后,車輛到達任務(wù)ik+1的時間比原來的推遲量;M表示預(yù)設(shè)的一個熟練程度值,在本文M=2,即當(dāng)工人完成某項工作的時間大于標(biāo)準(zhǔn)時間的2倍時,認為工人不能勝任該任務(wù),則該客戶不能分配給此工人。 在本文,鄰近任務(wù)的選擇需要考慮工人的等待時間、任務(wù)間的行駛時間等因素。設(shè)i表示當(dāng)前線路中的最后一個任務(wù),j表示未訪問的任務(wù),cij表示i與j之間的行駛時間,ti表示在任務(wù)i處開始服務(wù)的時間,wj(tj)表示工人在任務(wù)j的等候時間。tj和wj(tj)由式(5)和(7)計算得到。Nij表示任務(wù)i與j之間的廣義費用,則選擇最鄰近任務(wù)的廣義費用可定義如下: Nij=α1×cij+α2×wj(tj) (11) 其中α1,α2為系數(shù),且滿足α1+α2=1。通過計算未訪問任務(wù)的值,選出最小值對應(yīng)的任務(wù)插入線路中。最鄰近插入算法的過程如下。 U表示任務(wù)集合,Rk表示第k條線路的集合,CLk表示第k條線路的旅行時間,Vj表示工人j的客戶集合。 步驟1 設(shè)置U=C,k=0,Rk=?,CLk=0,j=0。 步驟2 判斷任務(wù)集合U是否為空,如果是則轉(zhuǎn)步驟5。如果不是,則從U中選擇開始服務(wù)時間最早的任務(wù)i,如果其時間窗Li 并把任務(wù)i從集合中刪除。 步驟3 根據(jù)插入可行性定理1,從集合U中選擇未服務(wù)的可行任務(wù)。根據(jù)式(11)計算這些任務(wù)的插入值Nij,選擇最小的插入線路,更新CLk和集合U。重復(fù)上述過程,直至沒有可行客戶為止。 步驟4 計算Rk中任務(wù)的重心,選擇距離該重心最近的員工j,將Rk的元素插入Vj中。k=k+1,CLk=0,轉(zhuǎn)步驟2。 步驟5 將構(gòu)造的初始解映射為果蠅優(yōu)化算法的編碼。 由于采用矩陣的編碼方式,現(xiàn)有果蠅算法的狀態(tài)更新方程不再適用。本文根據(jù)現(xiàn)場服務(wù)問題的特征,基于群智能理論和社會心理學(xué)原理,提出以下3種果蠅搜索策略。首先本文定義以兩種矩陣操作:posSwap(m,k)和valueSwap(m,k)。 1)posSwap(m,k)表示將矩陣A的第m行(或列)與第k行(或列)的元素互換,同時對于所有非零元素進行如下計算: (12) 2)valueSwap(m,k)表示將矩陣A中第k列的第m行元素進行重新賦值。執(zhí)行該操作時,首先根據(jù)式(13)計算amk,然后將該列除此元素之外的所有元素置0,以保證解的合法性,即每個任務(wù)只能分配給一個工人: (13) 3種果蠅搜索策略分別定義如下: Move1m∈D,k∈D,posSwap(m,k)。表示兩個工人之間互換所有任務(wù),同時任務(wù)的服務(wù)順序可能發(fā)生改變。 Move2m∈C,k∈C,posSwap(m,k)。表示將任務(wù)和互換,該操作可以使任務(wù)在工人之間交換,同時也可以改變?nèi)蝿?wù)在工人中的訪問順序。 Move3m∈C,k∈D,valueSwap(m,k)。表示將任務(wù)k分配給工人m,該操作可以改變?nèi)蝿?wù)的分配,同時改變?nèi)蝿?wù)在工人中的訪問順序。 在果蠅算法中:由于果蠅的嗅覺靈敏,可以在大范圍內(nèi)搜索,因此嗅覺搜索主要負責(zé)解空間的開發(fā)探索(exploitation),它的搜索范圍比較大;當(dāng)距離事物源較近時,則轉(zhuǎn)為視覺搜索,視覺搜索主要負責(zé)解空間的精細搜索(exploration)。根據(jù)上述原理,本文所提算法在嗅覺搜索中,依次執(zhí)行Move1、Move2和Move3搜索,根據(jù)最好接受(Best Acceptance)策略,選擇搜索到的最好位置信息更新當(dāng)前果蠅的狀態(tài);在視覺搜索過程中,僅執(zhí)行Move2和Move3搜索,根據(jù)更好接受策略(Better Acceptance),當(dāng)搜索到比當(dāng)前果蠅狀態(tài)更好的位置時,即進行更新。嗅覺搜索和視覺搜索的過程如圖1所示。 圖1 FOA的搜索過程 在執(zhí)行完果蠅優(yōu)化算法的搜索過程后,為了提高優(yōu)化質(zhì)量,使用局部搜索算法對每個解進行改進,此處主要采用兩種改進算法:2-Opt和OR-Opt。后優(yōu)化過程采用更好接受策略,當(dāng)搜索到比當(dāng)前解更好的解時,對果蠅的狀態(tài)進行更新?;旌瞎墐?yōu)化算法的流程如圖2所示。 目前現(xiàn)場服務(wù)調(diào)度問題沒有測試實例庫,本文基于帶時間窗的多倉庫車輛路徑問題(Multi-Depot Vehicle Routing Problem with Times Windows, MDVRPTW)的實例庫[21],構(gòu)建現(xiàn)場服務(wù)調(diào)度問題的實驗數(shù)據(jù)。原有數(shù)據(jù)的坐標(biāo)、時間窗、操作時間等信息不變,忽略其中的客戶需求量等信息。工人數(shù)量設(shè)定為與原實例中車輛數(shù)量相等,在將原有的倉庫位置設(shè)定為現(xiàn)場服務(wù)調(diào)度中工人位置的同時,還需要將一些客戶位置設(shè)定為工人位置。此外,對于每個實例還需要生成一個工人操作任務(wù)熟練度的矩陣,此矩陣隨機生成。其中:λki的取值范圍是[0.5,3],λki越小表示完成任務(wù)所需要的時間越短,操作越熟練,λki>2表示工人無法完成此任務(wù)。 圖2 混合果蠅優(yōu)化算法求解現(xiàn)場服務(wù)調(diào)度問題的流程 對于實例中的PR01問題,原問題表示有4個倉庫、48個客戶、每個倉庫有2輛車的問題,在轉(zhuǎn)換成現(xiàn)場服務(wù)調(diào)度問題時,則是有8個工人、44個客戶的問題,其中4個工人的地址是原倉庫地址,其余4個工人地址是從原48個客戶中隨機選擇4個設(shè)定的。根據(jù)此方法,選擇10組實例進行測試,問題規(guī)模如表1所示。 表1 仿真實例描述 混合果蠅優(yōu)化算法用C++語言實現(xiàn),運行在酷睿i5 2.5 GHz,4 GB內(nèi)存的計算機平臺上。果蠅算法的種群規(guī)模P=100,迭代次數(shù)NC=1 000,目標(biāo)函數(shù)的系數(shù)α=0.4,β=0.3,γ=0.3。針對每個實例,算法隨機運行20次,對其結(jié)果進行統(tǒng)計分析。首先對本文提出的初始化方法進行分析比較,最鄰近法的初始化參數(shù)α1=0.6,α2=0.4,將最鄰近算法和隨機初始化進行對比。針對PR01和PR02進行測試,優(yōu)化結(jié)果的均值和方差如圖3所示。 圖3 果蠅優(yōu)化算法初始化方法的比較 從圖3中可以看出,最鄰近法比隨機方法的均值有明顯降低(對于PR01問題,與隨機方法相比,最鄰近法均值了減小7%;對于PR02,減小6.9%),并且算法的偏差更小,表明最近鄰算法能使果蠅算法更加穩(wěn)定。 下面對3種局部搜索算子的搜索能力進行比較。依然以PR01和PR02為例,分別單獨執(zhí)行Move1、Move2和Move3三種搜索策略,算法的進化曲線如圖4所示。從圖4中可以看出,在算法初期(200代以內(nèi)),3種搜索策略的效率相差不大,都能很快地搜索到比較好的結(jié)果;但在迭代后期,Move1算法比較早地進入停滯期,無法跳出局部極值點。這是因為Move1主要將客戶在工人之間交換,搜索得比較粗糙。Move2算子在3種搜索策略中優(yōu)化能力最強,這主要因為Move2操作在進行任務(wù)交換的同時,不僅改變了任務(wù)在工人間的分配,同時還改變了任務(wù)的訪問順序,是一個集成了線路內(nèi)和線路間的2-Opt算子。Move3類似于一個插入算子,搜索能力比Move1強,但比Move2弱。 圖4 3種搜索算子的比較 對于嗅覺搜索和視覺搜索的搜索能力,本文也通過PR01和PR02兩個問題進行了驗證,結(jié)果如圖5所示。 圖5 搜索策略的比較 從圖5可以看出,僅執(zhí)行視覺搜索的結(jié)果最差,嗅覺和視覺都執(zhí)行的混合策略優(yōu)化結(jié)果最好。因為視覺搜索主要是由鄰域信息引導(dǎo)的局部搜索,采用更優(yōu)接受(better acceptance)策略。而嗅覺搜索是全局信息引導(dǎo)的搜索,并且3種搜索算子都執(zhí)行,采用最優(yōu)接受策略,因此,嗅覺搜索的優(yōu)化能力更強,當(dāng)把兩種搜索策略混合,視覺的局部搜索能改進嗅覺搜索的優(yōu)化結(jié)果。 圖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]提出的貪婪隨機自適應(yīng)搜索過程(Greedy Randomized Adaptive Search Procedure, GRASP)算法和江俊杰等[6]提出的遺傳算法進行了比較,結(jié)果如表2所示。從表2中數(shù)據(jù)可以看出,對于10個問題,混合優(yōu)化果蠅算法在均值和最優(yōu)值方面都優(yōu)于GRASP算法和遺傳算法,GRASP算法又比遺傳算法的優(yōu)化結(jié)果好。 表2 3種算法的均值與最優(yōu)值比較 隨著互聯(lián)網(wǎng)經(jīng)濟的發(fā)展,客戶的個性化服務(wù)需求日益凸顯?,F(xiàn)場服務(wù)進入飛速發(fā)展階段,為了提高服務(wù)質(zhì)量和效率,現(xiàn)場服務(wù)調(diào)度至關(guān)重要。本文建立了現(xiàn)場服務(wù)調(diào)度問題的數(shù)學(xué)模型,分析了問題解的性質(zhì)(插入可行性)。鑒于問題的復(fù)雜性,提出了混合果蠅優(yōu)化算法進行求解。設(shè)計了基于矩陣的實數(shù)編碼方案,基于群智能理論和社會心理學(xué)原理,定義了兩類矩陣操作算子,設(shè)計了3種搜索策略,進而重構(gòu)了果蠅優(yōu)化算法的嗅覺搜索和視覺搜索過程。為了提高算法的性能,構(gòu)建了基于最鄰近插入啟發(fā)式算法的初始化方法,并引入后優(yōu)化過程。通過實驗仿真,分析比較了各算子的優(yōu)化效果,并與其他算法進行了比較。結(jié)果表明,本文所提算法是求解現(xiàn)場服務(wù)調(diào)度問題的有效方法。2 基本果蠅優(yōu)化算法
3 混合果蠅優(yōu)化算法求解現(xiàn)場服務(wù)調(diào)度問題
3.1 編碼方法
3.2 種群初始化
3.3 果蠅搜索策略
3.4 后優(yōu)化過程
4 實驗仿真
5 結(jié)語