濮明月,張彥如
(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)輸損失.
蟻群算法實(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)解.
路徑優(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è)公式表示配送車輛完成配送后都必須回到配送中心.
在物流配送的過程中,為保證配送物品的新鮮與完整,配送的成本一般包括固定成本和變動(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)化.
算例分析以某連鎖生鮮經(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í)間窗
在分別對(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í)間窗約束和懲罰約束的情況下,能夠得到總成本最低的物流配送路徑方案.
物流車輛的入境規(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)一步解決.