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

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

2、52車(chē)輛路徑問(wèn)題的定義53車(chē)輛行駛路線(xiàn)的類(lèi)型53.1往復(fù)式行駛路線(xiàn)53. 2環(huán)形式行駛路線(xiàn)53. 3匯集式行駛路線(xiàn)54車(chē)輛行駛路線(xiàn)的選擇和優(yōu)化64.1環(huán)形式行駛路線(xiàn)的選擇64.1.1環(huán)形式行駛路線(xiàn)的優(yōu)選標(biāo)準(zhǔn)64.1.2數(shù)學(xué)模型64.2匯集式行駛路線(xiàn)的啟發(fā)式算法74. 2.1啟發(fā)式算法概述74. 2.2啟發(fā)式算法求解流程74.2.3啟發(fā)式算法實(shí)例分析95結(jié)論及設(shè)計(jì)體會(huì)12參考文獻(xiàn)131車(chē)輛路徑問(wèn)丿1. 1車(chē)輛路徑問(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% 之多。因此，如何在滿(mǎn)足客戶(hù)適當(dāng)滿(mǎn)意度的前提下，將配送的運(yùn)輸成本合理地降低，成 為一個(gè)緊迫而重要的研究課題，車(chē)輛路徑問(wèn)題正是基于這一需求而產(chǎn)生的。仁2車(chē)輛路徑問(wèn)題的定義車(chē)輛路徑問(wèn)題可以描述為：給定一組有容量限制的車(chē)輛的集合、一個(gè)物流中心（或 供貨地）、若干有供貨需求的客戶(hù)，組織適當(dāng)?shù)男熊?chē)路線(xiàn)，使車(chē)輛有序地通過(guò)所有的客 戶(hù)，在滿(mǎn)足一定的約束條件（如需求量、服務(wù)時(shí)間限制、車(chē)輛容量限制、行駛里程限制 等）下，達(dá)到一定的目標(biāo)（

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

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

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

