李 藝,葉 樺,仰燕蘭

(東南大學(xué) 自動(dòng)化學(xué)院,南京 210096)

在現(xiàn)代市場(chǎng)經(jīng)濟(jì)的競(jìng)爭(zhēng)環(huán)境下,服務(wù)的及時(shí)性以及服務(wù)質(zhì)量對(duì)客戶滿意度和客戶的忠誠(chéng)度有非常大的影響[1].一般來(lái)說(shuō),產(chǎn)品服務(wù)分為兩大類,基于設(shè)施的服務(wù)和現(xiàn)場(chǎng)服務(wù).基于設(shè)施的服務(wù)一般是需要客戶上門,采用專業(yè)的設(shè)備進(jìn)行處理.現(xiàn)場(chǎng)服務(wù)是指服務(wù)提供方前往客戶的地理位置上提供服務(wù),這其中的典型代表就是大型設(shè)備的安裝、維修和保養(yǎng).

現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題,又稱為現(xiàn)場(chǎng)技術(shù)人員調(diào)度問(wèn)題,其優(yōu)化實(shí)質(zhì)是對(duì)各類資源的合理調(diào)配和時(shí)間安排.目前眾多學(xué)者對(duì)其的研究主要分為兩方面,一類是對(duì)優(yōu)化模型的研究,另一類是對(duì)求解算法的研究.

優(yōu)化模型方面,Li 等通過(guò)在團(tuán)隊(duì)中調(diào)度不同類型的工人服務(wù)線路來(lái)最大限度的減少工人綜述和總位移[2].Kovac 等在執(zhí)行具有相同優(yōu)先級(jí)但具有不同時(shí)間窗口的現(xiàn)場(chǎng)服務(wù)時(shí),從公司的角度最大限度的減少位移和外包成本[3].Dohn 在受到有限數(shù)量團(tuán)隊(duì)成員的限制情況下研究了如何使得任務(wù)數(shù)量最大化[4].江俊杰等提出了等待時(shí)間的概念,利用遺傳算法求解該類問(wèn)題[5].吳斌等首次考慮客戶滿意度的概念,進(jìn)一步完善求解的模型[6].

求解算法方面,一部分學(xué)者將研究的重點(diǎn)放在技能指派方面.談文芳等指出維修指派問(wèn)題屬于NP 難題,運(yùn)用粒子群算法求解,建立了一種優(yōu)化指派的模型,驗(yàn)證了粒子群優(yōu)化的可行性[7].王慶建立了人員工作指派及調(diào)度的決策模型,并對(duì)人員進(jìn)行分析,提出了計(jì)算員工團(tuán)隊(duì)匹配度和員工任務(wù)匹配度的模型,提出并改進(jìn)了雙層編碼的混合遺傳算法[8].

還有一部分學(xué)者將現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題同已有的一些經(jīng)典問(wèn)題進(jìn)行對(duì)比,基于經(jīng)典模型已有的研究成果提出了新的策略.江俊杰等將現(xiàn)場(chǎng)服務(wù)調(diào)度問(wèn)題看做多技能匹配和多旅行商問(wèn)題的綜合,提出了基于分段染色體遺傳算法的求解方案[5].Pillac 等分析了現(xiàn)場(chǎng)調(diào)度服務(wù)問(wèn)題與帶時(shí)間窗車輛路徑問(wèn)題的區(qū)別,提出并行自適應(yīng)大領(lǐng)域搜索算法優(yōu)化解決該問(wèn)題[9].曹永榮等以排隊(duì)模型為基礎(chǔ),通過(guò)仿真的算法研究了現(xiàn)場(chǎng)服務(wù)問(wèn)題[10].

