熊 浩，符 卓，鄢慧麗

（1.中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙410083；2.長沙理工大學(xué) 交通運輸工程學(xué)院，湖南 長沙410004）

Psaraftis［1－2］最 早 提 出 了 動 態(tài) 旅 行 商 問 題（dynamic vehicle routing problem，DVRP），并 將DVRP定義為“安排車輛路徑以滿足實時出行的顧客需求”.后來，Bertsimas等［3－5］利用排隊理論進行策略有效性分析和設(shè)計，提出了多種優(yōu)化策略.Pillac等［6］對動態(tài)車輛路徑問題進行了綜述，首先將動態(tài)車輛路徑問題分為動態(tài)確定性問題和動態(tài)隨機性問題.動態(tài)確定性問題的方法分為精確算法和啟發(fā)式策略，分別包括基于線性規(guī)劃的滾動優(yōu)化法［7］、動態(tài)列生成算法［8］和基于場景的計劃法［9］、動態(tài)蟻群算法［10］等；動態(tài)隨機性問題的方法主要有Sampling策略［9］等.

20世紀90年代后期在計算機技術(shù)發(fā)展后，動態(tài)需求車輛路徑問題雖然逐漸得到了重視，但是相關(guān)研究注重以算法設(shè)計為主，其策略研究反而被忽略了.目前相對較好的策略是分區(qū)定量旅行商策略或分區(qū)定時旅行商策略［3－5］，且這2種策略的有效性相同，所以一般可以把這2種策略合稱為分區(qū)分批旅行商策略.但是該策略的有效性離理想狀態(tài)的效果仍有較大差距，是理想狀態(tài)的策略下界值的11倍［3－5］.可見，密集需求的實時優(yōu)化策略仍然有很大的進一步探索改進空間.

因此，本文在分區(qū)分批旅行商策略的基礎(chǔ)上提出了一種新的策略——隱分區(qū)靈活分批旅行商策略.該策略利用虛擬區(qū)域進行掃描分區(qū)，并且允許在排隊等候時分區(qū)中新出現(xiàn)的顧客進入決策，并保證優(yōu)化路徑中的顧客數(shù)與進入隊列時顧客群的顧客數(shù)保持一致.對這種新策略的有效性分析表明，新策略能在不改變顧客群排隊時間的情況下減少車輛平均行駛距離和顧客群形成時間，從而使平均系統(tǒng)時間減少.最后對該策略進行了仿真分析，結(jié)果表明了靈活分批旅行商策略相對于一般分批旅行商策略有較大的改進.

1 問題描述

本文的動態(tài)車輛路徑問題是指完全動態(tài)需求車輛路徑問題.完全動態(tài)需求是指動態(tài)出現(xiàn)的顧客要求響應(yīng)時間為零的車輛路徑問題，即顧客希望從呼叫到被服務(wù)的時間為零.該類問題在優(yōu)化的時候以追求響應(yīng)時間最短為唯一目標，盡量減少顧客等待時間.常見的動態(tài)旅行商問題（dynamic traveling salesman problem，DTSP）、動 態(tài) 修 理 員 問 題（dynamic traveling repairing problem，DTRP）等都屬于完全動態(tài)需求車輛路徑問題.準動態(tài)需求問題是指動態(tài)出現(xiàn)的顧客對響應(yīng)時間有一定的容忍范圍，允許在一定的時間范圍之內(nèi)接受服務(wù)的車輛路徑問題.根據(jù)響應(yīng)時間的時間范圍不同可以分為帶時間窗的動態(tài)需求車輛路徑問題和多階段動態(tài)車輛路徑問題.前者給出最早可以開始服務(wù)的時間和最晚必須服務(wù)的時間，后者只有最晚必須服務(wù)時間.該類顧客因為有提前呼叫的時間段，所以運營商有時間進行合理安排，所以這類問題一般以車輛路徑最短或服務(wù)的顧客最多為主要目標.

