基于貪心算法和遺傳算法的倉(cāng)儲(chǔ)車(chē)輛調(diào)度算法

王友釗，彭宇翔，潘芬蘭

(浙江大學(xué)儀器科學(xué)與工程學(xué)系，浙江杭州310027)

0 引言

隨著現(xiàn)代物流技術(shù)的發(fā)展，自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)在生產(chǎn)和流通領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用。自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)的管理技術(shù)，特別是調(diào)度技術(shù)日益成為自動(dòng)化倉(cāng)儲(chǔ)系統(tǒng)的關(guān)鍵技術(shù)之一。一般任務(wù)調(diào)度算法有2種:一種是累積一定任務(wù)后的統(tǒng)一調(diào)度，稱(chēng)為靜態(tài)調(diào)度;另一種是調(diào)度安排隨著新任務(wù)的進(jìn)入而改變，稱(chēng)為動(dòng)態(tài)調(diào)度。本文提出的算法主要解決大型倉(cāng)庫(kù)中運(yùn)輸車(chē)輛的靜態(tài)任務(wù)調(diào)度問(wèn)題。

任務(wù)調(diào)度的目標(biāo)是把任務(wù)分配到各被調(diào)車(chē)輛上，安排車(chē)輛的執(zhí)行次序，使其在滿足約束前提下完成時(shí)間最短。任務(wù)調(diào)度問(wèn)題是經(jīng)典的NP-Hard問(wèn)題，為解決這一問(wèn)題許多學(xué)者提出了多種啟發(fā)式調(diào)度算法，例如:模擬退火算法、蟻群調(diào)度算法、BDCP 調(diào)度法等［1，2］。遺傳算法(genetic algorithm，GA)因其可比其他調(diào)度算法獲得更好的解，而被應(yīng)用得最多的。特別是，如果把其他算法的解作為遺傳算法初始群中的個(gè)體，往往能獲得更好的解，缺點(diǎn)是遺傳算法執(zhí)行時(shí)間比其他調(diào)度算法長(zhǎng)得多［3，4］。

本文是在一種基于遺傳算法的倉(cāng)儲(chǔ)車(chē)輛調(diào)度方法的啟發(fā)下［5，6］，提出了一種基于貪心算法和遺傳算法的倉(cāng)儲(chǔ)車(chē)輛調(diào)度算法。不僅克服了遺傳算法在任務(wù)調(diào)度上的編碼限制，而且貪心算法的加入使得融合算法性能大大提高。此算法還可以應(yīng)用在多任務(wù)多處理器求最短完成時(shí)間的靜態(tài)調(diào)度方面。

1 相關(guān)理論

倉(cāng)儲(chǔ)車(chē)輛調(diào)度屬于多任務(wù)多處理器調(diào)度的一種，可分為任務(wù)分配和任務(wù)排序兩部分。此前已有學(xué)者采用遺傳算法解決該問(wèn)題。該調(diào)度方法編碼復(fù)雜，并且由于其遺傳算法的交叉和變異過(guò)程極易產(chǎn)生非可行解的個(gè)體，這些個(gè)體經(jīng)修正后隨機(jī)性降低，算法的全局搜索能力大大減弱。本文的算法采用遺傳算法優(yōu)化任務(wù)分配，采用貪心算法優(yōu)化任務(wù)排序。貪心算法的加入不僅使得遺傳算法在個(gè)體編碼簡(jiǎn)化和運(yùn)行時(shí)間縮短，同時(shí)排除了不可行解的出現(xiàn)，并增強(qiáng)了全局搜索能力。

1.1 貪心算法

貪心算法是一種常用的求解最優(yōu)化問(wèn)題的簡(jiǎn)單、迅速的方法。貪心算法總是做出在當(dāng)前看來(lái)最好的選擇，它所作的每一個(gè)選擇都是在當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇，并希望通過(guò)每次所作的貪心選擇最終得到問(wèn)題最優(yōu)解［7］。貪心算法是一種快速簡(jiǎn)易的求解旅行商問(wèn)題(traveling salesman problem，TSP)的方法［8，9］，其求解的基本思想是優(yōu)先選擇當(dāng)前點(diǎn)的最短邊。每次選擇邊的規(guī)則為

