運(yùn)輸課程設(shè)計(jì)--車輛行駛路線

1、山東交通學(xué)院運(yùn)輸工程課程設(shè)計(jì)運(yùn)輸課程設(shè)計(jì)一車輛行駛路線摘要目前，現(xiàn)代物流產(chǎn)業(yè)已經(jīng)是覆蓋整個(gè)產(chǎn)業(yè)鏈的、全方位的、立體化的服務(wù)供應(yīng)商， 國(guó)家和企業(yè)也越來(lái)越重視物流在國(guó)民經(jīng)濟(jì)中的重要地位?，F(xiàn)代物流被看作是降低資源消 耗、提高人力素質(zhì)之后的“第三利潤(rùn)源”。在物流領(lǐng)域中，車輛行駛路線選擇始終是 一個(gè)重要的組成部分，特別是在最近幾十年中，許多學(xué)者都對(duì)其進(jìn)行了大量的實(shí)驗(yàn)和研 究。本文首先介紹了車輛路徑問(wèn)題的產(chǎn)生背景及定義，然后由此引出并介紹了車輛行駛 路線的類型，以及行駛路線的選擇和優(yōu)化方法，并針對(duì)匯集式行駛路線的啟發(fā)式算法進(jìn) 行了實(shí)例分析。關(guān)鍵詞：車輛行駛路線，優(yōu)化，啟發(fā)式算法目錄1車輛路徑問(wèn)題的產(chǎn)生背景

2、52車輛路徑問(wèn)題的定義53車輛行駛路線的類型53.1往復(fù)式行駛路線53. 2環(huán)形式行駛路線53. 3匯集式行駛路線54車輛行駛路線的選擇和優(yōu)化64.1環(huán)形式行駛路線的選擇64.1.1環(huán)形式行駛路線的優(yōu)選標(biāo)準(zhǔn)64.1.2數(shù)學(xué)模型64.2匯集式行駛路線的啟發(fā)式算法74. 2.1啟發(fā)式算法概述74. 2.2啟發(fā)式算法求解流程74.2.3啟發(fā)式算法實(shí)例分析95結(jié)論及設(shè)計(jì)體會(huì)12參考文獻(xiàn)131車輛路徑問(wèn)丿1. 1車輛路徑問(wèn)題的產(chǎn)生背景美國(guó)物流管理學(xué)會(huì)（Council of Logistics Management, CLM）對(duì)物流所作的定義為： “為符合顧客的需要，對(duì)原料、制造過(guò)程中的存貨與制成品以及相

3、關(guān)信息，從其起運(yùn)點(diǎn) 至最終消費(fèi)點(diǎn)之間，做出的追求效率與成本效果的計(jì)劃、執(zhí)行與控制過(guò)程?！?而有關(guān) 資料顯示，物流配送過(guò)程（包含倉(cāng)儲(chǔ)、分揀、運(yùn)輸?shù)龋┑某杀緲?gòu)成中，運(yùn)輸成本占到52% 之多。因此，如何在滿足客戶適當(dāng)滿意度的前提下，將配送的運(yùn)輸成本合理地降低，成 為一個(gè)緊迫而重要的研究課題，車輛路徑問(wèn)題正是基于這一需求而產(chǎn)生的。仁2車輛路徑問(wèn)題的定義車輛路徑問(wèn)題可以描述為：給定一組有容量限制的車輛的集合、一個(gè)物流中心（或 供貨地）、若干有供貨需求的客戶，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過(guò)所有的客 戶，在滿足一定的約束條件（如需求量、服務(wù)時(shí)間限制、車輛容量限制、行駛里程限制 等）下，達(dá)到一定的目標(biāo)（

4、如路程最短、費(fèi)用極小、時(shí)間盡量少、使用車輛數(shù)盡量少等）。因此研究車輛路徑問(wèn)題，就是要研究如何安排運(yùn)輸車輛的行駛路線，使運(yùn)輸車輛依 照最短的行駛路線或最短的時(shí)間費(fèi)用，依次服務(wù)于每個(gè)客戶后返回起點(diǎn)，總的運(yùn)輸成本 實(shí)現(xiàn)最小。2車輛行駛路線的類型2.1往復(fù)式行駛路線往復(fù)式行駛路線，是指運(yùn)輸過(guò)程中車輛在某一運(yùn)輸路線的兩個(gè)端點(diǎn)之間做多次（包 括一次）往復(fù)行駛的路線類型。它又可以分成三種形式：?jiǎn)纬逃休d往復(fù)式、回程部分有 載往復(fù)式和雙程有載往復(fù)式。2. 2環(huán)形式行駛路線環(huán)形式行駛路線是指車輛在由若干個(gè)裝卸作業(yè)點(diǎn)組成的一條封閉回路上，作連續(xù)單 向運(yùn)行的行駛路線。由于各貨運(yùn)點(diǎn)在運(yùn)輸方向上的相互位置不同，這種形式的

