論文：乘公交 看奧運 - 07年全國數(shù)學建模競賽論文

1、07年b題：乘公交，看奧運我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。 為了設計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題： 1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。并根

2、據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485 (4)、s0008s0073 (5)、s0148s0485 (6)、s0087s3676 2、同時考慮公汽與地鐵線路，解決以上問題。 3、假設又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學模型。 【附錄1】基本參數(shù)設定 相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘 相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘 公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘) 地鐵換乘地

3、鐵平均耗時： 4分鐘(其中步行時間2分鐘) 地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘) 公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘) 公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元 地鐵票價：3元（無論地鐵線路間是否換乘） 注：以上參數(shù)均為簡化問題而作的假設，未必與實際數(shù)據(jù)完全吻合乘公交，看奧運摘要：本文是為了開發(fā)一個解決北京市公交線路選擇問題的自主查詢計算機系統(tǒng)。在充分理解題意的基礎上，我們從總體上把握，一致認為這是運籌學中的最短路問題。我們所提供的這個系統(tǒng)，對于當乘客輸入起始站和終點站，點擊查詢

4、結果后，查詢機就能很快地給出乘車路線及乘車所需要的最短時間，并且，還可以給出相應的乘車費用。所以，我們想到了建立網(wǎng)絡模型來解決。對于問題一，在僅僅考慮公共汽車的換乘的時候，我們以最短的乘車時間和最優(yōu)的乘車費用作為兩個目標函數(shù)，建立相應的雙目標規(guī)劃模型：對于問題二與問題三我們同樣建立了相應的數(shù)學規(guī)劃模型，具體模型見正文。并利用dijkstra算法解出我們所需要的結果。我們同樣利用了雙目標函數(shù)的統(tǒng)籌規(guī)劃原理，在dijkstra和回溯的算法下 ， 解決了在公共汽車和地鐵之間換乘的問題，求得最短時間問題，找到了最合適的公交路線，均為最短的乘車時間和最有的乘車費用，從而更加完善了我們的公交系統(tǒng)。關鍵詞：

5、最短行程 雙目標 網(wǎng)絡模型 dijkstra算法一、 問題重述 我國人民翹首企盼的第29屆奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。為了設計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路

6、選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學模型。【附錄1】基本參數(shù)設定相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘公汽換乘公汽平均耗時： 5分鐘(其中步行時間

7、2分鐘)地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡化問題而作的假設，未必與實際數(shù)據(jù)完全吻合?！靖戒?】公交線路及相關信息 （見數(shù)據(jù)文件b2007data.rar）二 、基本假設1、按常理，人們總是在換乘兩輛公汽后就不會再換其他的公汽，本模型假定可以查到換乘兩次公汽所行使的路線，至于其它線路，本模型也可以

8、繼續(xù)求出，但考慮到人們的觀念，所以在換乘兩輛車后就可以找到最優(yōu)的路線，并且乘車費合理，可以被人們所接受。 2、從一站乘l車到下一戰(zhàn)換車時，不會再乘坐同一輛車。3、最短的時間是人們首先考慮到的事情，所以在最短時間和最低費用相沖突的情況下，優(yōu)先考慮時間問題。三、基本符號說明為了便于問題的說明，我們用一些符號來代替問題中出現(xiàn)的一些基本變量。其它的一些變量，在文中會陸續(xù)說明。i:起始站臺的號數(shù)j:終點站臺的號數(shù)：從i站乘l車到j站:第i個站臺到第j個站臺所用的最優(yōu)時間權值（分鐘）, :目標函數(shù)最優(yōu)的乘車費（元） ：公汽的票價函數(shù)（元） ：整型函數(shù) ，其值為1或0：換車的兩站之間所隔的站臺數(shù)四 問題的分