1)不會(huì)引起頂點(diǎn)度數(shù)大于等于3;

2)除非選取的邊為最后一條邊，所選取的邊不應(yīng)形成回路。

本文貪心算法是當(dāng)每輛車(chē)分配到任務(wù)后，對(duì)任務(wù)執(zhí)行的先后進(jìn)行排序，獲得單個(gè)車(chē)輛完成任務(wù)的最優(yōu)解。單車(chē)輛的任務(wù)排序可視為一種TSP。經(jīng)任務(wù)分配后，單車(chē)輛任務(wù)量不大，即TSP中途經(jīng)點(diǎn)較少的情況下，貪心算法十分適用此排序問(wèn)題。

1.2 遺傳算法

遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程，搜索最優(yōu)解的方法，具有隱式并行性和很好的全局尋優(yōu)能力。遺傳算法基本操作過(guò)程如圖1所示，其構(gòu)成要素主要包括計(jì)算適應(yīng)度、選擇算子、交叉算子和變異算子［10］。

圖1 遺傳算法基本操作流程Fig 1 Basic operation flow chart of genetic algorithm

本文采用遺傳算法尋求最優(yōu)的任務(wù)分配方式，個(gè)體的基因型僅表示調(diào)度方法的任務(wù)分配。當(dāng)判定個(gè)體適應(yīng)度時(shí)，根據(jù)分配的任務(wù)采用貪心算法依次求得每輛車(chē)的執(zhí)行時(shí)間。使用遺傳算法的好處在于，無(wú)論初始化、交叉、變異得到的基因型都不會(huì)存在不可行解，確保了隨機(jī)性和全局搜索能力。

2 算法實(shí)現(xiàn)

本文的算法是以遺傳算法為框架，應(yīng)用貪心算法簡(jiǎn)化其編碼復(fù)雜度和計(jì)算適應(yīng)度。最優(yōu)解的求解過(guò)程依賴(lài)于遺傳算法。遺傳算法實(shí)現(xiàn)流程如圖2所示。計(jì)算適應(yīng)度環(huán)節(jié)主要使用貪心算法，對(duì)每輛車(chē)分配的任務(wù)進(jìn)行查表的方式獲得執(zhí)行時(shí)間最短的任務(wù)排序，同時(shí)獲得并記錄其個(gè)體代表的調(diào)度方案的執(zhí)行時(shí)間，從而求得個(gè)體適應(yīng)度。

圖2 遺傳算法實(shí)現(xiàn)流程Fig 2 Realization flow chart of genetic algorithm

2.1 遺傳算法的定義與設(shè)置

遺傳算法在編碼設(shè)計(jì)中常采用二進(jìn)制編碼、格雷碼和浮點(diǎn)編碼等。本文采用整數(shù)編碼，所需調(diào)度任務(wù)數(shù)為Nt，可調(diào)度車(chē)輛數(shù)為Nv。個(gè)體的染色體可編碼為:長(zhǎng)度Nt位，每位Nv種基因型。將所有任務(wù)編號(hào)為0，1，2，…，(Nt-1)，車(chē)輛編號(hào)為0，1，2，…，(Nv-1)。例如:有 8 項(xiàng)運(yùn)輸任務(wù)和4輛可調(diào)度車(chē)，每個(gè)個(gè)體編碼為一個(gè)8位字串x∈{0，1，2，3}，其中每位有4種編碼選擇。個(gè)體型與對(duì)應(yīng)分配方式如表1。

表1 8任務(wù)4車(chē)輛編碼示例Tab 1 Coding example of 8 tasks of 4 vehicles

每個(gè)個(gè)體代表一個(gè)調(diào)度方案，此編碼的個(gè)體型只能反映調(diào)度中的分配方案，具體調(diào)度方案需要經(jīng)過(guò)貪心算法得到。

選擇算子采用確定式采樣(deterministic sampling)選擇。設(shè)群體大小為M，個(gè)體i的適應(yīng)度為Fi。群體中每個(gè)個(gè)體在下一代群體中的期望生存數(shù)目Ni

用Ni的整數(shù)部分?Ni」確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目。由該步共可確定出下一代群體中的個(gè)個(gè)體。按照Ni的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排序，順序取前個(gè)個(gè)體加入到下一代群體中。至此可完全確定出下一代群體中的M個(gè)個(gè)體［11］。

