2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽

1、2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設(shè)置

2、報名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?西南交通大學(xué) 參賽隊員 (打印并簽名) ：1. 張書瑞 2. 裴星星 3. 黃如君 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 徐躍良 日期： 2007 年 09 月 24 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2007高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：乘公交 看奧運摘要為建立公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)，從實際情況出發(fā)考慮，本文建立了

3、滿足查詢者的各種不同需求的線路選擇模型與算法。并給出一些結(jié)果。問題一為僅考慮公汽線路的情況下給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。本文從費用、時間及換乘次數(shù)出發(fā)，先單獨再綜合的對三個因素進(jìn)行了詳細(xì)討論。在建模中我們將費用和時間視為有向圖邊的鄰接矩陣權(quán)，使原題巧妙的轉(zhuǎn)化為了圖論的最短路問題，建立了一個線性規(guī)劃模型，采用Dijkstra算法對模型進(jìn)行求解。對于多目標(biāo)，我們采用將目標(biāo)轉(zhuǎn)化為約束條件和將目標(biāo)無量綱化后進(jìn)行線性加權(quán)相結(jié)合的辦法進(jìn)行計算，得出最優(yōu)線路，如S3359S1828的線路有：1、S3395（L324）S1746（L027）S1784（L167）S1828（時間73

4、，費用3，換乘2）；2、S3359（L436）S1784（L167）S1828（時間101，費用3，換乘1）；3、S3359（L015）S1327（L296）S992（L475）S1671（L041）S1828（時間72，費用4，換乘3）。并對最優(yōu)線路給出了詳細(xì)的評價。問題二，同時考慮地鐵和公汽的線路選擇問題，我們從時間和費用兩方面進(jìn)行討論。建模中，我們保留第一問的建模思想，同時考慮了地鐵的情況，建立了01規(guī)劃模型。對此模型，我們采用Floyd最短路徑算法和Dijkstra算法再結(jié)合仿真算法用C語言編程求解。并得到最優(yōu)線路，如S3359S1828的線路：S3359-L015（上行）-S1327

5、-L296（環(huán)行）-S0992-L475（上行）-S1828，時間：72分鐘，費用:元。問題三，在知道所有站點之間的步行時間的情況下的公交線路選擇問題，我們從費用最少、總時間最少和步行時間最少進(jìn)行討論。在建模中，我們巧妙的把步行看作一種特殊的不花費用的交通方式，并結(jié)合圖論知識建立了3個目標(biāo)的多目標(biāo)0-1規(guī)劃模型。最后，我們還給出了求解此模型的思想和算法。在問題一中，構(gòu)造了有向賦權(quán)圖，巧妙地將原問題轉(zhuǎn)化為圖論的最短路問題是本文的亮點。在問題三中，將步行看作一種特殊的不花費用的交通方式，大大減輕了我們建模難度。另外，本文還采用了多個圖論算法，簡化了模型求解難度。最后，我們還對本文提出了推廣和改進(jìn)的

6、方案。關(guān)鍵詞：0-1規(guī)劃 Dijkstra算法 Floyd算法 仿真算法 多目標(biāo)規(guī)劃 有向賦權(quán)圖一、問題提出 我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：

7、1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。二、模型假設(shè)1、假設(shè)題目所提供參數(shù)均真實可信。2、忽略堵車等其他意外情況對題目計算的影響。3、假設(shè)公汽和地鐵容量、數(shù)量足