相較于普通的服務(wù)產(chǎn)品,工程機(jī)械的現(xiàn)場(chǎng)服務(wù)調(diào)度具有一定的特殊性.一方面,工程機(jī)械設(shè)備作為基礎(chǔ)建設(shè)的大型裝備,施工地點(diǎn)大多位于偏遠(yuǎn)地區(qū),交通十分不便,一般是由服務(wù)人員乘坐專用服務(wù)車趕赴現(xiàn)場(chǎng)進(jìn)行維修保養(yǎng)服務(wù),故涉及人車的聯(lián)合調(diào)度,相較一般的調(diào)度問(wèn)題更為復(fù)雜.另一方面,不同類型的工程機(jī)械在結(jié)構(gòu)、性能等方面都有很大的區(qū)別,例如從大類上分,有起重機(jī)、挖掘機(jī)、裝載機(jī)、泵車等種類,這就對(duì)維修保養(yǎng)人員的專業(yè)技能水平提出了更高的要求.如何針對(duì)具體的工程機(jī)械設(shè)備選派合適的專業(yè)技術(shù)服務(wù)人員是另一個(gè)亟待解決的問(wèn)題.

工程機(jī)械人車一體化調(diào)度屬于新的研究問(wèn)題,要考慮技能特點(diǎn)與維修需求的相匹配,同時(shí)相較于一般的現(xiàn)場(chǎng)服務(wù)問(wèn)題,還有額外的服務(wù)車約束.本文在現(xiàn)有服務(wù)調(diào)度問(wèn)題的基礎(chǔ)上,結(jié)合工程機(jī)械客戶服務(wù)的特點(diǎn),將其轉(zhuǎn)化為一個(gè)特殊的三次匹配問(wèn)題,提出了基于二分圖最小權(quán)匹配的混合遺傳算法進(jìn)行求解.

1 工程機(jī)械人車一體化調(diào)度問(wèn)題模型

1.1 問(wèn)題定義

工程機(jī)械人車一體化調(diào)度問(wèn)題可以定義為:多個(gè)企業(yè)的工程師從不同的起點(diǎn)搭載不同的服務(wù)車前往分散在不同地理位置上的多個(gè)工程機(jī)械處提供售后服務(wù),包括安裝、維護(hù)檢查、故障維修等類型.工程師具備不同的技能,且技能能力存在區(qū)分度,熟練度高的工程師維修速度快.每個(gè)工程機(jī)械的維修需求不同,需要對(duì)應(yīng)技能的工程師前往.

調(diào)度系統(tǒng)安排處于不同位置的服務(wù)車去接相關(guān)工程師去分別執(zhí)行這些任務(wù),假設(shè)服務(wù)車的設(shè)施配備滿足工程師的維修需求.在滿足一定的約束條件的前提下(技能匹配性、時(shí)間限制等),達(dá)到一定的目標(biāo)(路程短、花費(fèi)時(shí)間少、客戶滿意度高等).

上述問(wèn)題可以描述為:m名維修人員組成的集合A={1,2,3,…,m},n輛待修機(jī)械組成的集合M={1,2,3,…,n},p輛服務(wù)車組成的集合C={1,2,3,…,p}.

提出一個(gè)包含技能需求的集{合S={1,2,}· ··,l}.維修人員k具備的技能由向量gk=g1k,g2k,···,glk表示,gnk表示該維修人員在第n項(xiàng)技能上的表現(xiàn)能力,范圍在0-5 之間.gnk=0表示維修人員不具備該項(xiàng)技能；=h表示該維修人員具有等級(jí)為h的第n項(xiàng)技能,h值越大,表明具備的該相應(yīng)技能水平越高,完成該項(xiàng)任務(wù)所需要的時(shí)間更少.

1.2 維修時(shí)長(zhǎng)計(jì)算

服務(wù)人的技能特長(zhǎng)與技能能力水平直接影響該項(xiàng)服務(wù)任務(wù)的完成時(shí)間.傳統(tǒng)操作中,多依靠經(jīng)驗(yàn)對(duì)技能員工進(jìn)行分配,這種分配方式既費(fèi)時(shí)又費(fèi)力,且滿意度不高.本文希望在充分考慮員工技能工種和待維修機(jī)械的切實(shí)需求的前提下,通過(guò)一些可量化、可計(jì)算的方式針對(duì)匹配雙方的需求進(jìn)行處理,進(jìn)而獲取最終的匹配方案.

若待修機(jī)械j所需的服務(wù)為Sj=m,則服務(wù)人k完成該任務(wù)的維修時(shí)長(zhǎng)為:

tajk表示服務(wù)人k對(duì)待修機(jī)械j的維修時(shí)長(zhǎng).Tm表示第m類需求的標(biāo)準(zhǔn)工時(shí).gmk=0表示維修人員k不具備該項(xiàng)技能m,與該工程機(jī)械不匹配,任務(wù)完成時(shí)間無(wú)限長(zhǎng).

1.3 統(tǒng)一調(diào)度模型

工程機(jī)械在故障時(shí),能否在最短的時(shí)間內(nèi)得到維修,直接關(guān)系到工程機(jī)械效能的實(shí)現(xiàn),也是評(píng)價(jià)服務(wù)質(zhì)量高低的重要因素.服務(wù)人到達(dá)維修地點(diǎn)的方法是服務(wù)車到服務(wù)人所在地,搭載相關(guān)維修設(shè)備及服務(wù)人到目標(biāo)工程機(jī)械.針對(duì)若干個(gè)任務(wù)點(diǎn),需要找出多工程機(jī)械-多服務(wù)人-多服務(wù)車的最優(yōu)組合.

圖1 多服務(wù)車-多服務(wù)人-多工程機(jī)械匹配示意圖

設(shè)工程機(jī)械j到服務(wù)人k的所需時(shí)長(zhǎng)為tdjk,服務(wù)人k到服務(wù)車v的所需時(shí)長(zhǎng)為tdkv.

求解的目標(biāo)是對(duì)于需要的維修機(jī)械j,選擇合適的服務(wù)人與服務(wù)車組合,使得從分配到完成待修機(jī)械需求所花費(fèi)的時(shí)間盡可能短.總體最優(yōu)的目標(biāo)模型為:

約束條件如下:

式(2) 是求解目標(biāo),最小化完成所有任務(wù)的總時(shí)間.xjkv是0-1 變量,服務(wù)人k、服務(wù)車v與機(jī)械j構(gòu)成組合時(shí)值為1,反之為0.式(3)-式(5)是約束條件,本文是在服務(wù)資源充足的情況下,單次單任務(wù)分派的統(tǒng)一調(diào)度方案.服務(wù)人數(shù)目和服務(wù)車數(shù)目大于待修任務(wù),一個(gè)服務(wù)人最多安排一項(xiàng)任務(wù),一臺(tái)工程機(jī)械僅由一個(gè)服務(wù)人負(fù)責(zé).

2 基于二分圖最小權(quán)分配的混合遺傳算法

根據(jù)圖1,三個(gè)點(diǎn)集A,M,C,同一點(diǎn)集之間沒(méi)有邊,MC 點(diǎn)集之間沒(méi)有邊.MA 點(diǎn)集之間有邊,AC 點(diǎn)集之間有邊,求組合的最小權(quán)重,這是一類組合優(yōu)化問(wèn)題,屬于三分圖的最小權(quán)匹配,稱作AP3 問(wèn)題[11].二分圖匹配問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)有效的解決,但是AP3 問(wèn)題是一個(gè)非確定多項(xiàng)式問(wèn)題.

現(xiàn)有研究下,精確算法和啟發(fā)式算法都有建議解決AP3 問(wèn)題.在這些當(dāng)中,Burkard 等人專注于AP3 可分解的成本系數(shù)[12].即使有這個(gè)特例,AP3 問(wèn)題仍然是NP 難題.Aiex 等將GRASP(貪婪隨機(jī)自適應(yīng)算法)應(yīng)用于權(quán)重調(diào)整以期望獲取更好的結(jié)果[13].張樹威改善束搜索算法,求解AP3 問(wèn)題[14].

本文提出了一種基于二分圖最小權(quán)匹配與遺傳算法相結(jié)合的求解方案.

圖2 AP3 問(wèn)題X,(M,P)、Y(P,C)組合

如圖2是一個(gè)一般的三次匹配問(wèn)題.對(duì)于需要提供服務(wù)的工程機(jī)械{M1,M2,M3},提供服務(wù)的服務(wù)人組合為{P1,P3,P5},搭載服務(wù)人的服務(wù)車組合為{C2,C4,C6}.AP2 問(wèn)題只涉及一個(gè)組合X,AP3 問(wèn)題涉及組合X,Y.可以采用拆分的思路,假設(shè)在組合X已知的情況下,進(jìn)行服務(wù)車的分配,這就是一個(gè)二分圖的求解問(wèn)題.如下圖圖3所示.

