陳德軍，王 盼，隋建龍

(武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

?

基于遺傳算法的物流貨物與運(yùn)力撮合算法研究

陳德軍，王 盼，隋建龍

(武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

首先，分析了物流園區(qū)貨物與運(yùn)力資源優(yōu)化配置的需求；然后提出了一種基于改進(jìn)遺傳算法的物流貨物與運(yùn)力資源優(yōu)化配置的方法，實(shí)現(xiàn)了貨物與運(yùn)力信息的優(yōu)化組合；最后對(duì)改進(jìn)算法的效果進(jìn)行了詳細(xì)討論，并運(yùn)用Matlab對(duì)改進(jìn)前后的算法進(jìn)行仿真對(duì)比，驗(yàn)證了改進(jìn)算法的有效性。

改進(jìn)遺傳算法；物流園區(qū)；撮合算法

物流園區(qū)是為滿足貨物轉(zhuǎn)運(yùn)需求而建立的，對(duì)物流組織管理節(jié)點(diǎn)進(jìn)行集中建設(shè)與發(fā)展，具有經(jīng)濟(jì)開發(fā)性質(zhì)的功能區(qū)域，是物流作業(yè)集中的地區(qū)，可以依托區(qū)位交通優(yōu)勢(shì)，降低物流成本，提高物流運(yùn)作效率，實(shí)現(xiàn)物流資源的優(yōu)化配置。

國外學(xué)者較早對(duì)物流園區(qū)的規(guī)模、選址和運(yùn)營(yíng)模式等問題進(jìn)行了研究。如SHEU[1]提出了一種基于動(dòng)態(tài)客戶群的物流資源配置方法，TANIGUCHI等[2]采用雙層規(guī)劃模型來確定物流園區(qū)的規(guī)模和選址。在國內(nèi)，羅文文等[3]建立了灰色馬爾可夫預(yù)測(cè)模型用于物流園區(qū)物流量的預(yù)測(cè)，發(fā)現(xiàn)其精度較高。對(duì)于貨運(yùn)量預(yù)測(cè)還可以使用神經(jīng)網(wǎng)絡(luò)模型[4]等定量分析預(yù)測(cè)模型。秦進(jìn)等[5]設(shè)計(jì)了通用型的雙層模擬退火算法來研究物流設(shè)施的選址問題。姚峰等[6]采用知識(shí)型遺傳算法求解雙層CARP優(yōu)化問題。對(duì)物流園區(qū)運(yùn)作模式的研究，我國還鮮有關(guān)于此類的研究，多是借鑒國外的研究成果[7]。

在物流園區(qū)內(nèi)，貨物與運(yùn)力資源的優(yōu)化配置是其最重要也是最基本的需求。一般來說，物流需求方和物流供應(yīng)方通常在園區(qū)物流信息管理平臺(tái)發(fā)布各自的需求信息，物流需求方發(fā)布的信息內(nèi)容主要包括貨物類型、貨物質(zhì)量、貨物體積、貨物目的地及具體的收貨人或收貨公司的信息，而物流供應(yīng)方發(fā)布的信息通常包括閑置運(yùn)力噸位數(shù)、閑置運(yùn)力載積、車輛數(shù)量、運(yùn)輸單位價(jià)格等信息。為此，需要設(shè)計(jì)一種撮合算法，針對(duì)大批量的貨物運(yùn)單，算法可以組合適當(dāng)物流公司的閑置運(yùn)力去共同承運(yùn)這批貨物；針對(duì)小批量的運(yùn)單，算法也可以組合發(fā)往同一目的地的運(yùn)單，并根據(jù)各物流公司的閑置運(yùn)力情況交由一家或幾家托運(yùn)，從而提高物流效率，實(shí)現(xiàn)物流資源的優(yōu)化配置。針對(duì)當(dāng)前物流園區(qū)物流資源優(yōu)化配置與利用的問題，筆者提出了一種基于改進(jìn)遺傳算法的物流資源優(yōu)化配置方法。

1 基于遺傳算法的物流貨物與運(yùn)力撮合算法

1.1 撮合算法設(shè)計(jì)

遺傳算法[8-9]的計(jì)算過程是一個(gè)反復(fù)迭代的過程，不妨將第t代種群記作P(t)，這樣經(jīng)過一代的遺傳和進(jìn)化后，可以得到t+1代種群，其也是由多個(gè)個(gè)體組成的集合，記作P(t+1)，這樣經(jīng)過不斷的遺傳和進(jìn)化操作，每次都在當(dāng)代種群中選擇適應(yīng)度較高的個(gè)體遺傳到下一代，淘汰適應(yīng)度較低的個(gè)體，迭代一定的代數(shù)后，最終將會(huì)得到一個(gè)優(yōu)良個(gè)體，其表現(xiàn)型將接近或者達(dá)到問題的最優(yōu)解，從而解決問題。

圖1 基于遺傳算法的物流貨物與運(yùn)力撮合算法流程

由于大型貨物運(yùn)單匹配多家物流公司閑置運(yùn)力和物流公司閑置運(yùn)力匹配多個(gè)小型貨物運(yùn)單的本質(zhì)是相同的，所以筆者以后者為例對(duì)算法的設(shè)計(jì)過程進(jìn)行說明，算法的設(shè)計(jì)流程如圖1所示。首先取出園區(qū)物流管理平臺(tái)上各企業(yè)發(fā)布的尚未撮合的所有貨物信息和閑置運(yùn)力信息，對(duì)貨物信息按目的地進(jìn)行分組，取出第一個(gè)分組，從閑置運(yùn)力信息中選出業(yè)務(wù)范圍包含目的地區(qū)的物流公司集合，通過遺傳算法對(duì)貨物信息和物流信息進(jìn)行撮合，撮合完成后刪除已撮合信息，重復(fù)上述過程直到所有貨物信息均已撮合為止。不難看出，算法的核心部分是基于遺傳算法的貨物與運(yùn)力撮合過程。

假設(shè)園區(qū)物流信息平臺(tái)上選取發(fā)往同一地區(qū)Pi的所有貨物運(yùn)單的編號(hào)為1，2，…，n，對(duì)應(yīng)的貨物質(zhì)量為W1，W2，…，Wn，貨物體積為V1，V2，…，Vn，然后從平臺(tái)上已發(fā)布的閑置運(yùn)力信息中篩選業(yè)務(wù)范圍包含地區(qū)Pi的所有物流公司，將物流公司按照其信用和單位運(yùn)費(fèi)價(jià)格等因素進(jìn)行綜合評(píng)價(jià)，得到一個(gè)優(yōu)先配貨的序列，即L1，L2，…，Ln，則對(duì)應(yīng)的閑置運(yùn)力載重分別為WL1，WL2，…，WLn，閑置載積為WV1，WV2，…，WVn，并定義：

(1)

則對(duì)于運(yùn)力信息L1來講，質(zhì)量和體積的目標(biāo)函數(shù)分別為：

(2)

(3)

可見上述問題是一個(gè)多目標(biāo)優(yōu)化問題，需要通過數(shù)學(xué)方法將多目標(biāo)融合為單目標(biāo)，其中最常用的做法為加權(quán)法，對(duì)每個(gè)目標(biāo)函數(shù)分配權(quán)重并將其組合成一個(gè)目標(biāo)函數(shù)，則融合后的單目標(biāo)函數(shù)為：

(4)

(5)

約束條件為：

(6)

(7)

得到遺傳算法的目標(biāo)函數(shù)后，針對(duì)式(6)和式(7)的約束條件，需要設(shè)計(jì)懲罰函數(shù)來加快算法收斂速度，讓其同時(shí)滿足式(6)和式(7)的情況下不斷進(jìn)化，最終可以得到最優(yōu)解或近似最優(yōu)解。

(8)

(9)

(10)

其中，K1和K2為懲罰系數(shù)。懲罰系數(shù)的作用體現(xiàn)在計(jì)算適應(yīng)度的時(shí)候，目標(biāo)函數(shù)值與對(duì)應(yīng)的懲罰度相乘，如果個(gè)體滿足所有約束條件，其懲罰度為1，不會(huì)影響計(jì)算得到的適應(yīng)度；如果任何一項(xiàng)不滿足約束條件，其懲罰度都將變成一個(gè)小于1的很小的值，這樣便使得該個(gè)體的適應(yīng)度也變得很小，進(jìn)而面臨被淘汰的可能。

確定了目標(biāo)函數(shù)和懲罰函數(shù)后，則可按照遺傳算法的計(jì)算步驟進(jìn)行計(jì)算，整體計(jì)算過程如下：

(1)個(gè)體編碼。將具體問題轉(zhuǎn)化為遺傳算法使用的染色體，常用的有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼方法，由于此處用0或1表示該貨物運(yùn)單被選擇與否，所以采用二進(jìn)制編碼。

(2)初始化種群。根據(jù)設(shè)定的種群規(guī)模s，隨機(jī)生成s個(gè)個(gè)體，每個(gè)個(gè)體的染色體長(zhǎng)度為當(dāng)前貨物運(yùn)單的數(shù)量n。

(3)計(jì)算適應(yīng)度值。根據(jù)式(4)與式(8)，得到初代個(gè)體的適應(yīng)度值：

fitness(t)=F(t)×P(t)

(11)

進(jìn)而可以得到每個(gè)個(gè)體被選擇的概率：

(4)選擇個(gè)體。采用常見的輪盤賭選擇策略，每次通過Random.next()函數(shù)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，從第一個(gè)個(gè)體開始依次計(jì)算個(gè)體被選擇概率，直到累計(jì)概率大于等于該隨機(jī)數(shù)的個(gè)體被選擇，適應(yīng)度值較大個(gè)體的被選擇概率也相對(duì)較大，從而實(shí)現(xiàn)了優(yōu)勝劣汰的效果。

(5)交叉運(yùn)算。通過交叉運(yùn)算組合父代基因，使個(gè)體快速進(jìn)化，筆者采用兩點(diǎn)交叉方法進(jìn)行交叉運(yùn)算，即在滿足交叉運(yùn)算概率的前提下，根據(jù)染色體長(zhǎng)度隨機(jī)產(chǎn)生兩個(gè)位置，將這兩個(gè)位置之間的基因進(jìn)行交叉互換。

(6)變異運(yùn)算。可以在種群達(dá)到一定穩(wěn)定狀態(tài)時(shí)，通過改變個(gè)體基因座上的基因打破這種相對(duì)穩(wěn)定的狀態(tài)，從而使種群達(dá)到新的平衡，在這一過程中最大適應(yīng)度可能得到一個(gè)新的最大值，從而求出更優(yōu)的解集，變異概率一般選擇0.001～0.010，變異率過大則種群進(jìn)化速度過慢，變異率過小則耗時(shí)較長(zhǎng)，筆者選擇的變異概率為0.010。

(7)開始迭代過程。根據(jù)設(shè)置的最大進(jìn)化代數(shù)開始進(jìn)化，當(dāng)達(dá)到該數(shù)值時(shí)，算法結(jié)束，得到的最優(yōu)個(gè)體的表現(xiàn)型便是所選貨物運(yùn)單的組合。然后對(duì)未選中的貨物信息與下一個(gè)運(yùn)力信息重新進(jìn)行撮合，直到所有貨物被選中或者沒有可用運(yùn)力信息為止。

1.2 撮合算法仿真

使用Matlab對(duì)上述算法進(jìn)行仿真，輸入的貨物信息如表1所示。輸入閑置運(yùn)力信息總載重為70 t，載積為6.5 m3，設(shè)置種群規(guī)模為50，迭代代數(shù)為200，染色體長(zhǎng)度為當(dāng)前輸入的貨物信息數(shù)量15，算法通過隨機(jī)法生成初始種群，種群的迭代過程如圖2所示。

由圖2可知，初始時(shí)的種群個(gè)體是隨機(jī)產(chǎn)生，其適應(yīng)度值較低，通過不斷的進(jìn)化，適應(yīng)度值較高的個(gè)體被保存了下來，較低的被淘汰，經(jīng)過1 000代進(jìn)化后，種群內(nèi)大部分個(gè)體的適應(yīng)度值都已經(jīng)變得很高，且穩(wěn)定在一個(gè)較高的數(shù)值上，此時(shí)目標(biāo)函數(shù)的值0.966就可以看作當(dāng)前問題的一個(gè)最優(yōu)解，即編號(hào)為3、4、10、14的貨物信息被選中，從表1可知3號(hào)、4號(hào)、10號(hào)、14號(hào)貨物總質(zhì)量為66 t，總體積為6.5 m3，較好地匹配了70 t、6.5 m3的閑置運(yùn)力信息。

表1 貨物信息表

圖2 種群迭代過程圖

由于算法的運(yùn)算過程具有隨機(jī)性，需要多次運(yùn)行程序記錄統(tǒng)計(jì)結(jié)果，將每次得到的最佳個(gè)體的適應(yīng)度值繪圖，如圖3所示。由圖3可知20次的最佳適應(yīng)度均值為0.878 0。算法整體上實(shí)現(xiàn)了貨物與運(yùn)力信息的撮合，但有時(shí)會(huì)過早收斂而陷入局部最優(yōu)解，導(dǎo)致最佳編碼值不夠理想，如第7、9、10、16次的運(yùn)行結(jié)果。通過增大種群規(guī)模和迭代代數(shù)可以改善這種狀況，但是會(huì)增加算法的時(shí)間消耗。

圖3 運(yùn)行20次的結(jié)果圖

2 基于改進(jìn)遺傳算法的物流貨物與運(yùn)力撮合算法

2.1 撮合算法設(shè)計(jì)

針對(duì)撮合過程中遺傳算法易早熟、局部搜索能力不強(qiáng)等問題，筆者對(duì)遺傳算子進(jìn)行了改進(jìn)，再引入模擬退火算法來增強(qiáng)其局部搜索能力，以便獲得更優(yōu)的編碼結(jié)果。模擬退火算法[10]在搜索過程中引入了隨機(jī)因素，即在一定的概率下可以接受比當(dāng)前差的解，從而跳出局部最優(yōu)解，這樣便可以加強(qiáng)遺傳算法的局部搜索能力，退火過程的概率計(jì)算參考了金屬冶煉的退火過程，可表示為：

(13)

式中:T為當(dāng)前溫度；K為常數(shù)；dE為溫度下降所產(chǎn)生的能量差值，則dE<0。式(13)表示在溫度為T時(shí)，出現(xiàn)能量差為dE的降溫的概率，溫度越高，P(dE)的值越大，反之就越小，最后趨于穩(wěn)定。

在遺傳算法中引入模擬退火[11]，其具體的運(yùn)算過程如圖4所示。算法的主要改進(jìn)包括以下4個(gè)方面。

圖4 基于改進(jìn)遺傳算法的物流貨物與運(yùn)力撮合算法流程

(1)在選擇算子中加入保優(yōu)策略。即選出每代的最優(yōu)個(gè)體直接進(jìn)入下一代，這種策略可以加快種群的進(jìn)化速度。

(2)改進(jìn)交叉算子。①引入自適應(yīng)的交叉概率，使適應(yīng)度較高的個(gè)體在交叉運(yùn)算時(shí)對(duì)應(yīng)較小的交叉概率，從而保存優(yōu)良個(gè)體；而適應(yīng)度較低的個(gè)體對(duì)應(yīng)較高的交叉概率，促使個(gè)體進(jìn)化，交叉概率的計(jì)算公式如式(14)所示。②在原有交叉算子基礎(chǔ)上引入模擬退火選擇策略：假設(shè)個(gè)體Q1和Q2通過原有交叉算子產(chǎn)生的子代分別為F1和F2，分別計(jì)算其適應(yīng)度fitness(Qi)和fitness(Fi)，i=1，2。如果fitness(Qi)≥fitness(Fi)，則使用Fi代替Qi，否則以概率exp(-(f(Fi)-f(Qi))/T)接受Fi。

式中：fmax為種群中個(gè)體的最大適應(yīng)度值；favg為適應(yīng)度均值；f為當(dāng)前個(gè)體的適應(yīng)度值。

(3)改進(jìn)變異算子。在原有變異算子基礎(chǔ)之上加入模擬退火選擇策略，方法與步驟(2)相同。

(4)改進(jìn)固定的進(jìn)化代數(shù)。即判斷每代個(gè)體的最大適應(yīng)度值，如果連續(xù)20代無變化，則停止進(jìn)化，并選出最終的最優(yōu)個(gè)體進(jìn)行模擬退火運(yùn)算。這樣進(jìn)化初期充分利用了遺傳算法優(yōu)秀的全局搜索能力，在進(jìn)化中后期利用模擬退火算法的局部搜索能力進(jìn)行局部搜索，從而得到更為理想的個(gè)體編碼。上述的模擬退火運(yùn)算偽代碼描述如下：

While(T

根據(jù)當(dāng)代個(gè)體編碼Bestcode計(jì)算其適應(yīng)度值fitval1;

Fori=1:L

倒位法產(chǎn)生新個(gè)體X;

計(jì)算X的適應(yīng)度fitval(X);

If(fitval1

最佳編碼Bestcode=X的編碼組合code(X);

Else

接受較差解的概率dp=exp((-fitval(X)-fitval1)/T);

If(dp

最佳編碼Bestcode=X的編碼組合code(X);

End

T=T×K;

End

End

其中:個(gè)體編碼Bestcode的初始值是通過遺傳算法計(jì)算得到的全局較優(yōu)解;T表示當(dāng)前溫度;Tf表示終止溫度;L表示每一個(gè)溫度T下的狀態(tài)變化次數(shù)，即馬爾可夫鏈的長(zhǎng)度，狀態(tài)產(chǎn)生函數(shù)采用倒位法產(chǎn)生新狀態(tài)，即隨機(jī)產(chǎn)生兩個(gè)位置，并將這兩個(gè)位置之間的編碼進(jìn)行逆序；K表示退溫系數(shù)，通常取0.95左右，每次迭代通過K來調(diào)整溫度，從而調(diào)整模擬退火操作的接受概率。

2.2 撮合算法仿真

圖5 改進(jìn)算法的種群迭代過程圖

在保持原有全局搜索能力基礎(chǔ)上，通過對(duì)選擇、交叉和變異算子的改進(jìn)，加快了算法的收斂速度，通過并行搜索獲得全局較優(yōu)解后，使用模擬退火對(duì)該較優(yōu)解進(jìn)行串行搜索，從而加強(qiáng)了算法的局部搜索能力，最終實(shí)現(xiàn)了更優(yōu)的搜索性能。最后使用Matlab對(duì)算法迭代過程進(jìn)行了仿真，如圖5所示。從圖5可以看出，在進(jìn)化到10代時(shí)群體出現(xiàn)了較優(yōu)解，其適應(yīng)度值為0.965 7，且這一最大適應(yīng)度值持續(xù)40代沒有變化，這時(shí)結(jié)束遺傳算法的迭代過程，將這個(gè)全局較優(yōu)解作為模擬退火運(yùn)算的初始狀態(tài)，并展開局部搜索，最終獲得了更為理想的個(gè)體編碼，001100000001001，其適應(yīng)度值為1。且與固定進(jìn)化代數(shù)相比，算法迭代代數(shù)減少，從而節(jié)省了運(yùn)行時(shí)間。

多次運(yùn)行改進(jìn)后的算法程序，并記錄每次運(yùn)行得到的最佳編碼，如圖6所示。20次運(yùn)行結(jié)果的適應(yīng)度均值為0.971 4，與改進(jìn)前的均值0.878 0相比獲得了明顯的提升，且其中4次搜索到了問題的最優(yōu)解，可見改進(jìn)后的算法搜索能力更強(qiáng)，效率更高，可以獲得更為滿意的貨物與運(yùn)力的撮合結(jié)果。

圖6 改進(jìn)后算法的20次運(yùn)行結(jié)果圖

3 結(jié)論

筆者結(jié)合物流園區(qū)物流資源優(yōu)化配置的特點(diǎn)，確定了基于遺傳算法的貨物信息與運(yùn)力信息匹配方法，并對(duì)遺傳算法的特點(diǎn)和基本操作進(jìn)行分析。結(jié)果表明算法符合實(shí)際要求，達(dá)到了資源優(yōu)化配置的目的，又結(jié)合模擬退火算法對(duì)遺傳算法進(jìn)行改進(jìn)，以解決遺傳算法易早熟、局部搜索能力不強(qiáng)等問題，Matlab仿真結(jié)果顯示，改進(jìn)后的算法搜索能力更強(qiáng)、效率更高，達(dá)到了更好的撮合結(jié)果。

[1] SHEU J B. A novel dynamic resource allocation model for demand-responsive city logistics distribution operations[J]. Transportation Research Part E Logistics & Transportation Review,2006,42(6):445-472.

[2] TANIGUCHI E, NORITAKE M, YAMADA T, et al. Optimal size and location planning of public logistics terminals[J]. Transportation Research Part E Logistics & Transportation Review,1999,35(3):207-222.

[3] 羅文文,張文會(huì),李德才.物流園區(qū)物流量灰色馬爾可夫預(yù)測(cè)模型[J].森林工程,2014，30(5):184-187.

[4] 李曉利,王澤江.基于BP神經(jīng)網(wǎng)絡(luò)模型的煤炭物流需求預(yù)測(cè)研究[J].物流技術(shù),2014,33(1):145-149.

[5] 秦進(jìn),史峰.物流設(shè)施選址問題的雙層模擬退火算法[J].系統(tǒng)工程,2007,25(2):36-40.

[6] 姚鋒,邢立寧,李菊芳,等.求解雙層CARP優(yōu)化問題的知識(shí)型遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2014，34(1):239-247.

[7] 張錦惠,陶經(jīng)輝.國內(nèi)外物流園區(qū)研究評(píng)述及展望[J].中國市場(chǎng),2011(23):14-16.

[8] 周昕,凌興宏.遺傳算法理論及技術(shù)研究綜述[J].計(jì)算機(jī)與信息技術(shù),2010(4):37-39.

[9] 歐陽紅祥，陳偉偉，李欣.基于間隔率和遺傳算法的多資源均衡優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)，2014，36(1)：82-85.

[10] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社,2001：135-207.

[11] 呂曉峰,張勇亮,馬羚.一種求解0-1背包問題的改進(jìn)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(34):44-46.

CHEN Dejun:Prof.; School of Information Engineering, WUT, Wuhan 430070, China.

Research on Matching Algorithm of Logistics Goods and Transport Capacity Based on Genetic Algorithm

CHENDejun，WANGPan，SUIJianlong

This paper analyzes the optimal allocation between goods and transport capacity resources in the logistics park, then a method of the optimal allocation between logistics goods and transport capacity resources based on improved genetic algorithm is proposed, which optimize combination of goods and transport information. MATLAB as a simulation platform ,by discussing the simulation results of improved algorithm in detail，the effectiveness of the algorithm improvement is confirmed.

improved genetic algorithm; logistics park; matching algorithm

2095-3852(2017)02-0208-05

A

2016-10-16.

陳德軍(1964-)，男，湖北天門人，武漢理工大學(xué)信息工程學(xué)院教授，主要研究方向?yàn)閺?fù)雜系統(tǒng)建模、網(wǎng)絡(luò)控制與管理、智能信息控制與管理系統(tǒng).

國家自然科學(xué)青年基金項(xiàng)目(61303027).

F259.22;U116.5;U125

10.3963/j.issn.2095-3852.2017.02.018