【國家級精品課程】中南大學(xué)數(shù)學(xué)建模lingomatlab優(yōu)化建模數(shù)模培訓(xùn)全國賽論文物流車輛調(diào)度問題研究

1、物流車輛調(diào)度問題研究摘要物流車輛優(yōu)化調(diào)度是物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，也是電子商務(wù)活動不可缺少的內(nèi)容。通過對配送車輛進行優(yōu)化調(diào)度，企業(yè)可以降低運輸成本，提高顧客服務(wù)水平和經(jīng)濟效益，從而獲得更多的利潤, 而該類問題的解決在于尋找有效的裝配方案和行車路線。本文以基本車輛路徑問題(vrp)為基礎(chǔ)，通過建立數(shù)學(xué)模型，尋找車輛調(diào)度的最優(yōu)方案，從而為中心倉庫提供明確的車輛調(diào)度方案。在中心倉庫所收到客戶訂單的貨物需求量qi是已知固定不變的情況下，通過對基本車輛路徑問題的分析，分別建立模型和模型，得到在有時間窗問題下，車輛調(diào)度的最優(yōu)方案。模型：帶軟時間窗的車輛路徑優(yōu)化模型帶軟時間窗的車輛路徑問題由于與車輛數(shù)目及

2、時間(裝卸貨時間和每項任務(wù)執(zhí)行時間)有關(guān)，因此我們首先對需要的車輛數(shù)目進行一個估計，并使線路安排具有一定的彈性。然后確定在軟時間窗條件下的時間函數(shù)，同時，在考慮行駛線路的連通性以及一輛車所承擔的任務(wù)量之和不大于車的容量等約束條件的情況下，建立總派送費用最小的車輛路徑優(yōu)化模型。最后提出一種可以求解這一模型且效果較好的粒子群算法(pso)。模型：帶硬時間窗的車輛路徑優(yōu)化模型基于模型的帶軟時間窗的車輛路徑優(yōu)化模型，我們在對模型簡化中將客戶對任務(wù)執(zhí)行時間的要求增加，要求車輛必須在一定的時間范圍內(nèi)到達，不能提前也不能拖后，從而建立了帶硬時間窗的車輛路徑優(yōu)化模型。在假設(shè)車輛數(shù)為3的前提下，利用lingo8

3、.0軟件求解該模型，得到最優(yōu)化路徑的總運行最短距離min z=910，同時求得車輛的路徑分配方案：車1：0-6-4-0；車2：0-3-1-2-0；車3：0-8-5-7-0。模型：帶時間窗的隨機需求的車輛路徑優(yōu)化模型由于帶時間窗的隨機需求vrp問題中，客戶i的貨物需求量qi為隨機參數(shù)，情況更貼近實際但卻使得問題的復(fù)雜程度大大增加，為此我們引入了qi的概率分布函數(shù)，并考慮了客戶需求量小于車輛k剩余運輸能力的可能性以及滿足車輛在時間窗內(nèi)到達第i個客戶的置信水平，從而在基本的車輛路徑問題(vrp)基礎(chǔ)上建立了帶時間窗的隨機需求的車輛路徑優(yōu)化模型。最后，通過分析兩種分車輛路徑問題，即靜態(tài)的車輛路徑問題(

4、svrp)(模型和模型)和動態(tài)的車輛路徑問題(dvrp)(模型)，結(jié)合車輛路徑問題中經(jīng)常遇到的車輛的裝載能力、不同貨品之間的裝載問題以及客戶需求量的隨機性等情況，我們向中心倉庫提出調(diào)整車的容量、縮減或調(diào)整車的數(shù)量、分道規(guī)劃等建議。一、問題重述1.1 基本情況一個中心倉庫，擁有一定數(shù)量容量為q的車輛，負責(zé)對n個客戶進行貨物派送工作，客戶i的貨物需求量為qi，且車輛必須在一定的時間范圍內(nèi)到達，早到達將產(chǎn)生等待損失，遲達將處以一定的懲罰。1.2 問題提出(1)給出使派送費用最小的車輛行駛路徑問題的數(shù)學(xué)模型及其求解算法。(2)有8項貨物運輸任務(wù)(編號為1，2，8)，各項任務(wù)的貨運量 (單位：噸)、裝貨

