最優(yōu)公交線路選擇模型

1、最優(yōu)公交線路選擇模型摘 要本文討論了公眾出行時多條線路選擇的問題，給出了在公交系統(tǒng)中任意兩公交站點之間線路選擇的模型和算法，使得出行時的時間、費用和換乘次數(shù)都盡量的少。在問題1中，我們僅考慮公汽線路，將520條公汽線路信息讀入到兩個矩陣當中，利用矩陣表示站點間的直達經(jīng)過站數(shù)和線路，用matlab編程求解分別得到換乘1次和換乘2次時6對起始站終到站之間的最正確路線。僅在此給出S3359S1828的最正確路線，其余結(jié)果見正文。表1：換乘1次時S3359S1828的最優(yōu)線路方案起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元S3359S1828L436(下)S1784L167(下)1013表2：換乘2次時

2、S3359S1828的最優(yōu)線路方案起點站終點站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時間費用S3359S1828L015(下)S2903L027(環(huán))S1784L167(下)733問題2要求同時考慮公汽與地鐵線路，我們首先將增加的地鐵線路信息添加到問題1建立的兩個矩陣中，利用與問題1相似的編程思路，求解得到換乘1次和換乘2次時6對起始站終到站之間的最正確路線。S3359S1828的最正確路線與問題1的相同，其余結(jié)果見正文 問題3要求同時考慮公汽、地鐵和步行，我們建立了全局替換模型和局部替換模型。最后我們對模型進行了推廣，給出了線路“滿載度的定義，在考慮“滿載度之后，建立了新的模型。關(guān)鍵詞： 多目標

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

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

5、時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元地鐵票價：3元無論地鐵線路間是否換乘注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合。【附錄2】公交線路及相關(guān)信息 見數(shù)據(jù)文件B2007data.rar二、問題假設(shè)1假設(shè)題目給定的公交線路均合理有效；2假設(shè)題目中所給的根本參數(shù)合理有效，不會對最終結(jié)果的準確性造成影響；3假設(shè)不存在因公汽或地鐵滿載，使公交到站后，等車的乘客無法上

6、車的情況；4假設(shè)公交行駛過程中不受地形、天氣、路況和上車人數(shù)的影響，相鄰公交站的平均行駛時間包括停站時間固定不變；5假設(shè)乘客選擇乘車路線時僅考慮三個因素：時間、費用和換乘次數(shù)；6假設(shè)每個乘客從出發(fā)地到達目的地最多乘坐3輛公交車在能夠到達的情況下；7假設(shè)環(huán)行的公汽沒有始發(fā)站和終點站，在客觀情況允許的情況下，會繞著環(huán)行線路一直開下去，即乘客上車后無需下車再乘，就可以從環(huán)行線路的一站到達環(huán)行線路其他任意站；8假設(shè)地鐵直接換乘地鐵時只需購置一次地鐵票，花費3元，當?shù)罔F換乘公汽后再換乘地鐵時需要購置兩次地鐵票，花費6元。三、符號約定：僅考慮公汽線路時，從公汽站i到公汽站jij直達只乘坐一輛公交就可到達行

7、駛所經(jīng)過最少的路段相鄰兩公交站的路程稱為一個路段數(shù)目，當不能直達或i=j時，=0；：僅考慮公汽線路時，從公汽站i到公汽站j直達行駛所經(jīng)過最少的路段數(shù)目的公汽線路，當不能直達或i=j時，=0；A ：公交站點相關(guān)矩陣，其中存放元素；B ：直達公交線路矩陣，是矩陣A的對應矩陣，其中存放元素； ：從起點到終點所利用的公交線路總數(shù)； ：換乘的次數(shù)，s=n-1；：乘客第k次乘坐公交時所乘坐的站數(shù)由假設(shè)6知k可取1，2，3；：乘客第k次乘坐公交時所需要的費用由假設(shè)6知k可取1，2，3；：從起點i到終點j的所需要的時間；：從起點i到終點j的所需要的費用；：相鄰公汽站平均行駛時間包括停站時間；：相鄰地鐵站平均行

8、駛時間包括停站時間；：公汽換乘公汽平均耗時；：地鐵換乘地鐵平均耗時；：地鐵換乘公汽平均耗時；：公汽換乘地鐵平均耗時；：同一地鐵站對應的兩公汽之間通過地鐵站換乘的平均耗時。四、問題分析奧運會明年8月將在北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大局部人將會乘坐公共交通工具簡稱公交，包括公汽、地鐵等出行。這些年來，城市的公交系統(tǒng)有了很大開展，北京市的公交線路已達800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。怎樣才能在眾多的公交線路中找出既省時又省錢的公交線路，是人們所關(guān)心的問題。此文即要求給出線路選擇的模型與算法，從實際情況出發(fā)考慮，滿足乘客的各種不同需求。4.

