超速行車最短路徑模型

1、超速行車最短路徑模型摘要最短路徑問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最為廣泛的問(wèn)題之一，也是在進(jìn)行物流規(guī)劃和設(shè)計(jì)路線是遇到的最常見(jiàn)的問(wèn)題之一。這里是由城趕往城，是求網(wǎng)絡(luò)中兩點(diǎn)間的權(quán)數(shù)最小的問(wèn)題。算法是比較好解決此類問(wèn)題的一種方法。對(duì)于問(wèn)題，求解時(shí)間最短路徑和花費(fèi)最小路徑。首先將點(diǎn)到點(diǎn)關(guān)于時(shí)間的帶權(quán)鄰接矩陣，通過(guò)算法求解出最短路徑和其權(quán)數(shù)和，也就是時(shí)間最優(yōu)路徑、時(shí)間和花費(fèi)。對(duì)于問(wèn)題，結(jié)合題意提出四種預(yù)案，同樣通過(guò)算法求解最優(yōu)路徑和權(quán)數(shù)和。經(jīng)比較方案和方案能夠滿足條件要求，即除在安裝固定雷達(dá)路段限速行駛，方案全程提速， ；方案向右提速，向上提速， 。對(duì)于花費(fèi)較小的方案，可進(jìn)行一定改進(jìn)，即在向上限速提速的某一路段不

2、進(jìn)行提速，可計(jì)算得 花費(fèi)更少。關(guān)鍵詞：最短路徑 權(quán)數(shù) 算法 鄰接矩陣1.問(wèn)題重述A城和B城間的道路如下圖所示，橫向縱向各有10條公路，任意兩個(gè)相鄰的十字路口距離為100公里， A城到B城相距1800公里。任意一段公路都有限速，如圖所示，單位為公里每小時(shí)。標(biāo)注為130的路段是高速路段，每段收費(fèi)3元。費(fèi)用有如下兩類。與花費(fèi)時(shí)間相關(guān)，如住店和飲食，由公式給出。是汽車的油費(fèi)，每百公里油量(升)由公式給出，其中。單位為小時(shí)，的單位為公里每小時(shí)。汽油每升1.3元。圖上紅色的路段放置了一些固定雷達(dá)。另外， 20個(gè)移動(dòng)雷達(dá)等概率地出現(xiàn)在各個(gè)路段。一個(gè)路段可能同時(shí)發(fā)現(xiàn)多個(gè)雷達(dá)，每個(gè)雷達(dá)都監(jiān)控了自身所在的整個(gè)路段

3、。超速，有的可能被雷達(dá)探測(cè)到，會(huì)被罰款100元；超速，有的可能被雷達(dá)探測(cè)到，會(huì)被罰款200元。本文解決的問(wèn)題是：（1）遵守所有的限速規(guī)定，時(shí)間最短的路線和花費(fèi)最少的路線分別是哪一條？（2）是遵守所有限速規(guī)定所花的最少時(shí)間，要在時(shí)間內(nèi)趕往B城，那么包括罰款在內(nèi)最少花費(fèi)多少？路線又是哪一條？2.問(wèn)題分析問(wèn)題1：求時(shí)間最短的路線問(wèn)題，我們知道有向圖可以用來(lái)解決人們提出的從出發(fā)點(diǎn)到目的地的各種問(wèn)題。其中對(duì)應(yīng)著站點(diǎn)，被賦予權(quán)值（兩個(gè)站點(diǎn)之間的里程權(quán)重），表示站點(diǎn)之間賦予權(quán)值的交通聯(lián)系。根據(jù)條件時(shí)間最短可以求出各站點(diǎn)的權(quán)重，然后運(yùn)用matlab中的循環(huán)語(yǔ)句for求出整個(gè)路線圖的權(quán)值矩陣，再用用Floyd算

