上傳人：r***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：肖**（實(shí)名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2022-01-24 格式：DOC 頁數(shù)：6 大?。?1.50KB 積分：18 舉報 版權(quán)申訴

1、高教杯數(shù)學(xué)建模競賽公交線路的自主查詢系統(tǒng)【數(shù)學(xué)建?！?公交線路的自主查詢系統(tǒng) 摘要 本文首先對數(shù)據(jù)進(jìn)行處理和分析，根據(jù)圖論中加權(quán)有向圖的理論建立了公交站的最小站距矩陣，表示站到站的最小站數(shù)。利用該矩陣進(jìn)行全搜索解決了一個由公共汽車和地鐵組成的公交系統(tǒng)的最佳線路選擇問題。 我們以考不考慮“利用地鐵站公汽換乘公汽”為區(qū)別，將問題（1）分為兩部分。首先不考慮利用地鐵站公汽換乘公汽，我們通過對規(guī)劃目標(biāo)的討論、公汽線路信息的研究、各站之間最小站程的確定和可行線路的搜索以及最佳線路的選擇，逐步建立起用于選擇最佳線路的全搜索模型，用此模型對題中六組數(shù)據(jù)進(jìn)行了求解并進(jìn)行了清晰、詳盡的檢驗(yàn)和評價。接下來利用地鐵

2、站公汽換乘公汽，我們構(gòu)造了一個虛擬公交線路的方法，將同一地鐵站周圍的公交車串聯(lián)起來，通過全搜索解決了該問題，并同樣對六組數(shù)據(jù)進(jìn)行了求解和分析。 問題（2）中，我們再次運(yùn)用改進(jìn)后的全搜索模型，結(jié)合公汽-地鐵網(wǎng)的特點(diǎn)，建立公交站的最小地鐵站距矩陣，方便了模型的求解。對六組數(shù)據(jù)進(jìn)行求解后，結(jié)合上文所有結(jié)果對各種因素進(jìn)行了整體評價。 問題（3）中，我們從實(shí)際出發(fā)，定性分析了步行的作用和對最佳線路選擇的影響，并構(gòu)造了該問題的模型和算法。 我們的模型效率較高，能夠滿足查詢者的各種不同需求，有很強(qiáng)的實(shí)用性。 對六組數(shù)據(jù)在不同條件和要求下的求解結(jié)果見表1至表7，我們認(rèn)為最佳線路的判別標(biāo)準(zhǔn)為：綜合考慮換乘次數(shù)、

3、時間、車費(fèi)，根據(jù)個人的不同需求得出最佳線路。 關(guān)鍵詞：公交線路、最小站距矩陣、虛擬線路 1 問題的重述 第29屆奧運(yùn)會明年8月將在北京舉行，屆時到現(xiàn)場觀看奧運(yùn)比賽的大部分觀眾將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，公交線路繁多，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。 設(shè)計這樣一個系統(tǒng)需要注意： 一線路選擇的模型與算法必須利于程序的實(shí)現(xiàn)； 二應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。 請你們解決如下問題： 1、僅考慮公汽線路，給出任意

4、兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄（公交線路及相關(guān)信息數(shù)據(jù)），利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676 2、同時考慮公汽與地鐵線路，解決以上問題。 3、假設(shè)又知道所有站點(diǎn)之間的步行時間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。 為簡化問題而設(shè)的基本參數(shù)： 相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘 相鄰地鐵站平均行駛時間(包括停站時間)：

5、 2.5分鐘 公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘) 地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘) 地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘) 公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘) 公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元 地鐵票價：3元（無論地鐵線路間是否換乘） 2 符號說明 編號為的公汽站點(diǎn) 編號為的公汽線路 編號為的地鐵站點(diǎn) 編號為的地鐵線路 從起始站到終到站所需的時間（單位：分鐘） 從起始站到終到站所需的費(fèi)用（單位：元） 最小公汽站距矩陣 最小公汽站距對應(yīng)

6、的線路編號矩陣 最小地鐵站距矩陣 最小地鐵站距對應(yīng)的線路編號矩陣 從起始站到終到站的一條可行線路 可行線路相關(guān)信息矩陣 公汽線路信息數(shù)組 公汽站點(diǎn)信息數(shù)組 地鐵站換乘公汽信息矩陣 其余一些不常用的變量在文章中用到時會在后面注明。 3 問題的初步分析 3.1問題的假設(shè) 選擇公交線路是日常生活中經(jīng)常遇到的問題，每個人對此都有一些感性的認(rèn)識，比如寧可繞點(diǎn)圈子也不愿反復(fù)換乘車（因?yàn)榈溶嚨臅r間總比坐車的時間感覺漫長）等等?；诖?，我們的模型聯(lián)系實(shí)際做了一些假設(shè)和近似，這與題目“從實(shí)際情況出發(fā)”的要求也是一致的： （1）公汽線路間的換乘只能是在同一公汽站或是在對應(yīng)的地鐵站； （2）從起點(diǎn)步行至通過地鐵站相