9、1 問題1的分析僅考慮公汽線路某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。問題1要求在僅考慮公汽線路的情況下，給出任意兩公汽站點之間線路選擇的一般數(shù)學模型與算法。在文本文檔公汽線路信息中一共給出了520條公汽線路，3957個公汽站點。乘客選擇乘車路線時主要考慮三個方面的因素：時間、費用和換乘次數(shù)。三者之間是既有聯(lián)系又有區(qū)別的，一般情況下，換乘次數(shù)比較少時所用的時間也比較少，同時花費的費用也比較少；換乘次數(shù)比較多時所用的時間也比較多，同時花費的費用也比較多。但也不排除換乘次數(shù)

10、多時花費的時間反而比較少的情況?？紤]到人們的心理因素，人們對換乘次數(shù)有一個最大的承受上限，不能無限制的換乘下去，所以我們限定最大換乘次數(shù)為2，即最多利用3條公交線路從起點站到達終點站。即使換乘次數(shù)大于2時存在需要時間和費用更少的路線我們也不再考慮其實我們有理由相信這種事件的概率是非常小的，甚至是不存在的。所以我們先建立模型，搜索出換乘次數(shù)小于或等于2的所有的可行線路，再分別計算出這些線路學要的時間和費用，根據(jù)乘客不同的需求，即不同的目標函數(shù)，選擇最優(yōu)解。從起點i到終點j的所需要的總時間由兩局部構(gòu)成：一是公交的行駛時間；二是乘客換乘時的耗時，包括換乘時的步行時間和等待時間。公交的行駛時間等于相鄰

11、站點間的平均行駛時間乘以公交行駛的站數(shù)，即，屢次換乘時 只要將每次乘坐的行駛時間求和即可，即。乘客換乘時的耗時等于換乘次數(shù)乘以每次換乘所需的時間，即。所以總的耗時可以用下面的表達式來表示：乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和。乘坐公汽時的收費分為兩種情況：一種是單一票價的，無論乘坐多少站均收費1元；另一種是分段計價，分段計價的票價為：020站：1元；2140站：2元；40站以上：3元。將收費方式用數(shù)學表達式表示可寫成以下的形式：其中：表示對上取整，即取不小于的最小整數(shù)。乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和，即：4.2 問題2的分析同時

12、考慮公汽與地鐵線路問題2在問題1的根底上增加了地鐵線路，乘車時間和乘車費用的表達式都將改變。在從起點i到終點j的所需要的總時間由三局部構(gòu)成：一是公交的行駛時間；二是乘客換乘時的耗時，包括換乘時的步行時間和等待時間；三是當起始站和終點站乘車為地鐵時需要先由公汽站進地鐵站或從地鐵站走到公汽站點的步行時間，這個步行時間我們定義為修正時間，而在中途遇到進地鐵的情況那么沒有修正時間，因為步行時間已經(jīng)包含在換乘時間內(nèi)。公交的行駛時間等于相鄰站點間的平均行駛時間乘以公交行駛的站數(shù)，但公交此時分為公汽和地鐵，而且兩者相鄰站點間的平均行駛時間不同：為和。每一次乘坐公交的行駛時間可表示為以下形式：換乘也存在5種情

13、況，5種換乘的時間分別為：、和。每一次的換乘時間表示如下：修正時間可表示如下：總的耗時可以用下面的表達式來表示：乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和。乘坐公汽時的收費分為兩種情況：一種是單一票價的，無論乘坐多少站均收費1元；另一種是分段計價，分段計價的票價為：020站：1元；2140站：2元；40站以上：3元。乘坐地鐵時單一票價：3元無論地鐵線路間是否換乘將兩種收費方式用數(shù)學表達式表示可寫成以下的形式：其中：表示對上取整，即取不小于的最小整數(shù)。乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和，即：4.3 問題3的分析考慮公汽、地鐵和步行問題3要求

14、同時考慮公汽、地鐵和步行三種情況，對這個問題，我們建立兩種不同的模型。模型1的核心思路是將所有站點之間的步行時間信息添加到問題2的矩陣A、B當中，利用問題2中的算法直接求解；模型2的核心思路是直接利用問題2中所求得的結(jié)果，利用步行信息對其結(jié)果進行分析，改進。五、問題一的建模與求解5.1模型的建立 問題1要求在僅考慮公汽線路的情況下，給出任意兩公汽站點之間線路選擇的一般數(shù)學模型與算法。乘客選擇乘車路線時主要考慮三個方面的因素：換乘次數(shù)、時間和費用。三者之間是既有聯(lián)系又有區(qū)別的：一般情況下，換乘次數(shù)比較少時所用的時間也比較少，同時花費的費用也比較少，但也存在換乘次數(shù)多時需要的時間和費用反而比較少，

