基于蟻群算法的多配送中心車輛調(diào)度問(wèn)題的探討*

殷玲玲 蘇劍鋒

(六安職業(yè)技術(shù)學(xué)院 安徽六安 237158)

作為現(xiàn)代智能化物流系統(tǒng)中非常重要的環(huán)節(jié)之一，物流配送應(yīng)當(dāng)根據(jù)用戶方訂貨需求，在配送中心完成分貨、配貨工作并通過(guò)各種運(yùn)輸途徑將貨物送交至收貨方．在整個(gè)配送業(yè)務(wù)過(guò)程中存在大量需要進(jìn)行優(yōu)化的決策問(wèn)題，而車輛調(diào)度正是關(guān)系到配送速度、配送服務(wù)質(zhì)量、配送成本的核心問(wèn)題[1]．從這一角度上來(lái)說(shuō)，對(duì)多配送中心車輛調(diào)度優(yōu)化問(wèn)題進(jìn)行研究有著非常重要的意義.

1 車輛調(diào)度問(wèn)題概述

作為現(xiàn)代智能化物流系統(tǒng)中非常重要的環(huán)節(jié)之一，物流配送應(yīng)當(dāng)根據(jù)用戶方訂貨需求，在配送中心完成分貨、配貨工作并通過(guò)各種運(yùn)輸途徑將貨物送交至收貨方．如果將物流體系中的配送業(yè)務(wù)視作一個(gè)存在供求雙方關(guān)系的系統(tǒng)，則有關(guān)配送中心的車輛調(diào)度問(wèn)題就可以表述為：在擁有若干配送中心、配送車輛以及客戶的前提下，對(duì)車輛行駛路線以及從出行時(shí)間進(jìn)行合理調(diào)度與安排，以確保在車輛最大行駛距離以及最大載重條件的運(yùn)輸下能夠完成貨物在配送中心與客戶間的調(diào)度運(yùn)輸，達(dá)到目標(biāo)函數(shù)的最優(yōu)解[2]．因此，多配送中心車輛調(diào)度優(yōu)化問(wèn)題可以按照如圖1所示方式進(jìn)行描述.

圖1 多配送中心車輛調(diào)度優(yōu)化問(wèn)題示意圖

(1)

根據(jù)式(1)，對(duì)蟻群算法性能產(chǎn)生影響的因素包括信息素殘留系數(shù)、信息啟發(fā)式因子、總信息量、以及期望值啟發(fā)式因子等幾個(gè)方面．作為一種并行算法，螞蟻搜索過(guò)程保持較高的獨(dú)立性，信息通信通過(guò)信息激素的方式實(shí)現(xiàn)，在問(wèn)題空間多點(diǎn)同時(shí)進(jìn)行獨(dú)立解搜索操作，使整套算法在保持良好全局搜索能力的同時(shí)有較高的可靠性.

2 分解法求解多配送中心車輛調(diào)度問(wèn)題

2.1 分解法概述

分解法求解多配送中心車輛調(diào)度問(wèn)題的核心思路是將相對(duì)復(fù)雜的多配送中心車輛調(diào)度轉(zhuǎn)換為多個(gè)較簡(jiǎn)單單配送中心車輛調(diào)度問(wèn)題，整體問(wèn)題轉(zhuǎn)換為多個(gè)獨(dú)立且簡(jiǎn)單子問(wèn)題求解，各個(gè)子問(wèn)題最優(yōu)解進(jìn)行合成即為整體問(wèn)題的最優(yōu)解方案．在多配送中心車輛調(diào)度問(wèn)題的求解處理中，分解法一方面能夠使待求解問(wèn)題得到簡(jiǎn)化，另一方面還能夠縮短求最優(yōu)解的時(shí)間．根據(jù)前文分析，分解法的關(guān)鍵是解決單個(gè)配送中心服務(wù)區(qū)域的問(wèn)題，即如何將客戶分配至相應(yīng)配送中心．在蟻群算法中，解決該問(wèn)題的手段包括最近距離分配法以及邊界分配法這兩種類型．其中，最近距離分配法是指遵循距離最近的原則，通過(guò)對(duì)客戶與各個(gè)配送中心距離進(jìn)行計(jì)算的方式，遵循就近原則進(jìn)行分配．假定對(duì)于第i個(gè)客戶而言，該客戶距離第h個(gè)配送中心的距離可以用di(h)進(jìn)行表示，同時(shí)有dim=minDi的情況下，可以在客戶h與配送中心m間建立服務(wù)關(guān)系[3]．整個(gè)操作過(guò)程簡(jiǎn)單快捷，但僅納入對(duì)配送點(diǎn)與配送中心距離因素的考量，未評(píng)估配送點(diǎn)間距離因素的影響．便捷分配法則是遵循邊界原則分配配送中心．同樣對(duì)于di(h)而言，有集合關(guān)系Di={di(h)，h=1，2，…，H}，同時(shí)定義集合Di當(dāng)中最小值為minDi，次小值為subminDi，同時(shí)滿足r(i)=minDi/SubminDi，在此基礎(chǔ)之上定義存在σ，且滿足0<σ<1，此時(shí)若σ>r(i)，則用戶i可被分配至minDi對(duì)應(yīng)配送中心，若σ≤r(i)，則用戶i對(duì)應(yīng)配送中心可按照節(jié)約法進(jìn)行分配.