圖3 AP2 問(wèn)題 求解Y(P,C)組合

本節(jié)中利用匈牙利算法求解服務(wù)人與服務(wù)車的匹配,涉及二分圖最小權(quán)分配.待修機(jī)械與服務(wù)人的組合利用帶精英選擇策略的遺傳算法求解,適應(yīng)度函數(shù)為工程機(jī)械到服務(wù)人到服務(wù)車的權(quán)重之和.基本的數(shù)據(jù)流程如下:

圖4 服務(wù)車-服務(wù)人-工程機(jī)械調(diào)度計(jì)算過(guò)程

2.1 基于匈牙利算法求解人車匹配問(wèn)題

匈牙利算法最早是由匈牙利數(shù)學(xué)家Konig D 用來(lái)求矩陣中0 元素的個(gè)數(shù)的一種方法,他證明了“矩陣中獨(dú)立0 元素的最多個(gè)數(shù)等于能覆蓋所有0 元素的最少直線數(shù)”.1955年由Kuhn 在求解著名的指派問(wèn)題時(shí)引用了這一結(jié)論,并對(duì)具體算法做了改進(jìn),仍稱為匈牙利算法.

該算法是基于效率矩陣每一行元素減去改行的最小值,每一列元素減去該列的最小值,得到新效率矩陣,原效率矩陣與新效率矩陣最優(yōu)解相同.通過(guò)行/列變換讓費(fèi)用矩陣的每行和每列都出現(xiàn)0,找出不同行、列的n個(gè)0,這些0 對(duì)應(yīng)的指派就是最優(yōu)指派.求解步驟如下:

Step1.建立指派分配方案的效率矩陣A,A為n×m的矩陣.找出效率矩陣A每行的最小元素,每行減去該元素,對(duì)矩陣的列做相同操作.

Step2.將處理后的矩陣A轉(zhuǎn)化為匈牙利算法求解所需要的標(biāo)準(zhǔn)型d×d階矩陣B,d=max(m,n).當(dāng)m小于n時(shí),補(bǔ)充全零行.當(dāng)m大于n時(shí),補(bǔ)充全零列.

Step3.用最少直線數(shù)k覆蓋所有零元素.

Step4.當(dāng)k=d時(shí)停止計(jì)算,得到最優(yōu)配置方案.當(dāng)k≠d時(shí),從矩陣未被覆蓋的數(shù)字中找到最小數(shù)值s，未被覆蓋的元素減去s,直線相交處加上s,被直線覆蓋而沒(méi)有相交的元素不便,得到新效率矩陣c.

Step5.重復(fù)以上步驟Step2,Step3,直至k=d.

2.2 基于二分圖最小權(quán)匹配的混合遺傳算法

針對(duì)統(tǒng)一調(diào)度問(wèn)題的特征,本節(jié)介紹基于二分圖最小權(quán)匹配的混合遺傳算法求解方案.針對(duì)基本遺傳算法面臨的一些問(wèn)題,收斂太快陷入局部最優(yōu),收斂太慢耗時(shí)太長(zhǎng)的缺點(diǎn),應(yīng)用多種改進(jìn)策略,包括內(nèi)嵌精英保留策略的選擇算子,動(dòng)態(tài)的變異概率等.

(1) 編碼方式及解碼

遺傳算法現(xiàn)有的編碼方式主要有實(shí)數(shù)編碼和二進(jìn)制編碼.本文采用實(shí)數(shù)編碼作為人車一體化調(diào)度問(wèn)題解的表達(dá)形式.該編碼方式采用N個(gè)1～M之間互不重復(fù)的整數(shù)排列表示染色體.染色體的長(zhǎng)度取決于待修機(jī)械的總數(shù)(此處工程機(jī)械數(shù)目為N),節(jié)點(diǎn)的取值為服務(wù)人的編號(hào)范圍(此處服務(wù)人數(shù)目為M).圖5給出了一個(gè)工程機(jī)械數(shù)目為4,服務(wù)人數(shù)目為20 的簡(jiǎn)單染色體的編碼方式.