8、夠，即忽略由于滿載造成乘客不得上車的影響。4、不計乘客上、下車時間及公交啟動、加速、滑行制動時間（因為題中給的是平均時間）。5、假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘(無需支付地鐵費）。三、符號說明與概念引入1、概念引入（1）直達(dá)若能直接坐一趟車到達(dá)點則稱直達(dá)，否則不直達(dá)（注：此處與直達(dá)不相同）。（2）站點編號為了方便論文的敘述，我們對公汽站點和地鐵站點進(jìn)行重新編號。S0001-站點1S0002-站點2S3957-站點3957D1-站點3958D2-站點3959D39-站點3996（3）線路編號為了方便論文的敘述和計算的方便，我們對公汽線路和地鐵線路進(jìn)行重新編號。L001-線

9、路1L002 上行-線路2L002 下行-線路3L520 上行-線路928L520 下行-線路929T1-線路930T2-線路9312、符號說明-表示是否通過站點直達(dá)站點線路（01變量）-表示從站點直達(dá)站點的費用（若不能直達(dá)，則記無窮大）-表示從站點直達(dá)站點的時間（若不能直達(dá)，則記無窮大）-表示從站點直達(dá)站點所選乘的線路（若不能直達(dá)，則記為0）-表示起始站-表示終到站四、問題分析4.1問題背景的理解題目要求給出任意兩公汽站點之間的最佳線路，最佳線路是一個模糊概念，在此我們根據(jù)乘客的實際情況出發(fā)，對乘坐時間、費用和換乘次數(shù)進(jìn)行討論。顯然，由于不同乘客的要求不同，不可能直接找到一條令所有人都滿意的

10、線路，對此我們根據(jù)不同乘客的需求，求出不同的參考乘車線路。我們的目標(biāo)就是根據(jù)題目所給統(tǒng)計資料，把乘車線路問題抽象成一個明確完整的數(shù)學(xué)模型，并求解，根據(jù)我們的解，為不同需求的乘客提供乘車線路，以使乘客乘車?yán)孀畲蠡?.2問題一的分析問題一要求僅考慮公汽線路，給出任意兩公汽站點之間的線路選擇。我們通過對乘客線路選擇心理的調(diào)查討論，發(fā)現(xiàn)影響選擇的因素共有三個：時間、費用和換乘次數(shù)。為了方便我們對三個因素的全面討論，我們首先分別對各個因素建模進(jìn)行細(xì)致的討論，然后再對三個因素建立三目標(biāo)的優(yōu)化模型進(jìn)行討論。在建模過程中，我們以3957個公汽站點為頂點，分別用和為邊到賦權(quán)值，構(gòu)成了3957個頂點的有向賦權(quán)

11、圖，也就將題目轉(zhuǎn)化成了一個圖論問題1。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑。4.3問題二的分析此題加入了對地鐵線路的討論，使的乘坐工具的選擇更加多樣化和更加接近實際。對于此問我們以3996個站點為頂點，分別用和為邊到賦權(quán)值，構(gòu)成了3996個頂點的有向賦權(quán)圖，也就將題目轉(zhuǎn)化成了一個圖論問題。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑。此題相對第一問難點主要在于多了公汽轉(zhuǎn)地鐵、地鐵轉(zhuǎn)公汽和地鐵轉(zhuǎn)地鐵。4.4問題三的分析 對于問題三，引入了步行方式，對于步行的解決我們采用將步行看作一種新的乘坐工具，不過此乘坐工具費用為0。然后我們從費用、總時間和步行時間這三個因素對線路選擇

12、進(jìn)行了詳細(xì)討論。五、模型建立及求解5.1問題一1、模型建立模型1.1（只考慮乘車費用最少的情況）我們在此以3957個公汽站點為頂點，以為邊到的權(quán)，構(gòu)成了3957個頂點的有向賦權(quán)圖。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑（即乘車費用最小的路徑）。顯然，從站點直達(dá)站點可能會有多條線路選擇，但必有一條為費用最少的，記此條線路為，其費用為，時間為；若不能直達(dá)，則記為0，和為無窮大。設(shè)決策變量為，當(dāng)=1，說明邊位于頂點到頂點的路上；否則為0。所以，可以用數(shù)學(xué)表達(dá)式表示出，乘車費用為：由于從費用考慮，即要滿足費用最小，所以目標(biāo)函數(shù)為：Min 又因為要滿足從頂點到達(dá)頂點，所以由圖論一筆畫問題2

