基于貪心遺傳混合算法的倉庫貨物集成分配研究

張昊，王飛

（河海大學商學院，江蘇南京211100）

基于貪心遺傳混合算法的倉庫貨物集成分配研究

張昊，王飛

（河海大學商學院，江蘇南京211100）

針對運輸車輛和倉庫裝卸吊車作業的合理分派與調度問題，考慮抵達倉庫的運輸車輛的停靠總時間和平均裝卸吊車遷移次數為目標，在偏好車位的約束條件下，建立連續車位和裝卸吊車分配的規劃模型。利用貪心算法和遺傳算法相結合的方式，設計了一種混合進化算法提高倉庫貨物平臺的作業效率。最后的仿真求解結果表明：相對于貪心算法，平均收斂代數優化率達到86.7%；相對于遺傳算法，平均收斂時間優化率達到17.9%；該算法能夠在可接受的計算時間內獲得穩定的滿意解，新的車位和裝卸吊車分配策略較好的解決了偏好車位約束條件下的貨物集成分配問題。

貪心算法；遺傳算法；貨物集成；貨物分配

倉庫被看成一個無附加價值的成本中心，而現在倉庫不僅被看成是形成附加價值過程中的一部分，而且被看成是企業成功經營中的一個關鍵因素［1］。倉庫管理各個環節管理確保企業及時準確地掌握貨物的調度信息，合理管理貨物庫存［2］。而倉庫貨物的集成與分配合理化調度是企業的重要組成部分［3］，倉庫貨物平臺作為企業日常貨物運輸的關鍵節點，必將會發揮更大的作用［4］。倉庫的車位分配問題是提高貨物平臺運營效率的一個重要因素［5］，與之銜接的裝卸吊車分配問題則是貨物裝卸作業的關鍵［6］。車位和裝卸吊車是企業的倉庫貨物平臺資源，如何處理好有限的車位、裝卸吊車資源和運輸車輛的需要三者時間的矛盾，是倉庫作業計劃中的一個重要問題。在實際作業中裝卸吊車數量和裝卸吊車的成本限制，倉庫需要在最大限度的裝卸吊車數量和有限車位下，進行集成貨物優化配置來提高運行效率。

本研究從運輸車輛的等待時間，成本最低的停靠位置，離開時間，裝卸吊車的移動時間和裝卸作業效率等幾方面來研究倉庫貨物分配問題，利用抵達倉庫的運輸車輛的停靠總時間和平均裝卸吊車遷移次數構建目標函數，在偏好車位的約束條件下，建立連續車位和裝卸吊車分配的規劃模型。利用貪心算法和遺傳算法相結合的方式，設計了一種混合進化算法提高倉庫貨物平臺的作業效率。

1　倉庫貨物集成與分配建模

1.1問題描述

運輸車輛抵達倉庫，倉庫月臺調度員將根據相關信息和調度策略將車位和貨物平臺分配給車輛。考慮到車位與貨物平臺分配問題為動態性和連續性［7-8］，只要運輸車輛條件滿足停靠的月臺長度，車輛便可沿連續貨物平臺停靠，多輛運輸車輛可以同時停靠月臺。本研究提出的目標函數綜合3個方面的因素：對運輸公司而言，希望到達的車輛被分配到理想的偏好車位且處理時間延誤最小；對月臺管理人員而言，希望到達倉庫的運輸車輛數量和貨物吞吐量能最大。當車輛停靠時，占用車位單元數取決于其車長，占用時間取決于貨物平臺裝卸處理時間。本研究將月臺視為連續的車位，考慮的抵達車輛等待裝卸時間的約束條件，以最小化車輛總在車位時間和最小化平均月臺移動次數為目標，建立的連續車位和裝卸吊車集成分配模型將基于如下合理假設：

1）每輛運輸車輛必須被服務且被服務一次（不考慮車位的移動），且處理時間取決于所在車位、貨物平臺的裝卸吊車數量，與車輛的距離、貨物運輸以及其他因素等無關；

2）車位資源視為連續線性的，被劃分為盡可能多且相等的微小停靠單元，多輛運輸車輛可以同時停靠；

