動(dòng)態(tài)路網(wǎng)下帶時(shí)間窗車輛路徑規(guī)劃問(wèn)題研究

盛 強(qiáng)，鄭鵬飛，孫軍艷

（1.陜西科技大學(xué)，陜西 西安 710021；2.鄭州風(fēng)神物流有限公司，河南 鄭州 450000）

1 引言

車輛路徑問(wèn)題（VRP）最早是由Dantzig和Ramser于1959年提出，經(jīng)典的VRP假設(shè)已知客戶網(wǎng)絡(luò)中的客戶數(shù)量、客戶所在的位置、客戶需求和配送車輛的最大負(fù)荷，要求在滿足約束的前提下為給定的中心倉(cāng)庫(kù)設(shè)計(jì)車輛路徑，使運(yùn)輸成本最小。隨著研究的不斷深入，考慮客戶對(duì)配送時(shí)效性的要求衍生出帶時(shí)間窗約束的VRP（VRP with Time windows,VRPTW），其最優(yōu)解是在VRP的基礎(chǔ)上通過(guò)增加車輛數(shù)或行駛距離以滿足顧客對(duì)時(shí)間的要求，VRPTW的提出體現(xiàn)了物流配送企業(yè)在關(guān)注成本的同時(shí)開(kāi)始關(guān)注服務(wù)質(zhì)量。但車輛配送過(guò)程是在動(dòng)態(tài)路網(wǎng)中進(jìn)行，靜態(tài)路網(wǎng)VRP最優(yōu)線路會(huì)受交通堵塞、管制等路況信息的影響，車輛所消耗的時(shí)間并不一定最短，配送效率和服務(wù)質(zhì)量也無(wú)法保障，特別是當(dāng)顧客對(duì)訪問(wèn)時(shí)間有限制時(shí)，影響更為嚴(yán)重。隨著市場(chǎng)競(jìng)爭(zhēng)越來(lái)越激烈，企業(yè)對(duì)服務(wù)質(zhì)量的要求越來(lái)越高，因此動(dòng)態(tài)路網(wǎng)下路徑規(guī)劃問(wèn)題的服務(wù)質(zhì)量成為企業(yè)關(guān)注的熱點(diǎn)。

求解動(dòng)態(tài)路網(wǎng)路徑規(guī)劃的方法主要分為兩類：一類是通過(guò)預(yù)測(cè)獲取路況信息作為已知條件在算法中體現(xiàn)，如袁二明等[1]通過(guò)預(yù)測(cè)交通網(wǎng)絡(luò)中發(fā)生擁堵的概率并結(jié)合圖論求解最短路線，何靚等[2]使用灰色理論預(yù)測(cè)各路段車流速度，以時(shí)間最短為目標(biāo)求解最優(yōu)路徑。另一類是定義反映路況信息的相關(guān)變量并引入到算法中進(jìn)行求解，如杜業(yè)凡[3]在GM(1,1)模型的基礎(chǔ)上，定義路阻函數(shù)并與蟻群算法結(jié)合給出算法流程圖，于麗梅[4]定義車輛隨機(jī)減速影響因子，以耗時(shí)最短為目標(biāo)應(yīng)用模擬退火算法求解耗時(shí)最短線路，蔡延光等[5]認(rèn)為不同時(shí)段、路段上車輛速度不同，將油耗率轉(zhuǎn)化為信息素?fù)]發(fā)因子應(yīng)用蟻群算法求解耗時(shí)最短線路，李培慶等[6]考慮道路等級(jí)、路面不平度等影響因素，建立VRPTW模型并應(yīng)用遺傳算法求解滿足時(shí)間限制的最短路徑。但相關(guān)文獻(xiàn)多以行駛距離或行駛時(shí)間為指標(biāo)進(jìn)行評(píng)價(jià)，未對(duì)服務(wù)質(zhì)量進(jìn)行相關(guān)討論。