15、而換乘次數(shù)少時需要的時間和費用反而比較多的情況?？紤]到人們的心理因素，人們對換乘次數(shù)有一個最大的承受上限，不能無限制的換乘下去，所以我們限定最大換乘次數(shù)為2，即從起點站到達終點站最多利用3條公交線路，即使換乘次數(shù)大于2時存在時間和費用更少的路線我們也不再考慮。從起點i到終點j的所需要的總時間由兩局部構(gòu)成：一是公交的行駛時間；二是乘客換乘時的耗時。公交的行駛時間等于相鄰站點間的平均行駛時間乘以公交行駛的站數(shù)，即，屢次換乘時 只要將每次乘坐的行駛時間求和即可，即。乘客換乘時的耗時等于每次換乘所需的時間乘以換乘次數(shù)，即。所以總的耗時可以用下面的表達式來表示：其中為從起點到終點所利用的公交線路總數(shù)；為

16、乘客第k次乘坐公交時所乘坐的站數(shù)由假設(shè)6知k=1，2，3；為相鄰公汽站平均行駛時間包括停站時間；為換乘的次數(shù)，s=n-1；為公汽換乘公汽平均耗時。由題目中的根本參數(shù)知：=3分鐘，=5分鐘，代入數(shù)據(jù)得： 乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和。乘坐公汽時的收費分為兩種情況：一種是單一票價的，無論乘坐多少站均收費1元；另一種是分段計價，分段計價的票價為：020站：1元；2140站：2元；40站以上：3元。將兩種收費方式用數(shù)學表達式表示可寫成以下的形式：其中：表示對上取整，即取不小于的最小整數(shù)，如=26時，=2。乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用

17、的加和，即：選擇最優(yōu)公交線路的目標有三個：一為乘車時間最少，二為需要費用最少，三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型： s.t.其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)由假設(shè)6知k可取1，2，3；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。 通過分析乘坐公汽時的兩種收費分方式，我們可以得到感性的認識，乘車時間和乘車費用是相互關(guān)聯(lián)的，多數(shù)情況下，乘車時間越多，所需要的費用就越多，即兩個目標是統(tǒng)一的。但也不排除在個別情況下，所用時間最少時，所需費用并不是最少的。出現(xiàn)這種情況的主要原因有兩個：一是由于單一票價的收費形式，

18、當乘坐單一票價的公交時，可能已經(jīng)乘坐了很多站，用了很多時間，但費用卻并沒有相應的增加。類似的乘坐分段計價的公交時，如乘坐020站時，費用均為1元，費用也沒有和時間同步增長。5.2模型的求解對該模型我們可以直接全局搜索出時間和價格的最優(yōu)解，但直接搜索算法需要大量的時間，而且得到的單一解不利于我們對問題進行分析，同時這樣做也是沒有必要的。所以我們首先對換乘次數(shù)進行限制，首先搜索是否有路線可以直接從起點到達終點；如果沒有直達線路，再搜索通過1次換乘，利用2條線路是否可以到達，有幾種方案可以到達，分別計算出每種方案所需的時間和費用，從中選取最優(yōu)方案；如果通過1次換乘仍不可以從起點到達終點，那么搜索通過

19、2次換乘，利用3條線路是否可以到達，有幾種方案可以到達，分別計算出每種方案所需的時間和費用，從中選取最優(yōu)方案；我們假設(shè)通過2次換乘仍不可以從起點到達終點的情況是不存在的。因為題目中已說明這些年來，北京的城市公交系統(tǒng)有了很大的開展，已經(jīng)比較完善，對于一個完善的公交系統(tǒng)，我們有理由假設(shè)通過兩次換乘，利用3條公交線路，可以連接任意兩公汽站點。而且數(shù)據(jù)文件所給出的公交線路信息中一共有3957個公汽站點，由520條公汽線路相互連接，由概率論的知識我們也可以假設(shè)通過2次換乘仍不可以從起點到達終點的情況是不存在的。當然以上假設(shè)是我們從感性認識和定性分析中得到的，此假設(shè)不成立的情況也是有可能存在的，但存在的可

20、能性是非常小的，可能對于極個別的某兩個站點不成立，但對于絕大多數(shù)站點是一定成立的，此絕大多數(shù)的概率幾乎為1。還有一個要解決的問題是如果某兩個站點之間通過1次換乘可以到達，我們是否有必要再搜索通過2次換乘的到達方案？通過分析數(shù)據(jù)可以知道換乘2次的方案有可能比換乘1次的方案所需的時間和費用都更少，所以我們有必要在換乘1次已經(jīng)找到可行方案后任然搜索換乘2次的方案，然后在這所有的方案中選擇最優(yōu)解。但同樣的，換乘3次的方案也有可能比換乘1次或2次的方案所需的時間和費用更少，但我們是否也要將換乘3次甚至換乘3次以上的方案統(tǒng)統(tǒng)搜索一遍呢？我們認為沒有必要這么做，原因如下：1、每將換乘次數(shù)增加1，算法的時間復