4、法可以求出任意兩點(diǎn)間的時(shí)間最短路徑，通過(guò)代人、點(diǎn)坐標(biāo)從而求出的時(shí)間最短路徑；（2）求花費(fèi)最少的路線問(wèn)題，首先根據(jù)每百公里花費(fèi)與速度之間的函數(shù)關(guān)系，求出各站點(diǎn)的權(quán)重，再采用（1）中同樣的方法求出其相應(yīng)的權(quán)值矩陣，最后用Floyd算法求出的花費(fèi)最少路徑；問(wèn)題2：由問(wèn)題知遵守限速規(guī)定所花的最少時(shí)間為小時(shí)，在時(shí)間內(nèi)趕到B城。設(shè)為了使所花費(fèi)用盡可能少，在裝有固定雷達(dá)的地段限速行駛，為了使時(shí)間盡可能少，在其余路段都進(jìn)行超速。為此我們假設(shè)種預(yù)案。、其它路段都超速，同樣由算法求解時(shí)間最短路徑和時(shí)間。、其它路段都超速，同樣由算法求解時(shí)間最短路徑和時(shí)間。、其它路段，橫行路段都按超速，豎行路段都按超速，同樣由算法求

5、解時(shí)間最短路徑和時(shí)間。、其它路段，橫行路段都按超速，豎行路段都按超速，同樣由算法求解時(shí)間最短路徑和時(shí)間。發(fā)現(xiàn)種情況下的時(shí)間最短路徑相同，但是只有在、兩種方案所花費(fèi)的最短時(shí)間小于，在此基礎(chǔ)上我們?cè)谕ㄟ^(guò)求其花費(fèi)，得到最優(yōu)模型。3.模型假設(shè)與符號(hào)說(shuō)明3.1模型假設(shè)假設(shè)1：假設(shè)題目中所給的數(shù)據(jù)都是正確的、合理的。假設(shè)2：假設(shè)在每一個(gè)十字路口逗留所花費(fèi)的時(shí)間較短，忽略不計(jì)。假設(shè)3：為了使花費(fèi)時(shí)間最短，假設(shè)在每一段路上都是最高速度行駛的、忽略其他的堵車、超車、讓車等因素。假設(shè)4：假設(shè)在超速10%或50%的情況下行駛是可行的，忽略外界因素的干擾。3.2符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明表示的鄰接矩陣表示權(quán)向量（其中）表示

6、從所花費(fèi)的最短時(shí)間表示從車的行駛速度表示從的最優(yōu)路徑表示從所花費(fèi)的費(fèi)用表示從行駛過(guò)程中全程提速10%的時(shí)間表示從行駛過(guò)程中全程提速50%的時(shí)間全程中向上行駛時(shí)提速，向右行駛時(shí)提速的時(shí)間全程中向上行駛時(shí)提速，向右行駛時(shí)提速的時(shí)間4模型建立根據(jù)題目中的圖中數(shù)據(jù)，運(yùn)用Floyd算法的基本原理和實(shí)現(xiàn)方法，構(gòu)造一個(gè)鄰接矩陣其中表示與間的距離,若與間無(wú)路可通,則為無(wú)窮大。與間的最短距離存在經(jīng)過(guò)與間的和不經(jīng)過(guò)兩種情況,所以可以令,(其中為節(jié)點(diǎn)數(shù))。檢查與的值,在此,與分別為目前所知的到與到的最短距離,因此,就是到經(jīng)過(guò)的最短距離。所以,若有,就表示從出發(fā)經(jīng)再到的距離要比原來(lái)的到距離短,自然把到的重寫(xiě)成。每當(dāng)一

7、個(gè)搜索完,就是目前到的最短距離。重復(fù)這一過(guò)程,最后當(dāng)查完所有時(shí),就為到的最短距離。為了方便計(jì)算,先作出該圖的鄰接矩陣,如下:5模型求解問(wèn)題1：（1）先用附錄1.1.1在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,path,min1,path1=floyd(X,91,10):時(shí)間最短：其路徑為：path1 = 91 92 93 94 84 85 86 76 66 56 46 47 48 49 39 29 19 20 10（2）先用附錄1.1.2在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,

