2007高教社杯全國(guó)生數(shù)學(xué)建模競(jìng)賽

2007高教社杯大學(xué)生數(shù)學(xué)建模競(jìng)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)評(píng)閱前進(jìn)行編號(hào)賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用統(tǒng)一編號(hào)（由賽區(qū)送交前編號(hào)評(píng)閱編號(hào)（ 評(píng)閱前進(jìn)行編號(hào)乘看奧本題是一個(gè)線路最優(yōu)選擇問(wèn)題15.引入地鐵線路后，地鐵站的設(shè)置將使在網(wǎng)絡(luò)上不連通的站點(diǎn)在地鐵站中通過(guò)在通過(guò)兩次乘車(chē)與乘坐一次地鐵完成出行，通過(guò)計(jì)算出結(jié)果，并將結(jié)果與只乘坐公交方案進(jìn)行評(píng)判，發(fā)現(xiàn)該方案相較于單乘坐出行方案有一定的優(yōu)越性。關(guān)鍵字：最小換乘次數(shù)算法交集法滿意度評(píng)價(jià)模型一、問(wèn)題重隨著日新月異的發(fā)展和第29屆奧運(yùn)會(huì)的即將到來(lái)，公共交通所承受朋友將會(huì)大量涌向，交通壓力可想而知。為此給人們帶來(lái)了一些不便，特別是第29屆奧運(yùn)會(huì)開(kāi)賽在即。近期，市第五批線路的方案正式發(fā)布，奧運(yùn)會(huì)期間專(zhuān)線規(guī)劃已經(jīng)提出了第一版本的那么，此時(shí)建立一個(gè)科學(xué)合理的城市線路自主查詢(xún)系統(tǒng)，將會(huì)給人們帶來(lái)極大 間交通暢通，目前已經(jīng)啟動(dòng)了奧運(yùn)智能交通管理系統(tǒng)。我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)奧運(yùn)比賽其中大部分人將會(huì)乘坐公共交通工（簡(jiǎn)稱(chēng)包括公汽地鐵等）出行。這些年來(lái)，城市的系統(tǒng)有了很大發(fā)展，市的線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決線路選擇問(wèn)題的自主查詢(xún)計(jì)算機(jī)系統(tǒng)。1相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5公汽換乘公汽平均耗時(shí) 5分鐘(其中步行時(shí)間2分鐘地鐵換乘地鐵平均耗時(shí) 4分鐘(其中步行時(shí)間2分鐘地鐵換乘公汽平均耗時(shí) 7分鐘(其中步行時(shí)間4分鐘公汽換乘地鐵平均耗時(shí) 6分鐘(其中步行時(shí)間4分鐘20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無(wú)論地鐵線路間是否換乘）【附錄2】給出了市公汽和地鐵的線路及站點(diǎn)相關(guān)信息6對(duì)起始站→終到站之間的最佳 (4)、 (5)、 二、問(wèn)題分題[6]。研究表明一般出行者以換乘次數(shù)為優(yōu)先考慮的目標(biāo)[7]，網(wǎng)絡(luò)的設(shè)計(jì)也以減[9]。另外，旅途時(shí)間具有隨機(jī)性，而旅行費(fèi)用的計(jì)算方式較多[8]，但一般而言所需時(shí)間、費(fèi)用都與途經(jīng)問(wèn)題三中應(yīng)該應(yīng)和“2008綠色奧運(yùn)，奧運(yùn)中國(guó)”的來(lái)建立模型三、模型的條件和假各 線路流量均勻，乘客流分布均衡假 網(wǎng)絡(luò)中任意線路中任意 的任意兩個(gè)相鄰點(diǎn)距離相等四、符號(hào)說(shuō) C0 經(jīng)過(guò)第i個(gè)站點(diǎn)的公汽線路的集合； 經(jīng)過(guò)出發(fā)點(diǎn)S0所有線路的集合； 經(jīng)過(guò)目的地Sm所有線路的集合； C0C Cm五、模型的建立與求單一公汽有向線路最優(yōu)模目前應(yīng)用較廣泛的最短路徑算法有Dijkstra，F(xiàn)ylod算法等。Dijkstra算法的缺點(diǎn)主要[4] 一次出行需轉(zhuǎn)車(chē)n

：一次出行需轉(zhuǎn)車(chē)n次時(shí)，經(jīng)過(guò)轉(zhuǎn)車(chē)站點(diǎn)ik的公汽線路的集合 i 假設(shè)第i個(gè)站點(diǎn)有k條線路經(jīng)過(guò)，若把這k條線路按次序排列依次編號(hào)為L(zhǎng)1,L2....Lk，則所有的路線可設(shè)為集合Ci，CiL1, 基于城市換乘次數(shù)最小模 ij之間可以直達(dá)，則經(jīng)過(guò)這兩個(gè)站點(diǎn)的總路線集合C、C 有相同的元素--路線，用數(shù)學(xué)語(yǔ)言表達(dá)，即是

CjS0SmS0和Sm的路線集合分別為C0和CmStep1：輸入乘車(chē)的出發(fā)站點(diǎn)S0SmStep2：求出經(jīng)過(guò)站點(diǎn)S0的所有線路集C0和經(jīng)過(guò)站點(diǎn)Sm的所有線路集Cm，如 Cm如圖（1）所示，算法結(jié)束，否則轉(zhuǎn)Step31Step3：判斷是否存在這樣的中轉(zhuǎn)站點(diǎn)i1，先求出經(jīng)過(guò)站點(diǎn)i1的所有線路集1

ii0 C而且ii0

CmC0、CmS0和i1站點(diǎn)的那路車(chē)，以及經(jīng)過(guò)i1和Sm的那路車(chē)，就可得具體的路線。如圖（2）所示，C、DStep42Step4i2i22

Ci而且 Cm即這個(gè)站點(diǎn)所經(jīng)的路線集合與

Cm 集，即知在Step3…kStep ikikk

ii0 C，ii0 k

C而且ii ii

Cm，即這個(gè)站點(diǎn)所經(jīng)的路線集合與k 一步驟的基礎(chǔ)上再轉(zhuǎn)一次車(chē)就可到達(dá)目的地站點(diǎn)kCDCCDCDFE圖(1- 圖（1- SSnn(S

Cm上算法的基本步棸，可用交集的數(shù)學(xué)語(yǔ)言寫(xiě)出n(S0Cm

C

Cm n(S,

)

i1,i2

Ci Cm i1,i2...ik...iI, Ci; k Cm按此算法求出的路線一定是轉(zhuǎn)車(chē)次數(shù)最少的方案用軟件求出所有可能的轉(zhuǎn)車(chē)方案后，可得到一次出行需轉(zhuǎn)車(chē)n次時(shí)，所有可行的轉(zhuǎn)車(chē)站點(diǎn)的總集InIn基于乘客不同需求路線選擇的最優(yōu)模一次出行時(shí)，所需的總車(chē)費(fèi)可用Qi來(lái)表示QiQi(S0,Sm5分鐘。從而可以求出出行時(shí)間函數(shù)ti（單位：分鐘）n

Min

CmCm

Ci Cm C n(S,

)

i1,i2

Ci

Cm C

,

Ci;

k PP(S,S

Cm QiQi(S0,Sm t5n3 基于乘客滿意度的路線全局最優(yōu)選擇模經(jīng)過(guò)綜合考慮轉(zhuǎn)乘車(chē)次最優(yōu)、車(chē)次最?。磿r(shí)間最優(yōu)此，可以引入乘客乘車(chē)滿意度變量wi。wi直接與車(chē)內(nèi)人數(shù)的多少有緊密聯(lián)系。乘客乘車(chē)滿意度變量EMBEDEquation.DSMT4會(huì)減少。2008年奧運(yùn)會(huì)即近專(zhuān)線規(guī)劃編制工作即將啟動(dòng)市將開(kāi)展奧 線網(wǎng)調(diào)研 賽時(shí)交通需求管理政策 體系的研究 短而增多，此時(shí)乘客乘車(chē)滿意度變量wi將會(huì)越來(lái)越小。wi是一個(gè)單調(diào)遞減函數(shù)。假設(shè)乘客于站點(diǎn)Si搭乘線路Li時(shí)，其對(duì)車(chē)內(nèi)舒適滿意度為wiwf(L,x)1

xLZ Z

iSiZlLii若要求路線的全局最優(yōu)解，則只要對(duì)最優(yōu)路線的轉(zhuǎn)車(chē)站點(diǎn)進(jìn)行滿意度wi的大小把問(wèn)題一給出的六組起始站點(diǎn)帶入到Step3發(fā)現(xiàn)在(1)S3359→S1828、(3)S0971→S0485、(4)S0008→S0073和(6)S0087→S3676這四對(duì)站點(diǎn)之間，可以找到轉(zhuǎn)車(chē)站點(diǎn)Ci1使中的起始點(diǎn)只轉(zhuǎn)一次車(chē)即可到達(dá)目的地。

Ci1而且

Cm，說(shuō)明從這四組首先， 軟件求解，經(jīng)過(guò)初步篩選可以得到可行的轉(zhuǎn)車(chē)方案接著，考慮目標(biāo)函數(shù)Min

和

Qi第一組：始發(fā)站：S3359→目的站：S1828A、初步篩選后的可行解集（S0到轉(zhuǎn)車(chē)站點(diǎn)Ci1搭乘的車(chē)次，從轉(zhuǎn)車(chē)站點(diǎn)Ci1Sm表 PQ（元nt(分鐘31313131314131313131B、評(píng)價(jià)說(shuō)以上表格對(duì)目標(biāo)函數(shù)第(2)條和第(4)以上表格對(duì)目標(biāo)函數(shù)

P1=32進(jìn)一步優(yōu)化，則可得第一類(lèi)乘客的最優(yōu)選擇路線在(a)步棸的基礎(chǔ)上對(duì)目標(biāo)函數(shù)線為表中的第(2)條和第(4)

Q1進(jìn)一步優(yōu)化，則得出第三類(lèi)乘客的最優(yōu)選擇可畫(huà)出從始發(fā)站：S3359→目的站：S1828表 S3359→S1828最優(yōu)路 從L436

從L436至 C、全局最優(yōu)方案選表 路線路線總站數(shù)方案一方案二Z=35，Z=18，X=34X=17f(Lx1Z Z

w10.029w20.056，因?yàn)閣1w2，所以方案二優(yōu)于方案一，選擇第二條第三組：始發(fā)站：S0971→目的站A、可行解用軟件求解，經(jīng)過(guò)初步篩選可以得到12種可行轉(zhuǎn)車(chē)方案，如下表表 PQ（元nt(分鐘514131313131313131513131B評(píng)價(jià)說(shuō)以上表格針對(duì)目標(biāo)函數(shù)以上表格針對(duì)目標(biāo)函數(shù)

P3=41進(jìn)一步優(yōu)化，第一類(lèi)乘客的最優(yōu)路線是第(8)條Q33(3)在(a)步棸的基礎(chǔ)上對(duì)目標(biāo)函數(shù)線為表中的第(8)

表轉(zhuǎn) 搭站 車(chē) L13和3C第四組：始發(fā)站：S0008→目的站A可行解 軟件求解，經(jīng)過(guò)初步篩選可以得到19種可行轉(zhuǎn)車(chē)方案，由于數(shù)據(jù)過(guò)多，可對(duì)

表 PQ(元nt(分鐘888888831821821821821821821B評(píng)價(jià)說(shuō)初始表格針對(duì)目標(biāo)函數(shù)

Qi在(a)步棸的基礎(chǔ)上對(duì)目標(biāo)函數(shù)

Qi(3)(5)表轉(zhuǎn) 搭站 車(chē) L159和2 L159和2 L159和2 L159和2 L159和2 L159和2 L159和2 L355和2 L355和2 L463和2C局最優(yōu)方案選點(diǎn)不同。在同一類(lèi)方案中，由于從出發(fā)站點(diǎn)S0008到轉(zhuǎn)車(chē)站點(diǎn)時(shí)，乘客只能是從站點(diǎn)S0008上車(chē)，此時(shí)車(chē)內(nèi)的舒適度是確定的，因而其滿意度也是確定的，所以只考慮從轉(zhuǎn)車(chē)站點(diǎn)到目的站點(diǎn)S0073時(shí)，乘客搭乘車(chē)次的滿意度。從轉(zhuǎn)車(chē)站點(diǎn)到達(dá)目的站點(diǎn)S0073，四類(lèi)方案需搭乘的車(chē)次依次為L(zhǎng)058、L474、和L057表 由以上表格可得出：第一類(lèi)的最優(yōu)路線經(jīng)過(guò)轉(zhuǎn)車(chē)站點(diǎn)第二類(lèi)的最優(yōu)路線經(jīng)過(guò)轉(zhuǎn)車(chē)站點(diǎn)S0400；第三類(lèi)的最優(yōu)路線經(jīng)過(guò)轉(zhuǎn)車(chē)站點(diǎn)S2303；第四類(lèi)的最優(yōu)路線經(jīng)過(guò)轉(zhuǎn)車(chē)站點(diǎn)w1X10.554；w1X20.474；w1X30.77；w1X4

w3最大，從而得出全局最優(yōu)選擇路線為經(jīng)過(guò)站點(diǎn)S2303第六組：始發(fā)站：S0087→目的站：S3676A用軟件求解可以得到2種可行轉(zhuǎn)車(chē)方案，如下表表 PQ(元nt(分鐘2121B、評(píng)價(jià)說(shuō)明及全局最優(yōu)方案選以上表格針對(duì)目標(biāo)函數(shù)以上表格針對(duì)目標(biāo)函數(shù)第(1)和第(2)

Qi=2在(a)步棸的基礎(chǔ)上對(duì)目標(biāo)函數(shù)線為表中的第(2)

表 第六組最優(yōu)路 L454

二次轉(zhuǎn)車(chē)的算法實(shí)S0的所有路線集合C0目的站點(diǎn)Sm的所有路線集合Cm，為了方便站點(diǎn)的表示，可引入“圓形集合”的概念，即把路線集合C0和路線集合Cm中所有路線上的站點(diǎn)（圖中用表示）放入一個(gè)圓形集S0SmS0Sm路線集合C0SC0；路線集合CmSCmLKSkSC0、SCmSC

Sk0SC

Sk0集集集S0SmSC0SCm”表示出發(fā)站點(diǎn)和目的站點(diǎn)對(duì)應(yīng)集合C、C LKLKSk中的站點(diǎn)第二組：始發(fā)站：S1557→目的站A、最優(yōu)路線表格表 S1557→S0481最有線 從L084至 再至 從L084至 再至（車(chē)站點(diǎn)，以L）L084

表 方案方案一方案二A表 S0148→S0485最優(yōu)路出 目站 站

換 線路經(jīng)過(guò)車(chē)車(chē) 站臺(tái)總數(shù)總 從L308至 再至 從L308至 再至 從L308至 再至（車(chē)站點(diǎn)，以L）

C、評(píng)價(jià)說(shuō)明及全局最優(yōu)方案選此問(wèn)題有三條最優(yōu)路線，在站點(diǎn)S0036時(shí)三條線路開(kāi)始有了分岔，但其轉(zhuǎn)車(chē)的車(chē)次確實(shí)一樣的，說(shuō)明了S2210、S3332、S3351這三個(gè)轉(zhuǎn)車(chē)站點(diǎn)是在一條線的，而且依表 方案方案一方案二方案二表 (分鐘----22------31------2122------21型中提出地面公共汽車(chē)和地鐵混合型的交通方式，為解決城市擁擠注入了新的。針對(duì)公汽與地鐵互聯(lián)，有以下特點(diǎn)：地鐵的站點(diǎn)會(huì)一些地面公汽線路的站點(diǎn)，這樣本模型就要考慮新的網(wǎng)地鐵的票價(jià)為單一票價(jià)：3元，不考慮地鐵線路間是否換乘。換句話說(shuō)，乘客不出地鐵站就只用一張車(chē)票；C C0C CmTDi：地鐵T1Di經(jīng)過(guò)的公汽站點(diǎn)集合UDi：地鐵T1站點(diǎn)Di經(jīng)過(guò)的公汽站點(diǎn)集合SRi：沒(méi)有經(jīng)過(guò)地鐵站點(diǎn)的公汽站點(diǎn)集合

,i12,18, ,Step1：判斷起點(diǎn)是否在TDi或UDi上，若是，則創(chuàng)建起點(diǎn)集合，建立起始站集合：SC0,滿足S0SC0；判別起點(diǎn)是否在TDi或UDi中，若是，則將TDi或UDi并入起點(diǎn)站集合，同理，判斷終點(diǎn)站是否在TDi或UDi上，若是，則創(chuàng)建起點(diǎn)集合，建立起始站集合：SC0,滿足S0SC0；判別起點(diǎn)是否在TDi或UDi中，若是，則將TDi或UDi并入起點(diǎn)站集合；Step2：T1i,k,s.t.S0TDi,SmTDk

S0TDi,SmTDi

S0TDi,i,SmTDi;Step3：i,

；

TTDiTDkS ,S 此時(shí)，S0與Sm分別在兩條不同的地鐵線可采用地鐵線換乘的方法完成行（1）需要坐乘地鐵T1轉(zhuǎn)車(chē)后才到達(dá)的方案表 經(jīng)T1轉(zhuǎn)車(chē)的線路總535955需要坐乘地鐵T2表 經(jīng)T2轉(zhuǎn)車(chē)的線路總585350003始發(fā)站點(diǎn)和目的站點(diǎn)都不能和地鐵的站點(diǎn)直接相連，即需要在EMBED 所對(duì)所有線路站點(diǎn)的集合EMBEDEquation.DSMT4Sm所對(duì)應(yīng)的所有路線站點(diǎn)集合SCmDi直接相連。

經(jīng)過(guò)地鐵T1的路線和經(jīng)過(guò)地鐵T25

第二組：始發(fā)站：S1557→目的站經(jīng)過(guò)地鐵T1的路線和經(jīng)過(guò)地鐵T2的路線的比較第一條路線經(jīng)過(guò)的 站數(shù)以及總的花費(fèi)時(shí)間都比第二條路線多得多因此經(jīng)過(guò)地鐵T1的路線為較優(yōu)路線

此組站點(diǎn)之間沒(méi)有經(jīng)過(guò)T1和T2的路線?？梢园l(fā)現(xiàn)，這兩組經(jīng)過(guò)地鐵T1的路線和經(jīng)過(guò)地鐵T2的路線是完全一樣的。 S0073 第六組：始發(fā)站：S0087→目的站：S3676由于第六組的始發(fā)站點(diǎn)和目的站點(diǎn)都屬于T2過(guò)T2換乘時(shí)，不需要公汽換乘班次，直接通過(guò)T2即可相連。2）不需要坐乘地鐵T

第四組：始發(fā)站：S0008→目的站第四組可以即不需要坐乘地鐵T1轉(zhuǎn)車(chē)，又不需坐乘地鐵T2表 S0008→S0073與地鐵乘換路線883882882228282883838389282第六組：始發(fā)站：S0087→目的站：S3676第六組不需要坐乘地鐵T2表 S0087→S3676與地鐵乘換路線582乘車(chē)模“2008綠色奧運(yùn)，奧運(yùn)中國(guó)”的。ti,j：步行從站點(diǎn)i到j(luò)的時(shí)間，i、jzpp

：距離i點(diǎn)lp長(zhǎng)度的站集1）人們乘車(chē)時(shí)步行距離的最大心里承受極限，lpm2）人們步行時(shí)的平均速度v3）奧運(yùn)村車(chē)網(wǎng)絡(luò)，相鄰站點(diǎn)的平均距離sm為建立規(guī)劃模型首先假設(shè)人們?cè)谄鹗键c(diǎn)時(shí)步行走到另一車(chē)站乘車(chē)如下圖起始起始點(diǎn)圖SmEi,lpES ES i

S同模型二運(yùn)用的算法一樣，當(dāng)Sm

與EE

的中間變量為nn六、模型評(píng)6.1本文中三個(gè)模型是基于不同假設(shè)條件之上，對(duì)于模型一：?jiǎn)我还邢蚓€又沒(méi)有線路連通的站次在連通，使得本模型的輸出結(jié)果更加具有科學(xué)七、參考文， ， 等，數(shù)值分析與實(shí)驗(yàn)，科學(xué)等，以最小換乘次數(shù)和站數(shù)為目標(biāo)的出行算法，計(jì)算機(jī)應(yīng)用，第24卷第12期，136-137，200412月。 求解，GIS楊新苗，，．基于GIS的乘客出行路徑選擇模型,東南大學(xué)學(xué)報(bào)(自然科學(xué)版LOHK，YIPCW，WANKH．Model