圖5表示對(duì)工程機(jī)械1-4,分配的服務(wù)人編號(hào)分別為7,12,4,5.

圖5 染色體編碼

解碼過(guò)程是根據(jù)服務(wù)人的信息,利用匈牙利算法計(jì)算最小代價(jià)的服務(wù)車信息,得到服務(wù)車編號(hào),形成工程機(jī)械-服務(wù)人-服務(wù)車的組合信息.

(2)適應(yīng)度函數(shù)計(jì)算

種群的初始化采用均勻分布法,隨機(jī)產(chǎn)生num個(gè)不重復(fù)的染色體.首先計(jì)算服務(wù)人與待修機(jī)械的代價(jià)函數(shù),即路程與維修所消耗時(shí)間之和.

其次,根據(jù)確定的服務(wù)人組合,利用匈牙利算法計(jì)算對(duì)應(yīng)服務(wù)車組合.服務(wù)車接載服務(wù)人的時(shí)間消耗為:

對(duì)于該染色體,解碼之后,該組合匹配最終的時(shí)間為:

由于本節(jié)是求解最優(yōu)的組合匹配,目的是使得消耗的總時(shí)間長(zhǎng)度最小,因而需要將目標(biāo)函數(shù)映射為最大值且函數(shù)值非負(fù)的適應(yīng)度函數(shù).采用如下轉(zhuǎn)化方法:

Fmax(x) 表示種群中目標(biāo)函數(shù)值最大的個(gè)體對(duì)應(yīng)的時(shí)間長(zhǎng)度.

(3) 內(nèi)嵌精英選擇策略的輪盤賭選擇算子

遺傳算法的選擇算子是根據(jù)個(gè)體的適應(yīng)度對(duì)種群中的個(gè)體進(jìn)行的優(yōu)勝劣汰操作.輪盤賭選擇法的基本思想是各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比.

Rudolph 利用齊次有限馬爾科夫鏈證明了僅僅采用交叉、變異和選擇(比例選擇法)三個(gè)遺傳算子的標(biāo)準(zhǔn)遺傳算法不能收斂到全局最優(yōu).因?yàn)榇嬖诮y(tǒng)計(jì)誤差,根據(jù)產(chǎn)生的隨機(jī)數(shù)進(jìn)行選擇,可能會(huì)出現(xiàn)不正確的反映個(gè)體適應(yīng)度的選擇,導(dǎo)致適應(yīng)度高的個(gè)體也被淘汰.Eiben 利用馬爾科夫鏈證明了包含精英保留策略的遺傳算法具有全局收斂性,另一方面,它也會(huì)使的某個(gè)局部最優(yōu)個(gè)體不易被淘汰反而快速擴(kuò)散,以致算法收斂于局部最優(yōu)解[15].因而,它常與某些選擇算法配合使用.本文采用的是采用內(nèi)嵌精英選擇策略的輪盤賭選擇算子 ,其流程如圖6所示.

圖6 內(nèi)嵌精英保留策略的輪盤賭選擇算子

(4)染色體交叉操作

由于服務(wù)人與工程機(jī)械之間存在技能匹配,即服務(wù)人具備的技能特征與待修機(jī)械需求不符合時(shí),無(wú)法配對(duì).同時(shí),對(duì)于一個(gè)服務(wù)人,只安排一項(xiàng)待修任務(wù),因而染色體中不能存在重復(fù)編碼.為了增加解的可行性,本文采用點(diǎn)對(duì)點(diǎn)交叉去重策略.點(diǎn)對(duì)點(diǎn)交叉可以保證技能的匹配度,去重確保染色體基因的不重復(fù).

針對(duì)兩個(gè)父代染色體,記染色體父體,染色體母體.在種群中任意選擇兩個(gè)染色體作為父代染色體,在父代染色體上任意選擇一個(gè)基因位作為交叉位.如圖7所示為簡(jiǎn)單的交叉示意圖.

圖7 染色體交叉簡(jiǎn)單示意圖

(5) 自適應(yīng)變異概率的染色體變異操作