13、可知，頂點的出度減去其入度等于1，頂點的出度減去入度等于，其余頂點均滿足入度等于出度。所以，約束條件如下：s.t. 為變量綜上，可以建立模型如下：Min s.t. 為變量模型1.2（只考慮乘車時間最短的情況）同理，我們記站點直達(dá)站點時間最短的那條線路為，其費用為，時間為；若不能直達(dá)，記為0，和為無窮大。我們在此以3957個公汽站點為頂點，以為邊到的權(quán)，構(gòu)成了3957個頂點的有向賦權(quán)圖，我們就是要找到時間最少的乘車線路。設(shè)決策變量為，當(dāng)=1，說明邊位于頂點到頂點的路上；否則為0。所以，可以用數(shù)學(xué)表達(dá)式表示出，乘車時間為：顯然，表示的是總的乘車趟數(shù)，所以換車次數(shù)為換車時間為：，總時間為：由于從乘車

14、時間考慮，即要滿足時間最小，所以目標(biāo)函數(shù)為：Min 又因為要滿足從頂點到達(dá)頂點，所以由圖論一筆畫問題可知，頂點的出度減去其入度等于1，頂點的出度減去入度等于，其余頂點均滿足入度等于出度。所以，約束條件如下：s.t. 為變量綜上，可以建立模型如下：Min s.t. 為變量模型1.3（只考慮換乘次數(shù)優(yōu)先的情況下）設(shè)決策變量為，當(dāng)=1，說明邊位于頂點到頂點的路上；否則為0。容易求得乘車趟數(shù)為：，所以換乘次數(shù)為由目標(biāo)換乘次數(shù)最小，目標(biāo)函數(shù)為：Min 同理可以寫出約束，綜上，建立出模型如下：Min s.t. 為變量模型1.4（同時考慮時間、費用及換乘次數(shù)的影響）我們從費用與時間兩方面考慮，記站點直達(dá)站點

15、的最佳線路為，并記此時的費用為，時間為；若不能直達(dá)，記為0，和為無窮大。我們在此以3957個公汽站點為頂點，以為邊到的權(quán)，構(gòu)成了3957個頂點的有向賦權(quán)圖。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑（即乘車時間最小的路徑）。我們在此以3957個公汽站點為頂點，以為邊到的權(quán)，構(gòu)成了3957個頂點的有向賦權(quán)圖。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑（即乘車費用最小的路徑）。顯然對于以上兩個有向圖，具有相同的頂點，但邊的賦權(quán)不同。數(shù)學(xué)表達(dá)式表示出，換乘次數(shù)為：；總時間為：；乘車費用為：所以，目標(biāo)函數(shù)如下：換乘次數(shù)最少Min 總時間最少Min 總費用最少Min 另一方面，由圖論

16、知識，可以寫出約束條件如下：s.t. 為變量綜上，可以建立出模型如下：Min Min Min s.t. 為變量2、模型求解模型1.1的求解：對于這個單目標(biāo)規(guī)劃，由于數(shù)據(jù)量巨大，現(xiàn)成軟件的常規(guī)辦法不能完成求解。在此，我們采用Dijkstra算法3通過VC編程進(jìn)行求解。算法步驟如下：STEP1： 對于數(shù)據(jù)進(jìn)行簡單的預(yù)處理，將上行和下行的線路當(dāng)作兩種不同的線路看待。這兩條線路有相同的線路名，用a，b，ca，cb分別代表非環(huán)形單一票價，非環(huán)形分段票價，環(huán)形單一票價，環(huán)形分段票價。以方便程序閱讀。STEP2：將數(shù)據(jù)讀入程序中，統(tǒng)計站點的總數(shù)和線路總數(shù)。STEP2: 通過建立鄰接表的方式讀入公汽線路信息數(shù)

17、據(jù)，以站點作為表中的頂點，通過識別汽車所售票價方式等一系列信息，得到每個站點的所有直接可達(dá)站點及其附帶屬性，其中包括從一個站點到其直接可達(dá)站點的時間和費用。如果兩條路線同時經(jīng)過兩個點，保存兩點間費用較短的那條路線。STEP3：將鄰接表轉(zhuǎn)換成以費用作為權(quán)值得鄰接矩陣。并用一個三維字符數(shù)組變量來存儲任意兩點經(jīng)過的路線名稱。利用Dijkstra算法對鄰接矩陣進(jìn)行變換。得到從起點到任意一點的最短路徑值，并在變換的同時保留走過的軌跡。其中Dijkstra算法的具體變換如下： 1、 2、 3、 4、 5、找一點 且對所有 6、7、 說明：算法中指定的節(jié)點為T為通過的節(jié)點集合，初始值為當(dāng)T=V時表示所有節(jié)點

