張昊，王飛

（河海大學(xué)商學(xué)院，江蘇南京211100）

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

張昊，王飛

（河海大學(xué)商學(xué)院，江蘇南京211100）

針對(duì)運(yùn)輸車輛和倉庫裝卸吊車作業(yè)的合理分派與調(diào)度問題，考慮抵達(dá)倉庫的運(yùn)輸車輛的?？靠倳r(shí)間和平均裝卸吊車遷移次數(shù)為目標(biāo)，在偏好車位的約束條件下，建立連續(xù)車位和裝卸吊車分配的規(guī)劃模型。利用貪心算法和遺傳算法相結(jié)合的方式，設(shè)計(jì)了一種混合進(jìn)化算法提高倉庫貨物平臺(tái)的作業(yè)效率。最后的仿真求解結(jié)果表明：相對(duì)于貪心算法，平均收斂代數(shù)優(yōu)化率達(dá)到86.7%；相對(duì)于遺傳算法，平均收斂時(shí)間優(yōu)化率達(dá)到17.9%；該算法能夠在可接受的計(jì)算時(shí)間內(nèi)獲得穩(wěn)定的滿意解，新的車位和裝卸吊車分配策略較好的解決了偏好車位約束條件下的貨物集成分配問題。

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

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

本研究從運(yùn)輸車輛的等待時(shí)間，成本最低的?？课恢?，離開時(shí)間，裝卸吊車的移動(dòng)時(shí)間和裝卸作業(yè)效率等幾方面來研究倉庫貨物分配問題，利用抵達(dá)倉庫的運(yùn)輸車輛的?？靠倳r(shí)間和平均裝卸吊車遷移次數(shù)構(gòu)建目標(biāo)函數(shù)，在偏好車位的約束條件下，建立連續(xù)車位和裝卸吊車分配的規(guī)劃模型。利用貪心算法和遺傳算法相結(jié)合的方式，設(shè)計(jì)了一種混合進(jìn)化算法提高倉庫貨物平臺(tái)的作業(yè)效率。

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

1.1問題描述

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

1）每輛運(yùn)輸車輛必須被服務(wù)且被服務(wù)一次（不考慮車位的移動(dòng)），且處理時(shí)間取決于所在車位、貨物平臺(tái)的裝卸吊車數(shù)量，與車輛的距離、貨物運(yùn)輸以及其他因素等無關(guān)；

2）車位資源視為連續(xù)線性的，被劃分為盡可能多且相等的微小?？繂卧噍v運(yùn)輸車輛可以同時(shí)?？浚?/p>

3）每輛車設(shè)有同時(shí)作業(yè)的最大裝卸吊車數(shù)和最小裝卸吊車數(shù)，當(dāng)可用裝卸吊車數(shù)量不小于最小裝卸吊車數(shù)時(shí)才能開始作業(yè)，并且不能大于最大裝卸吊車數(shù)，且分散的閑置裝卸吊車不能橫跨工作，裝卸吊車只能在貨物平臺(tái)固定的位置為?？康能囕v進(jìn)行裝卸；

4）每輛運(yùn)輸車都有一個(gè)最優(yōu)?？科梦恢?，偏離偏好車位會(huì)增加?？繒r(shí)長，車位計(jì)劃在零時(shí)刻開始，車輛只有抵達(dá)車位才能進(jìn)行裝卸作業(yè)。此外，車輛?？孔鳂I(yè)過程中的?？繒r(shí)間和離開時(shí)間對(duì)于不同運(yùn)載量的車輛差異不大，且相對(duì)整個(gè)?？繒r(shí)間很小，在此忽略不計(jì)。

1.2模型建立

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

如果車輛i完全位于車輛j的左側(cè)，則εij=1，否則為0。如果車輛i完全位于車輛j的后方，則ζij=1，否則為0。則車輛i和j在時(shí)空?qǐng)D中的位置不重疊，即車輛i和j在貨物平臺(tái)連續(xù)月臺(tái)上不能?？吭谕晃恢蒙?。約束條件如下：

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

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

