【正文】 承 諾 書 我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則 . 我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。 我們知道，抄襲別人的成果是違反競賽規(guī)則的 , 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。 我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。 我們參賽選擇的題號是（從 A/B/C/D 中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）： 所屬學校（請?zhí)顚懲暾娜? 黔南民族師范學院 參賽隊員 (打印并簽名 ) ： 1. 曹龍 2. 彭開連 3. 陳勇 指導教師 或 指導教師組負責人 (打印并簽名 )： 薛先貴 日期： 2021年 8 月 15 日 乘公交 ,看奧運 摘要 :本文將公交線路（ 3957 個公 汽 站點 和 520 條公汽線路、 39 個地鐵站點和 2 條地鐵線路、地鐵與公汽間轉(zhuǎn)換關(guān)系）關(guān)系抽象 為有向賦權(quán)圖，并建立時間直達矩陣 、 費用直達矩陣 、 換乘直達線路數(shù)矩陣，利用最短路模型、搜索法及 01 整數(shù)規(guī)劃模型進行解答。對于問題一，在只考慮公汽的情況下，我們用修改 floyd 算法求出最小轉(zhuǎn)乘次數(shù)、最少費用、最少時間，并由搜索法得出最優(yōu)線路；對于問題二，在考慮公汽和地鐵的情況下，同樣，我們也用修改 floyd 算法求出最小轉(zhuǎn)乘次數(shù)、最少費用、最少時間，并由搜索法得出最優(yōu)線路； 對于第三問題，我們則需要考慮步行時間進去，在問題二的基礎(chǔ)上并利用 01整數(shù)規(guī)劃模型進行優(yōu)化組合取得最優(yōu)線路。 關(guān)鍵字 :線路選擇 有向賦權(quán)圖 修改 floyd 算法 搜索法 優(yōu)化模型 一、問題重述 : 奧運會是世界上舉行的一項重大的賽事活動 .第 29 屆奧運會明年8 月將在我國北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。近年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800 條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，我們準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng) ,關(guān)鍵在于線路選擇的模型與算法，應該從實際情況出發(fā)考慮，滿足查 詢者的各種不同需求。 具體問題如下 : 僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下 6 對起始站→終到站之間的最佳路線（要有清晰的評價說明）。 (1)、 S3359→ S1828 (2)、 S1557→ S0481 (3)、 S0971→S0485 (4)、 S0008→ S0073 (5)、 S0148→ S0485 (6)、 S0087→S 3676 同時考慮公汽與地鐵線路，解決以上問題。 假設(shè)又知道所有站點之間 的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學模型。 基本時間參數(shù)設(shè)定 : 相鄰公汽站平均行駛時間 (包括停站時間 ) 相鄰地鐵站平均行駛時間 (包括停站時間 ) 公汽換公汽平均耗時/(步行時間 ) 地鐵換地鐵平均耗時/(步行時間 ) 公汽換地鐵平均耗時/(步行時間 ) 地鐵換公汽平均耗時/(步行時間 ) 時間 (分鐘 ) 3 5/(2) 4/(2) 6/(4) 7/(4) 即 :換乘公汽等待３分鐘，換乘地鐵等待２分鐘 .公汽站 → 地鐵站（通道） → 公汽站 .換乘耗時 11 分鐘：步行 4+4=8 分鐘 , 等車 3 分鐘 . 基本 票價參數(shù)設(shè)定 : 單一計價 分段計價 公汽 1 元 0～ 20 站： 1 元； 21～40 站： 2 元； 40 站以上： 3 元 地鐵 3 元（無論地鐵線路間是否換乘） 公交線路及相關(guān)信息 （見數(shù)據(jù)文件 ） 二、問題分析 : 本論文主要研究公交線路選擇的問題，即要求 : a 如何換車 ... b 車與車之間的關(guān)系 ... c 滿足乘車人關(guān)心的問題： 1）換乘次數(shù)最少； 2）費用最低； 3）時間最短（初始等車時間 2(3)min 也不包括在內(nèi)，最后結(jié)果可公 交 票 價 方 式 加 上。）； ...... 在眾多 的條件中，為了切合人們的實際需要，優(yōu)先考慮是否有直達 ,若無直達公汽 ,則我們主要從最方便、最經(jīng)濟、最快捷等出發(fā)，建立以換乘次數(shù)、費用、時間為最優(yōu)的數(shù)學模型。 三、模型假設(shè) : 所有公交線路的每天的工作始末時間相同 。 公汽、地鐵均到站停車 。 各公交車都運行正常，不會發(fā)生堵車現(xiàn)象 。 環(huán)線可以看作以任意站作為起點站和終點站，并且是雙向的 ,并且經(jīng)過終點后 要重新收費 。 假設(shè)同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵費； 人們對換乘車次數(shù)盡量少的偏好程度總是大于對花費時間 相對短和花費金錢相對少的偏好程度 。 7 初始等車時間 2(或 3)min 也不包括在內(nèi) 。 同一公交線的往返路線視為兩條單行線 。 考慮兩地鐵之間不通過公汽乘換（即只：公汽站 → 地鐵站（通道）→ 公汽站）。 四、模型建立 : 對于公交線路選擇，我們主要考 、 慮乘換次數(shù)、費用、時間各因素最優(yōu)。 在線路選擇問題中，將公交路線關(guān)系抽象成一個有向賦權(quán)圖，當從 i 可直達 j 時（同為公汽或地鐵站點），定義弧 (i,j)；其上的權(quán)為：( 0 )0ij ijijijd i jld? ??? ? ????站 點 往 站 點 無 直 達 車否 則。 ijl 表示由 i 直達 j 付出的代價，可以為時間或費用 (不包括換乘代價；多條線路可達時只保留最小代 價 )； 公交乘換方式：公汽 —— 公汽，公汽 —— 地鐵，地鐵 —— 公汽，地鐵 —— 地鐵，公汽 —— 地鐵 —— 公汽。 A） i 站點是公汽站點， j 站點為地鐵站點： （ 1）若 j 站點對應的所有換乘 (公汽 )站點 k，均不能從 i 直達 (不在 i站點所在公汽線路 L 上 )，則 (0)ijd =∞ 。 （ 2） 若 j 站點對應的換乘（公汽）站點 k, 可從 i 站點直達 k，則費用為 (0)ijd = (0)kjd ； 注：對于時間則需要加上 k 到 j 的步行時間 . (若有多種選擇，取最小成本者即可 ) B） j 站點是公汽站點， i 站點為地鐵站點： （ 1）若從 i 站點對應的任何換乘 (公汽 )站點 k，均不能直達 j 站點，則 (0)ijd =∞ . （ 2）若從 i 站點對應的換乘 (公汽 )站點 k，能直達 j 站點， 則費用為(0)ijd = (0)kjd ； 注：對于時間則需要加上 i 到 k 的步行時間 . 定義： 矩陣算子“⊙”如下：設(shè) D（ k1）、 D 均為 n 階方陣， D(k) = D（ k1）⊙ D (考慮換乘代價 ) ? ?11 ,m in , 1 , 2 , ,k k kij ij ik k j i j k knd d d d ???? ? ? ? 當考慮費用矩陣間的運算時， ,ijk? =0； 當考慮時間矩陣間的運算時， ,ijk? 表示在 k 的換乘時間。 D(k)= D(k1)⊙ D 表示 k 次換乘的最低代價 (費用或時間 )，即通過修改 floyd 算法求解。 δ i,j,k 表示換乘時間 ： i = j 或 k = i， j 時，δ i,j,k = 0 其他情形： 若不可換乘 (當 i ， j 為公汽站點而 k 為地鐵站點，或者 i ， j 為地鐵站點而 k 為公汽站點時 )，則 δ i,j,k = 0 若可換乘，則：,5,4,3,2,i j k????? ????若 公 汽 換 乘 公 汽若 地 鐵 換 乘 地 鐵（ 只 考 慮 換 乘 時 間 ） 若 地 鐵 換 乘 公 汽（ 只 考 慮 換 乘 時 間 ） 若 公 汽 換 乘 地 鐵 問題一模型 ： 因為僅考慮公汽線路，為了能得到兩站點之間的最好選擇線路，將題中所提供的公汽網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖 ,建立直達矩陣 D = )( )0()0( dD ij nxn? 。 當 D 為時間直達矩陣時，按 D(k)= D(k1) ⊙ D 式重復地進行⊙運算得到 ()kD ，當 1kijd? ?? ， kijd?? 時，表示從 i 站點到 j 站點最少換乘 k 次能夠到達，且即 ()kijd 表示換乘 k 次到達所需的最短時間。 當 D 為費用直達矩陣時，按 D(k)= D(k1) ⊙ D 重復地進行⊙運算得到 ()kD ，運算適當次數(shù)后若 D(k)= D(k1)，則表示已得到所有站點間的最小費用， ()kijd 即表示從 i 站點到 j 站點所需的最少費用。 根據(jù)最少乘換次數(shù) 等約束條件 ，再利用圖的鄰接搜索法可得出兩站點之間的選擇線路。 問題二模型 ： 當還需要考慮地鐵時，為了能得到兩站點之間的最好選擇線路，同樣，將題中所提供的公汽（含地鐵轉(zhuǎn) 換的公汽）網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖 ,建立直達矩陣 D = )( )0()0( dD ij nxn? 。 算法設(shè)計基本與模型一相當。 當 D 為時間直達矩陣時，按 D(k)= D(k1) ⊙ D 式重復地進行⊙運算得到 ()kD ，當 1kijd? ?? ， kijd?? 時，表示從 i 站點到 j 站點最少換乘 k 次能夠到達，且即 ()kijd 表示換乘 k 次到達所需的最短時間。 當 D 為費用直達矩陣時，按 D(k)= D(k1) ⊙ D 重復地進行⊙運算得到 ()kD ，運算適當次數(shù)后若 D(k)= D(k1)，則表示已得到所有站點間的最小費用， ()kijd 即表示從 i 站點到 j 站點所需的最少 費用 。 根據(jù)最少乘換次數(shù)等約束條件，再利用圖的鄰接搜索法可得出兩站點之間的選擇線路。 問題三模型： 問題三是在模型二的基礎(chǔ)上添加步行時間進行考慮。 優(yōu)先考慮乘換次數(shù)。對直達時間矩陣 ? ?(0) (0)ij nnDD?? 按 D(k)= D(k1) ⊙ D 式重復地進行⊙運算得到 ()kD ，當 1kijd? ?? ， kijd?? 時，表示從 i站點到 j 站點最少換乘 k 次能夠到達。在運算過程中可記錄下?lián)Q乘站點信息，隨之可得到相關(guān)線路信息。若有若干條最小換乘路線，則比較另外兩個目標選擇最佳線路（即建立 01 整數(shù)規(guī)劃模型）。 設(shè)共有 m 條單行公交線，構(gòu)造一個 m+2 個點構(gòu)成的完全圖。 點： a 為起點（出發(fā)點）， b 為終點（目的地），此外每條公交線也視為一個點。 邊：邊表示兩點之間的步行關(guān)系。 邊權(quán)：步行時間為邊權(quán)。針對不同的邊可分為上車前、下車后和換車時步行時間，構(gòu)成步行時間矩陣 ? ? ( 1) ( 1)ij m msS? ? ?? 。行：依次表示的是 m 條公交線與起點，列：依次表示的是 m 條公交線與終點。 點權(quán)：第個公交線點還有三個信息為點權(quán)。 1）公交線名稱及上行或下行； 2）類型 ,LE T???? 公 汽地 鐵 及票價方式； 3）乘車站數(shù)表矩陣 ? ? ( 1 ) ( 1 ) , 1 , 2 , ,ii cd mmG g i m? ? ??? ，其中 icdg 表示從c 到 d 經(jīng)過 i 號公交線時需要乘車的站數(shù) ,c 到 d 利 用不上 i 時 icdg 取無窮大。這個矩陣的行列表示用 S。 于是原問題轉(zhuǎn)化為在這個圖上求 a 到 b 的最短路。 最短的可以理解為換乘車數(shù)最少、乘車的總站數(shù)最少、總的步行時間最少、總車費最少這樣幾個目標的各種組合方式。 可以用 01 整數(shù)規(guī)劃解決這個問題，方法是分出恰乘一次公交車，恰乘兩次公交車， 恰乘三次公交車 等等情況分別求出下列模型解然后比較得出最優(yōu)解。 優(yōu)化模型： 恰乘一次公交車的模型如下： 變量全部是 01 變量，共有 3*(m)個。 , 1, 2, ,ix i m? 表示選不選擇去第 i 條公交線的路；