21、雜度將成倍增長；2、當換乘已經(jīng)到達兩次后，再增加換乘次數(shù)對時間和費用的減少的幫助已經(jīng)不大；3、考慮到乘客的心理因素，人們對換乘次數(shù)有一個最大的承受上限，不能無限制的換乘下去，我們認為乘坐3輛車從一個地方到另一個地方還是可以接受的，但要乘坐4輛車，對一般的乘客而言是難以接受的。綜上我們將搜索起點到終點之間所有的利用1條線路，2條線路和3條線路的到達方案，在其中選取最優(yōu)方案。以下將對求解過程進行具體的說明。首先進行求解的準備工作，求解矩陣A和矩陣B。其中A為公交站點相關(guān)矩陣，其中存放元素，為僅考慮公汽線路時，從公汽站i到公汽站j直達行駛所經(jīng)過最少的路段數(shù)目ij，當不能直達或i=j時，=0；B為直達

22、公交線路矩陣，是矩陣A的對應矩陣，其中存放元素。 為僅考慮公汽線路時，從公汽站i到公汽站j直達行駛所經(jīng)過最少的路段數(shù)目的公汽線路，當不能直達或i=j時，=0。1.整理和完善路公汽線路數(shù)據(jù)。利用C語言編程，將公汽線路信息中的所有下行線是上行線原路返回的線路的下行補全，將環(huán)行路線在其后面原樣粘貼一次，注意粘貼時起點和終點相同，不要重復粘貼，并在其下一行補一行全“0”行。2.讀取數(shù)據(jù)。將已在上步中整理好的數(shù)據(jù)用matlab讀出，并存成矩陣形式，得到初始化矩陣D，該矩陣有5202=1040行520為公汽線路總數(shù)，每一行的行數(shù)除以2的得數(shù)上取整即為該行線路對應公汽線路信息中的線路號。3.轉(zhuǎn)換矩陣，得到矩

23、陣A、B。求解矩陣A、B的步驟如下：step1:將矩陣A初始化為39573957值的矩陣初始時任意兩站之間均沒有聯(lián)系，矩陣B初始化為39573957的零矩陣；step2:對于存有站點信息的矩陣D，如果 ，表示站點在同一公交線路上，線路號為，從。step3:如果,那么，。轉(zhuǎn)step2。step4:對于矩陣A如果，將置零。以下我們給出矩陣A和B的一局部，對兩矩陣的意義進行說明 矩陣A的局部例如 矩陣B的局部例如 矩陣A的第1行第2列為“0”，表示從公汽站點1到公汽站點2沒有直達的線路，所以對應矩陣B的第1行第2列也為“0”；矩陣A中第4行第6列為“47”，表示從公汽站點4到公汽站點6可以直達，且直

24、達時最少乘坐47站，對應的矩陣B中第4行第6列的“223”表示從公汽站點4到公汽站點6最短的直達線路是公汽線路“L223”。觀察矩陣A發(fā)現(xiàn)題目中所給的6對起始站和終點站對應的元素均為“0，表示這6對站點之間均不可以直達，下面我們首先搜索1次換乘，利用兩條線路的路線選擇方案。（一） 換乘1次的情況換乘次數(shù)s已經(jīng)確定為1時，從起點到終點所利用的公交線路總數(shù)=s+1=2，也就確定了，所以我們的模型改寫成以下形式：s.t其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)換乘1次時，k=1，2；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。首先我們利用第一對起始站

25、和終點站S3359S1828對我們算法的整體思想進行說明。判斷矩陣A中元素是否為“0，為“0，那么從起始站S3359到終點站S1828無法直達。然后搜索矩陣A的第3359行，找到第3359行的第一個非“0元素，假設(shè)在第j列，判斷1828列的第j行元素是否同時為非“0元素，假設(shè)非“0，那么記錄下j，和，表示從公汽站點S3359，乘坐公汽線路，經(jīng)過站后，在公汽站點Sj下車，然后換乘公汽線路，經(jīng)過站后，到達公汽站點S1828，用一個簡圖表示即為： ；假設(shè)為“0，那么繼續(xù)搜索矩陣A的第3359行的下一個非“0元素。依次類推，直到將矩陣A的第3359行中的3957個元素全部搜索完畢，那么得到了換乘1次時

26、從起始站S3359到終點站S1828的可行的線路選擇方案，其中一定包含了最優(yōu)的線路選擇方案。然后計算得到的方案的時間和費用，給出最優(yōu)解。下面給出從起始站i到終點站j編程求解的具體步驟：step1: 令k1，判斷是否為“0”，假設(shè)非“0”，記錄，；step2:判斷是否為“0”，假設(shè)非“0”，判斷是否為“0”，假設(shè)非“0”，判斷與是否相等相等時表示可以直達，假設(shè)不等，記錄k，；step3:k=k+1, 判斷k是否大于3957，假設(shè)不大于，轉(zhuǎn)step2;step4:計算所以可行線路方案需要的時間和費用。由上述步驟，利用Matlab編程，可以得到換乘1次的情況下從任意起點到任意站點的可行線路選擇方案，

27、我們?nèi)匀灰缘谝粚ζ鹗颊竞徒K點站S3359S1828為例，利用上述解法可以得到9種可行的方案，如下表所示：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元S3359S1828L436(下)S1784L167(下)1013L436(下)S1241L167(下)1073L436(下)S3695L217(下)1133L436(下)S2606L217(下)1253L469(上)S0304L217(下)1373L469(上)S0727L217(下)1373L469(上)S2364L217(下)1373L469(上)S3192L217(下)1373L469(上)S0519L167(下)1404表1：換乘1次時S3

