07年B題：乘公交，看奧運(yùn)我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng) 為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求請(qǐng)你們解決如下問題： 1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線（要有清晰的評(píng)價(jià)說明） (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同時(shí)考慮公汽與地鐵線路，解決以上問題 3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。

【附錄1】基本參數(shù)設(shè)定 相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)： 3分鐘 相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)： 2.5分鐘 公汽換乘公汽平均耗時(shí)： 5分鐘(其中步行時(shí)間2分鐘) 地鐵換乘地鐵平均耗時(shí)： 4分鐘(其中步行時(shí)間2分鐘) 地鐵換乘公汽平均耗時(shí)： 7分鐘(其中步行時(shí)間4分鐘) 公汽換乘地鐵平均耗時(shí)： 6分鐘(其中步行時(shí)間4分鐘) 公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元 地鐵票價(jià)：3元（無論地鐵線路間是否換乘） 注：以上參數(shù)均為簡(jiǎn)化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合乘公交，看奧運(yùn)摘要：本文是為了開發(fā)一個(gè)解決北京市公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)在充分理解題意的基礎(chǔ)上，我們從總體上把握，一致認(rèn)為這是運(yùn)籌學(xué)中的最短路問題我們所提供的這個(gè)系統(tǒng)，對(duì)于當(dāng)乘客輸入起始站和終點(diǎn)站，點(diǎn)擊查詢結(jié)果后，查詢機(jī)就能很快地給出乘車路線及乘車所需要的最短時(shí)間，并且，還可以給出相應(yīng)的乘車費(fèi)用所以，我們想到了建立網(wǎng)絡(luò)模型來解決對(duì)于問題一，在僅僅考慮公共汽車的換乘的時(shí)候，我們以最短的乘車時(shí)間和最優(yōu)的乘車費(fèi)用作為兩個(gè)目標(biāo)函數(shù)，建立相應(yīng)的雙目標(biāo)規(guī)劃模型：對(duì)于問題二與問題三我們同樣建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型，具體模型見正文。

并利用Dijkstra算法解出我們所需要的結(jié)果我們同樣利用了雙目標(biāo)函數(shù)的統(tǒng)籌規(guī)劃原理，在Dijkstra和回溯的算法下 ， 解決了在公共汽車和地鐵之間換乘的問題，求得最短時(shí)間問題，找到了最合適的公交路線，均為最短的乘車時(shí)間和最有的乘車費(fèi)用，從而更加完善了我們的公交系統(tǒng)關(guān)鍵詞：最短行程 雙目標(biāo) 網(wǎng)絡(luò)模型 Dijkstra算法一、 問題重述 我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求請(qǐng)你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線（要有清晰的評(píng)價(jià)說明）。

(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型附錄1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)： 3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)： 2.5分鐘公汽換乘公汽平均耗時(shí)： 5分鐘(其中步行時(shí)間2分鐘)地鐵換乘地鐵平均耗時(shí)： 4分鐘(其中步行時(shí)間2分鐘)地鐵換乘公汽平均耗時(shí)： 7分鐘(其中步行時(shí)間4分鐘)公汽換乘地鐵平均耗時(shí)： 6分鐘(其中步行時(shí)間4分鐘)公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎn)化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合附錄2】公交線路及相關(guān)信息 （見數(shù)據(jù)文件B2007data.rar）二 、基本假設(shè)1、按常理，人們總是在換乘兩輛公汽后就不會(huì)再換其他的公汽，本模型假定可以查到換乘兩次公汽所行使的路線，至于其它線路，本模型也可以繼續(xù)求出，但考慮到人們的觀念，所以在換乘兩輛車后就可以找到最優(yōu)的路線，并且乘車費(fèi)合理，可以被人們所接受。