5、路線分為 三種形式，即簡(jiǎn)單環(huán)式、交叉或三角環(huán)式以及復(fù)合環(huán)式。2. 3匯集式行駛路線匯集式行駛路線是指車輛沿著分布于運(yùn)行路線上各裝卸作業(yè)點(diǎn)，依次完成相應(yīng)的裝卸作業(yè)，且每運(yùn)次的貨物裝（卸）量均小于該車額定載質(zhì)量，直到整個(gè)車輛裝滿（或卸 空）后返回出發(fā)點(diǎn)的行駛路線。般情況下，匯集式路線為封閉路線。車輛可能沿著一條 環(huán)形式的路線行駛，也可能在一條直線形路線上往返行駛。匯集式的運(yùn)輸形式一般可分為三種形式：（1）分送式：車輛從起點(diǎn)裝車完成后，沿 著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)依次進(jìn)行卸貨，最終可返回起點(diǎn)；（2）收集式：車輛從起點(diǎn) 空車出發(fā)，沿著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)進(jìn)行裝貨，最終達(dá)到目的地；（3）分送一收 集式

6、：車輛沿著運(yùn)行路線上的各個(gè)貨運(yùn)點(diǎn)分別或者同時(shí)進(jìn)行裝貨以及卸貨。當(dāng)車輛采用匯集式行駛路線完成運(yùn)輸任務(wù)時(shí)，每次周轉(zhuǎn)的貨物周轉(zhuǎn)量的大小與車輛 沿路線上各貨運(yùn)點(diǎn)的繞行次序有關(guān)。若繞行次序不同，即使完成同樣貨運(yùn)任務(wù)其周轉(zhuǎn)量 也不一樣。在這種情況下，按總行程最短組織車輛進(jìn)行運(yùn)輸最為經(jīng)濟(jì)。3車輛行駛路線的選擇和優(yōu)化3.1環(huán)形式行駛路線的選擇3.1.1環(huán)形式行駛路線的優(yōu)選標(biāo)準(zhǔn)選擇環(huán)形式行駛路線的原則是：當(dāng)完成同樣貨運(yùn)任務(wù)時(shí)，里程利用率B最高為最 佳。環(huán)形式行駛路線以運(yùn)次為基本運(yùn)輸過(guò)程進(jìn)行組織，并且在一條環(huán)形路線上包含有多 個(gè)運(yùn)次、多項(xiàng)貨運(yùn)任務(wù)。其中，每個(gè)運(yùn)次的重車路線由貨運(yùn)任務(wù)決定，所以重車方向是 一定的，無(wú)

7、從選擇。那么，只有合理組織該環(huán)形路線各個(gè)運(yùn)次的銜接順序，使總空車行 程最短，才能使里程利用率B最高，才能獲得最經(jīng)濟(jì)的行駛路線。3.1.2數(shù)學(xué)模型假設(shè)m為空車發(fā)點(diǎn)數(shù)（包括卸貨點(diǎn)和車場(chǎng)），n為空車收點(diǎn)數(shù)（包括裝貨點(diǎn)和車場(chǎng)），Q“為由第i點(diǎn)發(fā)往第j點(diǎn)的空車數(shù)，為第j點(diǎn)所需空車數(shù)，Qi為第i點(diǎn)發(fā)出空車數(shù)，S為 第i點(diǎn)到第j點(diǎn)的距離，則其空車行駛路線的選擇問(wèn)題的數(shù)學(xué)模型如下：目標(biāo)函數(shù)是以全部車輛的總空車?yán)锍蘈v最短為求解目標(biāo)，即約束條件(i=l, 2, , m)為°F (j=l, 2,n)山東交通學(xué)院運(yùn)輸工程課程設(shè)計(jì)3.2匯集式行駛路線的啟發(fā)式算法3.2.1啟發(fā)式算法概述匯集式行駛路線的優(yōu)選原