28、359S1828的可行路線由表1，我們很容易發(fā)現(xiàn)，S3359S1828的可行線路方案中，時間最少的方案恰好也同時為費用最少的方案，就是說模型中的兩個目標：在此情況下是統(tǒng)一的，我們得到換乘1次時S3359S1828的時間和費用同時最優(yōu)的最正確路線如下：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元S3359S1828L436(下)S1784L167(下)1013表2：換乘1次時S3359S1828的最正確路線分別計算問題1中給出的其他5對起始站和終點站，得到的可行路線方案數(shù)目如下：(2)、S1557S0481 ：0 種(3)、S0971S0485 ：11種(4)、S0008S0073 ：62種(5)

29、、S0148S0485 ：0 種(6)、S0087S3676 ：2 種說明：利用的線路1和線路2完全相同，只是中轉(zhuǎn)站不同的方案我們算作2種方案。其中S1557S0481和S0148S0485無法通過1次換乘到達，也就無所謂最優(yōu)線路選擇方案。S0971S0485、S0008S0073和S0087S3676均有多于1種的可行線路選擇方案，而且與S3359S1828具有相同的特點，即可行線路方案中，時間最少的方案恰好也同時為費用最少的方案，就是說模型中的兩個目標：在此情況下是統(tǒng)一的，我們得到換乘1次時6對起始站到終點站之間的時間和費用同時最優(yōu)的最正確路線如下：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用

30、元1S3359S1828L436(下)S1784L167(下)10132S1557S0481無3S0971S0485L013(下)S2184L417(下)12834S0008S0073L159(上)S0291L058(下)8325S0148S0485無6S0087S3676L454(上)S3496L209(下)652表3：換乘1次時6對起始站終點站的最正確路線說明：時間和費用同時到達最優(yōu)的方案可能有多種，我們僅在此給出其中的一局部方案。以上我們給出了換乘一次時6對起始站到終點站之間的最正確線路，發(fā)現(xiàn)有2對無法通過換乘1次到達，其他的可以通過換乘1次到達的，換乘1次的方案也不一定是時間和費用的最

31、優(yōu)方案。所以，有必要給出換乘2次的算法。（二） 換乘2次的情況換乘次數(shù)s為2時，從起點到終點所利用的公交線路總數(shù)=s+1=3，模型改寫成以下形式：s.t其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)換乘2次時，k=1，2，3；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。下面給出從起始站i到終點站j換乘2次時的求解步驟：Step1: 令m=n=1；Step2:判斷是否為“0”，假設(shè)非“0”，判斷是否為“0”，假設(shè)非“0”， 判斷是否為“0”，假設(shè)非“0”，判斷，是否相等，假設(shè)，兩兩不等，記錄m，n ,，;Step3:n=n+1, 判斷n是否大于395

32、7，假設(shè)不大于，轉(zhuǎn)step2;Step4:m=m+1, 判斷m是否大于3957，假設(shè)不大于，轉(zhuǎn)step2;Step5:計算所以可行線路方案需要的時間和費用。由上述步驟，利用Matlab編程，可以得到換乘2次的情況下從任意起點到任意站點的可行線路選擇方案，我們?nèi)匀灰缘谝粚ζ鹗颊竞徒K點站S3359S1828為例，利用上述解法可以得到4016種可行的方案，介于篇幅原因，就不在此列表給出。觀察這4016種可行的方案，發(fā)現(xiàn)與換乘1次時具有相同的特點：時間最少的方案恰好也同時為費用最少的方案，就是說模型中的兩個目標：在此情況下是統(tǒng)一的，我們得到換乘2次時S3359S1828的時間和費用同時最優(yōu)的最正確路線

33、如下：起點站終點站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時間費用S3359S1828L015(下)S2903L027(環(huán))S1784L167(下)733L015(下)S2903L201(上)S0458L041(上)L015(下)S2903L201(上)S1671L041(上)L015(下)S2903L201(上)S1783L041(上)L015(下)S2903L201(上)S1790L041(上)L015(下)S2903L201(上)S1792L041(上)L324(下)S1746L027(環(huán))S1784L167(下)L324(下)S2027L027(環(huán))S1784L167(下)L324(下)S2

34、027L201(上)S0458L041(上)L324(下)S2027L201(上)S1671L041(上)L324(下)S2027L201(上)S1783L041(上)L324(下)S2027L201(上)S1790L041(上)L324(下)S2027L201(上)S1792L041(上)L484(下)S3697L027(環(huán))S1784L167(下)L484(下)S3727L027(環(huán))S1784L167(下)表4：換乘2次時S3359S1828最正確路線換乘2次時，一共有15種方案，使S3359S1828的時間和費用同時為最小，這15種方案的時間、費用和換乘次數(shù)均完全相同，所以這15種方案

