基于貪心算法和遺傳算法的倉儲車輛調(diào)度算法

王友釗，彭宇翔，潘芬蘭

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

0 引言

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

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

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

1 相關理論

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

1.1 貪心算法

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

1)不會引起頂點度數(shù)大于等于3;

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

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

1.2 遺傳算法

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

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

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

2 算法實現(xiàn)

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

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

2.1 遺傳算法的定義與設置

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

表1 8任務4車輛編碼示例Tab 1 Coding example of 8 tasks of 4 vehicles

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

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

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

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

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

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

2.2 貪心算法與適應度

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

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

1)對個體編碼串進行解碼，即按照編碼串對調(diào)度車輛進行任務分配;

2)貪心算法求得每輛運輸車完成所分配任務預計執(zhí)行最短的時間;

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

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

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

圖3 計算適應度流程Fig 3 Flow chart of calculating fitness

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

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

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

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

2)以C車為例，查C車初始位置執(zhí)行ⅰ，ⅱ，ⅲ的時間值選取最小，先執(zhí)行。如表2選取ⅱ先執(zhí)行，查詢ⅱ完成后ⅰ，ⅲ的時間值選最小ⅰ。最后查得ⅰ完成后執(zhí)行ⅲ所需時間，得此調(diào)度方案下C車的最佳任務排序為ⅱ→ⅰ→ⅲ，時間值為2+10+43=55 min。同理求得A車任務排序ⅵ，時間值89min;B車任務排序ⅴ→ⅳ，時間值66 min。

3)個體222110對應的調(diào)度方案執(zhí)行時間取最長的A車，時間值89 min。

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

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

3 實驗和結(jié)果分析

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

個體基因:012011;

A車:ⅰ→ⅲ，時間值51 min;

B車:ⅴ→ⅱ→ⅵ，時間值52 min;

C車:ⅳ，時間值16 min;

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

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

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

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

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

4 結(jié)論

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

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

［1］鐘一文，楊建剛.求解多任務調(diào)度問題的免疫蟻群算法［J］.模式識別與人工智能，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)倉儲車輛的智能導航與調(diào)度技術［D］.杭州:浙江大學，2011:4-8.

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

［7］魏英姿，趙明揚，黃雪梅，等.求解TSP問題的貪心遺傳算法［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］王曉東.計算機算法設計與分析［M］.北京:電子工業(yè)出版社，2004:134-142.

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

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