完全動態(tài)車輛調(diào)度問題包括：動態(tài)旅行商問題、動態(tài)修理員旅行問題和在線旅行商問題（online travelling salesman problem，OLTSP）.其中，動態(tài)旅行商問題和動態(tài)修理員問題幾乎是同一類問題，是指修理員或車輛需要服務(wù)隨時間動態(tài)出現(xiàn)的顧客需求，目標是使期望系統(tǒng)時間最少.顧客需求產(chǎn)生過程的時間符合以分布密度為λ的泊松分布，且獨立分布在某個區(qū)域A；車輛從車場出發(fā)以固定的速度去服務(wù)這些顧客，在每個顧客節(jié)點的服務(wù)時間為t0，節(jié)點i和節(jié)點j之間的距離為tij，該問題需要銷售商尋找最優(yōu)的路徑去服務(wù)這些需求，使每個顧客的平均系統(tǒng)時間最少.系統(tǒng)時間是每個顧客從其出現(xiàn)在系統(tǒng)中到服務(wù)被完成所必須花費的平均時間，包括等待時間和在線服務(wù)時間.利用顧客出現(xiàn)過程的時間分布和地理位置分布尋找最優(yōu)的策略使系統(tǒng)時間最少.

2 隱分區(qū)靈活分批旅行商策略

2.1 策略概述

隱分區(qū)策略是指在靜態(tài)子問題形成規(guī)則上做一些區(qū)域范圍的規(guī)定.區(qū)域中的分區(qū)并不固定，而是按照一定的規(guī)則靈活確定，滿足被計劃的顧客處在一定區(qū)域范圍內(nèi)，從而保證旅行商平均距離較短.隱分區(qū)策略又分為隱分區(qū)定量策略和隱分區(qū)定時策略.

隱分區(qū)策略利用普通分區(qū)策略的基本思路，保證制定計劃的顧客路徑始終發(fā)生在一定的區(qū)域內(nèi)，從而同樣保證了路徑的平均距離較短；并且由于是隱分區(qū)，所以顧客群組形成時間更短，從而縮短了平均系統(tǒng)時間.因此，與普通分區(qū)策略相比，其隊列形成時間變短，群組在隊列中的排隊時間不變，群組服務(wù)時間不變，群組的服務(wù)過程中的路徑時間不變.從而隱分區(qū)策略能夠使顧客的平均系統(tǒng)時間變短.

（1）隱分區(qū)定量策略.將區(qū)域分割成k個分區(qū)，則隱分區(qū)的范圍為2π/k.在區(qū)域中構(gòu)建2條射線夾角為2π/k的扇形，以該扇形進行掃描搜索，當(dāng)扇形覆蓋區(qū)域的顧客數(shù)大于等于n（定量策略的批量）時，該被覆蓋區(qū)域構(gòu)成的分區(qū)進入隊列，見圖1a.

（2）隱分區(qū)定時策略.將區(qū)域分割成k個分區(qū)，則隱分區(qū)的范圍為2π/k.在區(qū)域中構(gòu)建2條射線夾角為2π/k的扇形，每隔固定時間T，以該扇形對整個區(qū)域進行掃描搜索，統(tǒng)計所有被扇形覆蓋區(qū)域中顧客數(shù)量，被覆蓋區(qū)域顧客最多的區(qū)域被鎖定并進入隊列，見圖1b.

圖1 隱分區(qū)靈活定量與定時策略排隊情況Fig.1 The queuing of the virtual partition and flexible time batch TSP strategy

（3）靈活分批策略.靈活分批策略是對分區(qū)分批策略做了一些調(diào)整而形成的策略.假設(shè)分區(qū)進入隊列的時間為T1，車輛空閑的時間為T2，計劃優(yōu)化計算需要時間為Δt，則開始決策時間為T3＝max｛T1，（T2－Δt）｝.當(dāng)決策的時間為T2－Δt時，則T1～（T2－Δt）時間內(nèi)出現(xiàn)的新顧客也會進入決策范圍，從而使顧客數(shù)大于定量策略的批量n或定時策略的顧客批量N.

2.2 有效性分析

