交通堵塞擾動(dòng)下多車場(chǎng)車輛路徑優(yōu)化

朱冰冰

摘要：為解決物流配送中突發(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.