為提高物流配送企業(yè)服務(wù)質(zhì)量和顧客滿意度，本文提出一種解決動(dòng)態(tài)路網(wǎng)下VRPTW的方法，考慮動(dòng)態(tài)路網(wǎng)下各路段分時(shí)段的道路通過(guò)能力（road capacity）差異，定義通過(guò)能力系數(shù)來(lái)反映實(shí)時(shí)路況信息，在VRPTW基礎(chǔ)上建立優(yōu)化模型，結(jié)合遺傳算法進(jìn)行求解，并與靜態(tài)路網(wǎng)VRPTW結(jié)果從服務(wù)滿意度、行駛距離等指標(biāo)進(jìn)行對(duì)比和分析，為企業(yè)協(xié)調(diào)配送成本與服務(wù)質(zhì)量之間的矛盾提供借鑒。

2 問(wèn)題描述

為研究動(dòng)態(tài)路網(wǎng)下路況信息對(duì)車輛路徑的影響，參考相關(guān)文獻(xiàn)中有關(guān)表述，道路通過(guò)能力是指在通常的道路、交通和管制條件下，在一定時(shí)間段內(nèi)車輛能夠通過(guò)道路某一點(diǎn)的最大數(shù)量。道路通過(guò)能力越大表明該路段車輛越少，車輛的自由度越高，行駛該路段的時(shí)間也就越短[7]。

考慮到路段在不同時(shí)段的通過(guò)能力不同，尤其是存在早高峰、晚高峰等情況，本文定義三維向量T（i，j，t）為通過(guò)系數(shù)，其中i和j表示客戶編號(hào)，t為時(shí)間變量。定義當(dāng)T=0時(shí)兩客戶之間道路不聯(lián)通，T=1時(shí)客戶i和j之間道路t時(shí)刻車流量正常，車輛可以正常速度行駛，T＜1時(shí)該時(shí)刻該路段產(chǎn)生不同程度的擁堵，通過(guò)系數(shù)越小，擁堵程度越大。

本文結(jié)合參考文獻(xiàn)[7]把通過(guò)系數(shù)反映到車輛速度上，在進(jìn)行線路規(guī)劃時(shí)車速Vi等于標(biāo)準(zhǔn)車速T與通過(guò)系數(shù)V的乘積。公式如下：

時(shí)間窗[e，l]是顧客期望的服務(wù)時(shí)間段，超出這個(gè)時(shí)間段服務(wù)效果必然下降，甚至顧客拒絕接收，配送中心因此會(huì)產(chǎn)生經(jīng)濟(jì)上的損失。為了量化配送車輛超出客戶時(shí)間窗后所受到的“懲罰”，以及提前到達(dá)所產(chǎn)生的“機(jī)會(huì)成本”，本文定義懲罰函數(shù)Pi(Si)表示配送中心違反時(shí)間窗的成本支出。

其中ei為客戶i時(shí)間窗的起點(diǎn)；li為客戶i時(shí)間窗的終點(diǎn)；si為客戶i到達(dá)的時(shí)間；p為提前到達(dá)的單位懲罰成本；q為滯后到達(dá)的單位懲罰成本。

3 數(shù)學(xué)模型

動(dòng)態(tài)路網(wǎng)下VRPTW是一個(gè)多約束優(yōu)化問(wèn)題，可描述為：1個(gè)配送中心最多可用m輛車訪問(wèn)n個(gè)客戶，每個(gè)客戶必須訪問(wèn)且只能訪問(wèn)一次，車輛集合K={1,2,…,k}，客戶集合N={1,2,…,n}，客戶需求為qi，車輛容量限制為Q，兩點(diǎn)間的配送距離為dij，運(yùn)輸時(shí)間為tij，每個(gè)客戶都有一個(gè)指定的時(shí)間窗[ei，li]，車輛早到或者晚到都要受到懲罰，各路段在不同時(shí)刻的通過(guò)系數(shù)T可通過(guò)交通管理部門獲取，所有車輛從配送中心出發(fā)，服務(wù)客戶后回到配送中心。決策變量分別為：