9、析考慮到問題的假設與要求，我們以最短的行車時間和最低的乘車費用作為最佳的路線和方案。題目第一問要求我們根據(jù)附錄數(shù)據(jù)，僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法，并求出6對起始站終到站之間的最佳路線。實質上就是求兩站之間最佳路線問題。由于題中給的數(shù)量較多，逐條路線去求最佳路線的問題是不可能的，所以我們決定用dijkstra算法求出最佳的路線。題目的第二問要求我們在第一問的基礎上同時考慮公汽與地鐵線路的問題，并求出第一問所要解決的問題，實際上是將地鐵看成一輛新增加的公交車，并同時考慮新增加的公交車站的問題。題目第三個問題是要求我們在假設知道所有站點之間的步行時間的情況下

10、，給出任意兩站點之間線路選擇問題的數(shù)學模型。 圖1 最短路程問題的網(wǎng)絡圖五 問題的模型建立5.1 問題一的模型建立 為了解決這類的最優(yōu)路線問題，我們采用網(wǎng)絡理論模型來建立求解。在所求的起始站到終點站最佳問題中，僅僅考慮乘公汽的情況，也涉及到許多情況，如直接乘直達車，不經任何的中轉站的，換乘k輛車（k介于1到m-1指間）等。上面的網(wǎng)絡圖（圖1）反映了我們的思路：設我們所研究的問題共有n個公共汽車站點，并且我們有m個車，在第i個站點（起始站）到第j個站點（終點站）之間，我們不妨假設從1到n的乘車方法有直達車，換車并且可以換乘1輛，2輛，3輛 ，那么為了解決問題的 方便，我們假設有當車行使至第j站時

11、，我們又作如下假設：在題目給定的條件下，在僅考慮公交路線的情況下，我們可以的得到任意兩站（i和j站）之間的最優(yōu)乘車時間值，我們給出公式： （1）即所求的最優(yōu)時間為行使的時間和換乘時間的和。 所求的最優(yōu)時間要受到如下的7個條件約束：以上目標函數(shù)是公交車行使的時間和換乘時間的和，其中是從第站點到第站點輛車所經過的總站點數(shù)，是轉車次數(shù)。表示出發(fā)站應滿足的條件，即乘客必須乘某一車次前往某一站。表示目的站應滿足的條件，即乘客必須乘某一車次經某一站到達目的站。表示在第j站作為中間站點時，若有車次經過則式子左邊的值為0，若此站作為終點站則式子左邊的值為1，即有進無出去的情況。 表示第i站作為中間站點時，若有

12、車次經過則式子左邊的值為0，若此站作為起點站則式子左邊的值為1，即車輛有出無進的情況。表示車輛與某站點的關系，若某車輛既不進也不出某站點，此式子左右兩邊都為0，若車輛既從此站點進去同時也從此站點出來，則此式子左右兩邊都為1。分為以下幾種情況：1）假如車輛沒有經過某站點，此時的值為0，同時的值也為0，中間的式子為0;2)假如車輛經過了某站點且沒有轉車，此時的值為1，同時的值也為1，中間的式子為0；3）假如車輛經過了某站點且有轉車的情況，對于轉車前的車，此時的值為1，同時的值也為0中間式子為1；對于轉車后的車有的值為0，同時的值也為1，中間式子為-1。這三種情況的結果符合模型前的換車函數(shù)。上述目標

13、函數(shù)是基于時間最短而得出的最佳路線，這是人們在實際生活中乘公交車最基本的要求，所以此項指標作為評價一條路徑好不好的最重要的指標。但是同時人們也會考慮到乘車的花費多少，所以在選擇公交車時會對路徑和花費進行綜合考慮，即要求到達目的地的時間最短且花費最小。下面我們針對這種情況給出了模型及其方案，并相應得出最短時間和最少花費。所以綜合得出最終的模型為： 第二個目標函數(shù)是求最小花費，其中表示某一輛車從第i站點到第j站點中間所經過的站點數(shù)，表示票價函數(shù)，其函數(shù)式子為： ，其他的式子表示的含義同上面的約束條件中的解析。5.2 問題二模型的建立問題二中要求考慮乘客可以乘坐地鐵交通工具，因此我們依據(jù)問題一中的模