5、(或卸貨)時間 (單位：小時)以及要求每項任務(wù)開始執(zhí)行的時間范圍由表1(附錄1.1)給出，這些任務(wù)由車場0發(fā)出的容量為8噸的車輛來完成，車場0與各任務(wù)點以及各任務(wù)點間的距離(單位：公里)由表2(附錄1.2)給出。這里假設(shè)車輛的行駛時間與距離成正比，每輛車的平均行駛速度為50公里/小時，問如何安排車輛的行駛路線使總運行距離最短。 (3) 進一步請討論當客戶i的貨物需求量為隨機參數(shù)時的數(shù)學(xué)模型及處理方法。二、問題分析車輛路線問題(vehicle routing problem,簡稱vrp)考慮從一個或多個中心點出發(fā)的車輛將貨物發(fā)送至一系列顧客并最后回到中心點,問題的解決在于尋找有效的行車路線,使總

6、運行費用最省或者總運行距離最短。為此需要對中心點的車輛建立一個合理的最優(yōu)線路分配方案，使中心點以最少的成本獲得最大的經(jīng)濟效益對于帶軟時間窗的vrp問題，可以在適當增加等待成本或接受遲到懲罰的前提下減少總成本，在總收益不變的情況下實現(xiàn)中心倉庫獲利的最大化；硬時間窗vrp問題中，由于只能在給定的時間窗內(nèi)到達客戶處，中心倉庫在派送車輛時必須在滿足客戶時間窗要求的前提下最小化派送總成本；當客戶需求為隨機需求時，車輛在執(zhí)行任務(wù)時根據(jù)自身的剩余運輸能力以及下一客戶的隨機需求以一定的概率決定是不是繼續(xù)服務(wù)下一個客戶，以概率形式最優(yōu)化車輛得總運行路徑。三、模型假設(shè)(1)單物流中心，非滿載，單車型，多目標配送問

7、題；(2)中心倉庫擁有的車輛足夠多；(3)不考慮貨物的品名和包裝，以及配送車輛的類型，貨物可以混裝；(4)裝貨(或卸貨)的較簡單及約束較少；(5)不考慮在貨物運輸和配送過程中，由于交通事故、天氣變化等偶發(fā)因素等可能在造成的車輛旅行時間的變化；(6)每輛車最多被使用一次，每位客戶有且只有一輛車服務(wù)，并且沒有重復(fù)路線。四、符號說明q ：是車輛平均容量大?。籷i : 第i個客戶的貨物需求量；n : 是客戶的數(shù)量；si : 表示客戶i處裝貨(或卸貨)所需時間；tij : 表示從客戶j處到客戶i處所需時間；ai : 每項任務(wù)開始執(zhí)行的時間；bi : 每項任務(wù)結(jié)束的時間；v ：是每輛車的平均行駛速度。以上

8、為符號說明的不完全歸納，其余符號說明見具體模型五、模型的建立與求解車輛路線問題是考慮在車隊為一些有需求的顧客運送貨物時如何安排行駛路線,從而使服務(wù)效率達到最高,在原有車輛路線問題的基礎(chǔ)上,著重考慮車輛路線問題中客戶的隨機性及客戶接受服務(wù)的時間窗約束,建立車輛路徑優(yōu)化模型,并用粒子群算法進行求解, 尋找有效的行車路線,使總運行費用最省及總運行距離最短。下圖為車輛路徑問題的基本示意圖。圖5.1 車輛路徑問題示意圖5.1 帶軟時間窗的車輛路徑優(yōu)化模型由題意可知，該題是在基本車輛路徑(vrp)問題上加了客戶要求訪問的時間窗口的帶時間窗的車輛路徑問題(vehicle routing problem wi

9、th time windows, vrptw )，為此我們建立了帶軟時間窗的車輛路徑模型。為求解這一模型，我們采用粒子群算法(pso , particle swarm optimization)，它是最近出現(xiàn)的一種模擬鳥群飛行的仿生算法,與一般的啟發(fā)式算法相比有著個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點, 在各類多維連續(xù)空間優(yōu)化問題上均取得非常好的效果。本文將將pso 應(yīng)用于車輛路徑問題求解中, 取得了很好的效果。5.1.1 模型的準備(1)車輛數(shù)的確定一般來說，當問題的約束越多，組織線路就越難，一輛車所完成的滿足所有約束的任務(wù)就越少，這時，一輛車實際所能容納的任務(wù)量要小，而所用的車輛數(shù)可能要多。

