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