一般來(lái)說(shuō),變異操作包括兩點(diǎn)互換變異,以及單點(diǎn)特殊變異.兩點(diǎn)互換變異是針對(duì)選擇的染色體,隨機(jī)交換兩個(gè)基因位置.但受本文的實(shí)際場(chǎng)景約束,每個(gè)基因位對(duì)應(yīng)著不同編號(hào)的工程機(jī)械,工程機(jī)械的維修需求需要與服務(wù)人的技能一致,交換變異很可能造成不可行的解.本節(jié)采用單點(diǎn)特殊變異,隨機(jī)選擇染色體的隨機(jī)位置,進(jìn)行突變.

為了讓遺傳算法不變?yōu)橐环N無(wú)目的的隨機(jī)搜索算法,變異概率的取值一般為0.05-0.5.

對(duì)于小規(guī)模優(yōu)化問(wèn)題,變異概率通常取常數(shù),對(duì)于大規(guī)模優(yōu)化問(wèn)題,變異概率通常建議取變量[16].在進(jìn)化前期,變異概率較大有利于提高搜索能力,但是后期可能較大程度的破壞遺傳信息,進(jìn)化后期采用較小的變異概率對(duì)種群進(jìn)行微小調(diào)整.本文根據(jù)文獻(xiàn)[16]中的介紹,采用常用的線性變異方案.

設(shè)變異概率的取值范圍[rmin,rmax+rmin).隨著進(jìn)化次數(shù)的增加,變異概率在該區(qū)間內(nèi)呈現(xiàn)遞減趨勢(shì).若用cur表示當(dāng)前進(jìn)化次數(shù),curmax表示最大進(jìn)化次數(shù).則當(dāng)前進(jìn)化次數(shù)中的變異概率:

設(shè)置curmax=100,rmax=0.45,rmin=0.05,給出變異概率變化曲線如圖8所示.

2.3 算法收斂性分析

(1) 遺傳算法收斂定義

對(duì)于遺傳算法而言,收斂性是指算法的迭代種群逐漸趨于某一穩(wěn)定狀態(tài),如適應(yīng)值的最大值或者平均值收斂于解的最優(yōu)值[17].

圖8 變異概率變化曲線

設(shè)h(i)={x1,x2,···,xn} 為遺傳算法的第i代種群,n為當(dāng)前種群中的個(gè)體總數(shù),f(x) 為適應(yīng)度函數(shù).Zh(i)=max{f(xk) |k=1,2,···,n} 為種群最大適應(yīng)度,f+=max{f(x) |x∈S}為全局最大適應(yīng)度,S為所有群體的個(gè)體集合.如果:

則稱遺傳算法依概率收斂到全局最優(yōu)解.

(2) 馬爾科夫鏈定義

設(shè)隨機(jī)序列X={Xn,n=0,1···}的離散空間為E,如果對(duì)于任意n≥0 ,以及i0,i1,···,in,j∈E,滿足條件概率:

則稱這類X隨機(jī)過(guò)程為離散馬爾科夫鏈,馬爾科夫鏈具有無(wú)后效性的特點(diǎn),即當(dāng)前狀態(tài)只與前一狀態(tài)有關(guān),而與其他狀態(tài)無(wú)關(guān).

(3) 混合遺傳算法收斂性分析

將混合遺傳算法看做一個(gè)離散狀態(tài)空間下的隨機(jī)序列,把每一代種群P(1),P(2),…看做一種狀態(tài),種群的代代演變看做是狀態(tài)間的轉(zhuǎn)移,二分圖的匹配實(shí)際上是一種局部?jī)?yōu)化搜索.當(dāng)前種群的狀態(tài)僅依賴于上一代種群,與以往無(wú)關(guān),因而可以采用馬爾科夫鏈來(lái)證明算法的收斂性.

