1、動態車輛路徑問題排隊模型分析第 9卷第 1期 2006年 2月 管 理 科 學 學 報 JOURNAL OF MANAGEMENT SCIENCES IN CHINA V019 No1 Feb20()6 動態車輛路徑問題排隊模型分析 郭耀煌，鐘小鵬 (西南交通大學經濟管理學院，成都 610031) 摘要：分析了一類動態車輛路徑問題，其中顧客需求以泊松流形式出現，現場服務時間服從一 般分布。提 出解決該問題的兩種策略：順序服務策略和中點改進策略，利用排隊論、幾何概率論 等領域的知識分別求出了這兩種策略的系統時間，并通過仿真數據實驗驗證了這兩種策略的 有效性 關鍵詞：動態車輛路徑問題；旅行商問題；

2、排隊論；幾何概率 中圖分類號：U1162；02212 文獻標識碼：A 文章編號：10ft一9807(2006)01003305 0 引 言 車輛路徑問題(vehicle routing problem， ) 將運籌學理論與交通運輸中的實際問題緊密聯系 在一起，被認為是運籌學領域4o多年來研究最活 躍、成果最精彩的方向之一_1 J 可以大致描 述為一組車輛從單個或多個車場出發，沿著一定 的路徑去不同地點執行運輸服務，如裝貨、卸貨、 運貨或其它現場服務l2,3j傳統的vRP研究多集 中在靜態模型，近 lO年來，由于通訊技術和信息 技術的發展，明顯區別于傳統靜態模型的動態車 輛路徑問題引起了人們的廣

3、泛重視 與靜態 vRP相對應，動態VRP模型的特征表現為：1)計 劃者在制定車輛路線時并不完全知道所有相關的 信息；2)新的信息會在路線安排過程以及執行過 程中到來，原有的信息也可能發生改變；3)計劃者 不可能僅通過一次調度就得到確定的執行的行車 路線本文以顧客等待時間最小化作為系統目標， 研究了一類動態vRP的實時優化策略，計算出其 期望系統時問，通過數據仿真試驗驗證，表明它比 傳統的先來先服務策略更好 收稿 日期：20031031；修訂日期：200 管 理 科 學 學 報 2OO6年 2月 類似地，可以求得 E(1 zl z2 1)一052a (2) Vat(1 z1 z2 1)=E(1

4、z1 z2 I)一 (I zIz2 I) 006a (3) 設 z為1內服從均勻分布的一個隨機點，zn為 A 的中點，用上面的方法可以得到 E(1 z0z l )： (4) E(i ()z I)一038a ( 第 1期 郭耀煌等：動態車輛路徑問題排隊模型分析 均勻分布，所以根據式(2)、(3)有 d=E(I Z1 Z2 I)一052a 【 r(d)=liar(I Z1 Z2 I)一006a 因為E(I z。 z。I)= (一z ) ( 妻 )， (11) 所以有 把式(11)代入式(10)，得到順序服務策略的系統 時間 序服務策略 =(了+ )+ +o5 2a + (s )+ O06a2 (1

5、一 +05 2a) (12) 32 中點重定位策略 不同于靜態車輛路徑問題，在動態模型中減 小動態需求的等待時間往往比減小貨車行駛的總 距離或時間更為重要 考慮在沒有新的需求時調整貨車停留地的策 略以減小顧客等待時間圖 1中，由定義可知 I z1 z2 I=d，并設 d =I z1 z2 I當貨車執行完 z 點的任務后，如果已有需求 z2排隊，則貨車立即 從z 駛向Z2；如果隊列中沒有需求，則貨車返回中 點z0返回途中如果在某點Z，接收到新的需求Z2， 則立即駛向z：，否則返回到 zn待命此時有 J i Z0 田1 動態車輛路徑問題的中點重定位策略 Fig1 Median strategy o

6、f dynamic vehicle routing problem 點重定位策略 =(了+ )+ |=L _ _ _ 2 ( + ) + s)+一Var (d J ZlZo J - I啊t 0 38a ： Zl zl ， ： ? - (14) 038凸一 一T1 、 按照公式(1)，(2)的推導方法，可以求得 E(d，) )：(1+C2)竿 D -= ( 、 5 dxz2dy )d dy Var(d )：E(d ) )一( ) 要顯性地求出式(15)中的d 比較麻煩，實際 計算時可運用計算軟件(如 Mathematica)求得具 體數據 4 一個仿真例子 表 1給出了例子的系統參數 裹1 一個