隱分區(qū)定量旅行商策略與普通分區(qū)定量旅行商策略相比，不再以固定的分區(qū)統(tǒng)計顧客數(shù)量，而是任意夾角為2π/k的區(qū)域中顧客數(shù)達到n個時該區(qū)域被鎖定進入隊列.該策略不改變顧客的平均服務(wù)等待時間，不改變顧客群排隊時間.由于隊列仍然符合顧客到達時間間隔是一般分布和服務(wù)時間也為一般分布的G/G/m排隊模型條件［4］，且相關(guān)參數(shù)都沒有改變，所以分區(qū)排隊時間不變，但是顧客群形成時間可能會縮短，因為原固定分區(qū)邊界附近屬于不同分區(qū)的顧客按照隱分區(qū)策略只要達到n個也可以進入隊列，而原分區(qū)策略則仍然需要等待.

同樣，隱分區(qū)定時旅行商策略與普通分區(qū)定時策略相比，不再是以固定間隔期的掃描時間確定進入隊列，而是在固定的時間間隔內(nèi)，只要夾角為2π/k的區(qū)域中顧客數(shù)最多，則該區(qū)域被鎖定并進入隊列.該策略不改變分區(qū)顧客群形成時間和顧客群排隊時間（由于隊列仍然符合顧客到達時間間隔是固定值和服務(wù)時間為一般分布的D/G/m排隊模型條件，排隊時間的相關(guān)參數(shù)不變，所以分區(qū)排隊時間不變）；該策略能使同等時間內(nèi)分區(qū)中的顧客數(shù)量增加，則分攤到單個顧客的形成時間、排隊時間減少；且更多顧客構(gòu)成的路徑平均距離縮短；而單個顧客的服務(wù)時間固定不變；因此，隱分區(qū)靈活定時策略的平均系統(tǒng)時間明顯減少.

另外，隱分區(qū)靈活定量策略與隱分區(qū)非靈活定量策略相比，在隱分區(qū)內(nèi)進行不同群組中顧客的交換優(yōu)化要確保不影響群組形成時間.當(dāng)某個隱分區(qū)出現(xiàn)n個顧客時，按照規(guī)則對出現(xiàn)時間點和車輛空閑時間進行比較，若車輛空閑時間較晚則需要等待.由于等待可能會出現(xiàn)新的顧客，這時靈活分批要求將所有已經(jīng)出現(xiàn)顧客加入決策系統(tǒng)進行“擇優(yōu)選擇”.通過擇優(yōu)減少路徑時間，從而減少顧客系統(tǒng)時間.但是，擇優(yōu)選擇可能會使后來出現(xiàn)的顧客被安排進入執(zhí)行計劃，從而使非靈活分批策略的顧客發(fā)生了變化，數(shù)量不變但是位置發(fā)生了改變，所以對后續(xù)的隱分區(qū)的形成時間有一定影響，該影響比較隨機而難以判斷.

同理，隱分區(qū)靈活定時策略與隱分區(qū)非靈活定時策略相比，在隱分區(qū)內(nèi)進行不同群組中顧客的交換優(yōu)化不影響群組顧客的平均數(shù)量，需要事先統(tǒng)計隱分區(qū)的顧客數(shù)量，以保證靈活分批后的顧客數(shù)量仍然保持不變，以確保不影響群組形成時間而不改變排隊模型.但是，同樣由于擇優(yōu)選擇會影響顧客的位置，所以對后續(xù)的隱分區(qū)的形成時間有一定影響.

2.3 策略構(gòu)建

2.3.1 隱分區(qū)靈活定量旅行商策略

整個區(qū)域的顧客數(shù)達到n時以夾角為θ0的扇面開始掃描，判斷是否有n個顧客落在該扇面之內(nèi)，若沒有，繼續(xù)等待新的顧客出現(xiàn)直至以夾角為θ0的扇面能夠掃描，使落在該扇面內(nèi)的顧客數(shù)為n，該n個顧客中以極坐標角度θ1～θ2之間的扇面區(qū)域進入隊列，其中θ1為最小值，θ2＝θ1＋θ0.

2.3.2 隱分區(qū)靈活定時旅行商策略

每隔T0時間以夾角為θ0的扇面開始掃描，統(tǒng)計扇面內(nèi)顧客的數(shù)量和扇面的位置，扇面內(nèi)顧客數(shù)最多的區(qū)域進入隊列排隊.統(tǒng)計這時分區(qū)中的顧客數(shù)N，該區(qū)域為以其中顧客極坐標角度為θ1～θ2的扇面區(qū)域.