定義c1為單位距離運(yùn)輸成本，c2為車輛啟用固定成本，α為距離成本權(quán)重，β為車輛成本權(quán)重，γ為懲罰成本權(quán)重，在此基礎(chǔ)上建立以總成本最小為目標(biāo)函數(shù)的數(shù)學(xué)模型。如下：

其中，式（3）為目標(biāo)函數(shù)，包括距離成本、車輛成本、懲罰成本（提前或延遲）三種；式（4）表示每輛車從配送中心出發(fā)后又回到配送中心；式（5）表示每個(gè)客戶僅能被一輛車服務(wù)；式（6）為車輛容量限制；式（7）表示車輛到達(dá)客戶后必須離開(kāi)；式（8）為配送中心時(shí)間窗約束，fi為客戶i所需的裝卸時(shí)間（與需求量qi成正比），wi為車輛提前到達(dá)等待時(shí)間；式（9）為客戶時(shí)間窗約束；式（10）為懲罰函數(shù)。

4 算法設(shè)計(jì)

VRPTW問(wèn)題是一個(gè)NP難問(wèn)題，其求解主要集中在遺傳算法、蟻群算法等啟發(fā)式算法上。上世紀(jì)90年代Thangiah[8]和Joe[9]等就開(kāi)始研究用遺傳算法求解VRPTW問(wèn)題，隨后張麗萍等[10]、劉敏等[11]國(guó)內(nèi)學(xué)者針對(duì)遺傳算法求解VRPTW的“早熟性收斂”等問(wèn)題進(jìn)行了研究，并分別從改進(jìn)選擇規(guī)則、改進(jìn)變異方式等方面進(jìn)行相關(guān)研究，結(jié)果表明，改進(jìn)后的遺傳算法求解VRPTW效果優(yōu)于傳統(tǒng)遺傳算法。

車輛路徑是個(gè)順列問(wèn)題，本文采用自然數(shù)編碼，用矢量（s1,s2,…,sn）表示染色體，其中sn為1到n的自然數(shù)，表示客戶。首先隨機(jī)產(chǎn)生一組染色體，解碼過(guò)程依次從染色體中提取基因，檢查是否滿足約束條件，如果滿足就插入到線路中，如果不滿足就開(kāi)始新的路線，并在每條線路的起點(diǎn)和終點(diǎn)插入“0”表示配送中心。

為保證遺傳過(guò)程中優(yōu)秀基因高概率保留，在輪盤賭選擇前采用精英保留策略并對(duì)新種群進(jìn)行無(wú)序排列，將保留下來(lái)的優(yōu)良個(gè)體與輪盤賭選擇的個(gè)體隨機(jī)放置，以避免后續(xù)交叉過(guò)程中優(yōu)良個(gè)體相互交叉、隨機(jī)個(gè)體相互交叉的情況。

參考文獻(xiàn)[10]，本文采用類PMX重組方式，該方式能夠在父代染色體相同情況下達(dá)到一定的變異效果，對(duì)維持群體多樣性有較好的作用。選取兩個(gè)父代染色體A和B并隨機(jī)生成兩個(gè)交叉點(diǎn)，把兩個(gè)交叉點(diǎn)之間的基因片段添加到對(duì)方染色體的前端得到A′和B′，將交配區(qū)域后的重復(fù)基因刪除得到子代染色體A″和B″。具體過(guò)程如下所示：