14、型，考慮如下因素：1）乘客選擇的交通工具為公交或地鐵，此時相應地有變量：2）乘客可由公交車轉乘地鐵，此時相應地有變量及約束條件：3）乘客可由地鐵轉乘公交車，此時相應地有變量及約束條件：4）乘客可由地鐵轉乘地鐵，此時相應地有變量：5）乘客在公交站可不換公交車、或可轉乘公交車、或可轉乘地鐵，但三種選擇不可同時進行，因此相應的有約束條件，6）乘客在d12及d18地鐵站可不換地鐵線、或可換乘公交車、或可換乘地鐵線，但三種選擇不可同時進行，因此相應的有約束條件：綜合以上因素，即相應的新的乘車時間及票費的計算，我們建立如下的雙目標規(guī)劃模型：5.3 問題三的模型建立問題三中要求考慮乘客可以采用步行方式，因此

15、我們依據(jù)問題二中的模型，考慮如下因素：1）乘客選擇的交通工具為公交或地鐵或步行，此時相應地有變量：2）乘客可由公交車轉為步行方式3）乘客可由地鐵轉為步行方式 5）乘客在公交站可不換公交車、或可轉乘公交車、或可轉乘地鐵，或轉為步行方式，但四種選擇不可同時進行 6）乘客在d12及d18地鐵站可不換地鐵線、或可換乘公交車、或可換乘地鐵線、或改為步行方式，但四種選擇不可同時進行，因此相應的有約束條件：綜合以上因素，即相應的新的乘車時間及票費的計算，建立如下的雙目標規(guī)劃模型： 六 模型的求解6.1 模型一的求解為求最優(yōu)時間和費用的目標函數(shù)即：，我們決定用dijkstra算法來解決這類最短路問題，我們是通

16、過lingo軟件來實現(xiàn)的。經過計算機的編程運行解決后，得到問題一的解決方案，下面是在僅考慮公共汽車之間的換乘問題，給替乘車者提供最優(yōu)路線的方案。表1 僅考慮公汽線路時的s3359s1828最佳路線1、s3359s1828耗時（分鐘）101路費（元）3車次l436、l167轉車站s1784路徑s3359-s2026-s1132-s2266-s2263-s3917-s2303-s2301-s3233-s0618-s0616-s2112-s2110-s2153-s2814-s2813-s3501-s3515-s3500-s0756-s0492-s0903-s1768-s0955-s0480-s270

17、3-s2800-s2192-s2191-s1829-s3649-s1784s1784-s1828表2 僅考慮公汽線路時的s1577s0481最佳路線2、s1577s0481耗時（分鐘）106路費（元）3車次l084、l189、l460轉車站s1919、s3186路徑s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s0028-s0029-s0055-s0051-s1919s1919-s2840-s1402-s3186s3186-s3544-s2116-s2119-s1788-s1789-s1770-s2322-s0992-s2184-s2954-s

18、3117-s2424-s1174-s0902-s0903-s2101-s0481表3 僅考慮公汽線路時s0971s0485的最佳路線3、s0971s0485耗時（分鐘）128路費（元）3車次l013、l417轉車站s2184路徑s0971-s3832-s3341-s2237-s3565-s3333-s1180-s3494-s1523-s1520-s1988-s1743-s1742-s1181-s1879-s3405-s2517-s3117-s2954-s0531-s2184s2184-s0992-s2322-s1770-s1789-s2119-s2116-s3544-s3186-s3409-s

19、2717-s1402-s2840-s0643-s2079-s1920-s2480-s2482-s2210-s3332-s3351-s0485表4 僅考慮公汽線路時s0008s0073的最佳路線4、s0008s0073耗時（分鐘）83路費（元）2車次l159、l474轉車站s0400路徑s0008-s3412-s2743-s3586-s2544-s0913-s2953-s3874-s0630-s0854-s0400s0400-s2633-s3053-s0410-s0411-s2846-s0605-s0604-s0527-s0525-s3470-s2619-s2340-s3162-s2181-s2