8、path,min1,path1=floyd(X,91,10):花費(fèi)最?。浩渎窂綖椋篜ath1 = 91 81 82 72 62 52 53 54 44 34 35 25 26 16 6 7 8 9 10所以由最短的路徑如圖1所示，圖綠色所標(biāo)注的路線為時(shí)間最短路線，最短時(shí)間為小時(shí)，紫色所標(biāo)注的路線為花費(fèi)最短路線，最小花費(fèi)為元。問(wèn)題2：由問(wèn)題1我們知道，因?yàn)橛屑笔孪朐跁r(shí)間內(nèi)趕往B城,則。假設(shè)1：行駛過(guò)程中全程提速先用附錄2.1在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,path,min1,path1=floyd(X,91,10):花費(fèi)的時(shí)間為

9、：其路徑為：path1 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10 假設(shè)2：行駛過(guò)程中全程提速先用附錄2.2在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,path,min2,path2=floyd(X,91,10):花費(fèi)的時(shí)間為：其路徑為：path2 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10 假設(shè)3：行駛過(guò)程中向右行駛時(shí)提速，向上行駛時(shí)提速先用附錄2.3在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.

10、1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,path,min3,path3=floyd(X,91,10):花費(fèi)的時(shí)間為：其路徑為：path3 = 91 92 82 83 73 63 53 43 44 45 46 47 48 49 39 29 19 20 10假設(shè)4：行駛過(guò)程中向右行駛時(shí)提速，向上行駛時(shí)提速先用附錄2.4在時(shí)間最短條件下求權(quán)值矩陣，再用附錄1.1Floyd算法運(yùn)算出的時(shí)間和時(shí)間最短路徑，通過(guò)調(diào)用語(yǔ)句D,path,min4,path4=floyd(X,91,10):花費(fèi)的時(shí)間為：其路徑為：path4 = 91 92 82 83 73 63 53 43 44 45 4

11、6 47 48 49 39 29 19 20 10我們發(fā)現(xiàn)假設(shè)1、2、3、4所得到的最短路徑是同一條路徑，且如下圖2所示：圖2由，所以成立的假設(shè)只有假設(shè)2和假設(shè)4中所花費(fèi)的最短時(shí)間是符合條件的。再求出兩個(gè)假設(shè)的花費(fèi)：假設(shè)2：行駛過(guò)程中全程提速的最小花費(fèi)：=假設(shè)4：行駛過(guò)程中向上行駛時(shí)提速，向右行駛時(shí)提速假設(shè)5：由于比大，說(shuō)明假設(shè)比假設(shè)更合理，在假設(shè)的基礎(chǔ)上我們可以發(fā)現(xiàn)如果任選向上行駛的限速為的一個(gè)路段不超速行駛，那么其所花費(fèi)的時(shí)間；花費(fèi)的費(fèi)用元?？偨Y(jié)：?jiǎn)栴}2要我們求解的是在時(shí)間內(nèi)花費(fèi)最少的費(fèi)用和路線。由假設(shè)1、2、3、4、5方案求解結(jié)果可以看出假設(shè)5方案既符合條件,同時(shí)花費(fèi)的費(fèi)用為所有假設(shè)方案

12、中的最低，因此假設(shè)5是最合理的，花費(fèi)的費(fèi)用，其路徑如圖2所示。6.模型評(píng)價(jià)、改進(jìn)和推廣6.1模型評(píng)價(jià)優(yōu)點(diǎn)：（1）本模型的結(jié)論和結(jié)果是和實(shí)際較吻合的，說(shuō)明本模型比較合理。（2）利用Floyd算法，大大地減少了計(jì)算量，同時(shí)提高了計(jì)算的準(zhǔn)確性。（3）在求最短路徑問(wèn)題，將問(wèn)題按實(shí)際常理出發(fā)，將一個(gè)有向與無(wú)向結(jié)合的圖，轉(zhuǎn)化為一個(gè)單一的有向圖，使得問(wèn)題變得簡(jiǎn)化易解，該模型有利于解決一些解決常見(jiàn)的最短路問(wèn)題。缺點(diǎn)：由于模型假設(shè)忽略了實(shí)際的一些因素，及模型過(guò)于簡(jiǎn)單化和Floyd算法的欠缺，使結(jié)果存在一定的偶然誤差。6.2模型改進(jìn)可將超車行駛過(guò)程中的超車、堵車和讓車所花費(fèi)的時(shí)間及每個(gè)十字路口花費(fèi)的時(shí)間考慮進(jìn)去，

