徐耀群，尹遜芹

(哈爾濱商業(yè)大學(xué)管理學(xué)院，哈爾濱150028)

車輛路徑問(wèn)題(Vehicle Routing Problem，VRP)最早是由Danting和Ramser[1]于1959年首次提出，自此以后一直是物流領(lǐng)域的核心和熱點(diǎn)問(wèn)題，吸引了眾多學(xué)者和業(yè)者的研究和關(guān)注.現(xiàn)代物流市場(chǎng)的激烈競(jìng)爭(zhēng)和顧客的個(gè)性化需求不斷提高，使得現(xiàn)代物流配送配送運(yùn)作更加復(fù)雜，要求物流配送系統(tǒng)更加靈活、高效地針對(duì)變化的環(huán)境調(diào)整作業(yè)計(jì)劃，計(jì)算機(jī)及通訊技術(shù)的迅速發(fā)展，使得交通狀況及運(yùn)輸工具的實(shí)時(shí)信息更易獲取，為解決物流配送面對(duì)的新問(wèn)題提供了基礎(chǔ).動(dòng)態(tài)VRP正是在這樣的背景下開(kāi)始受到關(guān)注和研究.Eilon[2]等人首先提出了動(dòng)態(tài)規(guī)劃法，主要針對(duì)固定車輛數(shù)的VRP，采用遞歸方法求解.這種方法通過(guò)引入可行性規(guī)則或松弛過(guò)程減少狀態(tài)的數(shù)量，從而減少問(wèn)題的計(jì)算規(guī)模.Christofields之后提出了狀態(tài)空間松弛，極大地減少了狀態(tài)數(shù)量.這種方法認(rèn)為:轉(zhuǎn)化空間松弛數(shù)易于求解，映射出來(lái)的范圍小，可求得很好的下界.Fisher[3]等人提出了三下標(biāo)車輛流方程，主要是針對(duì)帶有能力約束、時(shí)間約束窗口以及無(wú)停留時(shí)間的VRP問(wèn)題.Clark和Wright[4]提出了Clarke－Wright算法，用來(lái)解決車輛數(shù)的不固定問(wèn)題.

目前，國(guó)內(nèi)對(duì)基于實(shí)時(shí)路況的動(dòng)態(tài)隨機(jī)車輛路徑問(wèn)題的研究還不多見(jiàn)，并且大多數(shù)采用預(yù)測(cè)的方法.主要具有以下特點(diǎn):1)大部分研究的問(wèn)題類型是確定性;2)研究手段比較單一;3)該領(lǐng)域的研究群體較小;4)對(duì)該領(lǐng)域的專有名詞沒(méi)有統(tǒng)一規(guī)范的提法[5].本文針對(duì)基于實(shí)時(shí)交通信息的配送路徑問(wèn)題建立數(shù)學(xué)模型，建立實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)模型，在此基礎(chǔ)上提出動(dòng)態(tài)調(diào)度策略.

1 問(wèn)題描述及數(shù)學(xué)模型

基于實(shí)時(shí)路況的車輛配送路徑問(wèn)題描述為:在完成任務(wù)的過(guò)程中，根據(jù)實(shí)時(shí)交通狀況和車輛狀況調(diào)整車輛任務(wù)安排，制定新的行車路徑.1)一個(gè)中心倉(cāng)庫(kù)，擁有容量為q的車輛R輛，負(fù)責(zé)對(duì)N個(gè)客戶進(jìn)行貨物配送工作;2)R輛車輛在初始時(shí)刻?？吭趥}(cāng)庫(kù)中心，并在調(diào)度周期結(jié)束前返回;3)客戶i的需求確定為gi(i=1，2，…N)，且gi＜q，1個(gè)客戶只能由1輛車來(lái)服務(wù)，需求有時(shí)間窗要求，只允許等待，不允許延遲;4)1個(gè)調(diào)度周期由若干離散的區(qū)間，各個(gè)時(shí)間區(qū)間內(nèi)部的車輛行駛速度是一定的;5)求滿足需求的路程最短行駛路徑，并使用盡量少的車輛，從而使費(fèi)用最低.

設(shè)倉(cāng)庫(kù)中心的編號(hào)為0，客戶的編號(hào)為1，2，…N，定義變量為:

建立數(shù)學(xué)模型如下:

在上述模型中，α、β為配送路徑優(yōu)化調(diào)度周期的開(kāi)始、結(jié)束的時(shí)刻，gi為客戶i的需求量cx為車輛的啟動(dòng)單位費(fèi)用，Cr為車輛r行駛單位費(fèi)用，P為等待單位費(fèi)用，rijr(t)表示車輛r在t時(shí)刻從i出發(fā)開(kāi)往j的到達(dá)時(shí)間.

