【正文】 1 公交線路轉(zhuǎn)乘 選擇 的優(yōu)化模型 摘 要 本文以?shī)W運(yùn)會(huì)的公交線路換乘為大背景，建立了在公汽線路、地鐵以及步行三種方式中綜合進(jìn)行路線轉(zhuǎn)乘的模型。此問(wèn)題可以歸結(jié)為兩個(gè)站點(diǎn)之間的最短路問(wèn)題，由于直接以站點(diǎn)構(gòu)建最短路問(wèn)題計(jì)算量較大，本文在處理三個(gè)問(wèn)題時(shí)分別提出了相應(yīng)的模型與求解算法，以乘坐時(shí)間最短為標(biāo)準(zhǔn)回答了問(wèn)題一與問(wèn)題二，對(duì)問(wèn)題三提出了最短路模型。 在問(wèn)題一 建模 過(guò)程中， 我們以任意兩條線路是否可以直接換乘為突破口，建立了以每條線路為頂點(diǎn)，兩條線路之間的換乘信息為弧的圖，將問(wèn)題一歸結(jié)為弧長(zhǎng)可變的最短路問(wèn)題，提出了結(jié)合動(dòng)態(tài)規(guī) 劃方法與分枝定界思想的算法。首先將題目所給出的路線與站點(diǎn)信息翻譯為兩條線路是否可以直接相交以及在何處相交的信息矩陣 ；其次以換乘時(shí)間最短或者費(fèi)用最小為決策函數(shù)，建立動(dòng)態(tài)規(guī)劃問(wèn)題；再次設(shè)計(jì)相應(yīng)的算法進(jìn)行求解。通過(guò)求解， 以最短時(shí)間為目標(biāo)， 問(wèn)題一的結(jié)果如下所示（ 以 (1),(2)組為例 ，其它見(jiàn)正文表 1）： 組（ 1）： S3359→S1828 ， 182845829033359 4120225 SSSS LLL ?? ???? ??? ?? ，最短時(shí)間 73分鐘，費(fèi)用 3元； 組（ 2）： S1557→S0481 ， 481318619191557 46018984 SSSS LLL ?? ???? ???? ?? ，最短時(shí)間 106分鐘，費(fèi)用 3元 。 同時(shí) 文章 對(duì)運(yùn)算結(jié)果進(jìn)行了相關(guān)分析。 在問(wèn)題二建模過(guò)程中，沿用問(wèn)題一的求解思想，將新增加的地鐵視為新的線路，將所有線路信息轉(zhuǎn)化為新的轉(zhuǎn)乘矩陣，同時(shí) 按照新的背景得到新的乘車時(shí)間與費(fèi)用計(jì)算方法，同樣以最短時(shí)間為目標(biāo)，相同的算法可以得到問(wèn)題二的結(jié)果（以 (5),(6)組為例，具體見(jiàn)正文表 2） ： 組 （ 5） ： S0148→S0485 ， 48546621021 4 8 70 1 4 8 51124 SSDDSS LTL ?? ???? ????? ?? 最短時(shí)間 分鐘，費(fèi)用 5 元 ； 組（ 6）： S0087→S3676 ， 3 6 7 636270 0 8 7 2 SDDS T ?? ??? ，最短時(shí)間 28分鐘（已經(jīng)加上地鐵站到地面站點(diǎn)的步行時(shí)間，其中地鐵運(yùn)行時(shí)間 20分鐘），費(fèi)用 3元。 在問(wèn)題三建模過(guò)程中，由于增加了步行的信息，問(wèn)題一、二的方法無(wú)法直接使用，文章建立了一個(gè)新的最短路問(wèn)題。以每個(gè)站點(diǎn)為頂點(diǎn)，以兩個(gè)頂點(diǎn)之間的最短路徑（ 最短 達(dá)到時(shí)間或者 最小到達(dá)費(fèi)用 ） 為弧構(gòu)造有向圖，其中最短達(dá)到時(shí)間由問(wèn)題二得到的兩個(gè)站點(diǎn)之間使用公交網(wǎng)絡(luò)的換乘時(shí)間與步行時(shí)間的最小值決定。從而將問(wèn)題三歸結(jié)為一個(gè)有向圖的最短路模型，文章對(duì)此模型給出了算法建議。 最后文章對(duì)所提出的模型進(jìn)行了優(yōu)缺點(diǎn)分析與推廣評(píng)價(jià)。 關(guān)鍵詞： 城市公交線路 、 圖與網(wǎng)絡(luò) 、 最短路 模型、 動(dòng)態(tài)規(guī)劃 2 一、 問(wèn)題重述 ： 近些年來(lái)，城市 公共交通系統(tǒng)有了很大發(fā)展，使得公眾的出行更加通暢、便利。絕大多數(shù)市民出行時(shí)首先會(huì)考慮選擇公交設(shè)施， 同時(shí)也面臨 如何在眾 多條線路 中如何選擇合適線路的 問(wèn)題。針對(duì)市場(chǎng)需求， 要求 開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)，可以滿足查詢者的各種不同需求 ，對(duì)不同的起點(diǎn)和終點(diǎn)給出最佳的公交轉(zhuǎn)乘路線 。 競(jìng)賽要求設(shè)計(jì)線路選擇的模型與算法，解決 以 下三個(gè)問(wèn)題： 僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型與算法，求出以下 6 對(duì)起始站 → 終到站之間的最佳路線（要有清晰的 評(píng)價(jià) 說(shuō)明）。 (1)、 S3359→S1828 (2) 、 S1557→S0481 (3) 、 S0971→S0485 (4)、 S0008→S0073 (5) 、 S0148→S0485 (6) 、 S0087→S3676 同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。 假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型 。 二、 問(wèn)題分析 ： （ 1） 從影響出行選擇的因素看，每個(gè)人主要會(huì)從兩個(gè)標(biāo)準(zhǔn)對(duì)線路進(jìn)行選擇與優(yōu)劣衡量：從起點(diǎn)到終點(diǎn)所需要 的總時(shí)間最短；從起點(diǎn)到終點(diǎn)需要花費(fèi)的費(fèi)用。 （ 2） 從本質(zhì)上 講 ，選擇線路的問(wèn)題可以歸結(jié)為最短路問(wèn)題，但是考慮到轉(zhuǎn)乘 線路需要時(shí)間，并且一條公交線路不能按照站點(diǎn)進(jìn)行拆分，因此以每個(gè)站點(diǎn)構(gòu)造路線圖不利于解決問(wèn)題。注意到從起點(diǎn)站到目標(biāo)站關(guān)鍵是選擇乘坐哪些公交線路，需要在公交線路中如何選擇轉(zhuǎn)乘線路，因此可以以公交線路為頂點(diǎn)，以兩個(gè)站點(diǎn)之間是否可以轉(zhuǎn)乘為弧構(gòu)造圖，而點(diǎn)到點(diǎn)之間最佳路線的選擇可以轉(zhuǎn)化為經(jīng)過(guò)分別兩個(gè)端點(diǎn)的公交線路集合之間的最短路問(wèn)題。 同時(shí)我們需要任意兩個(gè)線路之間是否可以轉(zhuǎn)乘的信息。 （ 3） 在給出的線路信息中，我們發(fā)現(xiàn)主要 有三類線路：下行線路與上行線路不同，下行線路是上行線路的原路返回，環(huán)形線路。為了區(qū)分同一條線路不同的運(yùn)行方向， 我們 人 為地將每一條線路變?yōu)閮蓷l線路，這樣做既可以分清楚所換乘的是那條線路的哪個(gè)方向，同時(shí)也可以將兩條線路換乘點(diǎn)的信息與每個(gè)站點(diǎn)在本條線路上的位置相聯(lián)系，這樣可以用來(lái)判斷乘坐某條線路公交車從某個(gè)站點(diǎn)出發(fā)時(shí)，可以換乘哪些公交線路（換乘站點(diǎn)必須在乘車點(diǎn)沿著公交車運(yùn)行方向的后方）。 （ 4） 在公交線路信息中，與決策目標(biāo)有關(guān)的元素還有每條線路的計(jì)費(fèi)方式 及每 條線路乘坐時(shí)花費(fèi)的時(shí)間。對(duì)于計(jì)費(fèi)方式，我們按照單一票價(jià)與分段計(jì) 價(jià)進(jìn)行識(shí)別，分段計(jì)價(jià)與乘坐的站點(diǎn)數(shù)有關(guān)，這也是我們需要每個(gè)站點(diǎn)在每條線路上具體位置的原因；同樣運(yùn)行時(shí)間也與站點(diǎn)的具體位置有關(guān)。 （ 5） 問(wèn)題一僅對(duì)公共汽車進(jìn)行分析，可以轉(zhuǎn)化為一個(gè)圖論問(wèn)題，使用動(dòng)態(tài)規(guī)劃方法進(jìn)行算法設(shè)計(jì)與計(jì)算。問(wèn)題二增加兩條地鐵信息后，對(duì)問(wèn)題一模型的影響僅在于需要考慮線路數(shù)的增加， 也只需要將地鐵線路與公車線路是否可以換乘的信息表現(xiàn)出即可。問(wèn)題三增加步行信息后，問(wèn)題變得較為復(fù)雜，因?yàn)槲覀儾⒉恢涝谀男┑胤綄?huì)步行，因此我們采用簡(jiǎn)單列舉的方法建立模型。 三、 模型假設(shè) ： 1． 乘客在乘坐公交線路過(guò)程中， 以平均耗時(shí)為實(shí) 際乘車、等車、轉(zhuǎn)乘耗時(shí)； 3 2． 乘客在選擇轉(zhuǎn)乘線路時(shí)，考慮的因素有兩個(gè)：花費(fèi)的時(shí)間最少與費(fèi)用最?。? 3． 在計(jì)算換乘時(shí)間時(shí)，由公交車換公交車、地鐵換地鐵、公交車換地鐵以及地鐵換公交車時(shí)不單獨(dú)計(jì)算步行時(shí)間； 4． 由起點(diǎn)所在站點(diǎn)直接乘坐地鐵及從地鐵直接到終點(diǎn)時(shí)，需單獨(dú)計(jì)算步行時(shí)間。 四、 符號(hào)說(shuō)明及定義 ： ),( jiLS ： 衡量每條線路在每個(gè)站點(diǎn)是否停靠的 0— 1 矩陣； ),( jiLSN ：衡量每條線路 經(jīng)過(guò) 的每個(gè)站點(diǎn)是從起點(diǎn)起 算 的第幾站 的矩陣 ； :),(iLSLi ? ：線路 iL 的?？空军c(diǎn)向量 C ：存儲(chǔ) 每條 線路的收費(fèi)信息； )( iSSB ：停靠 iS 的所有公交線路的集合； )( iLLB ： 線路 iL ?？康乃姓军c(diǎn)； ),( baiCost ：乘坐 iL 從其第 a 站到第 b （ ab? ）站的費(fèi)用 )(),( abTbaiTim bb ?? ：表示從線路 iL 的第 a 站到第 b 站的時(shí)間函數(shù) bbT ：表示相鄰公汽站平均行駛時(shí)間 ，本題為 3 ),( nm SSTime ? ：從站點(diǎn) mS 經(jīng)過(guò) 一系列線路到達(dá) nS 的總時(shí)間 ),( nm SSTCost ? ：從站點(diǎn) mS 經(jīng)過(guò)一系列線路到達(dá) nS 的總費(fèi)用 TR ：所有線路的轉(zhuǎn)乘矩陣 ),( jitr ：公交線路 iL ， jL 兩兩 轉(zhuǎn)乘集合 ； V ：為 所 有站點(diǎn) 集合； E ： 有向圖中表示兩個(gè)站點(diǎn)之間最短距離（最少時(shí)間或者最少費(fèi)用）信息 五、 問(wèn)題一建模與求解 一個(gè)城市所有的公交線路和停車點(diǎn)構(gòu)成了一個(gè)復(fù)雜的網(wǎng)絡(luò)圖 , 這些停車點(diǎn)可以看作該網(wǎng)絡(luò)圖的結(jié)點(diǎn) , 這些結(jié)點(diǎn)由相應(yīng)的公交路線相連 。 結(jié)點(diǎn)之間的邊就是公交路線 。 有的結(jié)點(diǎn)之間有邊相連 (即在某一條公交線上 ) , 有的結(jié)點(diǎn)之間無(wú)邊相連 (即這兩個(gè)結(jié)點(diǎn)不在任何一條公交線上 )。 因此 , 城市的公交路線網(wǎng)絡(luò)圖非常復(fù)雜 , 結(jié)點(diǎn)很多 , 公交線路縱橫交錯(cuò) 。 描述公交線路網(wǎng)絡(luò)的一個(gè)簡(jiǎn)單方法是以每個(gè)站點(diǎn) 為頂點(diǎn)，以兩個(gè)頂點(diǎn)之間的公交線路信息（需要花費(fèi)的時(shí)間、花費(fèi)的費(fèi)用等）為弧建立賦權(quán)圖，本題中站點(diǎn)個(gè)數(shù)共有 3957個(gè)，這樣得到的矩陣將是 3957階方陣，如此龐大的矩陣在使用計(jì)算機(jī)處理時(shí)，將會(huì)遇到很大的困難，我們所擁有的計(jì)算機(jī)硬件達(dá)不到要求。因此我們需要從另外一個(gè)角度重新描述公交線路網(wǎng)絡(luò)。進(jìn)而 我們 可以使用 通過(guò)動(dòng)態(tài)規(guī)劃 方法、最短路方法等建模思想構(gòu)造算法、編寫 程序 ， 使問(wèn)題得到圓滿地解決。 4 原始數(shù)據(jù)處理 （ 1）公交線路處理 我們將題中給出的 520 條公交線路進(jìn)行處理， 將每條線路人為地變成兩條，每一條代表一個(gè)具體 的行駛方向， 得到 1040 條起點(diǎn)終點(diǎn)固定的單方向行駛的公交線路。具體的處理方法如下： a) 對(duì)于上行與下行站點(diǎn) 相同 的線路 ，如 圖 1 中 (a)，將上行與下行視為不同的兩條線路，每一條作為一條新的單方向行駛的公交線路 ，即 BA? 及 AB? ； 由于兩個(gè)走向站點(diǎn)相同，因此這兩條線路經(jīng)過(guò)的站點(diǎn)集合相同，但是每個(gè)站點(diǎn)在兩條線路中的位置不同，這對(duì)衡量從某個(gè)站點(diǎn)出發(fā)乘坐該線路是否可以換乘其他線路，以及換乘哪條線路非常重要（詳細(xì)說(shuō)明見(jiàn)后續(xù)命題）； b) 對(duì)于 上行與下行站點(diǎn)不 同的 線路 ，如圖 1 中 (b)， 將上行方向與下行方向視為兩個(gè)不同的線路 BA? 及 AB? ，這兩條線路經(jīng)過(guò)的站點(diǎn)集合不同，從而每個(gè)站點(diǎn)在兩條線路中的站點(diǎn)位置也不同 ； c) 對(duì)于環(huán)形線路， 如圖 1 中 (c)，起點(diǎn)與終點(diǎn)為 A 的環(huán)形道路， 從中間某個(gè)站點(diǎn)斷開(kāi)，作為前一路線的終點(diǎn)以及后一路線的起點(diǎn)，這樣就形成兩條新的線路 。由于環(huán)線中間某些站可能重合，因此分割線路時(shí)要 保證 同一線路中沒(méi)有公共站點(diǎn)（編程設(shè)計(jì)的需要）并且兼顧兩條新 線路長(zhǎng)度均等。 圖 1 通過(guò)以上處理，我們將所有情況統(tǒng)一轉(zhuǎn)化為以起點(diǎn)和終點(diǎn)確定的 1040 條 具有單一方向的 有向線段 。 （ 2）建立站點(diǎn)與線路關(guān)系矩陣 利用（ 1）得到的 1040 條線路 及其上每個(gè)站點(diǎn)的信息， 構(gòu)造下列兩個(gè)反映 1040 條線路與 3957 個(gè)站點(diǎn)相關(guān)信息的矩陣 ，稱為?？啃畔⒕仃?： LS 與 LSN 。 LS 為 1040 行 3957 列的矩陣，元素為 0 或者 1，反 映 每條線路是否經(jīng)過(guò)每個(gè)站點(diǎn) ，元素取值為 ： ????jiji SL SLjiLS 不經(jīng)過(guò)站點(diǎn)線路 經(jīng)過(guò)站點(diǎn)線路01),( 。 LSN 也為 1040 行 3957 列的矩陣，元素為 0 或者某個(gè)自然數(shù) k ，反映每條線路經(jīng)過(guò)每個(gè)站點(diǎn)時(shí)，從該線路的起始點(diǎn)算起，該站為第 k 站，元素取值為： ????jiij SL kLSkjiL SN 不經(jīng)過(guò)站點(diǎn)線路 站的第為線路站點(diǎn)0),( 。 定義向量 :),(iLSLi ? 為線路 iL 的停靠向量 ， )( iLLB 為線路 iL 停靠的站點(diǎn)集合 ：}1),(|{)( ?? jiLSSLLB ji 。 A B （ a） A B （ b） （ c） A 5 )( jSSB 為停靠站點(diǎn) jS 的公汽線路集合 ： }1),(|{)( ?? jiLSLSSB ij 。 （ 3）每條線路的計(jì)費(fèi)信息 定義向量 ),( 1 0 4 021 cccC ?? 為每條線路的計(jì)費(fèi)信息， 按照題中所給出的計(jì)費(fèi)信息，元素取值為 ???? 條線路為分段計(jì)費(fèi)第 條線路為單一計(jì)費(fèi)第 iic i 10 。 若 0?ic ，則線路 iL 為單一收費(fèi)，票價(jià)均為 1 元； 若 1?ic ，則線路 iL 為分段收費(fèi)， 按照題中所給定的公汽票價(jià)方案，可以得到 乘坐 iL從其第 a 站到第 b （ ab? ） 站的費(fèi)用為 1),( ?? kcbaiCost i，其中 )2,20 1m in( ??? abk 。 可以發(fā)現(xiàn)單一收費(fèi)情形可以并入上述公式，因此 所有公汽線路（包括單一收費(fèi)與分段收費(fèi)）的費(fèi)用計(jì)算可以合并為一個(gè)函數(shù) 1),( ?? kcbaiCost i，其中 )2,20 1m in( ??? abk 。稱函數(shù) ),( baiCost 為沿著公交線路 iL 從其第 a 站到第 b 站的費(fèi)用函數(shù)。 相應(yīng)于費(fèi) 用函數(shù)，用函數(shù) )(),( abTbaiTim bb ?? 表示從該線路的第 a 站到第 b 站的時(shí)間函數(shù)，其中 bbT 表示相鄰公汽站平均行駛時(shí)間，在本題中取值為 3?bbT 。 判別兩條線路 之間 是否 可以換乘 ，得到任意兩條線路之間的換乘矩陣 命題 1： 乘客從 mS 出發(fā)， 乘坐線路 iL 可以直接到站點(diǎn) nS 的充要條件為1),(),( ?? niLSmiLS ，并且 ),(),( niL S NmiL S N ? 。同時(shí)可以得到 花費(fèi)的時(shí)間),( nim SLSTime 為 )),(),((3)),(),(,( miL S NniL S NniL S NmiL S NiT im ?? 花費(fèi)的車費(fèi) ),( nim SLSTCost 為 )),(),(,( niL S NmiL S NiC o st 。 命題 2： 設(shè) 線路 iL 的?？肯蛄?為 ))3 9 5 7,() ,. .. ,2,(),1,(( iLSiLSi