18、已通過，計算結(jié)束。計算從第四行循環(huán)語句開始，在不屬于的節(jié)點中選擇路徑長度最小的一點，將加入T中并根據(jù)修改不屬于T的節(jié)點的路徑長度，如此反復(fù)進(jìn)行直到所有節(jié)點都加入T中為止。上述算法中，一旦7中的then語句被執(zhí)行，的軌跡就變成了的軌跡再加上節(jié)點。模型1.2的求解：對于模型1.2可以利用類似與模型1.1的方法4。STEP1：利用求解模型1.1得到的數(shù)據(jù)，同樣可以建立以時間作為權(quán)重值得鄰接矩陣，如果兩條路線同時經(jīng)過兩個點，保存兩點間時間較短的那條路線。對鄰接矩陣進(jìn)行上述的Dijkstra變換。可以得到從起始點到任何其他點之間的以所花費時間作為權(quán)重的最短路徑。STEP2：統(tǒng)計并輸出經(jīng)過的站點和路線。模

19、型1.3的求解：我們采用逐步搜索算法進(jìn)行求解。STEP1:判斷起點和終點之間是否有直達(dá)的路線，如果有，則停止搜索。否則進(jìn)入就STEP2。STEP2：判斷起點和終點之間是否存在一次換乘的路線。即判斷起點和終點分別所在路線中是否存在一個站點為這兩個點的交點，而且通過這個交點可以由起點到達(dá)終點。如果存在，停止搜索。否則進(jìn)入STEP3。STEP3：判斷起點和終點之間是否存在二次換乘的路線，即判斷是否存在一條線路與一條起點所在線路和一條終點所在線路分別相交，而且通過這兩個交點可以由起點到達(dá)終點。模型1.4的求解：此模型難點主要在于有三個目標(biāo)，分別為：Min Min Min 我們首先，將第一個目標(biāo)做轉(zhuǎn)化，

20、將其轉(zhuǎn)化為約束條件： （最多換乘一次車） （1-1） （最多換乘兩次車） （1-2） （最多換乘三次車） （1-3）以及換乘次數(shù)無限制共四種情況進(jìn)行討論。而對于另外兩個目標(biāo)時間和費用我們先采用極值處理法對其進(jìn)行無量綱化處理，處理公式如下：為模型1.2求解所得時間的最小值。記（分別為起點站和終點站）同理，為模型1.1求解所得費用的最小值。記（分別為起點站和終點站）所以，目標(biāo)函數(shù)變?yōu)椋篗in Min 然后，采用線性加權(quán)的辦法將其轉(zhuǎn)化為單目標(biāo)：Min （其中為權(quán)重系數(shù)，）權(quán)重根據(jù)乘客的個人喜好來確定，其中我們采用了多組權(quán)重系數(shù)進(jìn)行比較，并篩選和對比得到比較理想的結(jié)果。轉(zhuǎn)化為單目標(biāo)后計算步驟如下：ST

21、EP1：利用求解模型1.1得到的數(shù)據(jù)，同樣可以建立以時間和費用的線性加權(quán)值作為權(quán)重值的鄰接矩陣，如果兩條路線同時經(jīng)過兩個點，保存兩點間時間較短的那條路線。對鄰接矩陣進(jìn)行上述的DIJ變換。可以得到從起始點到任何其他點之間的以所花費時間作為權(quán)重的最短路徑。STEP2：統(tǒng)計并輸出經(jīng)過的站點和路線。通過VC編程（程序見附錄1-1），采取前述算法，對以上4個模型進(jìn)行計算，我們得到問題一的結(jié)果如下：（1）S3359S1828線路：S3395S1746S1784S1828 L324 L027 L167費用3元，時間73分鐘，共21個站點，換乘2次此線路時間最短，適合趕時間人群選擇。線路：S3359S1784