2、從一站乘L車到下一戰(zhàn)換車時(shí)，不會(huì)再乘坐同一輛車3、最短的時(shí)間是人們首先考慮到的事情，所以在最短時(shí)間和最低費(fèi)用相沖突的情況下，優(yōu)先考慮時(shí)間問題三、基本符號(hào)說明為了便于問題的說明，我們用一些符號(hào)來代替問題中出現(xiàn)的一些基本變量其它的一些變量，在文中會(huì)陸續(xù)說明i:起始站臺(tái)的號(hào)數(shù)j:終點(diǎn)站臺(tái)的號(hào)數(shù)：從i站乘l車到j(luò)站:第i個(gè)站臺(tái)到第j個(gè)站臺(tái)所用的最優(yōu)時(shí)間權(quán)值（分鐘）, :目標(biāo)函數(shù)最優(yōu)的乘車費(fèi)（元） ：公汽的票價(jià)函數(shù)（元） ：整型函數(shù) ，其值為1或0：換車的兩站之間所隔的站臺(tái)數(shù)四 問題的分析考慮到問題的假設(shè)與要求，我們以最短的行車時(shí)間和最低的乘車費(fèi)用作為最佳的路線和方案題目第一問要求我們根據(jù)附錄數(shù)據(jù)，僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法，并求出6對(duì)起始站→終到站之間的最佳路線實(shí)質(zhì)上就是求兩站之間最佳路線問題由于題中給的數(shù)量較多，逐條路線去求最佳路線的問題是不可能的，所以我們決定用Dijkstra算法求出最佳的路線題目的第二問要求我們?cè)诘谝粏柕幕A(chǔ)上同時(shí)考慮公汽與地鐵線路的問題，并求出第一問所要解決的問題，實(shí)際上是將地鐵看成一輛新增加的公交車，并同時(shí)考慮新增加的公交車站的問題。

題目第三個(gè)問題是要求我們?cè)诩僭O(shè)知道所有站點(diǎn)之間的步行時(shí)間的情況下，給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型 圖1 最短路程問題的網(wǎng)絡(luò)圖五 問題的模型建立5.1 問題一的模型建立 為了解決這類的最優(yōu)路線問題，我們采用網(wǎng)絡(luò)理論模型來建立求解在所求的起始站到終點(diǎn)站最佳問題中，僅僅考慮乘公汽的情況，也涉及到許多情況，如直接乘直達(dá)車，不經(jīng)任何的中轉(zhuǎn)站的，換乘K輛車（k介于1到m-1指間）等上面的網(wǎng)絡(luò)圖（圖1）反映了我們的思路：設(shè)我們所研究的問題共有n個(gè)公共汽車站點(diǎn)，并且我們有m個(gè)車，在第i個(gè)站點(diǎn)（起始站）到第j個(gè)站點(diǎn)（終點(diǎn)站）之間，我們不妨假設(shè)從1到n的乘車方法有直達(dá)車，換車并且可以換乘1輛，2輛，3輛 …… ，那么為了解決問題的 方便，我們假設(shè)有當(dāng)車行使至第j站時(shí)，我們又作如下假設(shè)：在題目給定的條件下，在僅考慮公交路線的情況下，我們可以的得到任意兩站（i和j站）之間的最優(yōu)乘車時(shí)間值，我們給出公式： （1）即所求的最優(yōu)時(shí)間為行使的時(shí)間和換乘時(shí)間的和 所求的最優(yōu)時(shí)間要受到如下的7個(gè)條件約束：以上目標(biāo)函數(shù)是公交車行使的時(shí)間和換乘時(shí)間的和，其中是從第站點(diǎn)到第站點(diǎn)輛車所經(jīng)過的總站點(diǎn)數(shù)，是轉(zhuǎn)車次數(shù)。

表示出發(fā)站應(yīng)滿足的條件，即乘客必須乘某一車次前往某一站表示目的站應(yīng)滿足的條件，即乘客必須乘某一車次經(jīng)某一站到達(dá)目的站表示在第j站作為中間站點(diǎn)時(shí)，若有車次經(jīng)過則式子左邊的值為0，若此站作為終點(diǎn)站則式子左邊的值為1，即有進(jìn)無出去的情況 表示第i站作為中間站點(diǎn)時(shí)，若有車次經(jīng)過則式子左邊的值為0，若此站作為起點(diǎn)站則式子左邊的值為1，即車輛有出無進(jìn)的情況表示車輛與某站點(diǎn)的關(guān)系，若某車輛既不進(jìn)也不出某站點(diǎn)，此式子左右兩邊都為0，若車輛既從此站點(diǎn)進(jìn)去同時(shí)也從此站點(diǎn)出來，則此式子左右兩邊都為1分為以下幾種情況：1）假如車輛沒有經(jīng)過某站點(diǎn)，此時(shí)的值為0，同時(shí)的值也為0，中間的式子為0;2)假如車輛經(jīng)過了某站點(diǎn)且沒有轉(zhuǎn)車，此時(shí)的值為1，同時(shí)的值也為1，中間的式子為0；3）假如車輛經(jīng)過了某站點(diǎn)且有轉(zhuǎn)車的情況，對(duì)于轉(zhuǎn)車前的車，此時(shí)的值為1，同時(shí)的值也為0中間式子為1；對(duì)于轉(zhuǎn)車后的車有的值為0，同時(shí)的值也為1，中間式子為-1這三種情況的結(jié)果符合模型前的換車函數(shù)上述目標(biāo)函數(shù)是基于時(shí)間最短而得出的最佳路線，這是人們?cè)趯?shí)際生活中乘公交車最基本的要求，所以此項(xiàng)指標(biāo)作為評(píng)價(jià)一條路徑好不好的最重要的指標(biāo)但是同時(shí)人們也會(huì)考慮到乘車的花費(fèi)多少，所以在選擇公交車時(shí)會(huì)對(duì)路徑和花費(fèi)進(jìn)行綜合考慮，即要求到達(dá)目的地的時(shí)間最短且花費(fèi)最小。