模型中的(2)代表了目標(biāo)函數(shù)，表示此次配送費(fèi)用達(dá)到最低.其中，式(2)包括配送車輛的啟動(dòng)費(fèi)用、車輛的行駛費(fèi)用及等待費(fèi)用3個(gè)部分，式(3)、(4)表示所有的車輛從倉(cāng)庫(kù)中心出發(fā)，在調(diào)度結(jié)束內(nèi)返回倉(cāng)庫(kù)中心;式(5)表示倉(cāng)庫(kù)中心派出去的車輛的數(shù)目不能超過(guò)中心倉(cāng)庫(kù)所擁有的車輛數(shù);式(6)定義了車輛容量約束;式(8)表示所有車輛必須在調(diào)度周期內(nèi)返回倉(cāng)庫(kù)中心[6].

為了滿足客戶對(duì)準(zhǔn)時(shí)化的要求，從而引入了配送不準(zhǔn)時(shí)程度這個(gè)概念，用來(lái)處理時(shí)間窗的約束條件.配送不準(zhǔn)時(shí)程度U是指車輛到達(dá)客戶的時(shí)間早于或晚于時(shí)間窗邊界的值與時(shí)間窗跨度的比，根據(jù)這個(gè)定義可以發(fā)現(xiàn)，若配送時(shí)間剛好在時(shí)間窗的要求之內(nèi)，則其配送的不準(zhǔn)時(shí)程度0，配送不準(zhǔn)時(shí)程度U的數(shù)學(xué)表達(dá)式為:

其中:[Ei，Li]為客戶點(diǎn)的配送時(shí)間窗要求(τ)為在τ時(shí)刻出發(fā)，車輛在弧(vi，vj)上的行程時(shí)間;為客戶服務(wù)時(shí)間為車輛到達(dá)配送路線上第j個(gè)客戶的時(shí)間.到達(dá)客戶點(diǎn)的時(shí)間等于到達(dá)前一個(gè)客戶點(diǎn)的時(shí)間加上服務(wù)時(shí)間，再加上兩點(diǎn)之間的行程時(shí)間，即，且通過(guò)配送準(zhǔn)時(shí)程度就可以將時(shí)間窗約束轉(zhuǎn)化為客戶配送不準(zhǔn)時(shí)程度最低這樣一個(gè)新的目標(biāo)，其中

通過(guò)引入配送不準(zhǔn)時(shí)程度這一概念，可將原有的單一目標(biāo)路徑規(guī)劃問(wèn)題轉(zhuǎn)化成多目標(biāo)路徑規(guī)劃問(wèn)題，不僅僅考慮到配送成本費(fèi)用最低，還考慮到配送不準(zhǔn)時(shí)程度最低這個(gè)目標(biāo)，并為這兩個(gè)目標(biāo)賦予一定的權(quán)重η1和η2，用來(lái)表示這兩個(gè)目標(biāo)的重要程度.由此得到基于實(shí)時(shí)路況的配送路徑優(yōu)化模型的目標(biāo)函數(shù)可表示為:

約束條件不變?nèi)詾槭?3)、(4)、(5)、(6)、(7).

2 實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)分析

針對(duì)上述模型，提出了進(jìn)行配送的兩個(gè)目標(biāo)，一是成本最低;二是準(zhǔn)時(shí)化.本文使用靜態(tài)的網(wǎng)絡(luò)模型來(lái)處理動(dòng)態(tài)的VRP問(wèn)題，從而更好的滿足上述兩個(gè)配送目標(biāo).下面用有向圖來(lái)表示靜態(tài)網(wǎng)絡(luò)模型，圖中的每一條邊都標(biāo)有固定的權(quán)值，此權(quán)值表示兩個(gè)客戶之間的行駛時(shí)間，此處假設(shè)車輛的行駛速度是一致的，客戶之間的行駛時(shí)間由客戶之間的直接距離確定的.

在實(shí)際的配送路徑優(yōu)化中，兩個(gè)客戶之間的最佳路徑有兩個(gè)方面來(lái)確定，一是客戶之間的物理距離;二是客戶之間的行駛時(shí)間.用最短的時(shí)間，行駛最短的路徑，才能降低配送成本，提高配送的準(zhǔn)時(shí)性.本文設(shè)計(jì)了一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)模型，考慮到兩種情況:①VRP問(wèn)題的實(shí)時(shí)最短路徑;②兩個(gè)客戶之間的實(shí)時(shí)最短路徑[7].