變異策略是指?jìng)€(gè)體編碼串中的某些基因值用其它基因值來(lái)替換，從而形成一個(gè)新的個(gè)體。參考文獻(xiàn)[11]，本文采用基因片段反轉(zhuǎn)變異的變異策略，此策略在排序問(wèn)題方面優(yōu)于傳統(tǒng)的對(duì)換變異等策略。選取任意染色體C并隨機(jī)生成兩個(gè)交叉點(diǎn)，把兩個(gè)交叉點(diǎn)之間的基因片段進(jìn)行翻轉(zhuǎn)得到編譯后的染色體C′。具體過(guò)程如下所示：

C=6 5|8 2 4|7 9 3 1；C′=6 5|4 2 8|7 9 3 1

5 實(shí)驗(yàn)分析

對(duì)于車輛路徑問(wèn)題的測(cè)試算例最常用的是Solomon提出Benchmark Problems數(shù)據(jù)庫(kù)[12]。該測(cè)試庫(kù)中包含56個(gè)實(shí)例，每個(gè)實(shí)例都由一個(gè)配送中心和若干個(gè)顧客構(gòu)成，并給出了配送中心和客戶的位置坐標(biāo)、客戶的需求量以及服務(wù)的時(shí)間窗、車輛的載重量。結(jié)合本文研究對(duì)象選用實(shí)例R101，并結(jié)合實(shí)際取車輛的裝載量Q=80kg。根據(jù)以上信息得出算例見(jiàn)表1。

基于上述分析，運(yùn)行Matlab.2010b分別求解靜態(tài)路網(wǎng)和動(dòng)態(tài)路網(wǎng)VRPTW各40次，將運(yùn)行結(jié)果取均值進(jìn)行統(tǒng)計(jì)，見(jiàn)表2。

分別取動(dòng)態(tài)路網(wǎng)和靜態(tài)路網(wǎng)下40次求解中的最優(yōu)解路線圖和收斂圖，如圖1所示。

為定量評(píng)價(jià)不同算法的顧客滿意度，參考文獻(xiàn)[13]引入客戶滿意度函數(shù)U(Si)，并將其與車輛行駛距離等指標(biāo)進(jìn)行綜合分析。

表1 實(shí)驗(yàn)數(shù)據(jù)

表2 仿真結(jié)果統(tǒng)計(jì)

其中Si為第i個(gè)客戶的服務(wù)開(kāi)始時(shí)間，LTi為第i個(gè)客戶可接受最晚服務(wù)時(shí)間，ELTi為第i個(gè)客戶容忍最晚服務(wù)時(shí)間，β為時(shí)間的敏感系數(shù)，參考文獻(xiàn)[13]并結(jié)合實(shí)際，本文取β=1，ELTi取最晚服務(wù)時(shí)間加兩倍的服務(wù)時(shí)間，即：

其中k為裝卸服務(wù)時(shí)間與需求量的比例系數(shù)，為便于計(jì)算本文取k=1。從服務(wù)滿意度、車輛行駛距離、車輛數(shù)等指標(biāo)將上述兩問(wèn)題所運(yùn)行的40次最優(yōu)解進(jìn)行統(tǒng)計(jì)，結(jié)果見(jiàn)表3。

表3 實(shí)驗(yàn)效果對(duì)比

通過(guò)對(duì)比可以看出，本文提出的基于動(dòng)態(tài)路網(wǎng)的VRPTW模型獲得的最優(yōu)解比靜態(tài)路網(wǎng)最優(yōu)解提高了8.45%的服務(wù)滿意度，在車輛數(shù)不變的情況下增加了1.93%的車輛行駛距離，按照算例中的距離單位，實(shí)際增加行駛距離4.381km，相較于服務(wù)滿意度的提升，行駛距離增加量在可容忍范圍內(nèi)。本文提出的算法能夠幫助企業(yè)在平衡配送成本與服務(wù)質(zhì)量時(shí)提供一定的借鑒，尤其是對(duì)于追求高服務(wù)質(zhì)量的物流配送企業(yè)更加有價(jià)值。

圖1 不同路網(wǎng)環(huán)境下最優(yōu)路徑及收斂圖