35、并沒有優(yōu)劣之分，均是換乘2次時S3359S1828最優(yōu)線路方案。分別計算問題1中給出的其他5對起始站和終點站，得到的可行路線方案數(shù)目如下：(2)、S1557S0481 ：128 種(3)、S0971S0485 ：3738種(4)、S0008S0073 ：14435種(5)、S0148S0485 ：316 種(6)、S0087S3676 ：460 種說明：利用的線路1和線路2完全相同，只是中轉(zhuǎn)站不同的方案我們算作2種方案。所有起始站到終點站均可以通過2次換乘到達，且均有多于1種的可行線路選擇方案，而且與S3359S1828具有相同的特點，即可行線路方案中，時間最少的方案恰好也同時為費用最少的方案

36、，就是說模型中的兩個目標：在此情況下是統(tǒng)一的，我們得到換乘2次時6對起始站到終點站之間的時間和費用同時最優(yōu)的最正確路線如下：起點站終點站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時間費用1S3359S1828L015(下)S2903L027(環(huán))S1784L167(下)7332S1557S0481L084(下)S1919L189(下)S3186L460(下)10633S0971S0485L013(上)S1609L140(下)S2654L469(上)10634S0008S0073L043(下)S1383L296(環(huán))S2184L345(上)6735S0148S0485L308(上)S0036L156(上

37、)S2210L417(下)10636S0087S3676L021(下)S0088L231(環(huán))S0427L097(上)463表5：換乘2次時6對起始站終點站的最正確路線說明：時間和費用同時到達最優(yōu)的方案可能有多種，我們僅在此給出其中的一種方案。5.3所得方案的評價以上我們分別給出了6對站點之間換乘1次和換乘2次的最正確路線，下面將綜合評價這些最正確路線的優(yōu)劣。首先列表比較兩種情況下最正確路線的時間和費用：123456方案時間費用時間費用時間費用時間費用時間費用時間費用換乘1次1013無1283832無652換乘2次733106310636731063463表6：兩種方案最正確路線的時間、費用比

38、照表發(fā)現(xiàn)除第2與第4對站點之間只有換乘兩次的路線之外，其余的4對站點的時間最優(yōu)解均在換乘2次時出現(xiàn)，而費用的最優(yōu)解一般在換乘1次時出現(xiàn)。以第4對站點的最正確路線為例：換乘1次的時間83分鐘大于換乘2次的時間67分鐘，但換乘1次的費用2元小于換乘2次的費用3元，兩者之間誰更優(yōu)呢？而第1對站點，換乘1次的時間101分鐘大于換乘2次的時間73分鐘，換乘1次的費用3元等于換乘2次的費用3元，但就可以說換乘2次的最正確路線比換乘1次的最正確路線更優(yōu)嗎？但換乘1次比換乘2次的換乘次數(shù)少。換乘次數(shù)、時間和費用三個主要影響人們乘車線路選擇的因素對不同乘客不同時間而言地位是不同的。對于對時間比較看中的乘客如白領(lǐng)

39、、年輕人和趕時間的時候而言，時間的權(quán)值就比較高；對于對費用比較看中的乘客如低收入人群而言，費用的權(quán)值就比較高；對于對換乘次數(shù)比較看中的乘客如行動不是很方便的老年人和殘疾人而言，換乘次數(shù)的權(quán)值就比較高。所以只有當一條路線的時間、費用和換乘次數(shù)均比另一條路線少時我們才可認為這條路線更優(yōu)。經(jīng)過以上的分析我們認為每對站點之間的兩組最正確路線各有優(yōu)劣，對于不同目標，它們都有可能是最優(yōu)解。復原到題目的背景信息：某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)，我們建議在系統(tǒng)界面上給出一個查詢條件，乘客可以自行選擇是根據(jù)時間、費用和換乘其中的哪一個為首要目標進行查詢，系統(tǒng)根據(jù)首要目標，選擇輸出

40、最正確路線。六、問題二的建模與求解6.1模型的建立問題2要求在同時考慮公汽與地鐵線路的情況下，給出任意兩公汽站點之間線路選擇的一般數(shù)學模型與算法。問題2與問題1的目標相同，還是時間最少與費用最少，但是時間與費用的計算方式比問題1要復雜很多。從起點i到終點j的所需要的總時間由三局部構(gòu)成：一是公交的行駛時間；二是乘客換乘時的耗時；三是當起始站和終點站乘車為地鐵時需要先由公汽站進地鐵站或從地鐵站走到公汽站點的步行時間，這個步行時間我們定義為修正時間，而在中途遇到進地鐵的情況那么沒有修正時間，因為步行時間已經(jīng)包含在換乘時間內(nèi)。公交的行駛時間等于相鄰站點間的平均行駛時間乘以公交行駛的站數(shù)，但公交分為公汽