13、使得模型更符合生活實(shí)際。6.3模型推廣在現(xiàn)實(shí)生活中，我們可以選擇的交通工具多種多樣和交通路線四通八達(dá)，本模型也推廣與解決出行時(shí)的遇到如何選擇最經(jīng)濟(jì)實(shí)惠又方便快捷的路線問(wèn)題。7.參考文獻(xiàn)1 耿素云，屈婉玲，離散數(shù)學(xué)。北京：高等教育出版社，2001.2 耿素云，離散數(shù)學(xué)圖論分冊(cè)。北京：北京大學(xué)出版社，1990.3 數(shù)學(xué)軟件與數(shù)學(xué)實(shí)驗(yàn)（第二版）汪曉銀 周保平 科學(xué)出版社20014 數(shù)學(xué)建模及其基礎(chǔ)知識(shí)詳解 費(fèi)普生 武漢大學(xué)出版社 2006.5 韓中庚 宋明武 邵廣紀(jì)，數(shù)學(xué)建模競(jìng)賽獲獎(jiǎng)?wù)撐木x與點(diǎn)評(píng)，北京：科學(xué)出版社，2007。8.附錄%1、在matlab中建立M-fil

14、e如下：%1.1（1）先建立一個(gè)floyd.M文件function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,end if nargin=3 min1=

15、D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end （2）再建立一個(gè) xout.M的文件%1.1.1、求時(shí)間最短的路線X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=100./90 90 90 90 50 90 90 90 90;90 90 90 90 50

16、 50 110 110 110;90 90 50 50 90 90 110 110 110;50 50 90 90 50 50 50 90 50;90 90 110 110 110 110 110 110 90;90 90 90 90 90 90 90 90 50;50 90 110 110 110 90 90 90 90;50 90 90 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 50;110 130 130 130 130 130 130 130 130;B=100./90 90 110 90 90 90 110 90 90 110; 9