2.2 算法描述

(2)

(3)

考慮到對(duì)于單個(gè)配送中心而言，配送車輛均有一次配送的最大行駛距離限制，因此在完成對(duì)m+1客戶訪問(wèn)任務(wù)后，車輛k仍然有剩余最大行駛距離，并將其定義為：

(4)

(5)

(6)

3 蟻群算法改進(jìn)及其實(shí)現(xiàn)

3.1 算法改進(jìn)

按照前文所述方法進(jìn)行蟻群運(yùn)算容易出現(xiàn)搜索耗時(shí)長(zhǎng)，早熟停滯等問(wèn)題，為避免這些問(wèn)題影響最優(yōu)解輸出，應(yīng)著重提高算法的全局尋優(yōu)性能．前文提到的影響蟻群算法性能的參數(shù)包括：總信息量、信息啟發(fā)式因子、信息素殘留系數(shù)、以及期望值啟發(fā)式因子，在定義總信息量Q=1的情況下，對(duì)其他相關(guān)因素進(jìn)行優(yōu)化．在優(yōu)化后算法中，信息素更新受到如下式(7)-式(9)的影響：

(7)

(8)

(9)

其中，將迭代過(guò)程最優(yōu)解的距離值定義為f(sbest)，截止目前為止最優(yōu)解的距離值為Fbest，同時(shí)對(duì)于初始信息素τij(0)而言，滿足，τij(0)=τmax,根據(jù)上式(7)-式(8)，可知優(yōu)化后算法每次循環(huán)后僅在最優(yōu)路徑上留下信息素，算法正反饋?zhàn)饔靡约八惴ㄌ幚硭俣染玫搅艘欢ǔ潭鹊母纳疲诖嘶A(chǔ)之上，為更進(jìn)一步提高蟻群算法處理速度，改進(jìn)MMAS算法，用下式(10)-式(11)替代上式(7)-式(8)．經(jīng)二次優(yōu)化后，蟻群算法每次循環(huán)不但在最優(yōu)路徑上留下信息素，同時(shí)將信息素以負(fù)值方式留在最差路徑上，通過(guò)這種方式顯著強(qiáng)化了蟻群算法正反饋?zhàn)饔?，?duì)單次循環(huán)最差解進(jìn)行快速淘汰，使算法搜索速度更為理想.

τij(t+1)=ρτij(t)+△τij

(10)

(11)

3.2 實(shí)現(xiàn)步驟

第一步：對(duì)多配送中心車輛調(diào)度問(wèn)題相關(guān)參數(shù)進(jìn)行初始化處理.

第二步：定義NC并進(jìn)行初始化處理，令NC=0，同時(shí)定義配送區(qū)域H=h+1，若h>H，則直接轉(zhuǎn)入第九步處理程序.

第三步：定義f并進(jìn)行初始化處理，令f=0，循環(huán)次數(shù)NC=NC+1，循環(huán)達(dá)到一定次數(shù)后對(duì)算法參數(shù)α、β進(jìn)行修正，此環(huán)節(jié)中若NC>NCmax，則轉(zhuǎn)入第八步處理程序.

第五步：定義車輛k=k+1，在k>Kh的情況下轉(zhuǎn)入第四步進(jìn)行處理.

4 結(jié)語(yǔ)

文章基于對(duì)現(xiàn)代物流體系中配送車輛調(diào)度問(wèn)題的分析以及對(duì)蟻群算法模型的初步研究，提出基于分解法求解多配送中心車輛調(diào)度問(wèn)題的操作模型．在此基礎(chǔ)之上，對(duì)算法模型進(jìn)行改進(jìn)，并對(duì)改進(jìn)后模型的實(shí)現(xiàn)過(guò)程進(jìn)行分析，可用于解決多配送中心車輛調(diào)度問(wèn)題，尤其對(duì)物流配送中心業(yè)務(wù)高峰期下車輛調(diào)度緊張問(wèn)題的緩解有重要意義.