交叉算子采用單點(diǎn)交叉(one-point crossover)。經(jīng)確定式采樣選擇好的個(gè)體，以交叉概率Pc參與交叉操作。在參與交叉操作的個(gè)體編碼中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換2個(gè)配對(duì)的個(gè)體部分的染色體。

變異算子采用均勻變異(uniform mutation)。個(gè)體編碼串中每一個(gè)基因座都為變異點(diǎn)，每個(gè)變異點(diǎn)以較小的變異概率Pm從符合的基因范圍內(nèi)取一隨機(jī)數(shù)來(lái)替代原有基因值。

選擇算子會(huì)讓適應(yīng)度更高的個(gè)體更多地保留，交叉、變異等操作產(chǎn)生出新的優(yōu)良個(gè)體。但由于這些操作的隨機(jī)性，它們也可能破壞原有適應(yīng)度較好的個(gè)體。如圖2所示，新一代群體中會(huì)保留上一代群體中適應(yīng)度最高的個(gè)體，該操作保證了遺傳算法的收斂性并加快了進(jìn)化的效率。

2.2 貪心算法與適應(yīng)度

貪心算法主要應(yīng)用在根據(jù)已有任務(wù)分配下，計(jì)算車(chē)輛最短所需的執(zhí)行時(shí)間。個(gè)體的執(zhí)行時(shí)間是評(píng)判該個(gè)體優(yōu)劣的主要依據(jù)，所需的執(zhí)行時(shí)間越長(zhǎng)，說(shuō)明該方案越差，個(gè)體的適應(yīng)度也越低。倉(cāng)庫(kù)中的運(yùn)輸車(chē)輛如同多臺(tái)可并行執(zhí)行任務(wù)的處理器，為了實(shí)現(xiàn)資源優(yōu)化利用，調(diào)度者希望盡可能多地利用車(chē)輛，最好每輛運(yùn)輸車(chē)都分配有任務(wù)，達(dá)到車(chē)輛資源的充分利用。因此，本算法在求最后適應(yīng)度值時(shí)，增加了罰函數(shù)，對(duì)于出現(xiàn)不均分配的個(gè)體予以適應(yīng)度上的懲罰。

計(jì)算適應(yīng)度環(huán)節(jié)流程如圖3，可細(xì)分為:

1)對(duì)個(gè)體編碼串進(jìn)行解碼，即按照編碼串對(duì)調(diào)度車(chē)輛進(jìn)行任務(wù)分配;

2)貪心算法求得每輛運(yùn)輸車(chē)完成所分配任務(wù)預(yù)計(jì)執(zhí)行最短的時(shí)間;

3)取個(gè)體中最長(zhǎng)的執(zhí)行時(shí)間，作為整個(gè)調(diào)度方案的執(zhí)行時(shí)間;

4)根據(jù)調(diào)度方案的執(zhí)行時(shí)間T和罰參數(shù)P，求解適應(yīng)度函數(shù)如下

其中，Pi為調(diào)度方案i中有Pi輛調(diào)度車(chē)未被分配任務(wù)。

圖3 計(jì)算適應(yīng)度流程Fig 3 Flow chart of calculating fitness

個(gè)體基因先通過(guò)解碼得到任務(wù)分配情況，再由貪心算法通過(guò)查表對(duì)任務(wù)進(jìn)行排序求每輛車(chē)執(zhí)行時(shí)間。設(shè)3輛可調(diào)度車(chē)編號(hào)為A，B，C，6項(xiàng)需執(zhí)行任務(wù)編號(hào)為ⅰ，ⅱ，ⅲ，ⅳ，ⅴ，ⅵ。表2中每個(gè)單元格數(shù)值表示，完成橫向任務(wù)后再去處理縱向任務(wù)所需要花的時(shí)間值;橫向?yàn)檐?chē)編號(hào)代表，由車(chē)輛初始位置執(zhí)行縱向任務(wù)所需要花的時(shí)間值。時(shí)間值設(shè)置為1～100 min。

表2 執(zhí)行時(shí)間表Tab 2 Executing time table

例如:個(gè)體222110對(duì)其使用貪心算法，查表求解最短執(zhí)行時(shí)間，其步驟如下:

1)由解碼得A車(chē)處理任務(wù)ⅵ，B車(chē)處理任務(wù)ⅳ和ⅴ，C車(chē)處理任務(wù)ⅰ，ⅱ和ⅲ。

2)以C車(chē)為例，查C車(chē)初始位置執(zhí)行ⅰ，ⅱ，ⅲ的時(shí)間值選取最小，先執(zhí)行。如表2選?、⑾葓?zhí)行，查詢(xún)ⅱ完成后ⅰ，ⅲ的時(shí)間值選最?、　Ｗ詈蟛榈芒⊥瓿珊髨?zhí)行ⅲ所需時(shí)間，得此調(diào)度方案下C車(chē)的最佳任務(wù)排序?yàn)棰ⅰ　?，時(shí)間值為2+10+43=55 min。同理求得A車(chē)任務(wù)排序ⅵ，時(shí)間值89min;B車(chē)任務(wù)排序ⅴ→ⅳ，時(shí)間值66 min。

3)個(gè)體222110對(duì)應(yīng)的調(diào)度方案執(zhí)行時(shí)間取最長(zhǎng)的A車(chē)，時(shí)間值89 min。

4)按式(2)求出該個(gè)體適應(yīng)度為2.110。此處保留三位小數(shù)。

由上可見(jiàn):貪心算法由一個(gè)僅表示任務(wù)分配的遺傳算法個(gè)體編碼串，經(jīng)過(guò)解碼、貪心算法求解、適應(yīng)度函數(shù)，形成了一個(gè)完整的調(diào)度方案。用最快速、簡(jiǎn)便的方法在極短的時(shí)間里給出了最優(yōu)或是次優(yōu)的任務(wù)排序解。獲得每個(gè)任務(wù)由哪輛車(chē)完成，每輛車(chē)先后執(zhí)行哪些任務(wù)，預(yù)計(jì)需要多少時(shí)間等信息。

3 實(shí)驗(yàn)和結(jié)果分析

實(shí)驗(yàn)程序設(shè)3輛可調(diào)度車(chē)編號(hào)為A，B，C，6項(xiàng)需執(zhí)行任務(wù)編號(hào)為ⅰ，ⅱ，ⅲ，ⅳ，ⅴ，ⅵ。各任務(wù)執(zhí)行時(shí)間值如表2。種群大小M設(shè)置為M=NtNv×2=36。進(jìn)化代數(shù)Ge=100代，交叉概率Pc=0.7，變異概率Pm=0.01。初代個(gè)體編碼串與時(shí)間值表(表2)均為隨機(jī)數(shù)產(chǎn)生。圖4顯示了此算法在進(jìn)化中，種群的平均時(shí)間值和最優(yōu)個(gè)體時(shí)間值的變化過(guò)程。由圖可見(jiàn)，遺傳算法在前40代，種群的平均時(shí)間值明顯下降，意味著整個(gè)種群在向更優(yōu)進(jìn)化。由于該算法使用了最優(yōu)保存策略，故最優(yōu)個(gè)體時(shí)間值折線不像平均時(shí)間值那樣呈現(xiàn)波動(dòng)進(jìn)化。除非當(dāng)進(jìn)化中產(chǎn)生更優(yōu)個(gè)體才會(huì)替換原有的，時(shí)間值從而進(jìn)一步降低，否則，一直保持下去。該例最后一代種群的最優(yōu)個(gè)體，即算法的最終解為:

個(gè)體基因:012011;

A車(chē):ⅰ→ⅲ，時(shí)間值51 min;

B車(chē):ⅴ→ⅱ→ⅵ，時(shí)間值52 min;

C車(chē):ⅳ，時(shí)間值16 min;

調(diào)度時(shí)間值:52 min。

圖4 不同進(jìn)化代數(shù)的時(shí)間值變化Fig 4 Time value change of different numbers of evolution generation