車輛i等待?？康臅r(shí)間和等待裝卸吊車的時(shí)間分別為Wi和Wci，車輛i等待排隊(duì)進(jìn)倉庫的參數(shù)為Mli，則限制每輛運(yùn)輸車輛的等待時(shí)間小于其最大可接受的等待時(shí)間約束條件為：

2　貪心遺傳混合算法

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

2.1貪心算法

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

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

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

Step3：獲取當(dāng)前車位的占用現(xiàn)狀，以及Set A中車輛的偏好車位等參數(shù)；

Step4：利用貪心策略從Set A中選擇一輛運(yùn)輸車輛，使得該車輛停靠后的目標(biāo)函數(shù)值最??；

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

2.2遺傳算法

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

由于車輛?？控浳锲脚_(tái)的隨機(jī)性較大，有時(shí)會(huì)使基因出現(xiàn)“退化”現(xiàn)象，即采用輪盤賭的選擇策略［14］，使得適應(yīng)度較高的基因失去選擇的機(jī)會(huì)，使得收斂到最優(yōu)解。交叉操作采用兩點(diǎn)交叉法［15］，其交叉后得到的子代滿足公式（5）的約束條件。在獲得車輛i的車位位置（xi，xi+li）和當(dāng)前車位調(diào)度計(jì)劃中的時(shí)間窗（yi，ci）后，根據(jù)遺傳算法獲取分配給運(yùn)輸車輛i的裝卸吊車數(shù)n。假設(shè)位置基因選出的要參加交叉的粒子為xi，則有目的的選取的交叉粒子為：

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

3　算例驗(yàn)證

3.1參數(shù)設(shè)置

倉庫貨物平臺(tái)選取了月臺(tái)長為120米的連續(xù)車位，裝卸吊車總數(shù)為5，有12輛運(yùn)輸車輛陸續(xù)抵達(dá)倉庫，并以第一輛抵達(dá)倉庫車輛的抵達(dá)時(shí)間為基準(zhǔn)0，具體算例如表1所示。

表1　參數(shù)假設(shè)

3.2模擬對(duì)比

在分析時(shí)若考慮車輛偏好車位、等待時(shí)間和裝卸吊車移動(dòng)策略對(duì)停靠計(jì)劃的影響，車輛的等待時(shí)間、目標(biāo)函數(shù)值都是最小的；反之，車輛的等待時(shí)間、目標(biāo)函數(shù)值最大。由此反映了車輛的偏好車位、等待時(shí)間以及裝卸吊車遷移策略對(duì)?？窟^程中車輛的等待時(shí)間與在倉庫貨物平臺(tái)總時(shí)間成本有較大的影響，驗(yàn)證模型與算法的有效性。本研究將從以下3個(gè)方面驗(yàn)證算法的有效性，對(duì)比分析如表2所示。

表2　對(duì)比分析

根據(jù)表2模擬的3種情景分別對(duì)比分析：

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

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

情景3：不考慮船舶偏好車位、等待時(shí)間對(duì)?？坑?jì)劃的影響，也不考慮裝卸吊車遷移策略對(duì)車輛?？坑?jì)劃影響。根據(jù)算例數(shù)據(jù)，經(jīng)求解可得所有車輛總的等待時(shí)間t=67.13，所有車輛總在港的時(shí)間成本f=127.50。

3.3性能對(duì)比

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

表33　種算法性能比較

