基于混合果蠅優(yōu)化算法的現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題

吳 斌，王 超，董 敏

(南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，南京 211816)

0 引言

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

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

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

1 現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題的模型

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

對(duì)于一個(gè)網(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ò)的旅行時(shí)間，且cij=cji。di表示任務(wù)i的標(biāo)準(zhǔn)服務(wù)時(shí)間，λki∈(0,M]表示工人k服務(wù)任務(wù)i的熟練程度，λki越小表示熟練程度越高，完成時(shí)間越短；λki>M則表示無(wú)法完成該任務(wù)。[Ei,Li]表示任務(wù)i的時(shí)間窗；ti表示任務(wù)i開(kāi)始服務(wù)的時(shí)間；wi(ti)表示工人在任務(wù)i的等待時(shí)間。xijk=1,i,j∈V,k∈D表示工人k從節(jié)點(diǎn)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部分是旅行時(shí)間，第2部分是任務(wù)的完成時(shí)間，第3部分是工人的等待時(shí)間，通過(guò)加權(quán)使三者之和最小。約束式(2)保證每個(gè)任務(wù)點(diǎn)僅被1個(gè)工人服務(wù)。約束式(3)保證每個(gè)任務(wù)僅被服務(wù)1次，且工人進(jìn)入節(jié)點(diǎn)并從該節(jié)點(diǎn)離開(kāi)。約束式(4)表示工人需從自己的出發(fā)地出發(fā)。約束式(5)和(6)表示時(shí)間窗的約束，約束式(7)表示等待時(shí)間的計(jì)算。

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

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

步驟1 初始化種群中個(gè)體的位置。

步驟2 嗅覺(jué)搜索。由個(gè)體的當(dāng)前位置隨機(jī)選擇方向和位置進(jìn)行搜索。

步驟3 個(gè)體評(píng)價(jià)。對(duì)個(gè)體搜索到的新位置，計(jì)算其味道濃度。

步驟4 視覺(jué)搜索。選擇味道濃度最大的位置，個(gè)體根據(jù)視覺(jué)向該位置搜索。

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

3 混合果蠅優(yōu)化算法求解現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題

基本的果蠅算法主要用于函數(shù)優(yōu)化，將其應(yīng)用于現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題，需要在編碼方法、初始化方法、嗅覺(jué)搜索和視覺(jué)搜索等方面進(jìn)行改進(jìn)。

3.1 編碼方法

現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題是組合優(yōu)化問(wèn)題，果蠅優(yōu)化算法在求解這類(lèi)問(wèn)題時(shí)，如何進(jìn)行編碼是關(guān)鍵。本文提出一種基于矩陣的編碼方式表示現(xiàn)場(chǎng)服務(wù)調(diào)度的解，這種編碼方法可以將任務(wù)分配與工人旅行線路同時(shí)表達(dá)出來(lái)，方便果蠅優(yōu)化算子的設(shè)計(jì)。其編碼方式如下：

(8)

步驟1j=0。

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

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

步驟4 如果j=m-1，則結(jié)束程序；否則j=j+1轉(zhuǎn)步驟2。

例1 以3個(gè)工人、6個(gè)任務(wù)的現(xiàn)場(chǎng)服務(wù)系統(tǒng)為例，其編碼形式如下所示：

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

3.2 種群初始化

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

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

th

(9)

λfh≤M

(10)

其中：th表示到達(dá)任務(wù)h的時(shí)間；Lh表示任務(wù)h最晚允許達(dá)到的時(shí)間；Δt表示插入h后，車(chē)輛到達(dá)任務(wù)ik+1的時(shí)間比原來(lái)的推遲量；M表示預(yù)設(shè)的一個(gè)熟練程度值，在本文M=2，即當(dāng)工人完成某項(xiàng)工作的時(shí)間大于標(biāo)準(zhǔn)時(shí)間的2倍時(shí)，認(rèn)為工人不能勝任該任務(wù)，則該客戶(hù)不能分配給此工人。

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

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

(11)

其中α1,α2為系數(shù)，且滿(mǎn)足α1+α2=1。通過(guò)計(jì)算未訪問(wèn)任務(wù)的值，選出最小值對(duì)應(yīng)的任務(wù)插入線路中。最鄰近插入算法的過(guò)程如下。

U表示任務(wù)集合，Rk表示第k條線路的集合，CLk表示第k條線路的旅行時(shí)間，Vj表示工人j的客戶(hù)集合。

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

步驟2 判斷任務(wù)集合U是否為空，如果是則轉(zhuǎn)步驟5。如果不是，則從U中選擇開(kāi)始服務(wù)時(shí)間最早的任務(wù)i，如果其時(shí)間窗Li

并把任務(wù)i從集合中刪除。

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

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

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

3.3 果蠅搜索策略

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

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

(12)

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

(13)

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

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

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

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

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

圖1 FOA的搜索過(guò)程

3.4 后優(yōu)化過(guò)程

在執(zhí)行完果蠅優(yōu)化算法的搜索過(guò)程后，為了提高優(yōu)化質(zhì)量，使用局部搜索算法對(duì)每個(gè)解進(jìn)行改進(jìn)，此處主要采用兩種改進(jìn)算法：2-Opt和OR-Opt。后優(yōu)化過(guò)程采用更好接受策略，當(dāng)搜索到比當(dāng)前解更好的解時(shí)，對(duì)果蠅的狀態(tài)進(jìn)行更新。混合果蠅優(yōu)化算法的流程如圖2所示。

4 實(shí)驗(yàn)仿真

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

圖2 混合果蠅優(yōu)化算法求解現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題的流程

對(duì)于實(shí)例中的PR01問(wèn)題，原問(wèn)題表示有4個(gè)倉(cāng)庫(kù)、48個(gè)客戶(hù)、每個(gè)倉(cāng)庫(kù)有2輛車(chē)的問(wèn)題，在轉(zhuǎn)換成現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題時(shí)，則是有8個(gè)工人、44個(gè)客戶(hù)的問(wèn)題，其中4個(gè)工人的地址是原倉(cāng)庫(kù)地址，其余4個(gè)工人地址是從原48個(gè)客戶(hù)中隨機(jī)選擇4個(gè)設(shè)定的。根據(jù)此方法，選擇10組實(shí)例進(jìn)行測(cè)試，問(wèn)題規(guī)模如表1所示。

表1 仿真實(shí)例描述

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

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

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

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

圖4 3種搜索算子的比較

對(duì)于嗅覺(jué)搜索和視覺(jué)搜索的搜索能力，本文也通過(guò)PR01和PR02兩個(gè)問(wèn)題進(jìn)行了驗(yàn)證，結(jié)果如圖5所示。

圖5 搜索策略的比較

從圖5可以看出，僅執(zhí)行視覺(jué)搜索的結(jié)果最差，嗅覺(jué)和視覺(jué)都執(zhí)行的混合策略?xún)?yōu)化結(jié)果最好。因?yàn)橐曈X(jué)搜索主要是由鄰域信息引導(dǎo)的局部搜索，采用更優(yōu)接受(better acceptance)策略。而嗅覺(jué)搜索是全局信息引導(dǎo)的搜索，并且3種搜索算子都執(zhí)行，采用最優(yōu)接受策略，因此，嗅覺(jué)搜索的優(yōu)化能力更強(qiáng)，當(dāng)把兩種搜索策略混合，視覺(jué)的局部搜索能改進(jìn)嗅覺(jué)搜索的優(yōu)化結(jié)果。

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

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

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

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

5 結(jié)語(yǔ)

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