22、S1828 L436 L167費用3元，時間101分鐘，共32個站點，換乘1次此路線費用和換乘時間最少，但乘坐時間較長。線路：S3359S772S96S1828 L469 L204 L167費用3元，時間145分鐘，共45個站點，換乘2次此路線費用最少，換乘次數(shù)也較少，但乘坐時間較長，適合不趕時間的乘客選用，即可便宜簡單的到達(dá)目的地，又可在長時的乘坐過程，達(dá)到乘公交參觀北京的目的。線路：S3359S1327S992S1671S1828 L015 L296 L475 L041費用4元，時間72分鐘，共19個站點，換乘3次。此線路時間最短，但費用和換乘次數(shù)較大。綜上，S3359S1828的最短時間

23、為72分鐘，最小費用為3元，最小換乘次數(shù)為1次。其中最短時間為線路；最小費用為線路；最小換乘次數(shù)為線路。（2）S1557S0481線路：S1557S1919S902S481 L084 L417 L254費用3元，時間115分鐘，共35個站點，換乘2次此線路費用最少，換乘次數(shù)較少，但時間過長。線路：S1557S1919S3186S902S481 L084 L189 L091 L254費用4元，時間99分鐘，共28個站點，換乘3次此線路時間最短，但費用和換乘次數(shù)較多，適合急趕時間的人群選用。綜上，S1557S0481的最短時間為99分鐘，最小費用為3元，最小換乘次數(shù)為2次。其中最短時間為線路；最小

24、費用為線路；最小換乘次數(shù)為線路。（3）S0971S0485線路：S971S872S485 L119 L417費用3元，時間149分鐘，共有48個站點，換乘1次此線路費用最少，并且換乘簡單只需1次但時間較長線路：S971S1609S2113S1321S485 L013 L448 L002 L469費用4元，時間105分鐘，共30個站點，換乘3次此路線時間最少，但費用和換乘次數(shù)較大。線路：S971S1609S2654S0485 L119 L140 L469費用3元，時間106分鐘，共32個站點，換乘2次此線相對于上一條路線，費用便宜1元，換乘次數(shù)少1次，時間多1分鐘，為一不錯的適中選擇。綜上，S0

25、971S0485的最短時間為105分鐘，最小費用為3元，最小換乘次數(shù)為1次。其中最短時間為線路；最小費用為線路；最小換乘次數(shù)為線路。（4）S0008S0073線路：S8S291S73 L159 L058費用2元，時間83分鐘，共26個站點，換乘1次此路線時間較大，費用最少，換乘次數(shù)也少。線路：S8S3766S2184S73 L198 L296 L345費用3元，時間67分鐘，共19個站點，換乘2次此線路時間最少，但費用與換乘次數(shù)大于上面一條。綜上，S0008S0073的最短時間為67分鐘，最小費用為2元，最小換乘次數(shù)為1次。其中最短時間為線路；最小費用為線路；最小換乘次數(shù)為線路。（5）S014

26、8S0485線路：S148S036S3332S485 L308 L156 L417費用3元，時間106分鐘，共32個站點，換乘2次此路線費用和換乘次數(shù)最少，但時間較長。線路：S148S3604S2361S2210S485 L308 L081 L156 L417費用4元，時間102分鐘，共29個站點，換乘3次此線路時間最少，但換乘次數(shù)較大。線路：S148S36S2480S485 L308 L157 L417費用3元，時間109分鐘，共33個站點，換乘2次此路線費用最少，換乘最少，但時間較長。綜上，S0148S0485的最短時間為102分鐘，最小費用為3元，最小換乘次數(shù)為2次。其中最短時間為線路；

27、最小費用為線路；最小換乘次數(shù)為線路。（6）S0087S3676線路：S87S3496S3676 L454 L209費用2元，時間65分鐘，共20個站點，換乘1次此線路費用、時間均最少線路：S87S1893S3676 L454 L209費用2元，時間71分鐘，共22個站點，換乘1次此路線費用最少，時間相對上一條較長。線路：S87S630S427S3676 L027 L381 L097費用3元，時間49分鐘，共13個站點，換乘2次此路線時間最短，費用和換乘次數(shù)較大綜上，S0087S3676的最短時間為49分鐘，最小費用為2元，最小換乘次數(shù)為1次。其中最短時間為線路；最小費用為線路；最小換乘次數(shù)為線

