2007年b題公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)

1、賽馬不相馬敢為天下先mcm.1客戶部QQ：200975533賽事部QQ：200865533商務(wù)部QQ：20079553320072007年B題公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)本文是2007年高教社杯獲得者。將站點(diǎn)實(shí)體間的線路選擇抽象為圖論最短路模型采用01整數(shù)規(guī)劃表述。建立直達(dá)數(shù)據(jù)庫Q作為數(shù)據(jù)基庫，根據(jù)用戶需求建立不同目標(biāo)的01規(guī)劃模型運(yùn)用鄰接算法與……公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)海軍航空

2、工程學(xué)院（青島）湯志高、王繼利、曹瑩瑛指導(dǎo)教師曹華林【摘要】本文將站點(diǎn)實(shí)體間的線路選擇抽象為圖論最短路模型采用01整數(shù)規(guī)劃表述。建立直達(dá)數(shù)據(jù)庫Q作為數(shù)據(jù)基庫，根據(jù)用戶需求建立不同目標(biāo)的01規(guī)劃模型運(yùn)用鄰接算法與Lingo分別求解，最終方案集通過多目標(biāo)分層序列排序輸出到用戶終端。第一問，在數(shù)據(jù)處理階段將直行、環(huán)行線路分別抽象為2、4條路線(見5.0)。建立查詢系統(tǒng)時考慮服務(wù)器要同時響應(yīng)多個請求，計(jì)算任務(wù)繁重，采用空間換取時間的策略，先建立

3、站點(diǎn)至站點(diǎn)直達(dá)數(shù)據(jù)庫Q來描述兩兩可直達(dá)站點(diǎn)的所有線路，用戶查詢時，系統(tǒng)首先查詢Q，得到所有直達(dá)車方案。在沒有直達(dá)車情況下，針對不同用戶需求，目標(biāo)考慮：轉(zhuǎn)乘次數(shù)、總耗時、總費(fèi)用、轉(zhuǎn)站車輛是否始發(fā)、轉(zhuǎn)乘站點(diǎn)負(fù)載量；在Q的基礎(chǔ)上，量化不同目標(biāo)為有向賦權(quán)圖的不同權(quán)矩陣(見5.2.0)，以所求頂點(diǎn)到頂點(diǎn)的路徑是否包含xij弧為決策變量，上述5項(xiàng)用戶需求為目標(biāo)，始、終點(diǎn)連通為約束建立01整數(shù)線性規(guī)劃模型(見5.2.3模型Ⅰ)。為了能夠?yàn)橛脩籼峁┒喾N

4、備選方案，我們首先使用基于Dijkstra的鄰接算法求解，得到不同目標(biāo)下的多種優(yōu)化方案；對于鄰接算法不易求解的多次轉(zhuǎn)乘最優(yōu)方案，我們采用Lingo軟件直接求得全局最優(yōu)解；兩種方法求解步驟見(5.3.1)，綜合方案集見(5.3.2表1.1~1.6)，其中6條線路時間最短目標(biāo)分別為67、102、106、62、105、49(分鐘)；兩種求解方法的優(yōu)劣在5.4中給出了詳細(xì)評價。第二問考慮公汽與地鐵混排方案，首先把各地鐵站點(diǎn)和周圍的公汽站點(diǎn)集抽象

5、為同一新站點(diǎn)，把已知公汽線路到達(dá)都映射到，計(jì)算新直達(dá)數(shù)據(jù)庫，再結(jié)合地鐵的費(fèi)用與地汽換乘等待時間就可以把地鐵線與公汽線結(jié)合，建立多目標(biāo)01整數(shù)線性規(guī)劃模型(見6.2.3模型Ⅱ)；對于轉(zhuǎn)乘次數(shù)少于等于2次的方案仍可通過鄰接算法求解；對于鄰接算法不易求解的多次轉(zhuǎn)乘最優(yōu)方案，雖然模型規(guī)模較大但約束與目標(biāo)線性程度較好，還可用Lingo軟件求解得出6條線路的全局最優(yōu)解；綜合方案集(見6.3.2表2.1~2.6)，其中6條線路時間最短目標(biāo)分別為65、

6、102、98、56.5、89.5、30(分鐘)；隨后我們在6.4與6.5中給出了模型具體的評價與應(yīng)用。第三問綜合考慮所有站點(diǎn)間步行與乘車情況，將其抽象為最短路問題下的疊加有向賦權(quán)圖，在此基礎(chǔ)上以換乘次數(shù)為主要約束，以總行程時間(包括步賽馬不相馬敢為天下先mcm.3客戶部QQ：200975533賽事部QQ：200865533商務(wù)部QQ：200795533與問題一相同的抽象方法處理。在此基礎(chǔ)上按照相同的思路確定任意兩站點(diǎn)間的最佳方案?？紤]公

7、交及地鐵站點(diǎn)的實(shí)際分布情況，有時會出現(xiàn)步行小段距離再轉(zhuǎn)車的情況更能節(jié)省時間或轉(zhuǎn)車次數(shù)。因此，研究此種情況下的出行方案對節(jié)省出行時間具有重要的實(shí)際意義。3模型假設(shè)[1]假設(shè)車站不重名；[2]假設(shè)各路經(jīng)上公交車發(fā)車頻度相同；[3]假設(shè)相鄰站點(diǎn)間平均行駛時間一定；[4]假設(shè)不出現(xiàn)交通阻塞，公交運(yùn)行順暢；[5]假設(shè)不出現(xiàn)車輛故障及道路交通事故；[6]假設(shè)始發(fā)終點(diǎn)出入地鐵需要步行4分鐘；[7]假設(shè)公交準(zhǔn)點(diǎn)到達(dá)，不考慮紅綠燈等待時間。4符號系統(tǒng)——

8、弧是否在該有向賦權(quán)圖上；——站點(diǎn)→的總乘車時間；——第個站點(diǎn)是否為→的始發(fā)站；——站點(diǎn)→的乘車費(fèi)用。5公汽站點(diǎn)之間線路選擇模型（問題一）本節(jié)主要研究任意兩公汽站點(diǎn)間線路選擇的數(shù)學(xué)模型與算法。分別在不同行程需求下推薦最佳路線，給出更為人性化的站點(diǎn)負(fù)載壓力及轉(zhuǎn)乘點(diǎn)是否為始發(fā)站的提示。通暢、便利目標(biāo)：換乘次數(shù)最少；?不同的行程需求：行程耗時最少；?行程費(fèi)用最少；?人性化查詢設(shè)計(jì)：轉(zhuǎn)乘站點(diǎn)是否為始發(fā)站提示；站點(diǎn)負(fù)載壓力提示?；诖?，本部分共分如