運輸課程設(shè)計--車輛行駛路線

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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