基于改進(jìn)的DIJKSTRA算法的公交換乘簡(jiǎn)單實(shí)現(xiàn)

摘要：目前市面上提供公交查詢的網(wǎng)站有很多，一些網(wǎng)站只提供簡(jiǎn)單的路線查詢，也有一些網(wǎng)站提供了換乘方案查詢，但均沒(méi)有提供個(gè)性化的換乘方案，也均沒(méi)有考慮臨時(shí)改道情況。本設(shè)計(jì)在這兩個(gè)方向進(jìn)行改進(jìn)，能實(shí)現(xiàn)根據(jù)不同用戶的特點(diǎn)生成不同的最優(yōu)換乘方案，并提供了在換乘方案中考慮臨時(shí)改道情況的選項(xiàng)。

本設(shè)計(jì)的難點(diǎn)在于公交換乘方案的設(shè)計(jì)。這里采用圖論里經(jīng)典的單源最短路徑DIJKSTRA算法來(lái)實(shí)現(xiàn)，并對(duì)這個(gè)算法進(jìn)行了一定的改進(jìn)，使查詢結(jié)果更加人性化。本設(shè)計(jì)的亮點(diǎn)在于本次設(shè)計(jì)還提供了考慮改道情況的轉(zhuǎn)乘智能分析以及換乘方案的四種智能分析可選方向，這是目前市面上類似產(chǎn)品都沒(méi)有提供的。

本系統(tǒng)使用Visual Studio 2005+SQL Server 2005開(kāi)發(fā)。使用asp.net2.0框架。已錄入福州目前大部分的公交線路，經(jīng)測(cè)試能夠提供較人性的公交換乘方案查詢，并且界面清晰簡(jiǎn)潔，操作方便快捷，數(shù)據(jù)管理緊湊易用，對(duì)數(shù)據(jù)處理的速度能夠滿足現(xiàn)實(shí)查詢的速度需要。

關(guān)鍵詞：公交線路查詢；多種換乘方案；智能分析算法；臨時(shí)改道信息

中圖分類號(hào)：TP311.52 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 20-0000-02

1 概述

1.1 本設(shè)計(jì)解決的問(wèn)題

本文設(shè)計(jì)一個(gè)網(wǎng)站系統(tǒng)，實(shí)現(xiàn)福州公交線路的查詢。包括公交站點(diǎn)查詢，公交路線查詢，公交換乘方案查詢，改道信息查詢，后臺(tái)數(shù)據(jù)管理等模塊。能夠提供智能的公交換乘方案是其難點(diǎn)。

1.2 問(wèn)題現(xiàn)狀

公交車換乘方案是大家普遍關(guān)心的一個(gè)問(wèn)題。目前網(wǎng)上已有很多相關(guān)的公交查詢站點(diǎn)，目前公交換乘方案存在的問(wèn)題有：

一般只考慮該站點(diǎn)的情況，沒(méi)有考慮走路到相近站點(diǎn)后的情況。

一般都是以最少換乘優(yōu)先，沒(méi)有考慮通過(guò)增加換乘可能會(huì)更快到達(dá)的因素。

一般都是只考慮正常路線情況，沒(méi)有考慮到公交車臨時(shí)改道后的換乘情況。

換車方案中對(duì)換車點(diǎn)的選擇考慮不足，沒(méi)有考慮到換車點(diǎn)對(duì)路線優(yōu)化及可選擇性的作用。

1.3 問(wèn)題難點(diǎn)

公交換乘問(wèn)題的難點(diǎn)有：

公交車的變動(dòng)太快，有時(shí)甚至是個(gè)別路線的短時(shí)間的調(diào)整。這就要求對(duì)公交數(shù)據(jù)能夠及時(shí)的更新和維護(hù)。

