基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化方法

濮明月，張彥如

(1.安徽新華學(xué)院 商學(xué)院，安徽 合肥 230088；2.合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院，安徽 合肥 230009)

物流配送是物流系統(tǒng)中的重要環(huán)節(jié)，在企業(yè)配送過程選擇一個(gè)合理的路徑規(guī)劃能夠降低物流成本，提高自身的核心競(jìng)爭(zhēng)力，尤其是生鮮等容易腐敗產(chǎn)品的運(yùn)送，冷鏈運(yùn)輸成本較高，如果路徑規(guī)劃不當(dāng)，會(huì)造成很大的貨損和較高的運(yùn)輸成本，因此對(duì)物流配送車輛路徑進(jìn)行優(yōu)化十分必要[1-2].

在傳統(tǒng)的路徑優(yōu)化方法中，僅僅考慮到運(yùn)輸過程中的成本和損耗，忽略了客戶時(shí)間窗約束產(chǎn)生的懲罰成本，導(dǎo)致物流路徑的優(yōu)化效果并不理想，因此設(shè)計(jì)一種基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化方法.引入時(shí)間窗的懲罰機(jī)制，科學(xué)、合理地解決物流配送路徑優(yōu)化問題，對(duì)物流配送車輛路徑進(jìn)行合理規(guī)劃，盡量減少配送過程中的懲罰成本和貨損成本，壓縮運(yùn)輸損失.

1 物流配送車輛路徑優(yōu)化方法

1.1 蟻群算法的改進(jìn)

蟻群算法實(shí)際上是模仿螞蟻的覓食行為來尋找最優(yōu)路徑，基于蟻群的個(gè)體數(shù)量龐大，它們之間通過信息素進(jìn)行溝通，為同伴傳遞信息，大量的螞蟻形成一個(gè)反饋系統(tǒng)，因而具有較高的效率和時(shí)間復(fù)雜度，有效解決了尋找食物的問題[3-4].研究的是物流車輛的路徑優(yōu)化，主要目標(biāo)是縮短配送距離，降低成本，為企業(yè)創(chuàng)造更高的利潤(rùn).蟻群算法是一種基于種群的進(jìn)化算法，將其應(yīng)用在路徑優(yōu)化中，剛開始所有的蟻群會(huì)選擇不同的路徑尋找食物，在搜索過程中，蟻群會(huì)靠信息素進(jìn)行溝通，選擇較優(yōu)的路徑進(jìn)行二次食物尋找，如此反復(fù)迭代，會(huì)尋找到一條最優(yōu)路徑，其路徑搜索過程如圖1所示.

圖1 蟻群覓食路徑擇優(yōu)過程

蟻群算法具有很好的搜索能力，但是它的初始信息速匱乏，收斂速度比較慢，因此將蟻群算法和遺傳算法相結(jié)合，提出改進(jìn)的混合蟻群算法進(jìn)行迭代求解.結(jié)合蟻群算法，得到路徑優(yōu)化問題的算法流程，如圖2所示.

圖2 改進(jìn)蟻群算法流程

以上算法的改進(jìn)主要體現(xiàn)在信息素的更新步驟上.

主要待解決問題的目標(biāo)為路徑的最優(yōu)解.為更新信息素，假定蟻群中的蟻群數(shù)量為n，物流配送終點(diǎn)客戶z和x的距離為dzx，且設(shè)定為客戶之間的親密程度，即為可見度.在某時(shí)刻t的某蟻群到z客戶之間的不可逆移動(dòng)概率計(jì)算公式為：

(1)

公式(1)中，B為蟻群沒有達(dá)到的客戶集合，根據(jù)這個(gè)過程的不斷調(diào)整，得到路徑的信息素更新結(jié)果為：

(2)

公式(2)中的β為信息殘留程度.

在路徑信息素的更新基礎(chǔ)上，建立在基因編碼上進(jìn)行遺傳算法的選擇、交叉和編譯3個(gè)遺傳操作.采用模仿染色體編碼的方法對(duì)配送路徑進(jìn)行編碼，得到一組自然數(shù)組成的配送方案編碼，選擇的核心思想是復(fù)制，復(fù)制繼承父代中的最優(yōu)解繼續(xù)改進(jìn)，避免優(yōu)質(zhì)解丟失，交叉可以產(chǎn)生新個(gè)體，增加多樣性，防止早熟停滯，對(duì)最優(yōu)個(gè)體進(jìn)行變異操作，保存最優(yōu)解.

1.2 基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化建模

