【正文】 ，當(dāng)不能直達(dá)或i=j時(shí)，=0；：僅考慮公汽線路時(shí)，從公汽站i到公汽站j直達(dá)行駛所經(jīng)過(guò)最少的路段數(shù)目的公汽線路，當(dāng)不能直達(dá)或i=j時(shí)，=0；A ：公交站點(diǎn)相關(guān)矩陣，其中存放元素；B ：直達(dá)公交線路矩陣，是矩陣A的對(duì)應(yīng)矩陣，其中存放元素； ：從起點(diǎn)到終點(diǎn)所利用的公交線路總數(shù)； ：換乘的次數(shù)，s=n1；：乘客第k次乘坐公交時(shí)所乘坐的站數(shù)（由假設(shè)6知k可取1，2，3）；：乘客第k次乘坐公交時(shí)所需要的費(fèi)用（由假設(shè)6知k可取1，2，3）；：從起點(diǎn)i到終點(diǎn)j的所需要的時(shí)間；：從起點(diǎn)i到終點(diǎn)j的所需要的費(fèi)用；：相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間）；：相鄰地鐵站平均行駛時(shí)間（包括停站時(shí)間）；：公汽換乘公汽平均耗時(shí)；：地鐵換乘地鐵平均耗時(shí)；：地鐵換乘公汽平均耗時(shí)；：公汽換乘地鐵平均耗時(shí)；：同一地鐵站對(duì)應(yīng)的兩公汽之間通過(guò)地鐵站換乘的平均耗時(shí)?！靖戒?】基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)： 3分鐘相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)： 公汽換乘公汽平均耗時(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元（無(wú)論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎn)化問(wèn)題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。請(qǐng)你們解決如下問(wèn)題：僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。關(guān)鍵詞： 多目標(biāo)規(guī)劃 最少時(shí)間 相關(guān)矩陣 滿載度一、問(wèn)題提出我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。S3359→S1828的最佳路線與問(wèn)題1的相同，其余結(jié)果見正文 問(wèn)題3要求同時(shí)考慮公汽、地鐵和步行，我們建立了全局替換模型和局部替換模型。僅在此給出S3359→S1828的最佳路線，其余結(jié)果見正文。最優(yōu)公交線路選擇模型摘 要本文討論了公眾出行時(shí)多條線路選擇的問(wèn)題，給出了在已知公交系統(tǒng)中任意兩公交站點(diǎn)之間線路選擇的模型和算法，使得出行時(shí)的時(shí)間、費(fèi)用和換乘次數(shù)都盡量的少。在問(wèn)題1中，我們僅考慮公汽線路，將520條公汽線路信息讀入到兩個(gè)矩陣當(dāng)中，利用矩陣表示站點(diǎn)間的直達(dá)經(jīng)過(guò)站數(shù)和線路，用matlab編程求解分別得到換乘1次和換乘2次時(shí)6對(duì)起始站→終到站之間的最佳路線。表1：換乘1次時(shí)S3359→S1828的最優(yōu)線路方案起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站線路2時(shí)間（分）費(fèi)用（元）S3359S1828L436(下)S1784L167(下)1013表2：換乘2次時(shí)S3359→S1828的最優(yōu)線路方案起點(diǎn)站終點(diǎn)站線路1中轉(zhuǎn)站1線路2中轉(zhuǎn)站2線路3時(shí)間費(fèi)用S3359S1828L015(下)S2903L027(環(huán))S1784L167(下)733問(wèn)題2要求同時(shí)考慮公汽與地鐵線路，我們首先將增加的地鐵線路信息添加到問(wèn)題1建立的兩個(gè)矩陣中，利用與問(wèn)題1相似的編程思路，求解得到換乘1次和換乘2次時(shí)6對(duì)起始站→終到站之間的最佳路線。最后我們對(duì)模型進(jìn)行了推廣，給出了線路“滿載度”的定義，在考慮“滿載度”之后，建立了新的模型。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站→終到站之間的最佳路線（要有清晰的評(píng)價(jià)說(shuō)明）。假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型?！靖戒?】公交線路及相關(guān)信息 （）二、問(wèn)題假設(shè)1．假設(shè)題目給定的公交線路均合理有效；2．假設(shè)題目中所給的基本參數(shù)合理有效，不會(huì)對(duì)最終結(jié)果的準(zhǔn)確性造成影響；3．假設(shè)不存在因公汽或地鐵滿載，使公交到站后，等車的乘客無(wú)法上車的情況；4．假設(shè)公交行駛過(guò)程中不受地形、天氣、路況和上車人數(shù)的影響，相鄰公交站的平均行駛時(shí)間（包括停站時(shí)間）固定不變；5．假設(shè)乘客選擇乘車路線時(shí)僅考慮三個(gè)因素：時(shí)間、費(fèi)用和換乘次數(shù)；6．假設(shè)每個(gè)乘客從出發(fā)地到達(dá)目的地最多乘坐3輛公交車（在能夠到達(dá)的情況下）；7．假設(shè)環(huán)行的公汽沒(méi)有始發(fā)站和終點(diǎn)站，在客觀情況允許的情況下，會(huì)繞著環(huán)行線路一直開下去，即乘客上車后無(wú)需下車再乘，就可以從環(huán)行線路的一站到達(dá)環(huán)行線路其他任意站；8．假設(shè)地鐵直接換乘地鐵時(shí)只需購(gòu)買一次地鐵票，花費(fèi)3元，當(dāng)?shù)罔F換乘公汽后再換乘地鐵時(shí)需要購(gòu)買兩次地鐵票，花費(fèi)6元。四、問(wèn)題分析奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）出行。怎樣才能在眾多的公交線路中找出既省時(shí)又省錢的公交線路，是人們所關(guān)心的問(wèn)題。 問(wèn)題1的分析（僅考慮公汽線路）某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。問(wèn)題1要求在僅考慮公汽線路的情況下，給出任意兩公汽站點(diǎn)之間線路選擇的一般數(shù)學(xué)模型與算法。乘客選擇乘車路線時(shí)主要考慮三個(gè)方面的因素：時(shí)間、費(fèi)用和換乘次數(shù)。但也不排除換乘次數(shù)多時(shí)花費(fèi)的時(shí)間反而比較少的情況。即使換乘次數(shù)大于2時(shí)存在需要時(shí)間和費(fèi)用更少的路線我們也不再考慮（其實(shí)我們有理由相信這種事件的概率是非常小的，甚至是不存在的）。從起點(diǎn)i到終點(diǎn)j的所需要的總時(shí)間由兩部分構(gòu)成：一是公交的行駛時(shí)間；二是乘客換乘時(shí)的耗時(shí)，包括換乘時(shí)的步行時(shí)間和等待時(shí)間。乘客換乘時(shí)的耗時(shí)等于換乘次數(shù)乘以每次換乘所需的時(shí)間，即。乘坐公汽時(shí)的收費(fèi)分為兩種情況：一種是單一票價(jià)的，無(wú)論乘坐多少站均收費(fèi)1元；另一種是分段計(jì)價(jià)，分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元。乘客從起點(diǎn)i到終點(diǎn)j的所需要的總費(fèi)用為乘坐每一輛公交所需費(fèi)用的加和，即： 問(wèn)題2的分析（同時(shí)考慮公汽與地鐵線路）問(wèn)題2在問(wèn)題1的基礎(chǔ)上增加了地鐵線路，乘車時(shí)間和乘車費(fèi)用的表達(dá)式都將改變。公交的行駛時(shí)間等于相鄰站點(diǎn)間的平均行駛時(shí)間乘以公交行駛的站數(shù)，但公交此時(shí)分為公汽和地鐵，而且兩者相鄰站點(diǎn)間的平均行駛時(shí)間不同：為和。每一次的換乘時(shí)間表示如下：修正時(shí)間可表示如下：總的耗時(shí)可以用下面的表達(dá)式來(lái)表示：乘客從起點(diǎn)i到終點(diǎn)j的所需要的總費(fèi)用為乘坐每一輛公交所需費(fèi)用的加和。乘坐地鐵時(shí)單一票價(jià)：3元（無(wú)論地鐵線路間是否換乘）將兩種收費(fèi)方式用數(shù)學(xué)表達(dá)式表示可寫成以下的形式：其中：表示對(duì)上取整，即取不小于的最小整數(shù)。模型1的核心思路是將所有站點(diǎn)之間的步行時(shí)間信息添加到問(wèn)題2的矩陣A、B當(dāng)中，利用問(wèn)題2中的算法直接求解；模型2的核心思路是直接利用問(wèn)題2中所求得的結(jié)果，利用步行信息對(duì)其結(jié)果進(jìn)行分析，改進(jìn)。乘客選擇乘車路線時(shí)主要考慮三個(gè)方面的因素：換乘次數(shù)、時(shí)間和費(fèi)用?？紤]到人們的心理因素，人們對(duì)換乘次數(shù)有一個(gè)最大的承受上限，不能無(wú)限制的換乘下去，所以我們限定最大換乘次數(shù)為2，即從起點(diǎn)站到達(dá)終點(diǎn)站最多利用3條公交線路，即使換乘次數(shù)大于2時(shí)存在時(shí)間和費(fèi)用更少的路線我們也不再考慮。公交的行駛時(shí)間等于相鄰站點(diǎn)間的平均行駛時(shí)間乘以公交行駛的站數(shù)，即，多次換乘時(shí) 只要將每次乘坐的行駛時(shí)間求和即可，即。所以總的耗時(shí)可以用下面的表達(dá)式來(lái)表示：其中為從起點(diǎn)到終點(diǎn)所利用的公交線路總數(shù)；為乘客第k次乘坐公交時(shí)所乘坐的站數(shù)（由假設(shè)6知k=1，2，3）；為相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間）；為換乘的次數(shù)，s=n1；為公汽換乘公汽平均耗時(shí)。乘坐公汽時(shí)的收費(fèi)分為兩種情況：一種是單一票價(jià)的，無(wú)論乘坐多少站均收費(fèi)1元；另一種是分段計(jì)價(jià)，分段計(jì)價(jià)的票價(jià)為：0～20站：1元；21～40站：2元；40站以上：3元。乘客從起點(diǎn)i到終點(diǎn)j的所需要的總費(fèi)用為乘坐每一輛公交所需費(fèi)用的加和，即：選擇最優(yōu)公交線路的目標(biāo)有三個(gè)：一為乘車時(shí)間最少，二為需要費(fèi)用最少，三為換乘次數(shù)最少，即利用的公交線路數(shù)最少，所以我們可以建立如下模型： .其中為從起點(diǎn)到終點(diǎn)所利用的公交線路總數(shù)；為乘客第k次乘坐公交時(shí)所乘坐的站數(shù)（由假設(shè)6知k可取1，2，3）；為換乘的次數(shù)，s=n1；為乘客第k次乘坐公交時(shí)所需要的費(fèi)用。但也不排除在個(gè)別情況下，所用時(shí)間最少時(shí)，所需費(fèi)用并不是最少的。類似的乘坐分段計(jì)價(jià)的公交時(shí)，如乘坐020站時(shí)，費(fèi)用均為1元，費(fèi)用也沒(méi)有和時(shí)間同步增長(zhǎng)。所以我們首先對(duì)換乘次數(shù)進(jìn)行限制，首先搜索是否有路線可以直接從起點(diǎn)到達(dá)終點(diǎn)；如果沒(méi)有直達(dá)線路，再搜索通過(guò)1次換乘，利用2條線路是否可以到達(dá)，有幾種方案可以到達(dá)，分別計(jì)算出每種方案所需的時(shí)間和費(fèi)用，從中選取最優(yōu)方案；如果通過(guò)1次換乘仍不可以從起點(diǎn)到達(dá)終點(diǎn)，則搜索通過(guò)2次換乘，利用3條線路是否可以到達(dá)，有幾種方案可以到達(dá)，分別計(jì)算出每種方案所需的時(shí)間和費(fèi)用，從中選取最優(yōu)方案；我們假設(shè)通過(guò)2次換乘仍不可以從起點(diǎn)到達(dá)終點(diǎn)的情況是不存在的。而且數(shù)據(jù)文件所給出的公交線路信息中一共有3957個(gè)公汽站點(diǎn)，由520