乘公交,看亞運摘要本文解決的是最正確乘車路線問題,分析乘車路線選擇的主要影響因素建立了相應(yīng)的求解模型,確定不同情況下的最正確乘車路線.并分析各線路的交通情況,給出了緩解交通困難的方案.對于問題一:根據(jù)題目所給出的公交線路信息數(shù)據(jù),利用逐步搜索法求出任意兩公汽站點間的直達(dá)線路,在最少換乘次數(shù)的根底上以時間為主要目標(biāo)并考慮乘車費用建立多目標(biāo)優(yōu)化模型.通過編程找出三對站點的最正確方案,均需要換乘1次,總花費均為3元,詳細(xì)結(jié)果見下表:華穗路→交通大廈越秀橋→山村江南大道北→策邊村換乘方案由408路轉(zhuǎn)到1047路由184路轉(zhuǎn)到893路由235路轉(zhuǎn)到192路換乘站點江南大道口芳村隧道口動物園花費時間116分鐘38分鐘140分鐘對于問題二:以分別到達(dá)所有亞運場館的總換乘次數(shù)最多和所需時間最長為困難地區(qū)的評判標(biāo)準(zhǔn),建立新的多目標(biāo)優(yōu)化模型,利用MATLAB軟件編程求解得到結(jié)果. 對于問題三:在模型二的根底上,建立以總時間最少作為目標(biāo)的單目標(biāo)模型.將專線的路線設(shè)置分為兩種處理方法:一,對可在公交或地鐵線路中得到路線的四條線路用模型三求解;二,對不可在公交或地鐵線路中得到路線的直接搜索相關(guān)資料得到兩站的最短路程再換算成時間.最后統(tǒng)一給定根據(jù)行駛時間的收費標(biāo)準(zhǔn)得到專線具體設(shè)置情況. 對于問題四:以過站點的線路最少為交通困難目標(biāo)建立相應(yīng)的整數(shù)規(guī)劃模型,并用MATLAB軟件求解得到交通困難區(qū),在增加公交、地鐵或?qū)＞€時重點考慮求得的交通困難區(qū).本文分析考慮不同問題的需求建立了四個相應(yīng)的模型,但由于時間原因,局部模型沒有求得結(jié)果.關(guān)鍵詞:逐步搜索法多目標(biāo)規(guī)劃整數(shù)規(guī)劃