路徑優(yōu)化問題中，主要包括物流配送中心、需求地點(diǎn)、貨物、車輛、約束條件和目標(biāo)函數(shù)等要素構(gòu)成.在實(shí)際的物流配送過程中，會(huì)存在一個(gè)車輛實(shí)際載重問題，假設(shè)在一次配送過程中，有K輛車共同配送到N個(gè)需求地點(diǎn)，第i個(gè)地點(diǎn)對(duì)于運(yùn)送貨物的需求量為mi，每輛車的最大載重設(shè)為Q，需求點(diǎn)i到需求點(diǎn)j的距離表示為dij，車輛的平均行駛速度為s，需求點(diǎn)i要求貨物到達(dá)的最早時(shí)間表示為ai，要求貨物到達(dá)的最晚時(shí)間表示為bi，第i輛車的配送路線上需求點(diǎn)的數(shù)量表示為nk，那么研究問題最優(yōu)蟻群目標(biāo)函數(shù)可以表示為：

(3)

若第k輛車從需求點(diǎn)i行駛到了到需求點(diǎn)j，那么xijk的值為1，否則為0[5-6].針對(duì)上述的目標(biāo)函數(shù)做出假設(shè)，設(shè)定的配送中心僅有一個(gè)且位置確定不變，配備足夠的產(chǎn)品和物流配送車輛，所有的配送車輛都需要送配送中心出發(fā)，最后再返回配送中心，方便對(duì)物流車輛進(jìn)行下一次的調(diào)度管理，所有的需求點(diǎn)位置已知且固定不變，根據(jù)上述條件，能夠得到目標(biāo)函數(shù)的約束條件為：

(4)

公式(4)中L為客戶總數(shù).在配送過程中，若第k輛車完成需求點(diǎn)i的配送服務(wù)，那么yik的取值為1，否則為0[7-8].在約束條件中，對(duì)配送過程進(jìn)行相關(guān)的配送約束，約束條件中的第1個(gè)約束公式表示每個(gè)需求點(diǎn)有且僅有1次配送服務(wù)，也就是說只能由一輛車進(jìn)行配送；第2個(gè)約束公式表示每輛車的配送路線上所有需求點(diǎn)的貨物需求量總和不能超過車輛的最大載重；第3個(gè)公式表示配送車輛的出發(fā)地點(diǎn)都必須在配送中心；第4個(gè)公式表示配送車輛完成配送后都必須回到配送中心.

1.3 物流配送成本

在物流配送的過程中，為保證配送物品的新鮮與完整，配送的成本一般包括固定成本和變動(dòng)成本.固定成本主要是指與車輛有關(guān)的購(gòu)置費(fèi)、折舊費(fèi)以及開車司機(jī)和裝卸工人的工資等，固定成本是在進(jìn)行配送服務(wù)之前就已經(jīng)產(chǎn)生了，與后續(xù)的配送路程沒有關(guān)系，且固定成本是由配送車輛的數(shù)目決定的[9-11].變動(dòng)成本包含的項(xiàng)目比較多，主要包括運(yùn)輸成本、貨損成本、懲罰成本以及生鮮類商品需要冷鏈運(yùn)輸?shù)闹评涑杀綶12-13].對(duì)物流配送車輛路徑進(jìn)行優(yōu)化的主要目的就是要降低變動(dòng)成本，其中的運(yùn)輸成本主要是指商品在運(yùn)輸過程中所產(chǎn)生的費(fèi)用，包括燃油費(fèi)以及制冷費(fèi)等與車輛行駛的距離和時(shí)間成正比，可以表示為：

(5)

式(5)中，B代表所有需求點(diǎn)的集合；U代表所有車輛的集合；Ck表示運(yùn)輸車輛單位里程的運(yùn)輸成本.當(dāng)車輛k從需求點(diǎn)i行駛到需求點(diǎn)r時(shí)，zirk為1，否則為0,貨損成本可以表示為：

(6)

式(6)中，ρ1表示配送產(chǎn)生的貨損比例；ρ2表示卸貨貨損比例；C0表示單位商品的價(jià)值；tirk表示車輛k從需求點(diǎn)i到r的行駛時(shí)間.當(dāng)車輛k完成對(duì)需求點(diǎn)r的配送時(shí)，yrk為1，否則為0.制冷成本可以表示為[14-15]：

(7)

式(7)中，α0表示車體劣化程度；E為熱傳導(dǎo)率；Sout、Sin分別表示車體的外、內(nèi)表面積；Tout、Tin分別表示車體的外、內(nèi)溫度；p為制冷劑價(jià)格.運(yùn)送的懲罰成本可以表示為：

C5=δC0Mi.

(8)