20、705-s0073表5 僅考慮公汽線路時s0148s0485的最佳路線5、s0148s0485耗時（分鐘）106路費（元）3車次l308、l156、l417轉車站s0036、s2210路徑s0148-s0462-s0361-s1797-s2221-s0302-s2222-s2737-s1716-s0128-s2268-s1308-s1391-s2272-s00360036-s3233-s0618-s0617-s0721-s2057-s2361-s0608-s0399-s2535-s2534-s0239-s0497-s2090-s2082-s2210s2210-s3332-s3351-s0485

21、表6 僅考慮公汽線路時s0087s36766、s0087s3676耗時（分鐘）65路費（元）2車次l454、l209轉車站s3496路徑s0087-s0857-s0630-s1427-s1426-s0541-s0978-s3389-s1919-s0641-s2840-s3496s3496-s1883-s1159-s2699-s2922-s3010-s0583-s1987-s0082-s3676以上6個公交車路線是根據(jù)網(wǎng)絡模型所得出的結論，在起始站到終點站之間有很多不同的乘車路線，但我們可以看出所求的6條路線都是要經歷一個或兩個中轉站才能到達終點站，與其它的路線相比，它們耗費的時間短，且路費也低

22、，所以該模型很好的解決了最短行程的問題。6.2模型二的求解 在第一問的基礎上，我們又需要重新考慮公共汽車和地鐵的換乘問題，以及地鐵和地鐵的換乘問題，在利用數(shù)學軟件軟件進行的編程過程中，我們又得到以下的結論：表7 同時考慮公汽與地鐵線路時s3359s1828的最佳路線1、s3359s1828耗時（分鐘）101路費（元）3車次l436、l167轉車站s1784路徑s3359-s2026-s1132-s2266-s2263-s3917-s2303-s2301-s3233-s0618-s0616-s2112-s2110-s2153-s2814-s2813-s3501-s3515-s3500-s0756

23、-s0492-s0903-s1768-s0955-s0480-s2703-s2800-s2192-s2191-s1829-s3649-s1784s1784-s1828表8 同時考慮公汽與地鐵線路時 s1577s0481的最優(yōu)路線2、s1577s0481耗時（分鐘）106路費（元）3車次l084、l189、l460轉車站s1919、s3186路徑s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s0028-s0029-s0055-s0051-s1919s1919-s2840-s1402-s3186s3186-s3544-s2116-s2119-s17

24、88-s1789-s1770-s2322-s0992-s2184-s2954-s3117-s2424-s1174-s0902-s0903-s2101-s0481表9 同時考慮公汽與地鐵線路時s0971s0485 的最優(yōu)路線3、s0971s0485耗時（分鐘）128路費（元）3車次l013、l417轉車站s2184路徑s0971-s3832-s3341-s2237-s3565-s3333-s1180-s3494-s1523-s1520-s1988-s1743-s1742-s1181-s1879-s3405-s2517-s3117-s2954-s0531-s2184s2184-s0992-s232

25、2-s1770-s1789-s2119-s2116-s3544-s3186-s3409-s2717-s1402-s2840-s0643-s2079-s1920-s2480-s2482-s2210-s3332-s3351-s0485表10 同時考慮公汽與地鐵線路時 s0008s0073的最優(yōu)路線4、s0008s0073耗時（分鐘）70路費（元）5車次l159、t2、l474轉車站s3874、s0525路徑s0008-s3412-s2743-s3586-s2544-s0913-s2953-s3874-d30-d29-d28-d27-d12-d26-d25-s0525 -s3470-s2619-s2

26、340-s3162-s2181-s2705-s0073表11 同時考慮公汽與地鐵線路時s0148s0485的最優(yōu)路線5、s0148s0485耗時（分鐘）92.5路費（元）6車次l308、t1、t2、l156、l417轉車站s0302、d12、s0497、s2210路徑s0148-s0462-s0361-s1797-s2221-s0302-d3-d4-d5-d6-d7-d8-d9-d10-d11-d12-d27-d28-d29-d30-d31-d32-s0497-s2090-s2082-s2210s2210-s3332-s3351-s0485表12 同時考慮公汽與地鐵線路時s0087s3676的