假設(shè)總體狀態(tài)空間為H,算法中每一代種群h(t)對(duì)應(yīng)馬爾科夫鏈中的一個(gè)狀態(tài),種群的逐代進(jìn)化對(duì)應(yīng)馬爾科夫鏈中的狀態(tài)轉(zhuǎn)移.標(biāo)記每個(gè)h(i)∈H是否包含當(dāng)前最優(yōu)個(gè)體.根據(jù)遺傳算法的收斂性以及精英選擇策略的特征可知,一旦轉(zhuǎn)移后的狀態(tài)包含了當(dāng)前最優(yōu)個(gè)體,在以后的轉(zhuǎn)移過(guò)程中,將一直包含最優(yōu)個(gè)體狀態(tài),且其他個(gè)體狀態(tài)也會(huì)一直逼近最優(yōu)個(gè)體.最終:混合遺傳算法將以概率1 收斂到全局最優(yōu).

3 問(wèn)題求解

以某機(jī)械制造企業(yè)某段時(shí)間的報(bào)修單為例,驗(yàn)證本文算法的有效性.設(shè)置種群數(shù)為100,迭代次數(shù)為80,交叉概率0.8.服務(wù)車平均行駛速度以60 km/h 計(jì)算.

表1給出了待修機(jī)械的信息,表2是對(duì)應(yīng)維修需求的平均維修時(shí)長(zhǎng).表3給出了20 個(gè)服務(wù)人,20 個(gè)服務(wù)車的信息.位置信息用經(jīng)緯度表示,緯度在前,經(jīng)度在后.服務(wù)人技能數(shù)組簡(jiǎn)化為[a,b],a表示員工技能類型,b表示技能等級(jí).

表1 工程機(jī)械信息

表2 維修工種信息

與傳統(tǒng)遺傳算法搜索最優(yōu)解相比較,如圖9所示.

圖9 混合遺傳算法與傳統(tǒng)遺傳算法最優(yōu)值的對(duì)比

對(duì)于上述的M×P×C=4×20×20,可以看出混合遺傳算法的最優(yōu)值優(yōu)于傳統(tǒng)的遺傳算法,且相較傳統(tǒng)的算法可以較快的尋到最優(yōu)解.

表3 20×20 服務(wù)人、服務(wù)車信息

進(jìn)一步擴(kuò)展問(wèn)題規(guī)模,種群數(shù)目選擇為200,迭代次數(shù)選為100.將本文的基于二分圖最小權(quán)匹配的混合遺傳算法與傳統(tǒng)遺傳算法以及貪婪隨機(jī)自適應(yīng)搜索算法的結(jié)果進(jìn)行比較.

從表4-表6中可以看出,基于這6 個(gè)算例,基于二分圖最小權(quán)匹配的混合遺傳算法的最優(yōu)值和平均值均優(yōu)于傳統(tǒng)遺傳算法和貪婪隨機(jī)自適應(yīng)搜索算法.

表4 多工程機(jī)械混合遺傳算法求解結(jié)果

4 結(jié)束語(yǔ)

本文針對(duì)工程機(jī)械客戶服務(wù)系統(tǒng)人車一體化調(diào)度這一特殊的調(diào)度問(wèn)題,在服務(wù)資源充足的情況下,建立了最小化總時(shí)間長(zhǎng)度為目標(biāo)的優(yōu)化模型.將實(shí)際模型轉(zhuǎn)化為一個(gè)帶技能匹配的三次匹配問(wèn)題,利用匈牙利算法和遺傳算法混合求解,同時(shí)為了優(yōu)化解情況,引入了內(nèi)嵌精英匹配的選擇算子和動(dòng)態(tài)的變異概率.結(jié)果證明,該算法能有效解決對(duì)應(yīng)問(wèn)題.

本文的研究重點(diǎn)是服務(wù)資源充足的情況下的單次單任務(wù)安排,即對(duì)一名服務(wù)人安排一個(gè)維修任務(wù).但服務(wù)資源不足時(shí),一名工人一次需要指派多個(gè)任務(wù),這就涉及針對(duì)一個(gè)服務(wù)人的多任務(wù)安排.另外,為了進(jìn)一步提高客戶滿意度,需要進(jìn)一步完善約束條件,包括時(shí)間窗等,對(duì)相關(guān)模型的歸納求解是后續(xù)研究的方向.

圖10 混合遺傳算法與傳統(tǒng)遺傳算法平均值的對(duì)比

表5 擴(kuò)充仿真實(shí)例

表6 三種算法對(duì)比結(jié)果