7、連的車站和從某站（通過地鐵站與終點(diǎn)相連）步行至終點(diǎn)所花費(fèi)的時間不計入總乘車時間。 （3）在公汽線路的環(huán)線上乘車經(jīng)過起始站/終到站不另外收費(fèi)，且環(huán)線上有順時針和逆時針兩種走法； （4）多數(shù)人們至多只能接受轉(zhuǎn)兩次車，所以我們假設(shè)不管耗時或花費(fèi)多少，優(yōu)先選擇轉(zhuǎn)兩次以內(nèi)的車能夠到達(dá)的線路（當(dāng)然如果無論如何兩次之內(nèi)到達(dá)不了的話只能轉(zhuǎn)兩次以上）。事實(shí)上，如果換乘次數(shù)不限的話將有無數(shù)條可行線路； 3.2問題的層次 通過分析，得到三個問題之間的層次關(guān)系為： 3.3需求分析 要開發(fā)此公交線路選擇的自主查詢計算機(jī)系統(tǒng)至少需要滿足以下要求： 第一，模型的算法要利于程序的實(shí)現(xiàn)和在現(xiàn)實(shí)中的推廣應(yīng)用。即用戶輸入起始站和終

8、到站兩個參數(shù)后要在盡量短的時間內(nèi)得到最佳的公交線路走法。 第二，要滿足查詢者的各種不同需求。所謂“不同需求”一是乘公交的時間要盡量少，二是車費(fèi)要盡量少，三是轉(zhuǎn)車次數(shù)要盡量少； 因此我們認(rèn)為，算法簡單易行是本文建立模型的最重要標(biāo)準(zhǔn)。 3.4研究方向與算法選擇 一如果將此公交系統(tǒng)看成一個賦權(quán)圖(其權(quán)為各站點(diǎn)之間所用時間或車費(fèi)，其方向?yàn)榫€路類型所決定的行駛方向)，這就是一個求最短路問題，但又不是一般的最短路問題，因?yàn)楦鬟叺臋?quán)有時間和費(fèi)用兩種，而在各站點(diǎn)又有換乘時間等不定因素的影響。即使分別賦兩種權(quán)，運(yùn)用Dijkstra標(biāo)號法求最短路對換乘費(fèi)用的處理仍難以操作，需要加以改進(jìn)。 二由于某段的線路選擇會直

9、接影響下一段線路的選擇以及全局最優(yōu)線路的結(jié)果，這就啟發(fā)我們從全局的角度去建立模型： 首先求出任意兩站之間的最短距離，結(jié)合時間和費(fèi)用的計算方法給所有鄰接線路賦權(quán)；然后按照換乘的次數(shù)（即圖的通路上的邊數(shù)減1）分別求出換乘次數(shù)一定的最佳線路；最后比較所有線路得到全局最佳線路。 事實(shí)上，模型的核心算法是換乘次數(shù)一定時對所有可行線路的搜索，這種搜索通過對各站點(diǎn)的搜索，得到所有可行線路并比較出最佳線路。 三附錄中的數(shù)據(jù)量很大，尤其是公汽線路（線路有520個，站點(diǎn)有3957個），且乘車方式多元、換乘情況復(fù)雜。畫圖并從圖中找規(guī)律的嘗試是行不通的，這就需要將各個站點(diǎn)和各條線路的數(shù)據(jù)矩陣化，通過有序而全面的搜索，

10、用編程的方法實(shí)現(xiàn)，因此，關(guān)鍵是在編程的過程中大膽假設(shè)、分清主次、簡化算法。 4數(shù)據(jù)處理 數(shù)據(jù)的處理是和我們的模型與算法密切相關(guān)的，即有什么樣的模型算法就對應(yīng)著特定形式的數(shù)據(jù)處理。根據(jù)上面對問題的分析，在解決該問題的過程中，我們要找的最佳路線，是通過搜索出所有可能線路對應(yīng)的目標(biāo)值、然后比較目標(biāo)值得到的。而搜索的對象就是跟優(yōu)化目標(biāo)密切相關(guān)的數(shù)字矩陣。 我們可以通過以下的方法進(jìn)行數(shù)據(jù)處理： 把“”、“”和“”三個文本文件導(dǎo)入到 5相關(guān)理論應(yīng)用 構(gòu)造，表示第個站點(diǎn)，為車站的總數(shù)。如果到有直達(dá)線路，則從到畫有向弧，就對應(yīng)于從到的一條有向線路；又定義為所對應(yīng)的站距，這樣就將公交線路網(wǎng)抽象為一個賦權(quán)有向圖。