1)VRP問(wèn)題的實(shí)時(shí)最短路徑

假設(shè)有9個(gè)客戶由2輛車服務(wù)、倉(cāng)庫(kù)中心用0來(lái)表示.在時(shí)的最短路徑如圖1所示.

圖1 t=T0時(shí)的最短路徑

車輛1:0→1→2→3→4→0;車輛2:0→5→6→7→8→9→0.在這種情況下，我們可以實(shí)現(xiàn)總路徑的最短行駛路徑，即車輛1和車輛2的總的行駛路徑是最短.

假設(shè)t=Tn時(shí)，車輛1到達(dá)節(jié)點(diǎn)4，車輛2到達(dá)節(jié)點(diǎn)8，這時(shí)，在節(jié)點(diǎn)8和9之間的路徑上出現(xiàn)了較嚴(yán)重的交通事故，如圖2所示.

圖2 t=Tn時(shí)的最短路徑

很明顯，因?yàn)楣?jié)點(diǎn)8和9之間出現(xiàn)交通事故，需要對(duì)初始規(guī)劃的路徑進(jìn)行重新的設(shè)計(jì)規(guī)劃.新設(shè)計(jì)的路徑如圖3所示，這是車輛1和車輛2的起點(diǎn)是重新設(shè)計(jì)規(guī)劃時(shí)車輛所到達(dá)的地點(diǎn)(節(jié)點(diǎn)4和節(jié)點(diǎn)8)，由車輛1來(lái)對(duì)客戶點(diǎn)9服務(wù)，車輛2完成對(duì)客戶點(diǎn)8服務(wù)之后直接返回倉(cāng)庫(kù)中心.

圖3 t=Tn時(shí)的最短路徑

即由圖3可知，車輛1:0→1→2→3→4→9→0;車輛2:0→5→6→7→8→0.這樣可以應(yīng)對(duì)節(jié)點(diǎn)8到節(jié)點(diǎn)9之間出現(xiàn)的特殊狀況，也可以實(shí)現(xiàn)最大限度的最短路徑.

2)兩個(gè)客戶之間的實(shí)時(shí)最短路徑

在圖1、2、3中，節(jié)點(diǎn)3和節(jié)點(diǎn)4是有一條邊相連的，這表示車輛1完成對(duì)客戶3的服務(wù)之后，車輛1的下一個(gè)客戶就是客戶4，但并不表示這兩個(gè)客戶之間只存在一條路徑.實(shí)際上，這兩個(gè)客戶之間一般會(huì)有多條路徑，到底是那條路徑最短，這取決于當(dāng)時(shí)的網(wǎng)絡(luò)狀態(tài)來(lái)決定.在t=T0時(shí)，它們之間的最短路徑可能為:3→10→12→4，而在t=Tn時(shí)，最短路徑有可能變?yōu)?3→15→16→13→4.如圖4、5所示.

針對(duì)模型的目標(biāo)，在進(jìn)行動(dòng)態(tài)路徑規(guī)劃時(shí)首先對(duì)客戶的服務(wù)順序進(jìn)行調(diào)度，然后在對(duì)客戶之間路徑進(jìn)行規(guī)劃，在這個(gè)過(guò)程中，充分考慮到配送的成本費(fèi)用以及行駛時(shí)間.

3 調(diào)度策略

為了更好的解決性VRP問(wèn)題，Clarke·G等人構(gòu)造了節(jié)約算法，他們的基本觀點(diǎn)是:首先建立所有的客戶與配送中心之間的單客戶配送線路，然后按照節(jié)約值最大的原則將兩個(gè)客戶連接起來(lái)形成一條線路，隨之將所有客戶根據(jù)節(jié)約值最大的原則納入線路，直到車輛滿載，形成1條配送路線;根據(jù)上述方法構(gòu)造其他配送線路，直到節(jié)約值大于0的配送線路不再存在為止.本文針對(duì)模型的特點(diǎn)，在考慮到準(zhǔn)時(shí)性原則前提下，在對(duì)客戶進(jìn)行服務(wù)順序的調(diào)度時(shí)，利用帶插入規(guī)則的節(jié)約算法，從而降低配送成本，又能滿足客戶在時(shí)間上的要求[8－9].本文提出了如下調(diào)度策略:

第1步:連接客戶點(diǎn)i和客戶點(diǎn)j，并且計(jì)算連接之后的總的配送費(fèi)用節(jié)約值Mij;