27、最優(yōu)路線6、s0087s3676耗時（分鐘）38路費（元）3車次t2轉車站無路徑s0087-d27-d28-d29-d30-d31-d32-d18-d33-d34-d35-d36 -s3676 從以上的6條線路問題，我們可以得出前三個公交車路線都只有涉及到公交車之間的換乘，而不涉及到地鐵與公交車之間以及地鐵與地鐵之間的換乘，費用相對較低。當涉及到地鐵與公交車換乘時，所經歷的中轉站較多，超過兩個，且費用相對其它較高一些，但中間站都是地鐵站時，所用的時間短，路線也短。七 模型的推廣通過對題目的解讀我們不難發(fā)現(xiàn)這是一類運籌學中的最短路問題。我們建立了一個雙目標的網(wǎng)絡的模型。仔細分析我們建立的模型不難

28、發(fā)現(xiàn)：這個模型不僅僅適用于乘公交車配置問題，即最短路和最低費用的問題，它對圖論類的優(yōu)化問題的求解都可以起到指導作用。最短路問題是運籌學的圖論的一個重要分支。它在解決乘公交車的路徑選擇，都發(fā)揮著重要的作用。本文模型的建立是為了解決最優(yōu)的公交路線的問題，既要考慮到乘車時間的最短問題，又要考慮到公交費用的問題。通過網(wǎng)絡模型的建立最優(yōu)化乘車路線。決策者要通過概念抽象、關系分析可將各類影響因子放入網(wǎng)絡模型中，可以通過相關的計算機軟件得到兼顧全局的最優(yōu)解。本題的求解是一個典型的運籌學最短路問題，我們模型的使用范圍非常廣泛，在工業(yè)、商業(yè)、交通運輸、工程技術、行政管理等領域有著廣泛的應用。八 模型的優(yōu)缺點優(yōu)點

29、：1、文章真實性強，論文中的模型都是自行推導建立的；2、建立的最短路問題模型能與實際緊密聯(lián)系，結合實際情況對問題進行求解，使得模型具有很好的通用性和推廣性；3、模型的計算采用專業(yè)的數(shù)學軟件，可信度較高；4、對模型中涉及到的眾多影響因素進行了一般性分析，使得論文有說服力。缺點：1、雖然建立的模型比較完美，但是利用計算機在計算的過程中由于數(shù)據(jù)的龐大，嚴重影響了運行速度以及在以后的n次轉車時會出現(xiàn)溢出。2、由于在計算過程中題目給的平均行駛及轉車時間是非現(xiàn)實的，所以使得模型的計算會有所偏差。參考文獻1 謝金星,優(yōu)化建模與lindo/lingo軟件.北京:清華大學出版社，180頁-190頁，2005年2

30、沈繼英，數(shù)學建模.哈爾濱：哈爾濱工程大學出版社，1996年3 吳翊，數(shù)學建模的理論與實踐.長沙：國防科技大學出版社，1999年4朱道元，數(shù)序建模案例精選. 北京：科學技術出版社，2005年5月5李瑛，決策統(tǒng)計分析.天津：天津大學出版社，2005年3月6刑曾萍，最佳專輯.北京：人民有郵電出版社，2002年7王兵團，數(shù)學建?；A.北京：清華大學出版社 ，昆明大學出版社，2004年11月附錄/delphi 6.0unit methods;interfaceuses windows, messages, sysutils, variants, classes, graphics, controls,

31、forms, dialogs, stdctrls;const sn=3957;const max=9999 ;procedure getline(s1: string;s2:string;c:char;var lines:tstrings;data:tstrings); /找到兩個站點之間直接路線procedure search(s1:string;s2:string;var results:tstrings);/查找兩個站點之間的最佳路徑function getnum(l:string;c:char):integer; /找出給定線路的站點數(shù)function getname(l:string

32、;num:integer;c:char):string;/ 獲取給定路線的第num個站點function getindex(l:string;name:string;c:char):integer;/找某個站點的索引1開始，1表示無function extrnum(name:string):integer;function reverseroute(l:string;c:char):string;/翻轉路線function formname(num:integer):string; /把站點形成站名procedure loaddata(var data:tstrings);function g