下面我們針對(duì)這種情況給出了模型及其方案，并相應(yīng)得出最短時(shí)間和最少花費(fèi)所以綜合得出最終的模型為： 第二個(gè)目標(biāo)函數(shù)是求最小花費(fèi)，其中表示某一輛車從第i站點(diǎn)到第j站點(diǎn)中間所經(jīng)過的站點(diǎn)數(shù)，表示票價(jià)函數(shù)，其函數(shù)式子為： ，其他的式子表示的含義同上面的約束條件中的解析5.2 問題二模型的建立問題二中要求考慮乘客可以乘坐地鐵交通工具，因此我們依據(jù)問題一中的模型，考慮如下因素：1）乘客選擇的交通工具為公交或地鐵，此時(shí)相應(yīng)地有變量：2）乘客可由公交車轉(zhuǎn)乘地鐵，此時(shí)相應(yīng)地有變量及約束條件：3）乘客可由地鐵轉(zhuǎn)乘公交車，此時(shí)相應(yīng)地有變量及約束條件：4）乘客可由地鐵轉(zhuǎn)乘地鐵，此時(shí)相應(yīng)地有變量：5）乘客在公交站可不換公交車、或可轉(zhuǎn)乘公交車、或可轉(zhuǎn)乘地鐵，但三種選擇不可同時(shí)進(jìn)行，因此相應(yīng)的有約束條件，6）乘客在D12及D18地鐵站可不換地鐵線、或可換乘公交車、或可換乘地鐵線，但三種選擇不可同時(shí)進(jìn)行，因此相應(yīng)的有約束條件：綜合以上因素，即相應(yīng)的新的乘車時(shí)間及票費(fèi)的計(jì)算，我們建立如下的雙目標(biāo)規(guī)劃模型：5.3 問題三的模型建立問題三中要求考慮乘客可以采用步行方式，因此我們依據(jù)問題二中的模型，考慮如下因素：1）乘客選擇的交通工具為公交或地鐵或步行，此時(shí)相應(yīng)地有變量：2）乘客可由公交車轉(zhuǎn)為步行方式3）乘客可由地鐵轉(zhuǎn)為步行方式 5）乘客在公交站可不換公交車、或可轉(zhuǎn)乘公交車、或可轉(zhuǎn)乘地鐵，或轉(zhuǎn)為步行方式，但四種選擇不可同時(shí)進(jìn)行 6）乘客在D12及D18地鐵站可不換地鐵線、或可換乘公交車、或可換乘地鐵線、或改為步行方式，但四種選擇不可同時(shí)進(jìn)行，因此相應(yīng)的有約束條件：綜合以上因素，即相應(yīng)的新的乘車時(shí)間及票費(fèi)的計(jì)算，建立如下的雙目標(biāo)規(guī)劃模型： 六 模型的求解6.1 模型一的求解為求最優(yōu)時(shí)間和費(fèi)用的目標(biāo)函數(shù)即：，我們決定用Dijkstra算法來解決這類最短路問題，我們是通過LINGO軟件來實(shí)現(xiàn)的。

經(jīng)過計(jì)算機(jī)的編程運(yùn)行解決后，得到問題一的解決方案，下面是在僅考慮公共汽車之間的換乘問題，給替乘車者提供最優(yōu)路線的方案。