第2步:若配送費(fèi)用節(jié)約值Mij均為0，則調(diào)度策略結(jié)束;否則，找到Mij最大值所對(duì)應(yīng)的客戶點(diǎn)i和客戶點(diǎn)j，并考察這兩個(gè)客戶點(diǎn).

第3步:在考察客戶點(diǎn)i和客戶點(diǎn)j過(guò)程中，如果滿足以下4個(gè)方面，則繼續(xù)第4步;否則，直接轉(zhuǎn)到第7步;

1)客戶點(diǎn)i在該線路的起點(diǎn)，而客戶點(diǎn)j不在該條線路上;

2)客戶點(diǎn)i在該線路的終點(diǎn)，而客戶點(diǎn)j不在該條線路上;

3)客戶點(diǎn)i在一條線路上的起點(diǎn)，而客戶點(diǎn)j在一條線路的終點(diǎn);

4)客戶點(diǎn)i和客戶點(diǎn)j都不在同一條線路上.

第4步:連接客戶點(diǎn)i和客戶點(diǎn)j之后，計(jì)算此線路的總運(yùn)量G，如果G≤q，則繼續(xù)第5步;否則，直接轉(zhuǎn)到第7步.

第6步:計(jì)算連接客戶點(diǎn)i和j客戶點(diǎn)之后所有車輛完成各項(xiàng)任務(wù)的的新時(shí)間.

第7步:將該節(jié)約值Fij賦值為0，轉(zhuǎn)到第2步.

此調(diào)度策略運(yùn)用帶插入的節(jié)約算法來(lái)解決基于實(shí)時(shí)路況的配送路徑問(wèn)題，第3步中1)和2)可以使得沒(méi)有進(jìn)行配送線路的客戶點(diǎn)與已有的配送線路在起點(diǎn)或終點(diǎn)相連，3)可以使2條線路首尾相連，而4)可以使得節(jié)約值最大的2個(gè)沒(méi)有進(jìn)入配送線路的客戶點(diǎn)相連，通過(guò)這四個(gè)方面不僅可以協(xié)調(diào)真實(shí)的協(xié)調(diào)費(fèi)用，而且可以協(xié)調(diào)調(diào)度裕度.第六步保證了配送中心對(duì)客戶服務(wù)時(shí)間不延遲.通過(guò)這種方式，一方面滿足客戶的需求，另一方面降低配送成本.

4 結(jié)語(yǔ)

通過(guò)建立數(shù)學(xué)模型、分析實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)模型，提出了針對(duì)實(shí)時(shí)路況的配送路徑優(yōu)化調(diào)度策略，并采取帶插入規(guī)則的節(jié)約算法進(jìn)一步確保策略的有效性.通過(guò)考慮實(shí)時(shí)動(dòng)態(tài)模型，很好的解決道路交通運(yùn)輸過(guò)程中的交通運(yùn)輸過(guò)程中的交通阻塞問(wèn)題，通過(guò)減少擁塞時(shí)間降低總成本，具有一定的實(shí)際應(yīng)用價(jià)值.

[1]DANTZING G，RAMSER J.The truck dispatchting problem[J].Management Science，1959，10(6):80－91.

[2]EILON S，CHRISTOFIDES N.Distribution management:mathematical modeling and practical analysis[M].London:Griffin，1971.

[3]FISHER M L，JAIKUMAR R.A generalized assignment heuristic for vehicle routing[J].Networks，1981(11):109－124.

[4]CLARKE G，WRIGHT JW.Scheduling of vehicles from a central depot to a number of delivery point[J].Operations Research，1964(12):568－581.

[5]張 濤.王壽光.遺傳算法和3－OPT結(jié)合求解帶能力約束的VRP[J].東北大學(xué)學(xué)報(bào)，1999，20(3):253－256.

[6]徐 杰，江永亨，黃德先.基于實(shí)時(shí)交通信息的車輛路徑問(wèn)題研究[J].計(jì)算機(jī)與應(yīng)用化學(xué)，2009，26(9):1093－1094.

[7]王祥生，馬壽峰.實(shí)時(shí)路況信息下配送路徑的優(yōu)化[J].工業(yè)工程，2008，11(1):115.

[8]錢艷婷，王鵬濤，魏國(guó)利.動(dòng)態(tài)車輛路徑問(wèn)題的算法研究[J].天津理工大學(xué)學(xué)報(bào)，2010，26(6):73.

[9]李 嵐，姜偉強(qiáng).蟻群遺傳算法在物流配送路徑選擇中的應(yīng)用[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2009，25(6):707－710.