33、etdirectroute(line:string;lindex,rindex:integer): string;/求一條線路上兩站間的路徑procedure getroute_unch(s1,s2:string;data:tstrings;var time:integer;var linename,route:string); /尋找不經轉站的最優(yōu)路徑procedure getroute_ch1(s1,s2:string;data:tstrings;var time:integer;var linename1,linename2,chsite,route:string);procedure

34、getroute_ch2(s1,s2:string;data:tstrings;var time:integer;var linename1,linename2,linename3,chsite1,chsite2,route:string);implementationuses unit1, packs;function getdirectroute(line:string;lindex,rindex:integer): string;/求一條線路上兩站間的路徑var i:integer;var tem:string;begin result:=getname(line,lindex,s);

35、for i:=lindex+1 to rindex do begin tem:=; tem:= getname(line,i,s) ; result:=result+-+tem; end;end;function formname(num:integer):string; /把站點形成站名 var i:integer; name:string; begin name:=inttostr(num); while length(name)len then result:= else begin for i:=1 to length(l) do begin if li=c then n:=n+1;

36、if n=num then begin for j:=i to i+4 do result:=result+lj; break; end; end; end;end;function getnum(l:string;c:char):integer; /找出給定線路的站點數(shù)var i,n:integer;begin n:=0; for i:=1 to length(l) do begin if li=c then n:=n+1; end; result:=n;end; procedure loaddata(var data:tstrings); var filepath:string; begi

37、n filepath:=extractfilepath(application.exename)+data.txt; data.clear ; data.loadfromfile(filepath) ; end;procedure getline(s1: string;s2:string;c:char;var lines:tstrings;data:tstrings);var line,tem :string;var i:integer;begin lines.clear ; for i:=0 to data.count -2 do begin if (i mod 4)=2 then /如果是

38、上行線 begin line:=datai; tem:=; tem:=getname(line,getindex(line,s1,c)+1,c); if tem=s2 then lines.add(datai-2); end else if(i mod 4)=3 then /如果其他 begin line:=datai; if line= then line:=datai-1; if line1=c then line:=reverseroute(line,c); tem:=; tem:=getname(line,getindex(line,s1,c)+1,c); if tem=s2 then

39、 lines.add(datai-3); end; end;end;procedure getroute_unch(s1,s2:string;data:tstrings;var time:integer;var linename,route:string); /尋找不經轉站的最優(yōu)路徑var i,j:integer;var lindex,rindex:integer;var line,tem:string;/找到的路的名稱begin linename:=; time:=max; /找到的最短路徑時間 route:=; /找到的最短路徑 for i:=0 to data.count -2 do b

40、egin /-初時化line if (i mod 4)=2 then /如果是上行線 line:=datai else if(i mod 4)=3 then /如果其他 begin line:=datai; if line= then line:=datai-1; if line1=s then line:=reverseroute(line,s); end; /-初時化line lindex:=getindex(line,s1,s); rindex:=getindex(line,s2,s); if (lindex-1) and (rindex-1)and(rindexlindex) then

41、 if 3*(rindex-lindex)time then begin time:=3*(rindex-lindex); if (i mod 4)=2 then linename:=datai-2 else if(i mod 4)=3 then linename:=datai-3; route:=getname(line,lindex,s); j:=0; for j:=lindex+1 to rindex do begin tem:=; tem:=getname(line,j,s); route:=route+-+tem; end ; end; end;end;procedure getro

42、ute_ch1(s1,s2:string;data:tstrings;var time:integer;var linename1,linename2,chsite,route:string);var linename_t,route_t,line:string; j,index,i,time_t:integer; tem:string;begin time:=max; linename1:= ; linename2:=; chsite:=; route:=; for i:=0 to data.count -2 do begin if (i mod 4)=2 then /如果是上行線 line