特別是大城市，公交數(shù)據(jù)量是很大的（考慮各種換乘方案），所以要求要有良好的優(yōu)化的算法來(lái)實(shí)現(xiàn)，另一方面對(duì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也有很高的要求。

公交站名的復(fù)雜性，上下行公交站名不一致的情況，同一個(gè)站名出現(xiàn)在多個(gè)站點(diǎn)的情況。

1.4 本次設(shè)計(jì)的解決方案

提供簡(jiǎn)潔易用的操作界面，能夠方便準(zhǔn)確地進(jìn)行站點(diǎn)情況查詢，線路情況查詢，改道信息查詢，公交換乘查詢等。公交換乘算法采用改進(jìn)的圖論里經(jīng)典的單源最短路徑DIJKSTRA算法來(lái)實(shí)現(xiàn)，能夠提供多種查詢選項(xiàng)來(lái)控制公交換乘的算法的執(zhí)行。換乘方案可以按指定日期查詢，換乘算法中考慮當(dāng)天的車輛改道情況。

1.5 特色及實(shí)用價(jià)值

換乘方案的算法中提供了面向普通用戶，面向月票用戶，面向免費(fèi)用戶，面向自駕車用戶等四個(gè)方向來(lái)生成個(gè)性化的最優(yōu)換乘方案。

換乘方案的算法中提供了按指定日期查詢，考慮當(dāng)天的車輛改道情況，能夠生成更為準(zhǔn)確實(shí)用的換乘方案。能夠更好地滿足城市人出行公交查詢的實(shí)際需要。

2 單源最短路徑Dijkstra算法在本次設(shè)計(jì)中的應(yīng)用

2.1 數(shù)據(jù)準(zhǔn)備

數(shù)據(jù)的收集，要從網(wǎng)上收集福州的公交各線路站點(diǎn)集。在數(shù)據(jù)庫(kù)中，對(duì)所有的站點(diǎn)進(jìn)行編號(hào)，每個(gè)名字的站點(diǎn)具有唯一的全局編號(hào)。在公交線路經(jīng)站信息表中，對(duì)于每一條線路，分為上行和下行兩種情況公別對(duì)途經(jīng)的每個(gè)站點(diǎn)進(jìn)行站次編號(hào)。比如5路公交車的上行第一站為火車站。根據(jù)公交線路經(jīng)站信息表，可以通過(guò)查詢語(yǔ)句得到從任意站點(diǎn)到該站點(diǎn)可直達(dá)的最少經(jīng)站數(shù)量。比如從福大北門到東街口有三路車可以直達(dá)，分別是22（上行）經(jīng)過(guò)8站直達(dá)，5（下行）經(jīng)過(guò)7站直達(dá)，55（下行）經(jīng)過(guò)8站直達(dá)。則福大北門到東街口的直達(dá)最少經(jīng)站數(shù)量就是7。這樣就可以建立最短直達(dá)信息表。用到的查詢語(yǔ)句如下：

delete from st1tost2

insert into st1tost2（st1，st2，stlen）

（select s1.StId，s2.StId， min（s2.StNo-s1.StNo） stlen from xljzxx s1，xljzxx s2

where s1.StId<>s2.StId and s1.CarName=s2.CarName and

s1.UpDown=s2.UpDown and s2.StNo-s1.StNo>0

group by s1.StId，s2.StId）

在最優(yōu)公交換乘方案生成中，將直接讀取上述這張表來(lái)構(gòu)建一張有向圖。

如果要考慮到臨時(shí)改道情況，則就不能通過(guò)上述的最短直達(dá)信息表來(lái)構(gòu)建有向圖，而是應(yīng)該使用更復(fù)雜的查詢語(yǔ)句，假設(shè)要查詢的日期是time1，則要把在time1這個(gè)日期有關(guān)的所有改道信息替換原有的路線信息，來(lái)生成站間最短直達(dá)距離數(shù)據(jù)集。使用的查詢語(yǔ)句如下：

select st1，st2，min（stlen） stlen from （ （select s1.StId st1，s2.StId st2，min（s2.StNo-s1.StNo） stlen from xljzxx s1，xljzxx s2 where s1.StId<>s2.StId and s1.carname=s2.carname and s1.UpDown=s2.UpDown and s2.StNo-s1.StNo>0 and s1.StId<>74 and s2.StId<>74 and s1.carname not in

（select carname from gdjbxx where startdate<'\"+time1+\"' and enddate>'\"+time1+\"'）

group by s1.StId，s2.StId） union all （select s1.StId st1，s2.StId st2， min（s2.StNo-s1.StNo） stlen from gdjzxx s1，gdjzxx s2 where s1.StId<>s2.StId and s1.GdId=s2.GdId and s1.UpDown=s2.UpDown and s2.StNo-s1.StNo>0 and s1.StId<>74 and s2.StId<>74 and s1.gdid in

（select gdid from gdjbxx where startdate<'\"+time1+\"' and enddate>'\"+time1+\"'）

group by s1.StId，s2.StId）） a group by st1，st2

2.2 算法描述

通過(guò)上述數(shù)據(jù)準(zhǔn)備，我們已經(jīng)能夠生成一張有向圖，圖里面每?jī)牲c(diǎn)可達(dá)的權(quán)值來(lái)自于上述站間最短可達(dá)數(shù)據(jù)集。如果沒(méi)有出現(xiàn)在上述數(shù)據(jù)集中的兩點(diǎn)，則記為不可達(dá)。