式(8)中，δ為懲罰因子；Mi表示需求點(diǎn)i的缺貨數(shù)量.根據(jù)上述的成本計(jì)算公式，能夠清晰地計(jì)算出物流配送過程中的固定成本和變化成本.對(duì)于路徑的優(yōu)化有很好的參考作用.

至此完成基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化.

2 算例分析

2.1 數(shù)據(jù)來源

算例分析以某連鎖生鮮經(jīng)營(yíng)企業(yè)的物流配送為例，選取生鮮作為算例中的配送產(chǎn)品，由配送中心對(duì)編號(hào)1-18門店進(jìn)行冷卻生鮮配送.目標(biāo)是優(yōu)化配送中心生鮮的車輛配送路徑，將物流的配送成本降到最低.配送中心以及各個(gè)門店的地理位置如圖3所示：

圖3 配送中心和各個(gè)門店的地理分布圖

圖3中，標(biāo)號(hào)為0的地標(biāo)代表配送中心，標(biāo)號(hào)1～18代表18家門店，配送中心在對(duì)各個(gè)門店進(jìn)行生鮮產(chǎn)品配送時(shí)，要保證在規(guī)定時(shí)間內(nèi)送達(dá)，且需要保證供應(yīng)數(shù)量，否則會(huì)給該門店造成一定損失，配送要受到懲罰.因此在進(jìn)行路徑規(guī)劃時(shí)，需要對(duì)生鮮商品需求量以及約定的服務(wù)時(shí)間窗進(jìn)行設(shè)置，如表1所示.

表1 各門店生鮮商品需求量以及時(shí)間窗

2.2 實(shí)驗(yàn)結(jié)果分析

在分別對(duì)算例進(jìn)行100次求解后，最終得到了傳統(tǒng)文獻(xiàn)[3]方法和所提方法的最優(yōu)配送路徑，如圖4所示：

(a)文獻(xiàn)[3]方法

(b)所提方法圖4 不同配送路徑對(duì)比

圖4(a)為傳統(tǒng)方法最終得到的最優(yōu)路徑；圖4(b)為所提方法最終得到的最優(yōu)路徑.對(duì)這兩種配送路徑進(jìn)行成本分析，如表2所示：

表2 路徑成本分析

在路徑分析中，考慮了5種成本進(jìn)行路徑優(yōu)化，在實(shí)際應(yīng)用中的約束效果更好，得到的最優(yōu)路徑能夠明顯的節(jié)省運(yùn)輸成本，提高收益；懲罰成本是從各個(gè)門店的視角出發(fā)，能夠體現(xiàn)配送滿意度.

在驗(yàn)證所提方法的成本約束基礎(chǔ)上，為更直觀測(cè)試不同方法的物流配送車輛路徑的有效性，以耗時(shí)為實(shí)驗(yàn)指標(biāo)進(jìn)行實(shí)驗(yàn)結(jié)果輸出.假定本次實(shí)驗(yàn)中所有物流運(yùn)輸車輛的車速一致，其耗時(shí)越低，則說明其路徑越短，優(yōu)化效果越好，具體實(shí)驗(yàn)結(jié)果如圖5所示：

待配送門店數(shù)量/個(gè)圖5 不同方法的路徑耗時(shí)對(duì)比

由圖5的實(shí)驗(yàn)結(jié)果可以看出，隨著待配送門店數(shù)量的增多，兩種方法的路徑耗時(shí)不斷增加.但是很明顯，所提方法的耗時(shí)始終低于文獻(xiàn)[3]方法，且門店數(shù)量達(dá)到300個(gè)以上時(shí)，耗時(shí)的增量較小.通過以上實(shí)驗(yàn)結(jié)果可以得出結(jié)論：使用設(shè)計(jì)的方法對(duì)物流配送車輛路徑進(jìn)行優(yōu)化，在滿足車輛容量約束、時(shí)間窗約束和懲罰約束的情況下，能夠得到總成本最低的物流配送路徑方案.

3 結(jié) 論

物流車輛的入境規(guī)劃是物流配送的關(guān)鍵，基于傳統(tǒng)路徑規(guī)劃方法的缺陷，將蟻群算法與遺傳算法進(jìn)行結(jié)合設(shè)計(jì)了一種新的物流車輛配送路徑優(yōu)化方法.實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)方法對(duì)路徑進(jìn)行優(yōu)化后，能夠有效地降低變動(dòng)成本.但是研究還有一些不足之處，建立的模型約束條件相對(duì)于實(shí)際情況考慮的不夠全面，例如交通方面出現(xiàn)突發(fā)狀況時(shí)，缺乏實(shí)際的調(diào)度能動(dòng)性，在今后的研究中需要進(jìn)一步解決.