2.3.3 靈活分批策略

實時優(yōu)化策略決策輸入要素為顧客和車輛，其確定方法如圖2所示，其中T3為決策時間；T4為計劃分派時間；T′3為上次決策時間；T′4為上次計劃分派時間.

圖2 靜態(tài)子問題的輸入信息Fig.2 The input information of the static sub－problem

（1）靜態(tài)子問題的顧客群包括上次計劃時剩下未被服務(wù)的顧客和新出現(xiàn)的顧客.若用C表示在T4時上次計劃時剩下未被服務(wù)的顧客，Q表示在［T′3，T3］期間新出現(xiàn)的顧客，則在T3時進入決策的顧客為N′，N′＝C∪Q.并且，靜態(tài)子問題的優(yōu)化決策需要從顧客群N′中挑選最優(yōu)的n或N個顧客構(gòu)成新的路徑計劃.

（2）靜態(tài)子問題的車輛包括正在執(zhí)行路徑計劃的車輛和在車場等待的車輛.首先可以根據(jù)路徑計劃計算出在新的決策時刻執(zhí)行完路徑計劃的可用車輛為U1；然后考慮決策時仍然在車場閑置的車輛U0，則所有可用的車輛為V＝U1＋U0；最后從這些車輛中挑選合理的車輛進行路徑計劃.

3 實例仿真

3.1 仿真步驟

（1）設(shè)置策略參數(shù)：區(qū)域分區(qū)數(shù)量k，隱分區(qū)的角度θ0＝2π/k；區(qū)域分批的顧客數(shù)量n或定時的時間間隔T.

（2）生成顧客；隨機生成顧客位置在均勻分布的圓形區(qū)域，取原點為圓心；隨機生成到達時間間隔為負指數(shù)分布，累計構(gòu)成顧客的隨機到達時間，則該過程符合泊松過程.按照一定的條件設(shè)置參數(shù)：服務(wù)強度趨向于1，即服務(wù)時間與單位時間到達顧客個數(shù)之積趨近于1（多車輛需要除以車輛數(shù)）；一般區(qū)域半徑時間距離大于顧客服務(wù)時間（說明距離對系統(tǒng)時間影響較大，且符合實際情況）.一般限定顧客的總數(shù)量或者仿真時間長度.

（3）隱分區(qū)靈活定量旅行商策略的主循環(huán)包括以下三方面的主要內(nèi)容.①首先，利用扇形區(qū)域進行掃描，尋找滿足條件的區(qū)域.對于定量分批：統(tǒng)計區(qū)域中剩余未被安排計劃的顧客數(shù)量，當(dāng)整個區(qū)域中的顧客數(shù)量超過n時，開始隱分區(qū)掃描，若這n個顧客構(gòu)成的區(qū)域最小夾角大于θ，則需繼續(xù)等待新的顧客出現(xiàn)，每出現(xiàn)1位顧客，掃描1次，直到n＋Nt個（Nt表示前n個顧客之后出現(xiàn)的顧客數(shù)量），此時n＋Nt顧客中至少有n個顧客構(gòu)成的夾角小于等于θ.對于定時分批：在每個定時時間間隔點統(tǒng)計各種可能的隱分區(qū)的顧客數(shù)量，按照當(dāng)前系統(tǒng)中的顧客的角度從小到大排序，從系統(tǒng)中顧客角度最小的顧客開始掃描θ0，記錄該分區(qū)中的顧客數(shù)；然后依次從第2位顧客開始掃描θ0，記錄該分區(qū)中的顧客數(shù)；直到最后1位顧客再掃描θ0.記錄所有隱分區(qū)中顧客數(shù)量（假設(shè)為N，每個定時間隔點可能都不同）最大的隱分區(qū)的開始角度θ1和結(jié)束角度θ2.②比較進入隊列時間和車輛空閑時間，確定決策開始時間；根據(jù)該時間統(tǒng)計上一步確定的分區(qū)內(nèi)的顧客數(shù)量，進行路徑優(yōu)化分派.路徑優(yōu)化的方法可以采用不同的智能啟發(fā)式算法：遺傳算法、蟻群算法、粒子群算法等，本文選用遺傳算法.③對仿真期間剩余顧客進行更新，刪除已分派的顧客.