現(xiàn)在接下來(lái)的問(wèn)題，就是在構(gòu)建的這張圖里，查找某不可直達(dá)的兩點(diǎn)間的最短路徑。本次設(shè)計(jì)中使用的是圖論里經(jīng)典的單源最短路徑DIJKSTRA算法的改良，得到最優(yōu)的換乘方案，并把結(jié)果顯示在頁(yè)面中。在經(jīng)典DIJKSTRA算法中，只考慮兩點(diǎn)間的最短路徑，而沒(méi)有考慮每經(jīng)過(guò)一個(gè)結(jié)點(diǎn)產(chǎn)生的損耗（在本設(shè)計(jì)中也就是指每換乘一次需要付出的代價(jià)），所以改良此算法，在計(jì)算的過(guò)程中動(dòng)態(tài)地記錄經(jīng)過(guò)結(jié)點(diǎn)的次數(shù)，也就是換乘次數(shù)。并把這個(gè)次數(shù)乘以一定的權(quán)值加入到考慮更優(yōu)路徑的公式中。以改變生成的最優(yōu)方案的結(jié)果。本次設(shè)計(jì)中對(duì)上述的權(quán)值提供了四種不同的參數(shù)，分別是：

絕對(duì)最少換乘優(yōu)先（推薦）方案給的權(quán)值是100，因?yàn)榫嚯x方案中途經(jīng)一站的權(quán)值是1，所以這個(gè)權(quán)值100意味著換乘的代價(jià)遠(yuǎn)遠(yuǎn)要比距離的代價(jià)更高，所以也就是絕對(duì)最少換乘優(yōu)先方案（即盡量不換乘）。

相對(duì)最少換乘優(yōu)先（月票推薦）方案，給的權(quán)值是4。即如果轉(zhuǎn)車可以使距離縮短四站以上，則轉(zhuǎn)車，否則不轉(zhuǎn)車。

相對(duì)最短距離優(yōu)先方案，給的權(quán)值是2。即如果轉(zhuǎn)車可以使距離縮短兩站以上，就考慮轉(zhuǎn)車方案，否則不轉(zhuǎn)車。

絕對(duì)最短距離優(yōu)先（自駕推薦）方案，給的權(quán)值是0。也就是不考慮換乘帶來(lái)的影響，即使用標(biāo)準(zhǔn)的經(jīng)典DIJKSTRA算法。得出來(lái)的結(jié)果將是絕對(duì)最短距離的，但可能需要轉(zhuǎn)很多次車。轉(zhuǎn)車次數(shù)不在考慮之內(nèi)。

2.3 算法流程圖

頂點(diǎn)S為源。

pass[a，b]表示在構(gòu)建的圖中a點(diǎn)到b點(diǎn)的直達(dá)最短距離。

dist[v]表示當(dāng)前從源S到頂點(diǎn)V的最短特殊路徑長(zhǎng)度。

prev[v]表示從源s到頂點(diǎn)v的最短特殊路徑上頂點(diǎn)v的前驅(qū)結(jié)點(diǎn)。

zhuan[v]表示從源s到頂點(diǎn)v的最短特殊路徑上頂點(diǎn)v的前驅(qū)結(jié)點(diǎn)個(gè)數(shù)。

list[v]，當(dāng)值為1時(shí)表示該結(jié)點(diǎn)可以考慮作為中轉(zhuǎn)結(jié)點(diǎn)。

2.4 算法的程序?qū)崿F(xiàn)

在實(shí)際開(kāi)發(fā)中，在app_code/dataaccess.cs下定義了以下這個(gè)自定義的函數(shù)來(lái)獲得最優(yōu)轉(zhuǎn)車方案。

public string dijk（string stb，string ste，int findtype，int ftype，string time1）；

其中的各個(gè)參數(shù)說(shuō)明：

stb：起點(diǎn)站的名字，ste：終點(diǎn)站的名字。

findtype：這個(gè)參數(shù)用來(lái)傳遞權(quán)值。（關(guān)于權(quán)值的介紹請(qǐng)參見(jiàn)6.2.2算法描述）。

ftype，這個(gè)參數(shù)為為1時(shí)表示正常查詢，為0時(shí)表示考慮臨時(shí)改道情況。

time1：查詢時(shí)間。這個(gè)參數(shù)只有在ftype為0時(shí)才有效。

3 結(jié)語(yǔ)

本設(shè)計(jì)完成了公交查詢系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā)。該系統(tǒng)能夠滿足公交查詢的實(shí)際需要，提供了考慮改道情況的轉(zhuǎn)乘智能分析以及換乘方案的四種智能分析可選方向分析，可以生成較合理及人性化的換乘方案。由于時(shí)間有限，本系統(tǒng)還有很多待改進(jìn)的地方?jīng)]有改進(jìn)。比如還可以考慮到夏季冬季始未班時(shí)間的不同而根據(jù)具體時(shí)間生成不同的換乘方案，可以加入站點(diǎn)擁擠度，換乘靈活度等智能分析方向進(jìn)行進(jìn)一步的換乘優(yōu)化等等。

參考文獻(xiàn)：

[1]王莉，李文權(quán).公共交通系統(tǒng)最佳路徑算法[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2004，2：264-267.

[2]張存保，楊曉光.公交最優(yōu)路徑算法及其應(yīng)用[Z].2005年海峽兩岸智能交通運(yùn)輸系統(tǒng)學(xué)術(shù)研討會(huì)暨第二屆同舟交通論壇：609-614.