43、:=datai else if(i mod 4)=3 then /如果其他 begin line:=datai; if line= then line:=datai-1; if line1=s then line:=reverseroute(line,s); end else continue; index:=getindex(line,s1,s); if index1 then continue; for j:=index+1 to getnum(line,s) do begin tem:=; tem:=getname( line,j,s); getroute_unch(tem,s2,dat

44、a,time_t,linename_t,route_t); if (time_tmax)and(time_t+(j-index)*3+5)time) then begin time:= time_t+(j-index)*3+5 ; linename2:=linename_t; if (i mod 4)=2 then linename1:=datai-2 else linename1:=datai-3; route:=getdirectroute(line,index,j)+route_t; chsite:=tem; end; end; end;end;function reverseroute

45、(l:string;c:char):string;/翻轉路線var i,n:integer;var tem:string;beginresult:=;n:=getnum(l,c);result:=getname(l,n,c);for i:=1 to n-1 dobegintem:=;tem :=getname(l,n-i,c);result:=result+tem;end;end;procedure search(s1:string;s2:string;var results:tstrings);/查找兩個站點之間的最佳路徑var i:integer;var name:string;var t

46、imes: array1.sn of real;var sites :array1.sn of string;var routes: array1.sn of string;var tem:tstrings;var data:tstrings;begin data:=tstringlist.create ; tem:=tstringlist.create; loaddata(data); for i:=1 to sn do begin getline(s1,formname(i),s,tem,data); if tem.count =0 then timesi:=max else begin

47、timesi:=3; sitesi:=s1+-+formname(i); routesi:= formpack(tem); end; end; tem.free ; data.free;end;procedure getroute_ch2(s1,s2:string;data:tstrings;var time:integer;var linename1,linename2,linename3,chsite1,chsite2,route:string);var linename1_t,linename2_t,route_t,chsite_t:string; time_t:integer; lin

48、e:string; j,index,i:integer; tem:string;begin time:=max; linename1:= ; linename2:=; linename2:=; chsite1:=; chsite2:=; route:=; for i:=0 to data.count -2 do begin if (i mod 4)=2 then /如果是上行線 line:=datai else if(i mod 4)=3 then /如果其他 begin line:=datai; if line= then line:=datai-1; if line1=s then lin

49、e:=reverseroute(line,s); end else continue; index:=getindex(line,s1,s); if index1 then continue; for j:=index+1 to getnum(line,s) do begin tem:=; tem:=getname( line,j,s); getroute_ch1(tem,s2,data,time_t,linename1_t,linename2_t,chsite_t,route_t); if (time_tmax)and(time_t+(j-index)*3+5)time) then begi

50、n time:= time_t+(j-index)*3+5 ; linename2:=linename1_t; linename3:=linename2_t; if (i mod 4)=2 then linename1:=datai-2 else linename1:=datai-3; route:=getdirectroute(line,index,j)+route_t; chsite1:=tem; chsite2:=chsite_t; end; end; end;end;end.本題本質是一個關于不同權的最短路問題，我們建立公交查詢數(shù)學模型的理論依據(jù)是參考了floyd算法和dijkstra

51、算法的思想，并做了改進，建立了一個新型的公交路線查詢數(shù)學模型。 公交線路問題本身存在一定的復雜性，因此將公交網(wǎng)絡的空間結構以圖論的方法精確表達。具體步驟如下： 先利用mathematica軟件將數(shù)據(jù)整合成需要的形式。 根據(jù)處理問題的需要，將給定的數(shù)據(jù)按如下方式進行處理： 1、線路編號不變； 2、線路同一票價用整數(shù)1標識，分段記價用整數(shù)0標識； 3、上行線與下行線站點完全相同用整數(shù)1標識，上行線與下行線站點不完全相同用整數(shù)2標識，環(huán)形線路用整數(shù)3標識。 然后用mathematica軟件對數(shù)據(jù)進行處理，具體實例(前20條線路)見附錄i. 1、建立便于程序使用的矩陣，其中行表示所有的公交線路，其中上行線和下行線完全重合的算為上下兩條，環(huán)形線路從中間斷開，分上行和下行共計算為四條，列表示各條線路依次途徑的站點，行列交點表示站點的編號。 2、再建立一個新的分別以所