動(dòng)態(tài)車輛路徑問題排隊(duì)模型分析.doc

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

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

3、泛重視 與靜態(tài) vRP相對應(yīng)，動(dòng)態(tài)VRP模型的特征表現(xiàn)為：1)計(jì) 劃者在制定車輛路線時(shí)并不完全知道所有相關(guān)的 信息；2)新的信息會(huì)在路線安排過程以及執(zhí)行過 程中到來，原有的信息也可能發(fā)生改變；3)計(jì)劃者 不可能僅通過一次調(diào)度就得到確定的執(zhí)行的行車 路線本文以顧客等待時(shí)間最小化作為系統(tǒng)目標(biāo)， 研究了一類動(dòng)態(tài)vRP的實(shí)時(shí)優(yōu)化策略，計(jì)算出其 期望系統(tǒng)時(shí)問，通過數(shù)據(jù)仿真試驗(yàn)驗(yàn)證，表明它比 傳統(tǒng)的先來先服務(wù)策略更好 收稿 日期：20031031；修訂日期：200 管 理 科 學(xué) 學(xué) 報(bào) 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) 設(shè) z為1內(nèi)服從均勻分布的一個(gè)隨機(jī)點(diǎn)，zn為 A 的中點(diǎn)，用上面的方法可以得到 E(1 z0z l )： (4) E(i ()z I)一038a ( 第 1期 郭耀煌等：動(dòng)態(tài)車輛路徑問題排隊(duì)模型分析 均勻分布，所以根據(jù)式(2)、(3)有 d=E(I Z1 Z2 I)一052a 【 r(d)=liar(I Z1 Z2 I)一006a 因?yàn)镋(I z。 z。I)= (一z ) ( 妻 )， (11) 所以有 把式(11)代入式(10)，得到順序服務(wù)策略的系統(tǒng) 時(shí)間 序服務(wù)策略 =(了+ )+ +o5 2a + (s )+ O06a2 (1

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

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

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

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

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

10、duling ofVehicleslMChengdu：Chengdu Science and Technology University Press，1994 (in Chinese) 3李 軍，郭耀煌物流配送車輛優(yōu)化調(diào)度理論與方法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謝秉磊，郭耀煌，郭 強(qiáng)動(dòng)態(tài)車輛路徑問題：現(xiàn)狀與展望J系統(tǒng)工程理論方法應(yīng)用，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期 郭耀煌等：動(dòng)態(tài)車輛路徑問題排隊(duì)模型分析 13宋衛(wèi)斌，蘇 秦虛擬顧客服務(wù)系統(tǒng)排隊(duì)模型J管理科學(xué)學(xué)報(bào)，2001，4(3)：5257 Song Wei_bm，Su QinQueueing model of service for invented customer systemJJournal of Management Sciences