8、則是以每周轉(zhuǎn)的總行程最短為最優(yōu)?？蓪⒋藛?wèn)題歸為運(yùn)籌學(xué)中的貨郎擔(dān)問(wèn)題，應(yīng)用啟發(fā)式算法來(lái)進(jìn)行近似求解，其基本 思路是：當(dāng)貨運(yùn)點(diǎn)多，總運(yùn)量較大、需用運(yùn)輸車輛超過(guò)一輛時(shí)，選擇匯集式行駛路線首 先根據(jù)運(yùn)輸車輛每車次最高裝載量定額，按就近調(diào)車的原則對(duì)貨運(yùn)點(diǎn)進(jìn)行分組；然后按 總行程最短的原則，采用啟發(fā)式算法分別確定每車沿其本組貨運(yùn)點(diǎn)的繞行次序，以選定 單車運(yùn)行路線。3. 2. 2啟發(fā)式算法求解流程首先確定計(jì)算所需數(shù)據(jù)，其中包括:貨運(yùn)點(diǎn)的分布圖或貨運(yùn)點(diǎn)間里程矩陣L,貨運(yùn) 點(diǎn)收(卸)貨量(Q；單車最高裝載量(G。其中，i、j為貨運(yùn)點(diǎn)序號(hào)，q,、a的 計(jì)算單位視貨物情況而定，如可以是噸、件、桶、箱、瓶等。A :確

9、定貨運(yùn)點(diǎn)分組數(shù)d : d= Eq/qH+0.5B :單車貨運(yùn)點(diǎn)分組：其程序?yàn)椋?) 確定單車行駛路線序號(hào)N (N=l, 2，d),即單車貨運(yùn)點(diǎn)分組組別序列，以依 次確定單車行駛路線。2) 選擇第一個(gè)收貨點(diǎn)。以K表示收貨點(diǎn)的序號(hào)，即選擇01的收貨點(diǎn)。首先確定距發(fā)貨點(diǎn)(滬0)最遠(yuǎn)的收貨點(diǎn)(j = r)為第一個(gè)收貨點(diǎn)，即確定maxS及車 輛實(shí)際載質(zhì)量q=Qj ,并將該點(diǎn)記為Nk = Nx,即第N組單車行駛路線上的第一個(gè)收貨點(diǎn)。 此時(shí)第j收貨點(diǎn)已收到所需數(shù)量()的貨物，不再參加后續(xù)單車行駛路線上收貨點(diǎn)的 分組選擇，再令i=j ,繼續(xù)選擇下一個(gè)收貨點(diǎn)。3) 選擇其余收貨點(diǎn)。即按照就近選點(diǎn)的原則，選取距上

10、一個(gè)收貨點(diǎn)(i=j=r)最近 的第j (j Hr)收貨點(diǎn)為第K+1個(gè)收貨點(diǎn)，此時(shí)車輛實(shí)際載質(zhì)量增加至q=q+Qj ;將該 點(diǎn)記為 Nk (k=k+l)o如果qVQB,則表明車輛載質(zhì)量沒(méi)有充分利用，若尚有qHO ,則繼續(xù)選擇本組下 一個(gè)收貨點(diǎn)；如果FOh，表明本組單行駛路線上的全部貨運(yùn)點(diǎn)已選擇完畢，轉(zhuǎn)本程序第(1)步驟，進(jìn)行第N+1組單車貨運(yùn)點(diǎn)的選擇；如果q>OH，表示車輛實(shí)際裝載量已超過(guò) 車輛的每車次的最高裝載定額,不能再負(fù)擔(dān)第K+1個(gè)收貨點(diǎn)的送貨任務(wù)所以本組單車行駛路線的全部收貨點(diǎn)為K個(gè)，并按選點(diǎn)的先后順序初排貨運(yùn)點(diǎn)序列bk,然后轉(zhuǎn)本程序步 驟（1）進(jìn)行下一組貨運(yùn)點(diǎn)的選擇。若全部貨運(yùn)點(diǎn)