41、和地鐵，兩者相鄰站點間的平均行駛時間不同：=3分鐘，=2.5分鐘。每一次乘坐公交的行駛時間可表示為以下形式：換乘也存在5種情況，5種換乘的時間分別為：=5分鐘、=4分鐘、=7分鐘、=6分鐘和平均耗時。=從公汽站點步行到地鐵的時間+從地鐵站點步行到另一公汽站點的時間+等待公汽到來的時間 =4+4+7-4 =11分鐘每一次的換乘時間表示如下：修正時間表示如下：綜上總的耗時可以由下面的表達式來表示：乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和。乘坐公汽時的收費分為兩種情況：一種是單一票價的，無論乘坐多少站均收費1元；另一種是分段計價，分段計價的票價為：020站：1元；2140站

42、：2元；40站以上：3元。乘坐地鐵時單一票價：3元無論地鐵線路間是否換乘將兩種收費方式用數(shù)學表達式表示可寫成以下的形式：其中：表示對上取整，即取不小于的最小整數(shù)。乘客從起點i到終點j的所需要的總費用為乘坐每一輛公交所需費用的加和，即：選擇最優(yōu)公交線路的目標有三個：一為乘車時間最少，二為需要費用最少，三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型：s.t.其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)由假設(shè)6知k=1，2，3；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。6.2模型的求解首先修改矩陣A、B：由于地鐵線路的參加使得各個

43、公汽站點的聯(lián)系發(fā)生變化，所對應的A、B矩陣也隨之發(fā)生變化，因此我們將對A、B矩陣進行修改，使其能夠反響出新的聯(lián)系。具體的修改規(guī)那么如下：1、 同一地鐵站對應多個公汽站的情況。如D01：S0567，S0042，S0025假設(shè)之前兩公交站點i,j無直達車次，那么，均為零。因為現(xiàn)在通過地鐵使公汽站點i,j之間有聯(lián)系，B矩陣修改為1000，表示站點通過地鐵1號線聯(lián)系，A矩陣仍為0，表示站點間并沒有乘車；假設(shè)之前兩公交站點i,j有直達車次，那么，均非零。因為現(xiàn)在通過地鐵使公汽站點i,j之間有新的聯(lián)系，令B矩陣的相應元素假設(shè)通過2號線增加的聯(lián)系那么令，那么B矩陣的元素包含了雙重信息，的最高位為1表示通過地

44、鐵1號線，最高位為2表示通過地鐵2號線，低3位表示的仍為公汽線路號。A矩陣的元素不變。2、 不同地鐵站點對應的不同公汽站點的情況。如D01：S0567，S0042，S0025和D12：S0609，S0608所對應的公汽站之間原A矩陣中的數(shù)據(jù)表示的是兩公汽站點i，j通過公汽到達所需要的最短站數(shù)，現(xiàn)在需要A矩陣的數(shù)據(jù)既可以表示公汽線路站數(shù)又可以表示出地鐵線路的站數(shù)，我們所采取的方法是令地鐵相距站數(shù)×1000公汽站數(shù)，同時令B矩陣中相應元素假設(shè)通過2號線增加的聯(lián)系那么令。經(jīng)過這樣修改之后A、B矩陣就同時包含了公汽和地鐵的信息。其中各元素，的低3位仍然表示公汽線路的關(guān)系，高位表示地鐵線路的關(guān)

45、系。如=8034，=1284，高位8表示站點i，j通過地鐵最少需要8站直達，高位1表示利用的是地鐵1號線。低三位的數(shù)據(jù)034和284表示站點i，j通過公汽最少需要34站直達，利用的公汽線路L284。3、 兩站點之間有多條地鐵線路直達的情況D12和D18為兩條地鐵線路的交點當公汽站是從D12到D18時，兩條地鐵站均能到達，經(jīng)比較發(fā)現(xiàn)T1線經(jīng)過的站數(shù)少于T2線，因此但凡從D12到D18的公汽站均寫入T1站的信息。經(jīng)過以上修改，我們得到既包含公汽線路信息又包含地鐵線路信息的新的矩陣A和矩陣B。觀察矩陣B發(fā)現(xiàn)題目中所給的6對起始站和終點站中S0087S3676對應的元素為非“0元素，那么S0087S3

46、676可以直達，線路表示如下：起點站終點站線路時間價錢S0087S3676T02353表7：S0087S3676的直達路線一換乘1次的情況換乘次數(shù)s已經(jīng)確定為1時，從起點到終點所利用的公交線路總數(shù)=s+1=2，也就確定了，所以我們的模型改寫成以下形式：s.t.其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)換乘1次時，k=1，2；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。下面給出從起始站i到終點站j編程求解的具體步驟：step1: 令k1；step2:判斷是否為“0”，假設(shè)非“0”，判斷是否為“0”，假設(shè)非“0”，判斷和是否相等，假設(shè)不等，記錄k，