28、路。5.2問題二1、模型建立我們從費用與時間兩方面考慮，記站點直達(dá)站點的最佳線路為，并記此時的費用為（注：由公汽站點到地鐵站點和地鐵站點到公汽站點的費用為0；地鐵站點直達(dá)地鐵站點費用為3），時間為；若不能直達(dá)（注：此處地鐵直達(dá)包括地鐵線路之間的換乘），記為0，和為無窮大。設(shè)決策變量為，當(dāng)=1，說明邊位于頂點到頂點的路上；否則為0。我們在此以3996個站點為頂點，以為邊到的權(quán)，構(gòu)成了3996個頂點的有向賦權(quán)圖，我們就是要找到時間最短的乘車線路。我們在此以3996個站點為頂點，以為邊到的權(quán)，構(gòu)成了3996個頂點的有向賦權(quán)圖。我們要找到最佳乘車線路，即是找到頂點到頂點的最短路徑（即乘車費用最小的路徑

29、）。顯然對于以上兩個有向圖，具有相同的頂點，但邊的賦權(quán)不同。所以，可用數(shù)學(xué)表達(dá)式表示出，總乘車費用為：總時間=乘坐時間+公汽換乘地鐵平均耗時+地鐵換乘公汽平均耗時+地鐵換乘地鐵平均耗時+公汽換乘公汽平均耗時。又因為地鐵換地鐵平均耗時、公汽換乘地鐵平均耗時和地鐵換乘公汽平均耗時已經(jīng)在中記入，所以總時間為：公汽換乘公汽耗時公汽換乘公汽次數(shù)為：，公汽換乘公汽耗時為：，所以，總時間為綜上，目標(biāo)函數(shù)如下：總費用最小Min 總時間最小Min 又因為要滿足從頂點到達(dá)頂點，所以由圖論一筆畫問題可知，頂點的出度減去其入度等于1，頂點的出度減去入度等于，其余頂點均滿足入度等于出度。所以約束條件如下：s.t. 為變

30、量綜上，建立出模型如下：Min Min s.t. 為變量2、模型求解由于在線路中增加了地鐵，從問題一所的結(jié)果可知：乘車費用一般在三元和四元之間，地鐵票價為三元。如果以費用最小為目標(biāo)，必定大多數(shù)人選擇乘車，求解結(jié)果和問題一的結(jié)果沒有太大的差別。為了簡化模型和方便計算，我們直接以花費時間最少為目標(biāo)。通過VC編程進(jìn)行求解。（程序見附錄1-2）我們分坐地鐵和不坐地鐵兩種情況進(jìn)行考慮，其中不坐地鐵所花費的最少時間可以在第一問里面求得。觀眾從這兩種情況中選擇一種時間最省的方案。算法如下：STEP1:讀入地鐵站點和乘車站點之間的相關(guān)數(shù)據(jù)。STEP2:建立一個以地鐵站點數(shù)目為行數(shù)，對角線上元素大小為零的二維方

31、陣。如果兩個地鐵站點直接相連，就賦值為1。否則賦值為無窮大。再通過Floyd最短路徑算法對該方陣進(jìn)行變換，得到兩個站點之間邊的數(shù)目。STEP3:輸入汽車的站點數(shù)據(jù)，以此得到鄰接矩陣，并利用Dijkstra算法求得從起點到其他點的最短路徑，STEP4：從每個地鐵站點附近的乘車站點中選出與起點和終點距離最近的站點。這樣時間可以表示為從起點到達(dá)地鐵前，處在地鐵中，和離開地鐵后到達(dá)終點這幾個過程所花費時間的總和。從多個公車站點中選擇花費時間最小的站點，并保存該路線（路線包括公汽線路和地鐵線路，其中可利用問題一中的程序?qū)ふ覂蓚€站點之間的最短線路）如果求得的時間大于不坐地鐵的時間，則只選擇坐公汽。通過VC