11、的6=0,則表明本方案（S）的全部收 貨點(diǎn)選擇完畢，據(jù)此，初排本組貨運(yùn)序列。若還有其它貨運(yùn)點(diǎn)分組方案，則轉(zhuǎn)本程序第 （1）步繼續(xù)選擇下一組別N+1的貨運(yùn)點(diǎn)，直至S=e方案分組完畢，則轉(zhuǎn)下一程序C。C :選擇單車貨運(yùn)點(diǎn)繞行次序。1）列出本組各貨運(yùn)點(diǎn)間里程（LQ統(tǒng)計(jì)表，如表4-1所示。表內(nèi)各點(diǎn)按初排貨運(yùn)點(diǎn) 順序排列，包括收、發(fā)貨點(diǎn)。表4一1NoNxn2N.Nk012mNo00Lo,iLo,2Nx1Li,o0Li,2Lon22Lo0u. N.mkokl02）按M序列，選取前兩個(gè)貨運(yùn)點(diǎn)（假定其序號(hào)分別為a、b）與發(fā)貨點(diǎn)（j=0）組成 初選循環(huán)回路，記為0-a-bT。按M序列,選取前兩個(gè)貨運(yùn)點(diǎn)，組成初選

12、循環(huán)回路。3）按皿序列，依次選取貨運(yùn)點(diǎn)心插入初選循環(huán)回路。其插入原則是：回路中因包 含了貨運(yùn)點(diǎn)X （人）而使行駛路線長(zhǎng)度的增加值（最小為最優(yōu)。即 ih=Li, m+Lm, h*Li, hfi n4）計(jì)算本組貨運(yùn)點(diǎn)繞行里程JiLy.y + i5）依次確定下一組（第N+1組）單車貨運(yùn)點(diǎn)的繞行次序，直到各組貨運(yùn)點(diǎn)繞行次 序全部確定完畢（N=d）。然后求本方案各組繞行里程合計(jì)£=比=36）如果還有其它貨運(yùn)點(diǎn)分組方案（即S>1）,則就要重復(fù)上述各步，選定該方案 單車?yán)@行次序，直到全部方案（S=e）的單車貨運(yùn)點(diǎn)的繞行次序都確定為止。最后，從所有方案中選擇總繞行里程最短（即S : EU =m

13、in ）的方案。323啟發(fā)式算法實(shí)例分析某牛奶廠，擬采用一輛中型載重車（q=10噸）將鮮奶配送給6個(gè)固定的牛奶銷售點(diǎn), 要求采用啟發(fā)式法選擇車輛繞行次序，目標(biāo)是在完成任務(wù)的前提下,繞行的總里程最短。表4-2各點(diǎn)之間的里程表XBoBxB,RB<B,b6Bo0811107912Bi0956108b206469b90476b401210b3011Bs0表4- 3各牛奶銷售點(diǎn)的需求表銷售點(diǎn)Bib2BsB<B,BG需求（噸）435222解：（1）程序A：計(jì)算貨運(yùn)點(diǎn)的分組數(shù)d,即d= Sqj/qH+O. 5 = （4+3+5+2+2+2） /10+0. 5 =2（2）程序B:進(jìn)行單車貨運(yùn)點(diǎn)分組

14、。 確定第一組的第一個(gè)送貨點(diǎn)，即距離B0最遠(yuǎn)的送貨點(diǎn)，根據(jù)各點(diǎn)之間的里程表可以確 定第一個(gè)點(diǎn)是B6,其距離B0為12,并檢査車輛是否已經(jīng)裝滿，此時(shí)車輛裝載的貨物為2 噸，車輛未達(dá)到滿載. 確定第一組的第二個(gè)送貨點(diǎn)，此時(shí)應(yīng)選擇距離B6最近的送貨點(diǎn)，也就是B3,此時(shí)B3 距離B6最近，其最近距離為6,此時(shí)車輛裝載了 2+5=7噸貨物，車輛未達(dá)到滿載，第 一輛車還可以繼續(xù)裝載貨物. 確定第一組的第三個(gè)送貨點(diǎn)，此時(shí)距離第三個(gè)送貨點(diǎn)最近的是B4,最近距離為4,檢 査車輛是否達(dá)到滿載，此時(shí)車輛裝載的貨物為2+5+2=9噸，還差一噸就會(huì)滿載，但是其 他的送貨點(diǎn)所需求的送貨量都超過(guò)了 1噸，所以第一輛車的裝載