3）每輛車設有同時作業的最大裝卸吊車數和最小裝卸吊車數，當可用裝卸吊車數量不小于最小裝卸吊車數時才能開始作業，并且不能大于最大裝卸吊車數，且分散的閑置裝卸吊車不能橫跨工作，裝卸吊車只能在貨物平臺固定的位置為停靠的車輛進行裝卸；

4）每輛運輸車都有一個最優停靠偏好位置，偏離偏好車位會增加停靠時長，車位計劃在零時刻開始，車輛只有抵達車位才能進行裝卸作業。此外，車輛停靠作業過程中的停靠時間和離開時間對于不同運載量的車輛差異不大，且相對整個停靠時間很小，在此忽略不計。

1.2模型建立

其中，L為連續貨物平臺的總長度，Hci為車輛i要處理的貨物量，nit在t時刻服務車輛i的裝卸吊車數量，di為車輛i的離開時間期望，Bi為車輛i的實際開始處理時間。車輛抵達倉庫后才能開始被服務，且車輛的裝卸時間與裝卸吊車的數量和作業速度有關。最后對貨物平臺連續車位偏好位置的定義。則約束條件為：

如果車輛i完全位于車輛j的左側，則εij=1，否則為0。如果車輛i完全位于車輛j的后方，則ζij=1，否則為0。則車輛i和j在時空圖中的位置不重疊，即車輛i和j在貨物平臺連續月臺上不能停靠在同一位置上。約束條件如下：

若能夠同時分配給車輛的最小裝卸吊車數和最大裝卸吊車數分別為和，則每輛運輸車分配的裝卸吊車數的范圍為：

在時間段j內，如果裝卸吊車k為車輛i服務，則取λijk=1，否則為0。其中C=｛1，2，…，c｝為可利用裝卸吊車數的集合。則確保每個時間段一臺裝卸吊車最多只為一輛車服務，且每個時間分配給車輛的裝卸吊車數不能超過總的裝卸吊車數，則約束條件為：

車輛i等待停靠的時間和等待裝卸吊車的時間分別為Wi和Wci，車輛i等待排隊進倉庫的參數為Mli，則限制每輛運輸車輛的等待時間小于其最大可接受的等待時間約束條件為：

2　貪心遺傳混合算法

容忍度約束下連續運輸車輛和裝卸吊車作業集成分配問題主要由兩個子問題組成，即車位分配問題與裝卸吊車分配問題。本研究設計了一種基于貪心算法和遺傳算法的混合進化算法［9］，貪心算法生成相應的車位調度計劃，遺傳算法生成相應的裝卸吊車調度計劃。

2.1貪心算法

貪心策略就是指它在每一步都做出當時看起來最佳的選擇［10］，它總是做出局部最優的選擇，寄希望這樣的選擇能導致全局最優解［11-12］。對于陸續抵達倉庫的車輛建立兩個集合，分別命名為Set A，Set B。Set A代表陸續抵達的車輛集合，Set B代表抵達倉庫后已分配車位的車輛集合。每輛抵達倉庫的運輸車輛都有一個實際抵達時間ai和一個離開時間期望di。把陸續抵達倉庫的車輛加入到Set A集合中，然后根據貪心策略選擇Set A中的車輛把它加入到Set B中去，貪心算法步驟：

Step1：初始化各集合：Set A，存放抵達倉庫待處理的車輛集合，其初始化大小就是抵達車輛的總條數；Set B，初始化為空；

Step2：判斷Set A集合是否為空，若為空，程序結束；

Step3：獲取當前車位的占用現狀，以及Set A中車輛的偏好車位等參數；

Step4：利用貪心策略從Set A中選擇一輛運輸車輛，使得該車輛停靠后的目標函數值最小；

Step 5：將停靠的車輛從Set A中刪除，加入到Set B中，轉向Step2。

2.2遺傳算法

通過遺傳算法產生決策變量［13］，然后運用裝卸吊車啟發式算法在每一代中產生從屬變量。染色體編碼中每個基因的位置表示車輛的ID，相應的值表示在滿足公式（4）的約束條件下隨機產生的決策變量n。裝卸吊車分配問題仍是一個最小化問題，因此它的目標函數值轉換為適應度函數：

