【正文】 )=min[T（ Vi） ]當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為 P 標(biāo)號(hào)。 步驟：（ 1）給 Vs 以 P標(biāo)號(hào)， P（ s） =0,其余各點(diǎn)均給 T 標(biāo)號(hào)， T（ Vi） =+inf。 下面給出 dijkstra 算法的基本步驟，采用標(biāo)號(hào)法?？紤]到上面的三個(gè)因素和實(shí) 際情況，圖 1 中能夠被選作為起訖點(diǎn)的地點(diǎn)有： （ 1）凱里學(xué)院編號(hào) A16 （ 2）凱里南站編號(hào) A20 （ 3）桃花村與銅鼓村的十字路口編號(hào) A09 （ 4）規(guī)劃路與 320 國(guó)道的十字路口編號(hào) A01 （ 5）紅巖村與 320 國(guó)道十字路口編號(hào) A05 凱里學(xué)院畢業(yè)論文 5 公交起訖點(diǎn)的配對(duì) 結(jié)合實(shí)際情況、將來(lái)的發(fā)展趨勢(shì)和前面確定的起訖點(diǎn)，設(shè)置以下幾條公交線： 1路：下司 ? 凱里南站方向 2路：桃花村 ? 凱里南站方向 3路：環(huán) 城南路 ? 凱里南站方向 4路：凱里學(xué)院 ? 凱里南站方向 5路：紅巖村 ? 環(huán)城南路方向 6路：凱里南站環(huán)線 具體公交線路徑的確定 參照公交線網(wǎng)絡(luò)優(yōu)化目標(biāo)、凱里市經(jīng)濟(jì)開(kāi)發(fā)區(qū)的實(shí)際情況，本文重點(diǎn)以公交路徑的最短原則來(lái)確定公交線路徑（公交環(huán)線除外）。特殊的地點(diǎn)，如車站、碼頭、風(fēng)景區(qū)、居民區(qū)、學(xué)校等應(yīng)該選作為起訖點(diǎn)。 凱里學(xué)院畢業(yè)論文 4 經(jīng)上面處理，附件 4可以用圖 1表示（主要研究其主城區(qū)的交通，所以有些道路未畫(huà)出）。 資料 數(shù)據(jù) 分析 對(duì)附件 4 分析，整理得到統(tǒng)計(jì)資料附見(jiàn) 1。本文主要以凱里經(jīng)濟(jì)開(kāi)發(fā)區(qū)的道路規(guī)劃圖為基礎(chǔ)，進(jìn)一步給出其主城區(qū)的公交網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)，假設(shè)研究中的每條公路都滿足公交車運(yùn)行的相關(guān)要求，規(guī)劃圖中正在建設(shè)的道路和規(guī)劃道路全看成已有的道路。解決最短路問(wèn)題主要的算法有： Dijkstra 算法，逐次逼近算法和 Floyd 算法。 影響公交線路規(guī)劃的因素 （ 1）城市客運(yùn)交通需求 公路沿線的人口分布情況，直接影響到客運(yùn)量的大小。 （ 3）公交調(diào)度優(yōu)化。 （ 2）引導(dǎo)城市經(jīng)濟(jì)，規(guī)劃向著健康、高速、可持續(xù)的方向發(fā)展。北京交通大學(xué)高自友教授等人提出的連續(xù)平衡網(wǎng)絡(luò)設(shè)計(jì)的雙層規(guī)劃模型和求解方法 【 3】 。 公共交通網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)在城市公交發(fā)展規(guī)劃過(guò)程中是最為重要的規(guī)劃步驟。本文主要就公交系統(tǒng)的一個(gè)問(wèn)題 ——公交線路網(wǎng)進(jìn)行研究。 Dijkstra algorithm。本文主要對(duì)凱里經(jīng)濟(jì)開(kāi)發(fā)區(qū)主要城區(qū)的公交線網(wǎng)的優(yōu)化設(shè)計(jì)進(jìn)行研究。公共交通具有運(yùn)載量大、運(yùn)輸效率高、能源消耗低、相對(duì)污染少、運(yùn)輸成本低等優(yōu)點(diǎn)，在城市交通干線上最為明顯，所以在城市規(guī)劃中公共交通的規(guī)劃非常重要。公交線路網(wǎng)絡(luò)的優(yōu)化是城市公共交通設(shè)計(jì)的一個(gè)重要工作。本文用圖論的最短路知識(shí)對(duì)收集的資料進(jìn) 行處理，然后結(jié)合實(shí)際情況對(duì)實(shí)驗(yàn)所得的成果修改完善，最后給出公交線網(wǎng)優(yōu)化設(shè)計(jì)方案。 Matlab； 凱里學(xué)院畢業(yè)論文 1 提出問(wèn)題 隨著長(zhǎng)昆鐵路干線的即將通車，凱里市經(jīng)濟(jì)開(kāi)發(fā)區(qū)的城市化進(jìn)程將不斷的加快。研究結(jié)果能為相關(guān)部門(mén)的工作帶來(lái)一些科學(xué)參考，為凱里經(jīng)濟(jì)開(kāi)發(fā)區(qū)的公交系統(tǒng)的優(yōu)化設(shè)計(jì)提供理論依 據(jù)。對(duì)于任何一個(gè)城市的公共交通系統(tǒng)，公 交網(wǎng)絡(luò)布局是決定系統(tǒng)質(zhì)量的主要因素。林柏梁等人在對(duì)公交網(wǎng)絡(luò)設(shè)計(jì)的指派問(wèn)題模型分析基礎(chǔ)上，以所有乘客流的出行時(shí)間和實(shí)現(xiàn)公交網(wǎng)絡(luò)的資金投入為費(fèi)用目標(biāo)函數(shù)，綜合考慮 了起訖點(diǎn)站場(chǎng)的容量限制，同一條道路上的重復(fù)線路的數(shù)量限制等因素，建立了公交網(wǎng)絡(luò)設(shè)計(jì)非線性 01規(guī)劃模型 【 4】 。 （ 3）乘客與公交公司之間出現(xiàn)雙贏的畫(huà)面。 公交線路優(yōu)化目標(biāo) （ 1）最大的直達(dá)乘客人數(shù) 直達(dá)客人數(shù)指不需要中途換乘就可以到達(dá)目的地的乘客人數(shù)，直達(dá)乘客人數(shù)是一個(gè)非常重要的 指標(biāo)，它可以表示一個(gè)公交線路的主要方便程度，是較常用的優(yōu)化目標(biāo) （ 2）最小出行時(shí)間 該時(shí)間包括候車時(shí)間和乘車時(shí)間，候車時(shí)間與公交發(fā)車頻率有關(guān)，而乘車時(shí)間則與公交線路有關(guān)。 （ 2）道路條件 對(duì)于常規(guī)公交線路網(wǎng)來(lái)說(shuō)，道路網(wǎng)是公交線路網(wǎng)的基礎(chǔ)，設(shè)計(jì)公交線路網(wǎng)時(shí)首先要考慮到道路的幾何線性、路面條件和容量限制等因素。 Dijkstra 算法是由 Dijkstra于 1959 年提出，可用于求解指定兩點(diǎn)間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路，目前被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好辦法。研究結(jié)果能為凱里經(jīng)濟(jì)開(kāi)發(fā)區(qū)的城市規(guī)劃及相關(guān)課題的研究提供理論依據(jù)。 資料處理 將附件 4 中的圖結(jié)合附件 1 作以下處理： （ 1）用線段表示公路。 公交線路網(wǎng)絡(luò)研究設(shè)計(jì) 公交起訖點(diǎn)的選擇 對(duì)于公交起訖點(diǎn)的選擇，我們通常會(huì)考慮三個(gè)因素： (1)公交客流量。 （ 3)人口分布發(fā)展走向。對(duì)于求最短路徑本文主要采用 Dijkstra 算法求解?？捎脙煞N標(biāo)號(hào)： T 標(biāo)號(hào)和 P標(biāo)號(hào)， T標(biāo)號(hào)為了試探性的標(biāo)號(hào)， P 標(biāo)號(hào)為了永久性標(biāo)號(hào)，給 Vi 點(diǎn)到一個(gè) T標(biāo)號(hào)時(shí)，是從 Vs到 Vi點(diǎn)的最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒(méi)有得到 P 標(biāo)號(hào)的點(diǎn)都 沒(méi)有 T 標(biāo)號(hào)。 （ 2）若 Vi 點(diǎn)剛得到 P標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn) Vj：（ Vi， Vj）屬于 E，且 Vj為 T 標(biāo)號(hào)。如全部點(diǎn)均為 P 標(biāo)號(hào)則停止。 . Dijkstra 程序 MATLAB 的實(shí)現(xiàn) （ 1）根據(jù)附件 圖 1，對(duì)附件 1的數(shù)據(jù)進(jìn)行處理得到節(jié)點(diǎn)鄰接矩陣見(jiàn)附表 3。 ) 1路：（ 下司 ? 凱里南站方向） tolcost = 11 path = 1 2 3 4 5 6 14 19 25 即：該公交線經(jīng)過(guò)以下路段 A1A2,A2A3,A3A4,A4A5， A5A6， A6A14， A14A19， A19A25，后面的 path 均這樣理解。結(jié)合圖 2對(duì) 6 路公交線作如下設(shè)計(jì)： Path= 25 16 15 14 13 12 4 3 2 1 9 10 11 21 22 23 24 19 25 這樣設(shè)計(jì)能為旅游者提供便宜的觀光交通工具，同時(shí)也能為沿線居民的出行提供方便。該研究還很淺顯，公交系統(tǒng)是一個(gè)復(fù)雜的系統(tǒng)，其中包含很多子系統(tǒng)，以后我們可以進(jìn)一步完善其每個(gè)子系統(tǒng)。公交網(wǎng)路布局規(guī)劃優(yōu)化設(shè)計(jì)是一個(gè)系統(tǒng)過(guò)程，它包括公交線網(wǎng)優(yōu)化、公交換乘優(yōu)化、車輛配置優(yōu)化、車輛調(diào)度優(yōu)化和人員調(diào)度優(yōu)化。有了相關(guān)數(shù)據(jù)后我們還可以對(duì)本文未完成的優(yōu)化內(nèi)容進(jìn)一步研究，使該公交系統(tǒng)能更好地服務(wù)于凱里經(jīng)濟(jì)開(kāi)發(fā)區(qū)。 [4] 林伯梁、楊富社、