朱冰冰
摘要:為解決物流配送中突發(fā)性交通堵塞造成的干擾問(wèn)題,針對(duì)多車場(chǎng)帶時(shí)間窗的車輛路徑問(wèn)題,建立交通堵塞擾動(dòng)下多車場(chǎng)車輛路徑干擾管理模型,并用離散粒子群算法求解,驗(yàn)證模型和算法的可行性和有效性。
關(guān)鍵詞:交通堵塞;干擾管理;粒子群算法
一、引言
物流配送過(guò)程中,車輛經(jīng)常會(huì)受到隨機(jī)事件的干擾,如車輛故障、交通堵塞、顧客需求變化等。因此,如何有效處理此類干擾事件,是物流配送管理的難點(diǎn)。根據(jù)美國(guó)學(xué)者Yu Gang(2004)對(duì)干擾管理的定義可知,干擾管理正是處理這類問(wèn)題的方法論。
P.B.Mirchandani(2007)針對(duì)交通事故提出了干擾恢復(fù)備用車輛選擇。Lorin(2011)針對(duì)客戶需求和服務(wù)時(shí)間的變化構(gòu)建模型求解,驗(yàn)證了模型可行性。王旭坪等(2013)針對(duì)客戶需求變化干擾,提出了帶回程取貨車輛調(diào)度擾動(dòng)恢復(fù)模型。胡祥培等(2011)提出了多階段劃分方法,形成了處理時(shí)間延遲干擾問(wèn)題的序貫決策方法。
雖然上述文獻(xiàn)對(duì)干擾事件已經(jīng)有了一定的研究,但對(duì)多車場(chǎng)車輛路徑干擾問(wèn)題研究較少。本文研究交通堵塞多車場(chǎng)帶模糊時(shí)間窗的車輛路徑干擾管理模型及其算法,針對(duì)該類事件為物流企業(yè)提供決策支持。
二、交通堵塞多車場(chǎng)帶時(shí)間窗VRP干擾管理模型
三、求解算法
本文基于標(biāo)準(zhǔn)粒子群算法,提出離散粒子群優(yōu)化算法進(jìn)行求解。粒子群算法(PSO)是通過(guò)模擬鳥群覓食過(guò)程中遷徙和群聚行為而提出的基于群體智能的隨機(jī)搜索算法。PSO是將群中的個(gè)體看做在D維搜索空間中的微粒,每個(gè)粒子都有自己的適應(yīng)度值,以一定的速度v在解空間中運(yùn)動(dòng),通過(guò)不斷的迭代尋找最優(yōu)解。
(一)編碼方案
標(biāo)準(zhǔn)的粒子群算法具有連續(xù)本質(zhì),不太適宜求解離散問(wèn)題。因此,本文在屬于連續(xù)空間的粒子與屬于離散空間的行駛方案之間建立一種聯(lián)系,即設(shè)計(jì)粒子群編碼來(lái)映射行駛方案的解。將車場(chǎng)和需求點(diǎn)統(tǒng)一編碼,并以車場(chǎng)編號(hào)進(jìn)行劃分各個(gè)車場(chǎng)要服務(wù)的需求點(diǎn)的子竄,得到了每個(gè)車場(chǎng)服務(wù)的需求點(diǎn)之后,再根據(jù)每個(gè)需求點(diǎn)的需求量和每個(gè)車場(chǎng)的車輛的載重進(jìn)行指派車輛服務(wù),進(jìn)而完成整個(gè)解碼過(guò)程。
(二)堵塞問(wèn)題處理
加入路徑干擾或者堵塞的原理:對(duì)受到影響的客戶點(diǎn)i到客戶點(diǎn)j的路徑i→j,將其距離乘以一個(gè)系數(shù),如此一來(lái)使得i到j(luò)之間的虛擬距離邊長(zhǎng)了,也即產(chǎn)生了延遲,如果虛擬距離設(shè)置為無(wú)限大,那么這段路就是堵塞了。因此,對(duì)距離矩陣進(jìn)行延遲處理,也即改變其距離,然后在進(jìn)行用算法優(yōu)化得到相應(yīng)的結(jié)果。公式為Di,j=Di,j*γ,其中Di,j為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離,γ>1為延遲系數(shù),γ=inf時(shí)發(fā)生堵塞。
四、實(shí)驗(yàn)結(jié)果分析
本文的算法以matlab語(yǔ)言實(shí)現(xiàn),運(yùn)行程序在Inter Core 2.2GHz的處理器、內(nèi)存為2G的計(jì)算機(jī)上。本文數(shù)據(jù)從算例RC101取部分節(jié)點(diǎn)產(chǎn)生,最后計(jì)算結(jié)果不僅給出調(diào)整的路徑結(jié)果,同時(shí)在客戶容忍的時(shí)間窗內(nèi)計(jì)算客戶滿意度。在多車場(chǎng)車輛路徑的情形里,發(fā)生干擾事件后,從成本和客戶滿意度方面進(jìn)行量化并建立模型,快速生成新方案,兼顧各方利益,同時(shí),車輛在多個(gè)車場(chǎng)之間得到良好協(xié)調(diào)。
參考文獻(xiàn):
[1]Gang Yu,Xiangtong Qi.Disruption management:framwork,models,and applications[M].World Scientific Publishing Co.Pte.Ltd,2004.
[2]Jing Quan Li,Denis Borenstein,Pitu B.Mirchandani.A decision support system for the single-depot vehicle rescheduling problem[J].Computers and Operations Research,2007,34(4):1008-1032.
[3]王旭坪,阮俊虎,孫自來(lái),曹海艷.帶回程取貨車輛路徑問(wèn)題的干擾恢復(fù)模型[J].系統(tǒng)工程學(xué)報(bào),2013:28(5):608-616.
[4]胡祥培,于楠,丁秋雷.物流配送車輛的干擾管理序貫決策方法研究[J].管理工程學(xué)報(bào),2011,25(2):186-190.