由于車輛停靠貨物平臺的隨機性較大，有時會使基因出現“退化”現象，即采用輪盤賭的選擇策略［14］，使得適應度較高的基因失去選擇的機會，使得收斂到最優解。交叉操作采用兩點交叉法［15］，其交叉后得到的子代滿足公式（5）的約束條件。在獲得車輛i的車位位置（xi，xi+li）和當前車位調度計劃中的時間窗（yi，ci）后，根據遺傳算法獲取分配給運輸車輛i的裝卸吊車數n。假設位置基因選出的要參加交叉的粒子為xi，則有目的的選取的交叉粒子為：

其中，α＞0為步長因子，‖xi-xi′‖表示兩個基因粒子之間的二范數。采用取代變異的方法［16］，即隨機的選擇一個取代位置，并用當前個體中滿足公式（5）約束條件的基因信息取代當前位置上的基因信息。當達到設定值的最大迭代次數，算法終止并輸出結果然后，檢查相應車位空間（xi，xi+li）上空閑的裝卸吊車數量C，如果C≥n，選擇合適的裝卸吊車從前往后依次分配給船舶i；如果C＜n，則在滿足沒有交叉的前提下，從鄰近位置移動裝卸吊車到所須位置，直到滿足所需的裝卸吊車數量。

3　算例驗證

3.1參數設置

倉庫貨物平臺選取了月臺長為120米的連續車位，裝卸吊車總數為5，有12輛運輸車輛陸續抵達倉庫，并以第一輛抵達倉庫車輛的抵達時間為基準0，具體算例如表1所示。

表1　參數假設

3.2模擬對比

在分析時若考慮車輛偏好車位、等待時間和裝卸吊車移動策略對停靠計劃的影響，車輛的等待時間、目標函數值都是最小的；反之，車輛的等待時間、目標函數值最大。由此反映了車輛的偏好車位、等待時間以及裝卸吊車遷移策略對停靠過程中車輛的等待時間與在倉庫貨物平臺總時間成本有較大的影響，驗證模型與算法的有效性。本研究將從以下3個方面驗證算法的有效性，對比分析如表2所示。

表2　對比分析

根據表2模擬的3種情景分別對比分析：

情景1：綜合考慮車輛偏好車位、等待時間以及裝卸吊車遷移策略對停靠計劃的影響。根據算例數據，經求解可得偏所有車輛總的等待時間t=22，所有車輛總在停靠的時間成本f=93.29。

情景2：不考慮車輛偏好車位、等待時間對停靠計劃的影響，只考慮裝卸吊車遷移策略對車輛停靠計劃影響。根據算例數據，經求解可得所有車輛總的等待時間t=67.13，所有車輛總在港的時間成本f=105.22。

情景3：不考慮船舶偏好車位、等待時間對停靠計劃的影響，也不考慮裝卸吊車遷移策略對車輛停靠計劃影響。根據算例數據，經求解可得所有車輛總的等待時間t=67.13，所有車輛總在港的時間成本f=127.50。

3.3性能對比

為了分析本研究貪心遺傳混合算法中選擇策略的選取合理性，實驗過程中分別貪心算法和遺傳算法分別與本研究的算法進行比較。并且將基于以上選擇策略的。參數的取值均為表1所示，在相同參數取值下每組實驗重復10次，取相應的平均收斂代數和平均收斂時間。如表3所示。

表33　種算法性能比較

從表3可知，基于貪心遺傳混合算法具有最小的平均收斂代數為15，且平均收斂時間為273s，平均收斂代數表現上，貪心算法僅次于貪心遺傳混合算法，優化率為86.7%；而平均收斂時間表現上，遺傳算法需要僅次于貪心遺傳混合算法，優化率為17.9%。分析其原因，主要是因為在貪心算法中較小的位置基因規模中未能發揮出優勢；而遺傳算法在演化代數內并不能考慮到所有的貨物集成分配因素。正基于以上原因，在倉庫的貨物集成分配中選擇貪心遺傳混合算法。

4　結論