（4）循環(huán)結(jié)束條件：區(qū)域中剩余的顧客不能滿足分區(qū)進入隊列條件.

3.2 實例

設(shè)置1組數(shù)據(jù)進行仿真：區(qū)域范圍的半徑為r＝10，車輛數(shù)量為m＝5，顧客到達的時間符合泊松分布且平均值為λ＝10，服務(wù)時間為s＝1；設(shè)置策略參數(shù)：k＝10，n＝10或T＝20和計算時間Δt＝0.5，分別采用隱分區(qū)定量旅行商策略和隱分區(qū)靈活定量旅行商策略進行仿真，結(jié)果如表1所示.該結(jié)果表明：隱分區(qū)靈活定量旅行商策略由于可以較大幅度地降低路徑長度，從而使顧客的平均系統(tǒng)時間有所縮短.

表1 隱分區(qū)定量與隱分區(qū)靈活定量旅行商策略仿真結(jié)果Tab.1 Results of the simulation on the flexible and the non－flexible quantity batch strategies

利用該參數(shù)重新生成另外1組顧客，分別采用隱分區(qū)定時旅行商策略和隱分區(qū)靈活定時旅行商策略進行仿真，結(jié)果如表2所示.該結(jié)果顯示：隱分區(qū)靈活定時旅行商策略由于可以減少平均路徑長度，從而使顧客平均系統(tǒng)時間也有所減少.

表2 隱分區(qū)定時與隱分區(qū)靈活定時旅行商策略仿真結(jié)果Tab.2 Results of the simulation on the flexible and the non－flexible time－batch strategies

4 結(jié)論

隱分區(qū)靈活分批旅行商策略分為隱分區(qū)靈活定量旅行商策略和隱分區(qū)靈活定時旅行商策略.相對于一般分區(qū)分批旅行商策略而言，新策略主要從2個方面做了改進：①通過設(shè)置虛擬分區(qū)，保持了分區(qū)顧客的到達率不變，使顧客群的形成時間減少；②對決策時間進行了調(diào)整，允許在顧客群形成時間與開始決策時間內(nèi)出現(xiàn)的新顧客進入決策，使進入計劃的顧客更多，從而使路徑平均距離更短.仿真分析結(jié)果也證明了新策略能夠使路徑距離變短，從而使平均系統(tǒng)時間減少.

［1］ Psaraftis H N.Dynamic vehicle routing：status and prospects［J］.Annals of Operations Research，1995，61（1）：143.

［2］ Psaraftis H N.Dynamic vehicle routing problems［M］.North－Holland：Elsevier Science Publishers B V，1988.

［3］ Bertsimas D J，Van Ryzin G.Stochastic and dynamic vehicle routing with general demand and interarrival time distributions［J］.Advances in Applied Probability，1993，25（4）：947.

［4］ Bertsimas D J，Van Ryzin G.Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles［J］.Operations Research，1993，41（1）：60.

［5］ Bertsimas D J，Van Ryzin G.A stochastic and dynamic vehicle routing problem in the Euclidean plane［J］.Operations Research，1991，39（4）：601.

［6］ Pillac V，Gendreau M，Guéret C，et al.A review of dynamic vehicle routing problems［J］.European Journal of Operational Research，2013，225（1）：1.

［7］ Yang J，Jaillet P，Mahmassani H.Real－time multivehicle truckload pickup and delivery problems［J］.Transportation Science，2004，38（2）：135.

［8］ Chen Z L，Xu H.Dynamic column generation for dynamic vehicle routing with time windows［J］. Transportation Science，2006，40（1）：74.

［9］ Bent R W，Van Hentenryck P.Scenario－based planning for partially dynamic vehicle routing with stochastic customers［J］.Operations Research，2004：977.

［10］ Montemanni R，Gambardella L M，Rizzoli A E，et al.Ant colony system for a dynamic vehicle routing problem［J］.Journal of Combinatorial Optimization，2005，10（4）：327.