17、0 90 110 50 50 90 90 90 110 90; 50 50 110 50 50 50 50 50 110 50; 90 50 110 90 50 90 50 50 50 50; 90 90 110 90 90 90 90 90 50 50; 50 90 110 90 50 90 90 90 50 130; 50 90 90 90 90 110 90 50 50 130; 50 90 90 90 50 110 90 90 90 130; 90 110 90 90 50 50 50 90 90 130;for a=0:9for b=1:9 X(a*10+b,a*10+b+1)=A(

18、a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=B(b,a+1); endendX%1.1.2、求花費(fèi)最少的路線X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=90 90 90 90 50 90 90 90 90;90 90 90 90 50 50 110 110 110;90 90 50 50 90 90 110 110 110;50 50 90 90 50 50 50 90 50;90 90 110 110 110 110 110 110 90;90 90 90 90 90

19、 90 90 90 50;50 90 110 110 110 90 90 90 90;50 90 90 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 50;110 130 130 130 130 130 130 130 130;B=90 90 110 90 90 90 110 90 90 110; 90 90 110 50 50 90 90 90 110 90; 50 50 110 50 50 50 50 50 110 50; 90 50 110 90 50 90 50 50 50 50; 90 90 110 90 90 90 90 90 50

20、50; 50 90 110 90 50 90 90 90 50 130; 50 90 90 90 90 110 90 50 50 130; 50 90 90 90 50 110 90 90 90 130; 90 110 90 90 50 50 50 90 90 130;c1=500./A+(0.0625*1.3).*A+1.875*1.3;c2=500./B+(0.0625*1.3).*B+1.875*1.3;for a=0:9for b=1:9 X(a*10+b,a*10+b+1)=c1(a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=c2(b,a+1); en

21、dendX問(wèn)題2%2.1、求提速時(shí)間最短的路線的時(shí)間X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA= A=(1000/11)./90 90 90 90 50 90 90 900/11 90;900/11 90 90 90 50 50 110 110 110;90 90 50 50 900/11 90 110 110 110;50 50 90 90 500/11 50 50 90 50;900/11 90 110 110 110 110 110 110 90;90 90 90 900/11 90 90 90

22、90 50;50 90 110 110 110 900/11 90 90 90;50 90 900/11 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/11;110 130 130 1300/11 130 130 130 130 130;B=(1000/11)./900/11 90 110 90 90 900/11 110 90 90 110; 90 90 110 50 50 90 90 90 110 90; 50 50 110 50 50 50 50 50 110 50; 90 50 110 900/11 50 90 50 50 50

23、500/11; 90 900/11 110 90 90 90 90 90 50 50; 50 90 110 90 50 900/11 90 90 50 130; 50 900/15 90 90 90 110 90 500/11 50 1300/11; 50 90 90 90 50 110 90 90 90 130; 90 110 900/11 90 50 50 50 90 90 130;for a=0:9for b=1:9 X(a*10+b,a*10+b+1)=A(a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=B(b,a+1); endendX%2.2、求提速時(shí)

24、間最短的路線的時(shí)間X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=(1000/15)./90 90 90 90 50 90 90 900/15 90;900/15 90 90 90 50 50 110 110 110;90 90 50 50 900/15 90 110 110 110;50 50 90 90 500/15 50 50 90 50;900/15 90 110 110 110 110 110 110 90;90 90 90 900/15 90 90 90 90 50;50 90 110 110

25、110 900/15 90 90 90;50 90 900/15 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/15;110 130 130 1300/15 130 130 130 130 130;B=(1000/15)./900/15 90 110 90 90 900/15 110 90 90 110; 90 90 110 50 50 90 90 90 110 90; 50 50 110 50 50 50 50 50 110 50; 90 50 110 900/15 50 90 50 50 50 500/15; 90 900/15 11

26、0 90 90 90 90 90 50 50; 50 90 110 90 50 900/15 90 90 50 130; 50 900/15 90 90 90 110 90 500/15 50 1300/15; 50 90 90 90 50 110 90 90 90 130; 90 110 900/15 90 50 50 50 90 90 130;for a=0:9for b=1:9 X(a*10+b,a*10+b+1)=A(a+1,b); X(b-1)*10+a+1+10,(b-1)*10+a+1)=B(b,a+1); endendX%2.3、行駛過(guò)程中向上行駛時(shí)提速10%，向右行駛時(shí)提速5

27、0%X=zeros(100);for i=1:100 for j=1:100 if i=j X(i,j)=inf; end endendA=(1000/11)./90 90 90 90 50 90 90 900/11 90;900/11 90 90 90 50 50 110 110 110;90 90 50 50 900/11 90 110 110 110;50 50 90 90 500/11 50 50 90 50;900/11 90 110 110 110 110 110 110 90;90 90 90 900/11 90 90 90 90 50;50 90 110 110 110 900

28、/11 90 90 90;50 90 900/11 90 90 90 50 50 50 ;90 110 110 110 110 90 90 50 500/11;110 130 130 1300/11 130 130 130 130 130;B=(1000/15)./900/15 90 110 90 90 900/15 110 90 90 110; 90 90 110 50 50 90 90 90 110 90; 50 50 110 50 50 50 50 50 110 50; 90 50 110 900/15 50 90 50 50 50 500/15; 90 900/15 110 90 90 90 90 90 50 50; 50 90 110 90 50 900/15 90 90 50 130; 50 900/15 90 90 90 110 90 500/15 50 1300/15; 50 90 90 90 50 110 90 90 90 130; 90 110 900/15 90 50 50 50 90 90 130;for a=0:9for b=1:9 X(a*10+b,a*10+b