從表3可知，基于貪心遺傳混合算法具有最小的平均收斂代數(shù)為15，且平均收斂時(shí)間為273s，平均收斂代數(shù)表現(xiàn)上，貪心算法僅次于貪心遺傳混合算法，優(yōu)化率為86.7%；而平均收斂時(shí)間表現(xiàn)上，遺傳算法需要僅次于貪心遺傳混合算法，優(yōu)化率為17.9%。分析其原因，主要是因?yàn)樵谪澬乃惴ㄖ休^小的位置基因規(guī)模中未能發(fā)揮出優(yōu)勢；而遺傳算法在演化代數(shù)內(nèi)并不能考慮到所有的貨物集成分配因素。正基于以上原因，在倉庫的貨物集成分配中選擇貪心遺傳混合算法。

4　結(jié)論

本研究在倉庫貨物集成分配研究的基礎(chǔ)上，引入運(yùn)輸車輛抵達(dá)倉庫等待裝卸時(shí)間的策略，考慮抵達(dá)倉庫的運(yùn)輸車輛的?？靠倳r(shí)間和平均裝卸吊車遷移次數(shù)構(gòu)造目標(biāo)函數(shù)。分別利用貪心算法生成相應(yīng)的車位調(diào)度計(jì)劃，遺傳算法生成相應(yīng)的裝卸吊車調(diào)度計(jì)劃，該貪心遺傳混合算法綜合模擬倉庫貨物集成與分配。最后在平均收斂代數(shù)和平均收斂時(shí)間方面，比較了貪心算法、遺傳算法與貪心遺傳混合算法的性能。結(jié)果顯示，貪心遺傳混合算法在平均收斂代數(shù)和平均收斂時(shí)間上均優(yōu)于其他兩種算法，說明該混合算法可作為企業(yè)的倉庫貨物集成與分配的參考性分析。

［1］張彥嘉.X制造企業(yè)倉庫規(guī)劃與管理研究［D］.大連：大連海事大學(xué)，2014.

［2］唐佳瑩，張瑞林，季君君，等.RFID在紡織企業(yè)倉庫管理系統(tǒng)中的應(yīng)用［J］.物聯(lián)網(wǎng)技術(shù)，2012（9）:28-30.

［3］楊文強(qiáng)，鄧麗，費(fèi)敏銳，等.基于改進(jìn)禁忌搜索的多目標(biāo)自動(dòng)化倉庫調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013（8）:2097-2104.

［4］楊銘，秦華容，陳蔭三.區(qū)域公路貨物周轉(zhuǎn)量結(jié)構(gòu)分析與推算方法［J］.交通運(yùn)輸工程學(xué)報(bào)，2011（5）:93-100.

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

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

［7］李曉君，謝新連.重大件運(yùn)輸?shù)呢浳锓峙渑c航速聯(lián)合優(yōu)化［J］.西南交通大學(xué)學(xué)報(bào)，2015，50（4）:747-754.

［8］周華.基于電子標(biāo)簽的物流貨物自動(dòng)分配策略設(shè)計(jì)［J］.自動(dòng)化與儀器儀表，2016（1）:104-105.

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

［10］聶長海，蔣靜.覆蓋表生成的可配置貪心算法優(yōu)化［J］.軟件學(xué)報(bào)，2013（7）:1469-1483.

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

［12］李寶磊，施心陵，茍常興，等.多元優(yōu)化算法及其收斂性分析［J］.自動(dòng)化學(xué)報(bào)，2015，41（5）:949-959.

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

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

［15］劉大蓮，徐尚文.求解約束優(yōu)化問題的內(nèi)外交叉遺傳算法［J］.系統(tǒng)工程理論與實(shí)踐，2012，32（1）:189-195.

［16］閉應(yīng)洲，陸建波，丁立新，等.基于有導(dǎo)向變異算子的GM-EA算法［J］.計(jì)算機(jī)應(yīng)用研究，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稿件編號(hào)：201602179

國家自然科學(xué)基金項(xiàng)目（71372166）；江蘇高校哲學(xué)社會(huì)科學(xué)研究重點(diǎn)項(xiàng)目（2010ZDIXM004）

張昊（1992—），男，吉林大安人，碩士研究生。研究方向：財(cái)務(wù)管理。