47、；step3:判斷當前記錄的，是否大于1000，從而來區(qū)分選擇公汽線路還是地鐵線路，并將大于1000的數(shù)據(jù)復原為公汽線路和地鐵線路信息，重新記錄k，；step4:k=k+1, 判斷k是否大于3957，假設(shè)不大于，轉(zhuǎn)step2;step5:計算所以可行線路方案需要的時間和費用。由上述步驟，利用Matlab編程，可以得到換乘1次的情況下從任意起點到任意站點的可行線路選擇方案，我們?nèi)匀灰缘谝粚ζ鹗颊竞徒K點站S3359S1828為例，利用上述解法可以得到9種可行路線，如下表所示：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元S3359S1828L436(下)S1784L167(下)1013L436(下)S

48、1241L167(下)1073L436(下)S3695L217(下)1133L436(下)S2606L217(下)1253L469(上)S0304L217(下)1373L469(上)S0727L217(下)1373L469(上)S2364L217(下)1373L469(上)S3192L217(下)1373L469(上)S0519L167(下)1404表8：換乘1次時S3359S1828的可行路線我們發(fā)現(xiàn)表8與問題1中的表1是完全相同的，所以最優(yōu)解與問題1也相同。換乘1次時S3359S1828的時間和費用同時最優(yōu)的最正確路線方案如下：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元S3359S1828

49、L436(下)S1784L167(下)1013表9：換乘1次時S3359S1828的最正確路線分別計算問題1中給出的其他5對起始站和終點站，得到的可行路線方案數(shù)目如下：(2)、S1557S0481 ：0 種(3)、S0971S0485 ：11種(4)、S0008S0073 ：62種(5)、S0148S0485 ：0 種(6)、S0087S3676 ：18 種說明：利用的線路1和線路2完全相同，只是中轉(zhuǎn)站不同的方案我們算作2種方案。通過觀察發(fā)現(xiàn)此時求得的2、3、4、5對起點站到終點站之間的可行線路選擇方案與只考慮公汽線路時的方案完全相同，說明在換乘1次時，增加的地鐵線路對這幾對站點沒有影響。第6

50、對起點站到終點站S0087S3676之間的可行線路選擇方案有所增加，而且增加后的方案中時間最少的方案與費用最少的方案是不同的，所以S0087S3676就有時間最優(yōu)和費用最優(yōu)兩種不同的最優(yōu)方案。換乘1次時6對起始站到終點站之間的最優(yōu)目標為時間最少或費用最少的最正確路線如下：起點站終點站線路1中轉(zhuǎn)站線路2時間分費用元最優(yōu)目標1S3359S1828L436(下)S1784L167(下)1013同時2S1557S0481無3S0971S0485L013(下)S2184L417(下)1283同時4S0008S0073L159(上)S0291L058(下)832同時5S0148S0485無6S0087S3

51、676(D36)L021(上)S0630(D29)T2334時間6S0087S3676L454(上)S3496L209(下)652費用表10：換乘1次時6對起始站終點站的最正確路線說明：時間和費用相同的最優(yōu)方案同時存在多種，我們僅在此給出其中的一種方案。增加地鐵線路后，6對數(shù)據(jù)中仍有2對無法通過換乘1次到達；3對的可行方案沒有任何改變；只有第6對S0087S3676增加了可行的線路選擇方案，而且由于地鐵的參加，使最優(yōu)解的時間由原來的65分鐘縮短到了33分鐘，幾乎節(jié)省了一半的時間，但是由于地鐵的票價比較高，所以這種方案的費用也比較高，為4元，是最少費用2元的2倍。以最少費用為目標的最優(yōu)解與問題1

52、相同。兩種最優(yōu)方案具體選取哪一種，乘客可以根據(jù)其自身的需求，自行選取。二換乘2次的情況換乘次數(shù)s為2時，從起點到終點所利用的公交線路總數(shù)=s+1=3，模型改寫成以下形式：s.t.其中為從起點到終點所利用的公交線路總數(shù)；為乘客第k次乘坐公交時所乘坐的站數(shù)換乘2次時，k=1，2，3；為換乘的次數(shù)，s=n-1；為乘客第k次乘坐公交時所需要的費用。下面給出從起始站i到終點站j換乘2次時的求解步驟：step1:令m=n=1；step2:判斷是否為“0”，假設(shè)非“0”，判斷是否為“0”，假設(shè)非“0”， 判斷是否為“0”，假設(shè)非“0”，判斷，是否相等，假設(shè)，兩兩不等，記錄m，n ,，;step3:判斷當前記錄的，是否大于1000，從而來區(qū)分選擇公汽線路還是地鐵線路，并將大于1000的數(shù)據(jù)復原為公汽線路和地鐵線路信息，重新記錄m，n ,，；step4:n=n+1, 判斷n是否大于3957，假設(shè)不大于，轉(zhuǎn)step2;step5:m=m+1, 判斷m是否大于3957，假設(shè)不大于，轉(zhuǎn)step2;step6:計算所以可行線路方案需要的時間和費用。由上述步驟，利用Matlab編程，可以得到換乘2次的情況下從任意起點到任意站點的可行線路選擇方案。我們將問題1中給出的6對起始站和終點站分別代入運行，得到換乘2次時6對起始站到終點站之間最優(yōu)目標為時間