10、為了安排路線，須預(yù)先對需要的車輛數(shù)進行一個估計。為了使線路安排具有一定的彈性，可按下式確定車輛數(shù): (1)式中， 表示不大于括號內(nèi)數(shù)字的最大整數(shù)；0a6-4-0；表5.2 車二的行駛路線：012345678012345678000100000001000000100000000010000000000000000000000000000000000000000000000000000可知：車二的行駛路徑為：0-3-1-2-0；表5.3車三的行駛路線：0123456780123456780000000010000000000000000000000000000000000000000000100

11、00000000100000000000001000 可知：車三的行駛路徑為：0-8-5-7-0。5.3 帶時間窗的隨機需求vrp優(yōu)化模型在實際問題中，顧客的需求往往是隨機的，即客戶i的貨物需求量 為隨機參數(shù)，因此我們在模型i的基礎(chǔ)上將靜態(tài)的vrp(svrp)模型轉(zhuǎn)化為動態(tài)的vrp(dvrp)模型。5.3.1 模型的準備假設(shè)顧客的需求和車輛到達顧客的時間是隨機的，并且服從的分布為；某一車輛k服務(wù)s(sn)個客戶后，其總運載量為；車輛k的剩余運載能力為；下一客戶需求量小于車輛k剩余運輸能力的可能性為。在客戶的需求為隨機需求時，當車輛k的剩余運輸能力越大，下一個客戶的需求量越小，該車能夠服務(wù)下個客

12、戶的機會就越大，我們希望車輛k服務(wù)下一客戶時，下一個客戶的需求量不超過車輛k剩余運輸能力的可能性滿足置信水平。對于給定的值，在車輛路徑的安排過程中，當p時，該車輛k繼續(xù)完成下個客戶的運輸任務(wù)，若p，則該車返回車場，新派車完成剩余運輸任務(wù)。重復(fù)上述過程，直到客戶排列中所有客戶都安排完畢，這樣可產(chǎn)生一個可行的車輛安排。但在實際的配送過程中，由于需求量的隨機性，當車輛k按計劃的可行路徑達到某個客戶時，可能會由于車輛剩余運輸能力不能滿足該客戶需求而導(dǎo)致任務(wù)失敗，車輛只能返回車場卸貨后空駛至該失敗點繼續(xù)完成剩余運輸任務(wù)，從而產(chǎn)生額外的行駛距離。同時給每個顧客分配一個滿足車輛在時間窗內(nèi)到達的置信水平,于是

13、有下面的約束條件：，5.3.2 模型的建立由模型的準備我們建立帶時間窗的隨機需求vrp數(shù)學(xué)模型，該模型同樣滿足模型中的約束條件。模型iii目標函數(shù) (24)約束條件 (25) (26) (27) (28) (29) (30) (31) 模型中， ：從任務(wù)點i到任務(wù)點j的距離； ：車輛k的額外行駛距離；z：總計劃路徑距離與額外行駛距離之和；式(24)：表示總計劃路徑距離與額外行駛距離之和最小的目標；式(25)：表示車輛k承擔的任務(wù)量之和不大于車輛的容量的概率滿足置信水平；式(26)：表示任務(wù)i只能由一輛車完成；式(27)：表示由車場0發(fā)出m輛車；式(28)：表示保證每個客戶點處有且僅有一輛車訪問

