基于遺傳算法的物流貨物與運力撮合算法研究

陳德軍，王 盼，隋建龍

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

?

基于遺傳算法的物流貨物與運力撮合算法研究

陳德軍，王 盼，隋建龍

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

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

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

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

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

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

1 基于遺傳算法的物流貨物與運力撮合算法

1.1 撮合算法設(shè)計

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

圖1 基于遺傳算法的物流貨物與運力撮合算法流程

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

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

(1)

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

(2)

(3)

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

(4)

(5)

約束條件為：

(6)

(7)

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

(8)

(9)

(10)

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

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

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

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

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

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

(11)

進而可以得到每個個體被選擇的概率：

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

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

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

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

1.2 撮合算法仿真

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

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

表1 貨物信息表

圖2 種群迭代過程圖

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

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

2 基于改進遺傳算法的物流貨物與運力撮合算法

2.1 撮合算法設(shè)計

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

(13)

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

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

圖4 基于改進遺傳算法的物流貨物與運力撮合算法流程

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

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

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

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

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

While(T

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

Fori=1:L

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

計算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

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

2.2 撮合算法仿真

圖5 改進算法的種群迭代過程圖

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

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

圖6 改進后算法的20次運行結(jié)果圖

3 結(jié)論

筆者結(jié)合物流園區(qū)物流資源優(yōu)化配置的特點，確定了基于遺傳算法的貨物信息與運力信息匹配方法，并對遺傳算法的特點和基本操作進行分析。結(jié)果表明算法符合實際要求，達到了資源優(yōu)化配置的目的，又結(jié)合模擬退火算法對遺傳算法進行改進，以解決遺傳算法易早熟、局部搜索能力不強等問題，Matlab仿真結(jié)果顯示，改進后的算法搜索能力更強、效率更高，達到了更好的撮合結(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] 羅文文,張文會,李德才.物流園區(qū)物流量灰色馬爾可夫預(yù)測模型[J].森林工程,2014，30(5):184-187.

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

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

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

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

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

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

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

[11] 呂曉峰,張勇亮,馬羚.一種求解0-1背包問題的改進遺傳算法[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-)，男，湖北天門人，武漢理工大學信息工程學院教授，主要研究方向為復(fù)雜系統(tǒng)建模、網(wǎng)絡(luò)控制與管理、智能信息控制與管理系統(tǒng).

國家自然科學青年基金項目(61303027).

F259.22;U116.5;U125

10.3963/j.issn.2095-3852.2017.02.018