11、 求從到的一條最佳線路，就轉(zhuǎn)化為中的最短路問題。 6 模型的建立 題目的要求是給出任意兩站點(diǎn)之間的最佳線路。所謂最佳線路不外乎是指某個指標(biāo)（時間或費(fèi)用）最小的線路，對此指標(biāo)的探討和計算就是我們建立模型的目的。通過問題的分析，給出此規(guī)劃模型的一般形式： 其中為某可行線路，而為此線路所需的時間，為此線路所需的費(fèi)用。 和是對次線路的某些限制。 現(xiàn)在，要運(yùn)用全搜索等方法對其進(jìn)行求解。 7 問題（1）公汽站點(diǎn)間的線路選擇 在該問中，題目要求根據(jù)附錄數(shù)據(jù)，僅考慮公汽路線，給出任意兩站之間路線選擇的數(shù)學(xué)模型和算法。而在附錄數(shù)據(jù)中，關(guān)于公汽路線的有兩種數(shù)據(jù)，一種是僅有公汽的數(shù)據(jù)，另一種是關(guān)于公汽和地鐵的數(shù)據(jù)。

12、現(xiàn)在的問題就是用還是不用后一種數(shù)據(jù)，我們不妨這樣處理：把兩種情況都算一下，等結(jié)果出來后，在分析用還是不用。 7.1不考慮地鐵站換乘的全搜索模型 目標(biāo)的討論 由于公眾乘坐公交的原因有二：比步行或騎自行車省時、比坐出租車省錢，那么在選擇公交線路時省時和省錢兩個方面都必須考慮。提出雙目標(biāo)規(guī)劃問題： 其中，和表示可行線路所要滿足的某些條件。 根據(jù)公眾的乘車要求和習(xí)慣不同，我們分以下三種情況討論： 一選擇不同的線路只有幾元錢的花費(fèi)差別，對于不太計較幾元錢得失的乘客來說，節(jié)省時間是最重要的，需要將作為規(guī)劃目標(biāo)； 二有些人乘公交的選擇主要源于出租車的高昂價格，因此乘公交的價格稍高的話就會使其難以接受，對這部

13、分人來說，寧可多花點(diǎn)時間，最小才是重要的； 三由于公眾的心理作用，有些人很在意轉(zhuǎn)車的次數(shù)，即使只是多轉(zhuǎn)一站，因此，必須將換乘次數(shù)也考慮在規(guī)劃目標(biāo)之內(nèi)。 需要指出的是，以上規(guī)劃目標(biāo)的選擇是考慮一般情況的結(jié)果，并非必須如此。當(dāng)然以上三種選擇基本上可以滿足公眾的需求。 線路信息的研究 公汽線路的類型是有差別的： 一按票價信息分為：單一票制和分段計價，反映在信息表每條線路的第二行；兩種線路有不同的收費(fèi)方法。 二按線路的循環(huán)模式分為：單線（分為上下行不一致的型和上下行一致的型兩種）和環(huán)線（設(shè)為型），反映在信息表每條線路的第三、四行；兩種線路有不同的計站方法； 為此，我們把公汽線路信息表做成如下的結(jié)構(gòu)數(shù)組

14、“公汽線路信息數(shù)組”： 一第條公汽線路的信息占用數(shù)組中的第到行，（）； 二對第條公汽線路： （1）第行為線路編號，以字符開頭； （2）第行為票價信息，以字符“單”（代表單一票制）或“分”（代表分段計價）開頭； （3）第、行的內(nèi)容對不同循環(huán)模式的線路有所區(qū)別： 對于型線路，第行表示上行線路，以字符“上”開頭，第行表示下行線路； 對于型線路，第行表示全程線路，以字符“”開頭，第行是空字符； 對于型線路，第行表示全程線路，以字符“環(huán)”開頭，第行是空字符。 截取中的一段以說明其結(jié)構(gòu)： 注：主要用于對線路編號、票價信息和線路循環(huán)模式等公汽線路的整體特征進(jìn)行區(qū)別和標(biāo)識。 此外，為方便對每條公汽線路中具體的站點(diǎn)進(jìn)行提取和計算，還需要建立一個能反映站點(diǎn)情況的“站點(diǎn)信息數(shù)組”，為的矩陣，每一行的內(nèi)容和相同，只不過將其中每一行中的站點(diǎn)字符串轉(zhuǎn)換為以站點(diǎn)的編號為值的數(shù)字，且每個數(shù)字占據(jù)一個元素位置，其余字符串舍去，空格用0補(bǔ)齊。 同樣