14、一次；式(29)：保證了進入和離開一給定客戶點的車輛數(shù)相同；式(30)：保證車輛行駛線路的連通性，即車輛到達了一個客戶節(jié)點，從該點離開；式(31)：車輛到達客戶的時間在客戶時間窗內(nèi)的概率滿足置信水平。 六、給中心送貨倉庫的建議在模型二中，通過對幾個約束條件分析得到貨運量與車自身容量成為約束中心倉庫最優(yōu)化送貨的重要條件。適當調(diào)整會對中心倉庫得到更優(yōu)化效益。所以，向中心送貨倉庫提出如下建議：(1)對車的載貨性能主要為車的容量進行調(diào)整。因為線路不同，客戶需求量不同，對于不同方向不同客戶量采取不同型號(容量)車運送。對于一方向大量需求和另一方向少量需求采用同種容量車運貨只會造成資源不足或資源浪費。所以

15、，應(yīng)在倉庫多配備不同運貨性能的車以便采取合理的派送分配；(2)縮減或調(diào)整車的數(shù)量。因為對于一些派送方案，最大車輛運送并不能帶來最優(yōu)效益，可以適當縮減主運車數(shù)，調(diào)整備用車輛以備突發(fā)性需求運輸；(3)采取分道規(guī)劃?？梢詫σ酝蛻粜枨筮M行數(shù)據(jù)統(tǒng)計，得到分布函數(shù)，知道不同方向大致需求以便能對將來需求做預(yù)測，對于需求較大需求穩(wěn)定的客戶點進行路徑規(guī)劃，配備專門車輛隨時準備運輸以減少臨時調(diào)度損失；(4)規(guī)范送貨制度。一套完整的制度體系對于人員調(diào)度是十分必要的，人員規(guī)范化必然也能帶來送貨規(guī)范化。七、模型評價 物流車輛調(diào)度過程中，雖然受到很多影響因素的共同影響，但是主要的影響因素為時間、車場、車型、任務(wù)和目標為

16、代表的影響因素對一般物流車輛調(diào)度問題的影響，每一種因素對車輛調(diào)度的影響特點具有自己的特點。就本文所建立的3個模型，模型的帶時間窗的隨機需求vrp模型相對于模型的靜態(tài)的帶軟時間窗的車輛路徑模型，更實際具有實際意義，因為對svrp而言，相關(guān)信息不會發(fā)生變化，但在實際過程中，由于交通流量、天氣變化、交通事故等因素的影響，行駛速度總在不斷變化，從而導(dǎo)致各個路段上的運行時間也發(fā)生相應(yīng)變化。因此在考慮客戶貨物需求量 在服從一定的概率分布后的隨機需求vrp模型具有一定的推廣價值。八、參考文獻：1 劉霞，車輛路徑問題的研究，2 石勇，物流車輛調(diào)度問題研究， 2007.11；3 李寧、鄒彤、孫德寶，帶時間窗車輛

17、路徑問題的粒子群算法，4 吳斌，車輛路徑問題的粒子群算法研究與應(yīng)用，5 徐玖平、胡知能、王委 編著，運籌學(xué)(第二版)，科學(xué)出版社，2004.5；6 盛麗俊，帶有時間窗的車輛路徑問題的優(yōu)化研究， 2003.3；7 高明霞、楊濤、張春民，帶時間窗的隨機需求車輛路線問題的模型研究，8 徐芳，基于隨機需求的道路貨物調(diào)運方法研究， 2008.4；9 曹二保、賴明勇、張漢江，模糊需求車輛路徑問題研究，10 陳寶文、宋申民、陳興林，隨機需求車輛路徑問題及其啟發(fā)式算法, 九、附錄：附錄1.1表1 任務(wù)的特征及其要求任務(wù)12345678(噸)21.54.531.542.53(小時)121322.530.81,4

18、4,61,24,73,5.52,55,81.5,4附錄1.2表2 點對之間的距離 01234567801 23456780406075902001001608040065401005075110100606507510010075757575407501005090901509010010010001007575100200501005010007090751007575907570070100160110759075907001008010075150100751001000附錄1.1 lingo求解程序model: !定義原始級和派生級；sets: points/0,1,2,3,4,5,6

