航空物流配送路徑優(yōu)化

［摘要］ 航空物流配送對(duì)航空貨運(yùn)時(shí)間及服務(wù)水平有著極大的影響，其中，配送路徑優(yōu)化是配送合理化的核心問題。采用遺傳算法設(shè)計(jì)航空物流配送路線，具有更高的準(zhǔn)確度，對(duì)降低成本提高效率更有效。

［關(guān)鍵詞］ 航空物流；配送；路徑優(yōu)化問題；遺傳算法

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2011 . 17. 043

［中圖分類號(hào)］F560.84；U116.2［文獻(xiàn)標(biāo)識(shí)碼］A ［文章編號(hào)］1673 - 0194（2011）17- 0076- 02

一、航空物流配送背景

航空物流配送是指按客戶的訂貨要求，在航空物流中心進(jìn)行分貨、配貨，并將貨物及時(shí)送交收貨人的物流活動(dòng)。送交收貨人環(huán)節(jié)包括車輛選擇及運(yùn)輸路線規(guī)劃。目前，國內(nèi)航空貨運(yùn)配送環(huán)節(jié)，由于路線規(guī)劃缺乏優(yōu)化選擇，使航空貨運(yùn)無法更好發(fā)揮快捷性優(yōu)勢(shì)。常用規(guī)劃方法有：動(dòng)態(tài)規(guī)劃、分支定界、節(jié)約里程、掃描、貪婪算法及現(xiàn)代遺傳、模擬退火、蟻群算法。其中，遺傳算法結(jié)合現(xiàn)代智能技術(shù)，能適應(yīng)航空物流多點(diǎn)配送的特點(diǎn)，提高精確度。

二、航空貨運(yùn)配送規(guī)劃

根據(jù)遺傳算法基本理論設(shè)計(jì)適用于配送路徑模型的遺傳算法，主要包括染色體編碼與解碼、初始群體、適應(yīng)度函數(shù)、遺傳等要素的設(shè)計(jì)。

1.編碼與解碼及產(chǎn)生初始種群

假設(shè)配送中心有車輛ｋ臺(tái)，客戶點(diǎn)ｌ個(gè)，采用增加ｋ＋１個(gè)虛擬配送中心可形成一條長為ｋ＋ｌ＋１的染色體編碼串（０，ｉ１１，ｉ１２，…ｉ１ａ，０，ｉ２１，ｉ２２，…，ｉ２ｂ，０，…，０，ｉｋ１，…，ｉｋｃ，０），其中染色體相鄰兩個(gè)０之間表示一條子路徑。將路徑分隔符的０加入到染色體中，所有路徑中被訪問的客戶依次編碼至一條染色體中，可保證每個(gè)客戶節(jié)點(diǎn)均被訪問有且只有一次，大大地簡化了對(duì)模型約束條件的處理。

解碼時(shí)，初始化一條路徑，將染色體中的基因值順序插入到當(dāng)前路徑中，若一個(gè)基因值的插入導(dǎo)致該路徑的負(fù)荷超過了車輛的最大容量或返回配送中心的時(shí)間晚于最晚返回時(shí)間，則開始構(gòu)建新的路徑，重復(fù)上面操作，直至所有客戶均被插入到路徑中。

由于遺傳算法搜索最優(yōu)解不依賴于初始種群，為使初始種群盡可能地均勻分布在整個(gè)解空間，隨機(jī)生成初始種群。

2.選擇

采用改進(jìn)輪盤賭選擇算子，設(shè)種群大小為Ｍ，父代種群Ｚ＝ ｛ａ１，ａ２，…，ａｉ，…，ａM｝，其中每個(gè)個(gè)體的適應(yīng)度大小為ｆ（ａｉ），子代群體初始狀態(tài)為Ｘ＝｛ ｝。