1.問題重述1.1問題背景:2010年11月12日第16屆亞運會在廣州舉行,為了讓全體市民更好觀看亞運會,廣州市政府決定在亞運期間放假3天、以及全體市民可在亞運及亞殘運會期間免費坐公交、地鐵30個工作日等惠民政策,這一政策的施行在很大程度上加劇了廣州市交通出行的困難.為了方便游客看亞運會,請你用數(shù)學(xué)建模的方法1.2題目所給信息交通困難以某條線路上的最困難作為指標(biāo);根本參數(shù)設(shè)定見附錄一;公交線路及相關(guān)信息見附錄二.1.3本文需解決的問題有:問題一:在亞運會開幕前,僅考慮公汽線路,給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法.并根據(jù)附錄數(shù)據(jù),利用你們的模型與算法,求出以下3對起始站→終到站之間的最正確路線〔要有清晰的評價說明〕.(1)、華穗路→交通大廈(2)、越秀橋→山村(3)、江南大道北→策邊村問題二:在亞運會期間考慮公交和地鐵的情況下,哪些地區(qū)的交通困難,并說明原因.問題三:在亞運會開幕前現(xiàn)擬建專線,請合理設(shè)置專線的路線,運行時間,以及收費標(biāo)準(zhǔn).問題四:如何增加公交,地鐵或者專線,緩解交通困難.2.模型的假設(shè)與符號說明2.1模型的假設(shè)假設(shè)1:各路徑上的公交車發(fā)車平度相同;假設(shè)2:相鄰站點的平均行駛時間一定;假設(shè)3:不出現(xiàn)交通阻塞,公交運行順暢;假設(shè)4:不出現(xiàn)車輛故障及交通事故;假設(shè)5:公交準(zhǔn)點到達(dá),不考慮紅綠燈等待時間;假設(shè)6:除環(huán)形線路外其他線路均是單向行駛.2.2符號說明符號符號說明公汽網(wǎng)的有向賦權(quán)圖站點號直達(dá)線路數(shù)矩陣引入的中間矩陣最少換乘數(shù)矩陣第個站點到第個站點的直達(dá)線路數(shù)第個站點到第個站點的最少換乘次數(shù),弧是否在該路徑上總站點數(shù)兩站點的直達(dá)線路數(shù),站點的最短乘車時間站點的總乘車費用表示站點的過站數(shù)人為設(shè)定參數(shù),乘客可接受的最多換乘次數(shù)公汽地鐵網(wǎng)的有向賦權(quán)圖亞運六個主場館的站點集合始發(fā)的等待時間總的乘車時間總的等待時間總的步行時間換乘時步行的時間站點在線路上3.問題分析為了設(shè)計一個公交線路查詢系統(tǒng)去滿足查詢者的各種需求,我們分析題目要求,先對題目給出的公交線路各站點名按一定的順序進(jìn)行標(biāo)號,以便后面的求解表達(dá).再分析主要的影響因素——換乘次數(shù)、行駛時間、乘車費用等,建立相應(yīng)的求解模型,確定不同情況的最正確乘車路線.并分析各線路的交通情況,給出緩解交通困難的方案.對問題的具體分析如下.針對問題一:只考慮公交車線路的情況下,要給出任意兩公汽站點之間線路選擇.首先,我們根據(jù)題目所給出的公交線路信息,利用逐步搜索法求出任意兩公汽站點間的直達(dá)線路,并用矩陣表示出直達(dá)線路的條數(shù),這是為后面的目標(biāo)及約束的考慮做準(zhǔn)備.再考慮換乘次數(shù),在最少換乘次數(shù)的根底上先后考慮行駛時間及乘車費用,并以它們建立相應(yīng)的目標(biāo)函數(shù).通過編程找出供選的多種參考方案.并以時間為主要目標(biāo)建立任意兩站點的行駛時間最短的最優(yōu)化模型.針對問題二:在亞運會期間,考慮公交和地鐵的情況下,將地鐵站點與其對應(yīng)的公交站點視為一個站點處理.另外,由于亞運期間乘公交地鐵免費,故此問少了問題一中的最少乘車費用的目標(biāo).但由于要考察地區(qū)的交通困難情況,所以在問題一的根底上要增加新的目標(biāo)函數(shù).交通困難是以某條線路上的最困難作為指標(biāo),通過查詢我們知道廣州亞運的主場館在六個站點〔奧林匹克體育中心、體育中心、大學(xué)城體育中心、廣州體育館、黃埔體育館、增城體育館〕附近,所以我們定義站點的交通困難為分別到達(dá)所有亞運場館的總換乘次數(shù)最多和所需時間最長.而增加了地鐵后,換乘的情況也相應(yīng)變化,特別是換乘時間,這對總時間和換乘次數(shù)的目標(biāo)函數(shù)都有影響,約束條件根本不變,這樣建立新的優(yōu)化模型,再用matlab編程求解.針對問題三:要設(shè)置合理的專線線路,我們在問題二的根底上,考慮專線設(shè)置的總路程最短即耗時最少作為線路設(shè)置指標(biāo),可直接將問題二的模型改成總時間最少的單目標(biāo),并對相應(yīng)約束條件進(jìn)行調(diào)整得到優(yōu)化模型三.但考慮到有四條擬建專線的站點不能在公交或地鐵線路中得到路線,所以我們將專線的路線設(shè)置分為兩種處理方法:對可在公交或地鐵線路中得到路線的四條線路用模型三求解;對不可在公交或地鐵線路中得到路線的直接搜索相關(guān)資料得到兩站的最短路程再換算成時間.最后統(tǒng)一給定根據(jù)行駛時間的收費標(biāo)準(zhǔn).針對問題四:要增加公交、地鐵或者專線,緩解交通困難,我們以過站點的線路最少的作為交通困難區(qū),建立相應(yīng)的整數(shù)規(guī)劃模型,并用MATLAB軟件求解得到交通困難區(qū),在增加公交、地鐵或?qū)＞€時重點考慮求得的交通困難區(qū),這樣可緩解交通壓力.4.數(shù)據(jù)分析 把題目所給數(shù)據(jù)信息分類整理:整理一:將題目所給附錄二中的同條線路上的兩個相同站點名改后一個為“站名+2”,如第五條線路的“江夏〔安華燈飾城〕”就在此條線路中出現(xiàn)了兩次,我們將第二次出現(xiàn)的改名為“江夏〔安華燈飾城〕2整理二:根據(jù)題目的站點數(shù)歸類原那么,將題中附錄二中的線路按:0—2擬建專線;3—47公交線;47—55地鐵線進(jìn)行歸類.最后得到:公交線路1052條,其中環(huán)線39條;地鐵線路9條;擬建專線8條.將上述結(jié)果制成下列圖,即:圖4-1:附錄一的線路分類結(jié)果從圖中可以看出:廣州市以公交線路為主,其中包括局部+環(huán)線公交,地鐵和專線數(shù)都很少,這主要與城市的交通及需要有關(guān). 整理三:將題中附錄二的線路按附錄一中的票價標(biāo)準(zhǔn)進(jìn)行票價分類,即:站點數(shù)小于6的線路為2.5元票價;站點數(shù)小于10的線路為2.0元票價;站點數(shù)大于等于10的線路為1.5元票價;地鐵票價為3元.統(tǒng)計結(jié)果見下表〔源程序參見附錄三〕:表4-1:票價統(tǒng)計結(jié)果表票價〔元〕3.02.52.01.5線路數(shù)〔條〕920261044從上表我們看出:大局部線路的票價為1.5元.接著,我們將每條線路的站點數(shù)目進(jìn)行統(tǒng)方案分得到下面的站點數(shù)分布圖,即:圖4-2:線路的站點數(shù)分布圖 從上圖我們可以看出:大局部線路的站點數(shù)在15—30之間,站點數(shù)大于30的線路數(shù)比站點數(shù)小于15的線路數(shù)多.可見,廣州市的站點線路設(shè)置還是比擬合理的,根本符合線路覆蓋面廣和地鐵數(shù)量合理的原那么.5．問題一的解答針對問題一,我們建立了以時間為主要目標(biāo)的任意兩站點的行駛時間最短的最優(yōu)化模型一.5.1模型的準(zhǔn)備準(zhǔn)備一:引用圖論相關(guān)知識,將題目所提供的公汽網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖,中每個頂點代表不同的站點,如果到有直達(dá)路線,那么這兩點之間就用有向邊相連,記做,相應(yīng)用表示該有向邊的權(quán),這樣公汽網(wǎng)絡(luò)就抽象為了一個有向賦權(quán)圖.準(zhǔn)備二:問題分析中我們提出為了方便乘客乘車,考慮到換乘既存在時間消耗又有增加乘車費用,所以我們在最少換乘次數(shù)的根底上考慮公眾對其他因素的需求.所以,我們首先確定最少換乘次數(shù).第一步,構(gòu)造直達(dá)線路數(shù)矩陣:通過求得任意兩點的直達(dá)線路并構(gòu)造兩兩間直達(dá)路線數(shù)目的直達(dá)路線數(shù)矩陣.其矩陣元素表示第個站點到第個站點的直達(dá)線路數(shù),其中,當(dāng)時,,即:以所有公汽所經(jīng)過的站點總數(shù)為,那么直達(dá)線路數(shù)矩陣可表示為:第二步,建立換乘線路數(shù)矩陣:根據(jù)矩陣運算法那么,的元素可表示為:假設(shè)上式中等號右邊僅,其余為0,說明僅第一個站點可直到達(dá)第三個站點,第三個站點可直到達(dá)第二個站點,那么,即第一個站點可通過一次換乘到達(dá)第二個站點,換乘站點為3.通過上面的例子我們發(fā)現(xiàn),可以用表示第個站點到第個站點通過1次換乘的路線數(shù).依次類推,用表示方陣的次冪,為站點的直達(dá)路線數(shù),那么:其中,元素為通過次換乘從站點的線路數(shù).如:表示從站點4到站點3有1條兩次換乘路線,其換乘站點可通過運算參數(shù)記錄得到.第三步,建立最少換乘次數(shù)矩陣:先引入矩陣,其矩陣元素為使得的的最小值,,即:那么表示從站點必要的最少換乘次數(shù),以矩陣表示最少換乘次數(shù)矩陣,元素表示從站點必要的最少換乘次數(shù),那么:5.2模型一的建立5.2在問題分析中我們已經(jīng)提出,要滿足乘客的不同需求,主要分三個因素考慮:換乘次數(shù)、行駛時間、乘車費用.并且,我們在最少換乘次數(shù)的根底上考慮公眾對其他因素的需求.這樣目標(biāo)函數(shù)就有三個,即:換乘次數(shù)最少在模型準(zhǔn)備中我們建立了公汽網(wǎng)的有向賦權(quán)圖,在此,我們引入0-1決策變量表示弧是否在起點與終點的路上,即:假設(shè)與之間無直接相連的弧,但可以通過中間節(jié)點跳轉(zhuǎn),說明站點與之間不可直達(dá),但可通過轉(zhuǎn)乘到達(dá),那么兩點的轉(zhuǎn)乘次數(shù)為經(jīng)過的總弧數(shù)減一,即:行駛時間最短以第個站點到第個站點的時間為元素建立時間權(quán)值矩陣:那么乘車總時間就為:由公汽換公汽的時間固定為5分鐘,那么換乘時間為:包含起始站等待時間3分鐘的行駛總時間最短為:所需花費最少依題意,的直達(dá)費用滿足:得到行程費用最少為:5.2約束一,換乘次數(shù)的約束 之前的分析中已經(jīng)提到,應(yīng)盡量減少換乘次數(shù),但不同的乘客可能承受的換乘次數(shù)不同,所以我們用〔且為整數(shù)〕表示乘客所能接受的最大換乘次數(shù),得到換乘次數(shù)的約束為: 參數(shù)為人為設(shè)定值,分以下三種情況:當(dāng)時,嚴(yán)格約束不能換乘;當(dāng)時,無換乘次數(shù)約束,可無限換乘;當(dāng)為不為0的常數(shù)時,約束換乘次數(shù)在次以內(nèi)的情況.假設(shè)單從模型的通用性考慮,可取到正無窮;假設(shè)從實際情況出發(fā),查詢系統(tǒng)中應(yīng)由查詢者自行設(shè)定,當(dāng)最小換乘次數(shù)小于時輸出無解.約束二,最短路始末點的約束 因為有向圖中,頂點分為了:起點、中間點、終點,對于起點只有出的邊而無入的邊,對于中間點既有入的也有出的邊,對于終點只有入的沒有出的邊. 那么,用進(jìn)入第個頂點的邊和出第個頂點的邊表示兩頂點的最短路徑中三類點的約束為:綜上所述,得到問題一的最優(yōu)化模型:5.3模型一的求解按照以上模型,利用以換乘次數(shù)最少為根本目標(biāo)的逐步搜尋法,把問題一中的三對起始站→終到站輸入算法程序〔參見附錄四〕中,即得到基于最少換乘次數(shù)的選擇方式的乘車路線.由于可行方案較多,為了得到最優(yōu)可行方案,根據(jù)以下原那么進(jìn)行篩選:原那么一,乘車費用和乘車耗時都大的先剔除;原那么二,三個目標(biāo)都相同的方案任選其一,其他剔除.按上訴原那么進(jìn)行篩選后,給出最正確選擇方案如下:表5-2:模型一的求解結(jié)果華穗路→交通大廈越秀橋→山村江南大道北→策邊村換乘次數(shù)111換乘方案由408路轉(zhuǎn)到1047路由184路轉(zhuǎn)到893路由235路轉(zhuǎn)到192路換乘站點江南大道口芳村隧道口動物園花費時間116分鐘38分鐘140分鐘乘車費用3元3元3元5.4結(jié)果分析:通過上面的結(jié)果我們看出,題目所求的三對站點都無法直接到達(dá),需要至少換乘一次才能到達(dá),但考慮到多數(shù)人可能不會接受屢次換乘,故在此以換乘次數(shù)最少為第一目標(biāo),得到三對站點的一次換乘結(jié)果.此結(jié)果中的一次換乘方案中華穗路→交通大廈需要的總時間為116分鐘,江南大道北→策邊村需要的總時間為140分鐘,這兩個時間都很長,所以在乘客希望更省時間的情況下,考慮兩次的換乘可能更符合乘客要求.另外,在乘車費用的角度來講,一次換乘是既可到達(dá)目的地又最省錢的,都只需3元.6．問題二的解答針對問題二我們在問題一模型的根底上建立了新的多目標(biāo)優(yōu)化模型,即模型二.6.1模型的準(zhǔn)備用模型一準(zhǔn)備中相同的方法將公汽、地鐵混合網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖,圖中的含義同模型一.再用模型一準(zhǔn)備中相同的方法確定最少換乘次數(shù),得到含義與模型一相同的表達(dá)式,即:6.2模型二的建立6.問題二是在亞運期間考慮地鐵的情況下求交通困難的地區(qū),考慮到亞運期間乘車免費,所以去掉費用的目標(biāo),以總的行駛時間最長和分別到達(dá)所有亞運場館的總換乘次數(shù)最多為目標(biāo)函數(shù),即:分別到達(dá)所有亞運場館的總換乘次數(shù)最多在此模型的準(zhǔn)備中我們同樣建立了公汽網(wǎng)的有向賦權(quán)圖,在此,我們同樣引入0-1決策變量表示弧是否在起點與終點的路上,即:同樣得到兩站點的最少換乘次數(shù):不同的是,我們需要給定六個亞運場館〔奧林匹克體育中心、體育中心、大學(xué)城體育中心、廣州體育館、黃埔體育館、增城體育館〕作為終點站,以分別到達(dá)所有亞運場館的總換乘次數(shù)最多為目標(biāo)函數(shù),即:總的行駛時間最長先求到達(dá)每個亞運場管的最短時間.在問題一的目標(biāo)二根底上,由于增加了地鐵,所以,換乘的時間上就有所改變,且給定了終點站.首先,在考慮地鐵后,第個站點到第個站點的時間為元素建立時間權(quán)值矩陣:得到總的乘車時間為:始發(fā)的等待時間滿足:得到總的等待時間為:根據(jù)題目所給的兩兩間的換乘所步行的時間知道,步行時間與換乘的交通工具是否相同有關(guān),即:從上面知道,根底步行時間為2分鐘,再加上不同交通工具間換乘多步行的2分鐘.得到總的步行時間為:綜上所述,得到總的乘車時間最長的目標(biāo)函數(shù)為:5.2問題分析中已經(jīng)知道,本問的約束條件根本不變,即:綜上所述,得到問題二的最優(yōu)化模型:6.3模型二的求解6.4結(jié)果分析:7．問題三的解答針對問題三我們建立了新的收益最大的規(guī)劃模型,即模型三.7.1模型三的建立確定目標(biāo)函數(shù)在問題二的根底上,考慮專線設(shè)置的總路程最短即耗時最少作為線路設(shè)置指標(biāo),可直接將問題二的模型改成總時間最少的單目標(biāo),即:確定約束條件 因為限定了四條可求的擬建專線,那么它們的起點站終點站都以確定,它們的編號分別為,那么:綜上所述,得到問題三的單目標(biāo)優(yōu)化模型:7.2模型三的求解7.3結(jié)果分析:8．問題四的解答針對問題四我們建立了一個經(jīng)過此站點的線路數(shù)最少的整數(shù)規(guī)劃模型,即模型四.8.1模型四的建立 引進(jìn)0-1變量,且以經(jīng)過站點的線路數(shù)最少為目標(biāo)函數(shù),即:綜上所述,得到問題四的模型:8.2模型四的求解根據(jù)建立的整數(shù)規(guī)劃模型,編寫相應(yīng)的MATLAB程序〔源程序參見附錄五〕,求得交通困難的站點〔具體結(jié)果見附錄五〕.8.3結(jié)果分析:

9.模型的評價9.1模型優(yōu)點:優(yōu)點一:問題一中我們綜合考慮了轉(zhuǎn)車次數(shù)、乘車費用、乘車時間建立了多目標(biāo)的快速公交模型,能提供多種可行方案同時給出推薦比擬好的乘車方案,可以更好滿足人們乘車需要.優(yōu)點二:在問題一的根底上將地鐵線路參加到乘車網(wǎng)絡(luò)當(dāng)中在模型一的情況下很容易就能查找相關(guān)乘車方案,再去討論后面的問題,模型簡單且容易求解.優(yōu)點三:在對題目復(fù)雜數(shù)據(jù)的處理方面,我們先將個站點進(jìn)行編號,同時巧妙處理環(huán)路和非環(huán)路的兩種情況,有利于模型的建立和求解.優(yōu)點四:在考慮亞運會開幕前和亞運會期間的問題時以亞運場館為基準(zhǔn)點向周圍搜索,方向比擬明確,使模型更為簡單.9.2模型缺點缺點一:建立的模型在綜合考慮各方面的因素時,查詢算法不夠高高效,程序運行時間比擬長.缺點二:在考慮交通困難等方面的問題時,沒有結(jié)合各站點人流量等實際情況綜合各方面因素考慮交通的困難程度.10.模型的改良及推廣10.1模型改良改良一:定義新的直達(dá)矩陣,建立一種基于矩陣運算的高效公交查詢算法.改良二:交通困難并不僅僅是有些地區(qū)線路上無法到達(dá)目的地還應(yīng)包括局部地區(qū)經(jīng)過的車次比擬多造成交通比擬擁擠的情況,我們應(yīng)該建立綜合考慮二者的數(shù)學(xué)模型.改良三:通過實地調(diào)研廣州市各站點人流量的情況,對模型進(jìn)行改良.10.2模型推廣 本文所建立的公交查詢模型能很快的查得廣州市各地區(qū)的乘車方案,能很好的滿足廣闊廣州市民的生活需求,同時建立了評判交通困難的模型,以及給出了減小交通困難的具體解決方法.這也可以應(yīng)用于其它城市公交線路的查詢和公交線路的優(yōu)化以及對城市的交通作出合理的指導(dǎo).參考文獻(xiàn)[1]宋來忠,王志明,《數(shù)學(xué)建模與實驗》,北京:科學(xué)出版社,2005.[2]運籌學(xué)教材編寫組編,《運籌學(xué)(3版)》,北京:清華大學(xué)出版社,2005.6[3]張志涌,楊祖纓,《matlab教程R2011a》,北京:航空航天大學(xué)出版社,2011.7