19、,7,8/:f； point_aim/1,2,3,4,5,6,7,8/:timea,timeb,q,s； roads(points,points):dist,x1,time_between； cars/1.3/； reach/1 2 3 4 5 6 6 7 8/:time_reach； road_car(roads,cars):x； task_car(points,cars):y； task_aim(point_aim,cars):y1； endsets!數(shù)據(jù)輸入；data: dist=0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110

20、100 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 80 100 75 150 100 75 100 100 0； m=3； timea=1 4 1 4 3 2 5 1.5； timeb=4 6 2 7 5.5 2.5 8 4； q=2 1.5 4.5 3 1.5 4 2.5 3； s=1 2 1

21、 3 2 2.5 3 0.8； capacity=8； time_between=0 0.8 1.2 1.5 1.8 4 2 3.2 1.6 0.8 0 1.3 0.8 2 1 1.5 2.2 2 1.2 1.3 0 1.5 2 2 1.5 1.5 1.5 1.5 0.8 1.5 0 2 1 1.8 1.8 3 1.8 2 2 2 0 2 1.5 1.5 2 4 1 2 1 2 0 1.4 1.8 1.5 2 1.5 1.5 1.8 1.5 1.4 0 1.4 2 3.2 2.2 1.5 1.8 1.5 1.8 1.4 0 2 1.6 2 1.5 3 2 1.5 2 2 0；enddata!目

22、標函數(shù)；min=sum(roads(i,j): dist(i,j)* sum(cars(k): x(i,j,k)；!定義x為0，1變量；for(road_car:bin(x)；!定義y為0，1變量；for(task_car:bin(y)；for(task_aim:bin(y1)；!約束條件；!約束一：表示k承擔的任務(wù)量之和不大于車的容量；sum(point_aim(i): q(i)*sum(cars(k)|k#eq#1: y1(i,k)=capacity；sum(point_aim(i): q(i)*sum(cars(k)|k#eq#2: y1(i,k)=capacity；sum(point_

23、aim(i): q(i)*sum(cars(k)|k#eq#3: y1(i,k)sum(point_aim(i):timea(i)；for(reach(j):time_reach(j)sum(point_aim(j):timeb(j)；end附錄1.2 lingo求解結(jié)果global optimal solution found at iteration: 21 objective value: 910.0000 variable value reduced cost m 3.000000 0.000000 capacity 8.000000 0.000000 f( 0) 0.000000 0

24、.000000 f( 1) 0.000000 0.000000 f( 2) 0.000000 0.000000 f( 3) 0.000000 0.000000 f( 4) 0.000000 0.000000 f( 5) 0.000000 0.000000 f( 6) 0.000000 0.000000 f( 7) 0.000000 0.000000 f( 8) 0.000000 0.000000 timea( 1) 1.000000 0.000000 timea( 2) 4.000000 0.000000 timea( 3) 1.000000 0.000000 timea( 4) 4.0000

25、00 0.000000 timea( 5) 3.000000 0.000000 timea( 6) 2.000000 0.000000 timea( 7) 5.000000 0.000000 timea( 8) 1.500000 0.000000 timeb( 1) 4.000000 0.000000 timeb( 2) 6.000000 0.000000 timeb( 3) 2.000000 0.000000 timeb( 4) 7.000000 0.000000 timeb( 5) 5.500000 0.000000 timeb( 6) 2.500000 0.000000 timeb( 7

26、) 8.000000 0.000000 timeb( 8) 4.000000 0.000000 q( 1) 2.000000 0.000000 q( 2) 1.500000 0.000000 q( 3) 4.500000 0.000000 q( 4) 3.000000 0.000000 q( 5) 1.500000 0.000000 q( 6) 4.000000 0.000000 q( 7) 2.500000 0.000000 q( 8) 3.000000 0.000000 s( 1) 1.000000 0.000000 s( 2) 2.000000 0.000000 s( 3) 1.000000 0.000000 s( 4) 3.000000 0.000000 s( 5) 2.000000 0.000000 s( 6) 2.500000 0.000000