7、動態車輛路徑問題例子的系統參數 Table l Parameters of the example Tr廣 一 f 1 I 服從0，o5內的均勻分布， a=l 1 V=1 l =091一 一 l J 025 1iar( ) 002 由式(9)，可以求出順序服務策略的系統時問 序服務策略 176，而由式(10)、(11)、(12)，得至0中點 重定位策略的系統時問 點重定位策略一16 一 36 一 管 理 科 學 學 報 2006年 2月 匝序服務策略 = 5O 序月睹 策略一 稅 = 耋 一黼 誤差率 序服務策略 一 匝序服務策略 ：= 一 順序服務策略 X 10o 115 I 312 l中點

8、重毫 可以看出仿真結果 匝序服務策略、 中點重定位策略 都與各自理論計算值基本保持一致中點重定位 策略的系統時間比順序服務策略的系統時間減少 率為 點重定位铘 一 卿芋服務策略 一 ：= 一 TeeA X 100 805 仿真結果表明了中點重定位策略比順序策略 參 考 文獻： 更能減小顧客的平均等待時間 5 結束語 與靜態模型相比，動態車輛路徑問題的研究 更具有實際意義本文應用排隊論、幾何概率論等 理論導出r一類動態車輛路徑問題系統時間的公 式雖然在公式推導過程中作了一些簡化，但這一 結果可以推廣到更為一般的情形，如多車型有限 載荷，任意凸有界區域等本文還給出了順序服務 和中點重定位這兩種實時

9、策略的各自的系統時 間需要注意的是為了使動態車輛路徑問題的排 ， 一 、 隊模型穩定，一定要滿足P= (s +號)<l的條 、 件當 增大時，如果s 和 受客觀條件制約不能 改變，這時調度人員可以減小 d，即通過把整個服 務區域分解成若干個子區域來實現 1Canen A G，Scott L GBridging theory and practice in vRPjJournal of the Operational Society，1995，46(1)：18 2郭耀煌，李 軍車輛優化調度M成都：成都科技大學出版社，1994 Guo Yao-hnang，Li JunOptimum Sche

10、duling ofVehicleslMChengdu：Chengdu Science and Technology University Press，1994 (in Chinese) 3李 軍，郭耀煌物流配送車輛優化調度理論與方法M北京：中國物資出版社，2001 Li Jun，Guo Yao-huangTheory and Method of Vehicle Optimum Scheduling in Logistics DistributionMBeijing：The Goods and materials Press of China，2001(in Chinese) 4Psaraftl

11、s HDynamic vehicle routing：Slatus and prospectsJAnnalsof Operations Research，1995，61：143-164 5謝秉磊，郭耀煌，郭 強動態車輛路徑問題：現狀與展望J系統工程理論方法應用，2002，11(2)：11612o Xie Bing-lei，Guo Yao-huang，Guo QiangThe dymmic vehicle routing problem：Status and prospectsJSystems Engineering： Theory，Methodology，Applications，2002，l

12、l(2)：ll 1加(in Chinese) l6Bertsimas D JRyfin G VA stochastic and dynamic vehicle muting problem in the euclidean planeJOperations Research， 1991，39(4)：601-61 第 1期 郭耀煌等：動態車輛路徑問題排隊模型分析 13宋衛斌，蘇 秦虛擬顧客服務系統排隊模型J管理科學學報，2001，4(3)：5257 Song Wei_bm，Su QinQueueing model of service for invented customer systemJJournal of Management Sciences