附錄附錄一:題目所給附錄一說明〔略〕附錄二:題目所給附錄二線路〔略〕附錄三:數(shù)據(jù)分析整理三的MATLAB源程序clcclearloadpath[a,data]=xlsread('data.xls');b=path;station=unique(data);station(1)=[];[n1,n2]=size(b);C=zeros(1108,1);fori=1:1108C(i)=sum((b(i,:)~=0));enddisp('票價2.5')ind=find(C<6&C>2)C(ind)n1=length(ind)disp('票價2.0')ind1=find(C<10&C>=6)C(ind1)n2=length(ind1)disp('票價1.5')ind2=find(C<48&C>=10)C(ind2)n3=length(ind2)disp('票價3')ind3=find(C>=48)C(ind3)n4=length(ind3)n=max(C);D=zeros(n-1,1);fori=2:nD(i-1,1)=length(find(C==i));endx=[2:n];plot(x,D','-*b')gridon,axisequalaxis([2,55,0,61])xlabel('線路站點數(shù)目'),ylabel('線路條數(shù)')運行結(jié)果:'上下九步行街''東鄉(xiāng)村口''東環(huán)路(東怡新村)''東風(fēng)中學(xué)''東風(fēng)小學(xué)''中醫(yī)院東''中醫(yī)院東門''中央酒店''樂捷圖廣場''五''仁濟(jì)西路''傍東村''傍江東坊''光屬纖維廠''勒竹新村''勒竹村''北斗星''北村路''區(qū)星海青少年宮(城北公園)總站''華南工商學(xué)院''華工大牌坊''南華東路''南華廣場新世紀(jì)東''南浦中路''南浦大橋北''南浦大橋南''名雅公司''塘埗西''多寶路(市二醫(yī)院)''大學(xué)城中部樞紐〔共54站〕''大新路''大石橋底''大龍橋''天成路''姬棠商業(yè)街''富華市場〔下行〕