(5）轉(zhuǎn)動(dòng)Ｍ輪輪盤。

1）產(chǎn)生Ｍ個(gè)［０，１］之間的均勻隨機(jī)數(shù)r。如果ｒ≤Qi，則選擇染色體ｂｉ，否則，選擇第ｉ個(gè)染色體ｂｉ（2≤i≤M），使得Qi-1≤r≤Qi。

2）統(tǒng)計(jì)各區(qū)間ξ值ξ１，ξ２，…，ξＭ，其中ξｉ是落在ｉ號(hào)區(qū)域的隨機(jī)數(shù)個(gè)數(shù)

3）取最大的ξ值ξｊ＝ｍａｘ｛ξ１，ξ２，…，ξＭ｝所在區(qū)間ｊ對(duì)應(yīng)的個(gè)體ｂｊ為本輪轉(zhuǎn)動(dòng)后所選中的個(gè)體Ｍｉ，即

4）將Ｍｉ并入Ｘ，即X（０）＝?準(zhǔn)Ｘ（ｔ）＝ｘ（ｔ－１）∪Mi

5）若選出的個(gè)體數(shù)到達(dá)種群大小，則轉(zhuǎn)７），否則轉(zhuǎn)1）。

（６）找出子代種群Ｘ中適應(yīng)度最低個(gè)體ｍ。

（７）用個(gè)體ｋ代替?zhèn)€體ｍ。

（８）存儲(chǔ)所有新選出的個(gè)體，并且返回。

3.交叉

（１）隨機(jī)在父代個(gè)體中選擇一個(gè)交叉區(qū)域，如兩父代個(gè)體及交叉區(qū)域選定為：Ａ＝“２５６｜８４３７｜１９”，Ｂ＝“３５９｜４１７８｜２６”，其中“｜｜”表示交叉區(qū)域；

（２）將Ｂ的交配區(qū)域加到Ａ的前面，Ａ的交配區(qū)域加到Ｂ的前面，得兩中間個(gè)體：Ａ′＝“４１７８｜２５６８４３７１９｜”，Ｂ′＝“８４３７｜３５９４１７８２６｜”；

（３）在Ａ′和Ｂ′中，自交叉區(qū)域后依次刪除與交叉區(qū)相同的基因，得到最終的兩個(gè)個(gè)體為：Ａ１＝“８４３７５９１２６”，Ｂ１＝“４１７８２５６３９”。

4.變異

采用倒位變異算子進(jìn)行變異操作，隨機(jī)選擇一染色體的兩變異點(diǎn)，將變異區(qū)域進(jìn)行倒位得到新的個(gè)體。倒位變異在進(jìn)化過程中可對(duì)種群中的個(gè)體進(jìn)行有效地調(diào)整，防止早熟收斂問題，改善遺傳操作的全局尋優(yōu)性能。

（１）隨機(jī)產(chǎn)生一個(gè)體ｔｅｍｐ＝“９ ２ ５ ８ ７ ３ １０ ４ ６ １”和兩變異點(diǎn)，如２和３，即ｔｅｍｐ＝ “９ ｜２ ５ ８ ７ ３ ｜ １０ ４ ６ １”，其中“｜｜”表示變異區(qū)域。

（２）將變異區(qū)域基因按反序插入到原位置中得到新個(gè)體ｔｅｍｐ１＝“９｜３ ７ ８ ５ ２｜ １０ ４ ６ １”。

5.適應(yīng)度

ｚｉ為群體中第ｉ條染色體對(duì)應(yīng)的目標(biāo)函數(shù)值，反映了第ｉ條染色體所對(duì)應(yīng)的的配送總費(fèi)用； ｆｉ為第ｉ條染色體對(duì)應(yīng)的適應(yīng)度，其值決定了該染色體產(chǎn)生后代的概率。

6.終止規(guī)則

配送中，可判斷進(jìn)化的代數(shù)是否為要求代數(shù)Ｎ，若是，則停止進(jìn)化，選性能最好的染色體所對(duì)應(yīng)的配送路徑集合作為所求ＶＲＰＴＷ問題的最優(yōu)解輸出。反之，繼續(xù)執(zhí)行進(jìn)化運(yùn)算。

三、結(jié)論

通過多次試驗(yàn)，編制ＭＡＴＬＡＢ算法驗(yàn)證，可證明遺傳算法有效性更高。上述步驟的迭代搜索，得到最優(yōu)染色相應(yīng)的配送路徑，完成帶時(shí)間窗車輛路徑問題的自動(dòng)尋優(yōu)過程。實(shí)現(xiàn)貨物配送路徑優(yōu)化，選擇最優(yōu)配送路線，節(jié)約成本和時(shí)間，促進(jìn)航空貨運(yùn)優(yōu)勢(shì)的發(fā)揮。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文