7、從選擇。那么，只有合理組織該環(huán)形路線(xiàn)各個(gè)運(yùn)次的銜接順序，使總空車(chē)行 程最短，才能使里程利用率B最高，才能獲得最經(jīng)濟(jì)的行駛路線(xiàn)。3.1.2數(shù)學(xué)模型假設(shè)m為空車(chē)發(fā)點(diǎn)數(shù)（包括卸貨點(diǎn)和車(chē)場(chǎng)），n為空車(chē)收點(diǎn)數(shù)（包括裝貨點(diǎn)和車(chē)場(chǎng)），Q“為由第i點(diǎn)發(fā)往第j點(diǎn)的空車(chē)數(shù)，為第j點(diǎn)所需空車(chē)數(shù)，Qi為第i點(diǎn)發(fā)出空車(chē)數(shù)，S為 第i點(diǎn)到第j點(diǎn)的距離，則其空車(chē)行駛路線(xiàn)的選擇問(wèn)題的數(shù)學(xué)模型如下：目標(biāo)函數(shù)是以全部車(chē)輛的總空車(chē)?yán)锍蘈v最短為求解目標(biāo)，即約束條件(i=l, 2, , m)為°F (j=l, 2,n)山東交通學(xué)院運(yùn)輸工程課程設(shè)計(jì)3.2匯集式行駛路線(xiàn)的啟發(fā)式算法3.2.1啟發(fā)式算法概述匯集式行駛路線(xiàn)的優(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)輸車(chē)輛超過(guò)一輛時(shí)，選擇匯集式行駛路線(xiàn)首 先根據(jù)運(yùn)輸車(chē)輛每車(chē)次最高裝載量定額，按就近調(diào)車(chē)的原則對(duì)貨運(yùn)點(diǎn)進(jìn)行分組；然后按 總行程最短的原則，采用啟發(fā)式算法分別確定每車(chē)沿其本組貨運(yùn)點(diǎn)的繞行次序，以選定 單車(chē)運(yùn)行路線(xiàn)。3. 2. 2啟發(fā)式算法求解流程首先確定計(jì)算所需數(shù)據(jù)，其中包括:貨運(yùn)點(diǎn)的分布圖或貨運(yùn)點(diǎn)間里程矩陣L,貨運(yùn) 點(diǎn)收(卸)貨量(Q；單車(chē)最高裝載量(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 :單車(chē)貨運(yùn)點(diǎn)分組：其程序?yàn)椋?) 確定單車(chē)行駛路線(xiàn)序號(hào)N (N=l, 2，d),即單車(chē)貨運(yùn)點(diǎn)分組組別序列，以依 次確定單車(chē)行駛路線(xià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及車(chē) 輛實(shí)際載質(zhì)量q=Qj ,并將該點(diǎn)記為Nk = Nx,即第N組單車(chē)行駛路線(xiàn)上的第一個(gè)收貨點(diǎn)。 此時(shí)第j收貨點(diǎn)已收到所需數(shù)量()的貨物，不再參加后續(xù)單車(chē)行駛路線(xiàn)上收貨點(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í)車(chē)輛實(shí)際載質(zhì)量增加至q=q+Qj ;將該 點(diǎn)記為 Nk (k=k+l)o如果qVQB,則表明車(chē)輛載質(zhì)量沒(méi)有充分利用，若尚有qHO ,則繼續(xù)選擇本組下 一個(gè)收貨點(diǎn)；如果FOh，表明本組單行駛路線(xiàn)上的全部貨運(yùn)點(diǎn)已選擇完畢，轉(zhuǎn)本程序第(1)步驟，進(jìn)行第N+1組單車(chē)貨運(yùn)點(diǎn)的選擇；如果q>OH，表示車(chē)輛實(shí)際裝載量已超過(guò) 車(chē)輛的每車(chē)次的最高裝載定額,不能再負(fù)擔(dān)第K+1個(gè)收貨點(diǎn)的送貨任務(wù)所以本組單車(chē)行駛路線(xiàn)的全部收貨點(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 :選擇單車(chē)貨運(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 （人）而使行駛路線(xiàn)長(zhǎng)度的增加值（最小為最優(yōu)。即 ih=Li, m+Lm, h*Li, hfi n4）計(jì)算本組貨運(yùn)點(diǎn)繞行里程JiLy.y + i5）依次確定下一組（第N+1組）單車(chē)貨運(yùn)點(diǎn)的繞行次序，直到各組貨運(yùn)點(diǎn)繞行次 序全部確定完畢（N=d）。然后求本方案各組繞行里程合計(jì)£=比=36）如果還有其它貨運(yùn)點(diǎn)分組方案（即S>1）,則就要重復(fù)上述各步，選定該方案 單車(chē)?yán)@行次序，直到全部方案（S=e）的單車(chē)貨運(yùn)點(diǎn)的繞行次序都確定為止。最后，從所有方案中選擇總繞行里程最短（即S : EU =m

13、in ）的方案。323啟發(fā)式算法實(shí)例分析某牛奶廠(chǎng)，擬采用一輛中型載重車(chē)（q=10噸）將鮮奶配送給6個(gè)固定的牛奶銷(xiāo)售點(diǎn), 要求采用啟發(fā)式法選擇車(chē)輛繞行次序，目標(biāo)是在完成任務(wù)的前提下,繞行的總里程最短。表4-2各點(diǎn)之間的里程表XBoBxB,RB<B,b6Bo0811107912Bi0956108b206469b90476b401210b3011Bs0表4- 3各牛奶銷(xiāo)售點(diǎn)的需求表銷(xiāo)售點(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)行單車(chē)貨運(yùn)點(diǎn)分組

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

15、完成，運(yùn)輸路線(xiàn)也已經(jīng) 確定，接下來(lái)只需要選擇此車(chē)的下一次繞行路線(xiàn)就可以了。 重復(fù)第二步的做法，選出此車(chē)的下一次運(yùn)輸路線(xiàn)，首先排除已經(jīng)選擇好了的點(diǎn)，選擇 距離B0最遠(yuǎn)的點(diǎn)B2,此時(shí)B2距離B0最遠(yuǎn)，為11,并檢査車(chē)輛裝載率，此時(shí)車(chē)輛裝載 的貨物為3噸，未達(dá)到滿(mǎn)載，所以這輛車(chē)可以繼續(xù)裝載貨物。 選擇第二輛車(chē)的第二個(gè)送貨點(diǎn)，距離B2最近的B5,距離為6,檢查車(chē)輛裝載率，此時(shí) 車(chē)輛裝載的貨物為3+2=5噸，未達(dá)到滿(mǎn)載，可以繼續(xù)裝載貨物。 第二輛車(chē)最后一個(gè)送貨點(diǎn)為B1,此是車(chē)輛裝載的貨物為3+2+4=9噸，車(chē)輛運(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：選擇單車(chē)貨運(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)樾旭偮肪€(xiàn)增加值最小為1,所以應(yīng)選擇循環(huán)回路0-6-3-4-0 此時(shí)單車(chē)?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)樾旭偮肪€(xiàn)增加值最小為6,所以應(yīng)選擇循環(huán)回路0-1-2-5-0 此時(shí)單車(chē)?yán)@行里程為32.結(jié)果如表4-5表4

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