32、編程（程序見附錄1-2），采取前述算法，對以上4個模型進(jìn)行計算，我們得到問題一的結(jié)果如下： (1)S3359S1828 線路：S3359-L015（上行）-S1327-L296（環(huán)行）-S0992-L475（上行）-S1828時間：72分鐘（如果選擇坐地鐵，需要93分鐘）費用:元(2)S1557S0481線路：S1557-L084（下行）-S1919-L189（下行）-S3186-L091（上行）-S0902-L254（上行）-S0481時間：99分鐘費用：4元(3)S0971S0485線路：S0971-L013（上行）-S1609-L448（上行）-S2113-L002（下行）-S2654-

33、L469（上行）-S0485時間：105分鐘費用：4元(4)S0008S0073線路：S0008-L159（下行）-S0630-L231（環(huán)行）-S0483 -L328 (上行) -S0525 -L103(上行) -S0073時間：63分鐘費用：4元(5)S0148S0485線路：S0148-L308 (上行)- S3604 -L081 (下行)-S2361 L156(上行) S2210 L417 (上行) -S0485時間：102分鐘費用：4元(6)S0087S3676線路：S0087-L021（上行）-S0630（D29）-S3676（D36）時間：36分鐘費用：4元5.3問題三將公汽和地

34、鐵稱為交通工具，以區(qū)別于步行。-表示是否通過交通工具站點直達(dá)站點線路（01變量）-表示是否通過步行從站點步行至站點（01變量）-表示通過交通工具從站點直達(dá)站點的費用（若不能直達(dá)，則記無窮大）-表示從站點步行至站點的費用-表示通過交通工具從站點直達(dá)站點的時間（若不能直達(dá)，則記為無窮大）-表示從站點步行至站點的時間模型的建立由問題分析可知，我們從費用、總時間和步行時間進(jìn)行了討論。費用：因為步行費用為0，所以費用只包含交通工具費用：總時間：為了計算方便我們直接將地鐵換乘地鐵時間記入到地鐵行駛時間中，而地鐵轉(zhuǎn)公汽時間記為步行時間總時間=交通工具時間+步行時間+等車時間步行時間=；交通工具時間=；等車時

35、間=綜上，總時間=步行時間所以，綜上目標(biāo)函數(shù)為：Min Min Min 約束及關(guān)系式：同一路線只能在步行與交通工具之間二選一 （=1,2,3996; =1,2,3996）從出發(fā)到達(dá)變量均為01變量，均為01變量綜上，建立模型如下：Min Min Min s.t. （=1,2,3996; =1,2,3996） ，均為01變量模型的求解思路與算法：由上面的模型很容易發(fā)現(xiàn)這是一個多目標(biāo)性形組合優(yōu)化問題。所有變量均為0- 1變量。但由于變量個數(shù)比較多，所以可能導(dǎo)致計算速度比較緩慢。在此，我們給出一種動態(tài)的遺傳多目標(biāo)算法。STEP1：我們分別估計出三個單目標(biāo)的上限， STEP2：用0-1碼為兩個矩陣進(jìn)行

36、編碼。給出一個有N個染色體的初始種群POP（1），t：=1；STEP3: 對種群中的每個染色體計算它的適應(yīng)度函數(shù)適應(yīng)度是三個目標(biāo)的線性加權(quán)函數(shù)。 STEP4：若停止規(guī)則滿足，則算法停止，否則，計算概率 ；并以如上概率從中隨機(jī)選取一些染色體構(gòu)成一個種群 STEP5：通過交配，交配概率為0.8，得到一個N 個染色體的STEP6：以一個較小的概率p，使得一個染色體的一個基因發(fā)生變異，形成一個新的群體；返回STEP2。六、模型的評價與改進(jìn)6.1、模型的評價 （1）在問題一中，我們用費用和時間為邊到賦權(quán)值，構(gòu)成了有向賦權(quán)圖，巧妙地將原問題轉(zhuǎn)化為圖論的最短路問題。 （2）在問題一中，我們先對各個單一目標(biāo)討