本研究在倉庫貨物集成分配研究的基礎上，引入運輸車輛抵達倉庫等待裝卸時間的策略，考慮抵達倉庫的運輸車輛的停靠總時間和平均裝卸吊車遷移次數構造目標函數。分別利用貪心算法生成相應的車位調度計劃，遺傳算法生成相應的裝卸吊車調度計劃，該貪心遺傳混合算法綜合模擬倉庫貨物集成與分配。最后在平均收斂代數和平均收斂時間方面，比較了貪心算法、遺傳算法與貪心遺傳混合算法的性能。結果顯示，貪心遺傳混合算法在平均收斂代數和平均收斂時間上均優于其他兩種算法，說明該混合算法可作為企業的倉庫貨物集成與分配的參考性分析。

［1］張彥嘉.X制造企業倉庫規劃與管理研究［D］.大連：大連海事大學，2014.

［2］唐佳瑩，張瑞林，季君君，等.RFID在紡織企業倉庫管理系統中的應用［J］.物聯網技術，2012（9）:28-30.

［3］楊文強，鄧麗，費敏銳，等.基于改進禁忌搜索的多目標自動化倉庫調度［J］.計算機集成制造系統，2013（8）:2097-2104.

［4］楊銘，秦華容，陳蔭三.區域公路貨物周轉量結構分析與推算方法［J］.交通運輸工程學報，2011（5）:93-100.

［5］邢麗娟，李建國.立體車庫車位分配仿真與分析［J］.鐵路計算機應用，2011，20（10）:32-34.

［6］鄭忠，周超，陳開.基于免疫遺傳算法的車間天車調度仿真模型［J］.系統工程理論與實踐，2013，33（1）:223-229.

［7］李曉君，謝新連.重大件運輸的貨物分配與航速聯合優化［J］.西南交通大學學報，2015，50（4）:747-754.

［8］周華.基于電子標簽的物流貨物自動分配策略設計［J］.自動化與儀器儀表，2016（1）:104-105.

［9］王友釗，彭宇翔，潘芬蘭.基于貪心算法和遺傳算法的倉儲車輛調度算法［J］.傳感器與微系統，2012，31（10）:125-128

［10］聶長海，蔣靜.覆蓋表生成的可配置貪心算法優化［J］.軟件學報，2013（7）:1469-1483.

［11］宮國順.貪心算法在P類問題求解中的應用［J］.電腦知識與技術，2011，7（2）:444-446.

［12］李寶磊，施心陵，茍常興，等.多元優化算法及其收斂性分析［J］.自動化學報，2015，41（5）:949-959.

［13］馬永杰，云文霞.遺傳算法研究進展［J］.計算機應用研究，2012，29（4）:1201-1206.

［14］魏波，喻飛，徐星，等.基于改進輪盤賭策略的交互式演化算法［J］.計算機與數字工程，2014（10）:1763-1767.

［15］劉大蓮，徐尚文.求解約束優化問題的內外交叉遺傳算法［J］.系統工程理論與實踐，2012，32（1）:189-195.

［16］閉應洲，陸建波，丁立新，等.基于有導向變異算子的GM-EA算法［J］.計算機應用研究，2010，27（4）:1249-1251.

Study on the integrated distribution warehouse based on blend of genetic and greedy algorithm

ZHANG Hao，WANG Fei
（Business School，Hohai University，Nanjing 211100，China）

For the truck and warehouse loading and unloading crane of reasonable assignment and scheduling problem considering arrived in warehouse transport vehicles docked total time and the average loading crane migration times as the goal，under the constraints of the preference of parking spaces，the establishment of continuous parking and loading and unloading crane allocation programming model.Using the greedy algorithm and genetic algorithm combination，designed a hybrid evolutionary algorithm to improve the efficiency of warehouse cargo platform.Finally the simulation to the results show that:compared with the greedy algorithm，optimizing the average Algebraic Convergence rate reached 86.7%；compared with the genetic algorithm，average convergence time optimization rate reached 17.9%；the algorithm can obtain satisfactory solutions in acceptable computation time，new parking and loading and unloading crane allocation strategy better solves the parking preference constraint goods integrated allocation problem.

greedy algorithm；genetic algorithm；integrated of goods；distribution of goods

TN01

A

1674－6236（2016）17-0007-04

2016-02-28稿件編號：201602179

國家自然科學基金項目（71372166）；江蘇高校哲學社會科學研究重點項目（2010ZDIXM004）

張昊（1992—），男，吉林大安人，碩士研究生。研究方向：財務管理。