算法中進(jìn)化代數(shù)Ge與種群大小M都是隨著調(diào)度量的需求而變化的。經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，尤其種群數(shù)量M極大影響著算法的搜索能力。若M設(shè)置過(guò)小，遺傳算法容易早熟，全局搜索能力明顯變差。相較而言代數(shù)Ge的變化，只是影響已有種群中發(fā)生交叉、變異等操作發(fā)生的概率。因此，當(dāng)M不大或Pc，Pm設(shè)置較小時(shí)，Ge變化的作用并不明顯。若把種群數(shù)量縮小一半至18進(jìn)化情況見(jiàn)圖5。平均時(shí)間值折線顯示種群較早就停止進(jìn)化，有明顯的早熟現(xiàn)象。且最終解的時(shí)間值為57 min，并非最優(yōu)調(diào)度方案?？梢?jiàn)種群數(shù)量M的縮小使得搜索能力大大減弱。

圖5 種群數(shù)量縮小一半的時(shí)間值變化Fig 5 Time value change of half population quantity

若保持M=36，將進(jìn)化代數(shù)減少一半至50，進(jìn)化情況見(jiàn)圖6。由平均時(shí)間值折線可見(jiàn)，進(jìn)化情況與圖4相似，并未產(chǎn)生早熟現(xiàn)象。通過(guò)50代的進(jìn)化也獲得了最優(yōu)調(diào)度方案。為確保進(jìn)化完整和適應(yīng)更大調(diào)度量，進(jìn)化代數(shù)應(yīng)設(shè)置得足夠大。

4 結(jié)論

圖6 遺傳代數(shù)減少一半的時(shí)間值變化Fig 6 Time value change of half inheritance generations

本文提出的基于貪心算法和遺傳算法的倉(cāng)儲(chǔ)車(chē)輛調(diào)度算法，經(jīng)編程實(shí)現(xiàn)與實(shí)驗(yàn)證明:本方法簡(jiǎn)化了遺傳算法對(duì)車(chē)輛調(diào)度應(yīng)用中復(fù)雜的編碼方法。避免了由于約束條件而將個(gè)體調(diào)整為可行解時(shí)而產(chǎn)生的非隨機(jī)性，不僅避免遺傳算法易出現(xiàn)的早熟的困境，也提高全局搜索能力。本算法的交叉、變異等操作使用起來(lái)更加靈活，限制更少，使用者可根據(jù)使用范圍，選擇更適用的操作種類(lèi)。本算法還可通過(guò)改動(dòng)任務(wù)、時(shí)間表、罰函數(shù)等，以適用于其他更高要求的多任務(wù)多處理器的調(diào)度。

［1］鐘一文，楊建剛.求解多任務(wù)調(diào)度問(wèn)題的免疫蟻群算法［J］.模式識(shí)別與人工智能，2006，19(1):73-78.

［2］Sapkal SU，Laha D.An improved scheduling heuristic algorithm for no-wait flow shops on total flow time cirterion［C］∥2011 the 3rd International Conf on Electronics Computer Technology，2011:159-163.

［3］Gupta S，Agarwal G，Kumar V.Task scheduling in multiprocessor system using genetic algorithm［C］∥2010 the 2nd International Conf on Machine Learning and Computing，2010:267-271.

［4］Correa R C，F(xiàn)erreira A，Rebreyend P.Scheduling multiprocessor tasks with genetic algorithms［J］.IEEE Trans on Parallel and Distributed Systems，1999，10(8):825-837.

［5］郭小溪.RFID室內(nèi)倉(cāng)儲(chǔ)車(chē)輛的智能導(dǎo)航與調(diào)度技術(shù)［D］.杭州:浙江大學(xué)，2011:4-8.

［6］韓曉路.基于局部搜索遺傳算法的倉(cāng)庫(kù)車(chē)輛調(diào)度優(yōu)化研究［J］.物流技術(shù)，2011，30(4):65-67.

［7］魏英姿，趙明揚(yáng)，黃雪梅，等.求解TSP問(wèn)題的貪心遺傳算法［J］.計(jì)算機(jī)工程，2004，30(19):19-34.

［8］Chakraborty N，Akella S，Wen JT.Coverage of a planar point set with multiple robots subject to geometric constraints［J］.IEEE Trans on Automation Science and Engineering，2010，7(1):111-122.

［9］王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［M］.北京:電子工業(yè)出版社，2004:134-142.

［10］陳國(guó)良.遺傳算法及其應(yīng)用［M］.北京:人民郵電出版社，1996:51-98.

［11］周 明，孫樹(shù)棟.遺傳算法原理及應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，1999:47-48.