37、論，再綜合討論的方式，使我們的討論更加的合理和容易接受。 （3）在模型求解中，我們采用Dijkstra算法，使最短路的求解更加的簡單。 （4）在問題三中，我們將步行看作，一種不付費的交通方式，使我們在建立模型時更加的簡練和思路清晰。6.2、模型的改進(jìn)（1）模型檢驗的補充，我們在求解完后，還可以采用啟發(fā)式搜索算法，對我們的求解結(jié)果進(jìn)行檢驗。（2）我們可以引入乘客線路滿意度概念，我們即是找出乘客滿意度最大的交通線路。七、模型的推廣及應(yīng)用7.1模型的推廣在現(xiàn)實生活中，乘客對于時間和費用及轉(zhuǎn)車次數(shù)并沒有絕對的等級觀念，反而是一般有一個合理區(qū)間可以讓乘客接受。我們通過實際調(diào)查，發(fā)現(xiàn)乘客在時間多于最小時間

38、1.5倍，費用超過最小費用1.5倍，轉(zhuǎn)車次數(shù)超過最少轉(zhuǎn)車次數(shù)1.5倍的情況下會產(chǎn)生不滿情緒，因此，我們可以從另一個方面考慮。只要能夠給出不讓乘客產(chǎn)生不滿情緒的乘車方式即可。另一方面，我們也可以根據(jù)乘客對公交線路的選擇，相應(yīng)的安排合理的城市交通情況，以避免交通擁擠的出現(xiàn)。7.2模型的應(yīng)用模型的實際應(yīng)用必須考慮到其實用性，因此本文模型在應(yīng)用中必須加入路況特征、交通疏導(dǎo)、人流量等實際因素，綜合考慮。八、參考文獻(xiàn)1肖位樞，圖論及其算法，北京：航空工業(yè)出版社，1993年7月2謝金星，薛毅，優(yōu)化建模與LINDO/LINGO軟件，北京：清華大學(xué)出版社，2005年7月3運籌學(xué)教材編寫組，運籌學(xué)，北京：清華大學(xué)

39、出版社，2005年6月4嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)，北京：清華大學(xué)出版社，2003年5月九、附錄程序附錄1-1（問題1）#include stdafx.h#include stdio.h#include stdlib.h#include string.h#include conio.h#define N 3957#define M 929#define INF 3000#define CreateNode(p) p=(NodeTp *)malloc(sizeof(NodeTp);#define DeleteNode(p) free(void *)p);typedef struct nodeint

40、 na; int t; int m; int e; char nu5; struct node *next; NodeTp;NodeTp wN;int tNN,mNN;int fgN100;char vNN5;int main(int argc, char* argv) int i,k,j,r,l=0,h,x1,x2,flag=0,a6,b6,flag1N,r1,r2,r3,min,y1,y2; char qM5,s2000,e2,g2006;NodeTp *p,*y;FILE *fw1,*fw2,*fw3;a0=3358;b0=1827;a1=1556;b1=480;a2=970;b2=48

41、4;a3=7;b3=72;a4=147;b4=484;a5=86;b5=3675;r1=86;r2=3675;for(i=0;iN;i+)for(j=0;jN;j+)tij=INF; mij=INF; if(i=j) tij=mij=0; vij0=s; vij1=s; vij2=s; vij3=s; vij4=0;printf(*); for(i=0;iN;i+) flag1i=0; fgi0=r1; for(j=1;j100;j+) fgij=-1;/對fg初始化 wi.na=i; wi.next=NULL; for(i=0;i100;i+)printf( %d,fgr2i); for(r

42、=0;rM;r+) scanf(%s,ql+); printf(%s,ql-1); scanf(%s,e); scanf(%s,s); j=0; k=0; h=strlen(s); while(jh-4) for(i=0;i5;i+) gki=sj+; gki=0; k+; j+; if(e0=a) for(i=0;ik;i+) for(j=i+1;jna=x2; y-e=1; y-m=1; y-t=3*(j-i); strcpy(y-nu,ql-1); flag=0; while(p-next)if(p-na=y-na)if(p-my-m)p-e=y-e; p-m=y-m; p-na=y-na; strcpy(p-nu,y-nu); p-t=y-t;flag=1; break;p=p-next; if(flag=0) p-next=y; y-next=NULL; / y-pre=&wx1; else if(e0=b) for(i=0;ik;i+) for(j=i+1;jna=x2; y-e=1; /printf(%s,ql-1); strcpy(y-nu,ql-1); /printf(#%s#,y-nu); y-t=3*(j-i); if(j-i)m=1; else if(j-i)m=2; else y-