15、完成，運(yùn)輸路線也已經(jīng) 確定，接下來(lái)只需要選擇此車的下一次繞行路線就可以了。 重復(fù)第二步的做法，選出此車的下一次運(yùn)輸路線，首先排除已經(jīng)選擇好了的點(diǎn)，選擇 距離B0最遠(yuǎn)的點(diǎn)B2,此時(shí)B2距離B0最遠(yuǎn)，為11,并檢査車輛裝載率，此時(shí)車輛裝載 的貨物為3噸，未達(dá)到滿載，所以這輛車可以繼續(xù)裝載貨物。 選擇第二輛車的第二個(gè)送貨點(diǎn)，距離B2最近的B5,距離為6,檢查車輛裝載率，此時(shí) 車輛裝載的貨物為3+2=5噸，未達(dá)到滿載，可以繼續(xù)裝載貨物。 第二輛車最后一個(gè)送貨點(diǎn)為B1,此是車輛裝載的貨物為3+2+4=9噸，車輛運(yùn)輸安排 完畢。得出貨運(yùn)點(diǎn)分組方案如表4-4表4-4貨運(yùn)點(diǎn)分組方案統(tǒng)計(jì)表方案S組別N初排貨運(yùn)點(diǎn)

16、序列jI16,3,422,5,1(3)程序C：選擇單車貨運(yùn)點(diǎn)繞行次序。組別1：初選循環(huán)回路：0-6-3-0插入貨運(yùn)點(diǎn)4后的循環(huán)回路情況有：0-4-6-3-0 Aih=5;0-6-4-3-0 Aih=8；0-6-3-4-0 込=1； 因?yàn)樾旭偮肪€增加值最小為1,所以應(yīng)選擇循環(huán)回路0-6-3-4-0 此時(shí)單車?yán)@行里程為29.組別2：初選循環(huán)回路：0-2-5-0 插入貨運(yùn)點(diǎn)1后的循環(huán)回路情況有：0-1-2-5-0 Aih=6；0-2-1-5-0 Aih=13；0-2-5-1-0 Aih=9； 因?yàn)樾旭偮肪€增加值最小為6,所以應(yīng)選擇循環(huán)回路0-1-2-5-0 此時(shí)單車?yán)@行里程為32.結(jié)果如表4-5表4

17、一5方案S組別N單車?yán)@行路線單車?yán)@行里程繞行里程合計(jì)I10-6-3-4-0296120-!-2-5-032由于此題只有方案I 一種方案，所以此方案即為本題的最佳單車?yán)@行路線方案，單車?yán)@ 行里程合計(jì)為61。13山東交通學(xué)院運(yùn)輸工程課程設(shè)計(jì)4結(jié)論及設(shè)計(jì)體會(huì)在物流快速發(fā)展的大背景下，正確合理地安排車輛的運(yùn)行線路，實(shí)現(xiàn)合理的線路運(yùn) 輸，可以有效地節(jié)約運(yùn)輸時(shí)間，增加車輛利用率，從而降低運(yùn)輸成本，提高企業(yè)經(jīng)濟(jì)效 益與客戶服務(wù)水平，使企業(yè)達(dá)到科學(xué)化的物流管理，這也是企業(yè)提高自身競(jìng)爭(zhēng)力的有效 途徑之一。通過(guò)此次課程設(shè)計(jì)，我明白了車輛運(yùn)行線路的優(yōu)化對(duì)物流的重要性，不僅知道了 車輛行駛線路的類型，更是學(xué)習(xí)到并掌握了一些運(yùn)行線路的優(yōu)化方法，總之，這次課程 設(shè)計(jì)讓我受益匪淺。山東交通學(xué)院運(yùn)輸工程課程設(shè)計(jì)參考文獻(xiàn)1胡思繼.交通運(yùn)輸學(xué)叩北京：人民交通出版社，2001.2陳京.汽車運(yùn)輸組織管理M.北京：機(jī)械工業(yè)出版社，20043王之泰.現(xiàn)代物流學(xué)M.北京：中國(guó)物資出版社，20014楊兆升.智能運(yùn)輸系統(tǒng)概論囿北京：人民交通出版社，20035孫媛.企業(yè)物流網(wǎng)絡(luò)規(guī)劃研究.同濟(jì)大學(xué)學(xué)位論文，20086李