何其祎

（1.武漢工程大學(xué)，湖北 武漢 430205）

近年來，城區(qū)“打車難”問題一直難以解決，打車軟件的出現(xiàn)在一定程度上緩解了這一矛盾。但是部分打車軟件的司機(jī)端在選擇乘客時(shí)，并未真正依據(jù)的士與乘客的實(shí)際最短距離給出最佳的乘客推薦，或給司機(jī)的線路選擇余地很小。本文將運(yùn)用最短路徑算法中的Dijkstra算法對(duì)打車軟件司機(jī)端的選客程序進(jìn)行探討。文中提出的方法，可以針對(duì)的士與乘客的兩點(diǎn)間最短路徑給出最為合理的選客方案。

1 最短路徑

在一個(gè)無權(quán)的圖中，若從其中一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)存在一條路徑，則該路徑所經(jīng)過的邊的數(shù)目為該路徑長(zhǎng)度。在大多數(shù)情況下，兩頂點(diǎn)間有多條路徑，每條路徑經(jīng)過的點(diǎn)不同，路徑長(zhǎng)度也不同，我們稱路徑長(zhǎng)度最短的那條叫做最短路徑。

對(duì)于帶權(quán)的圖，考慮路徑各邊的權(quán)值，將一條路徑上所經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長(zhǎng)度，并將帶權(quán)路徑最短的那條稱為最短路徑，其權(quán)值之和稱為最短路徑長(zhǎng)度或最短距離。

2 Dijkstra算法基本思想

設(shè)G=（V，E）是一個(gè)帶權(quán)有向圖，將所有頂點(diǎn)V分為兩組，第一組為已求出最短路徑的頂點(diǎn)集合，用S表示，初始是S中只有源點(diǎn)，隨后每求出一條最短路徑，V1，V2，…VK都加入到S中，算法結(jié)束。第二組為未確定最短路徑的頂點(diǎn)集合，用U表示，按最短路徑長(zhǎng)度的遞增次序依次將U中頂點(diǎn)放入S中，在向S中添加頂點(diǎn)時(shí)，要保持從源點(diǎn)V到S中各頂點(diǎn)的距離為最短路徑，具體步驟為：①初始時(shí)，S中只包含源點(diǎn)，即S={V}，頂點(diǎn)V到自身的距離為0。U包含除源點(diǎn)以外所有頂點(diǎn)，比較V到U中頂點(diǎn)距離（非鄰接點(diǎn)距離為∞），將距離最小頂點(diǎn)P取出放入S中，選定距離即為V到P的最短路徑長(zhǎng)度；②以頂點(diǎn)P為新的考慮點(diǎn)，修改頂點(diǎn)V到U中各頂點(diǎn)的距離：若從源點(diǎn)V到頂點(diǎn)U的距離（經(jīng)過P）比原來距離（不經(jīng)過P）短，則修改頂點(diǎn)U的距離值，修改后的距離值為頂點(diǎn)V到頂點(diǎn)P加上邊（P,U）上的權(quán)；③重復(fù)上述步驟直到S包含所有頂點(diǎn)。

圖1為Dijkstra算法示例，由點(diǎn)1到點(diǎn)3的步驟為：①由點(diǎn)1出發(fā)，比較點(diǎn)1到其相鄰點(diǎn)點(diǎn)2、點(diǎn)4、點(diǎn)5的距離，可知到點(diǎn)2距離最近，權(quán)值為10；②更新源點(diǎn)為點(diǎn)2，此時(shí)點(diǎn)2的相鄰點(diǎn)為點(diǎn)3，權(quán)值為50；③更新源點(diǎn)為點(diǎn)3，到達(dá)終點(diǎn)，最終權(quán)值為10+50=60。

圖1 Dijkstra算法示例圖

3 應(yīng) 用

3.1 算法分析

要使用Dijkstra算法進(jìn)行最短路徑分析，首先要將整個(gè)道路交通構(gòu)造成賦權(quán)有向圖G。令道路的交叉點(diǎn)與有向圖中的節(jié)點(diǎn)對(duì)應(yīng)，道路與有向圖中的弧對(duì)應(yīng)，弧的方向與行車方向一致（單行線只對(duì)應(yīng)一條弧，雙行線則對(duì)應(yīng)兩條弧）。具體的權(quán)值可以依據(jù)以下原則配賦，用戶可以在下面3種方法中任選一種進(jìn)行操作：①按照道路具體長(zhǎng)度計(jì)算（軟件中對(duì)應(yīng)選項(xiàng)為“路程最短”）；②按照經(jīng)過路口個(gè)數(shù)最少計(jì)算（軟件中對(duì)應(yīng)選項(xiàng)為“紅綠燈最少”）；③按照行駛時(shí)間計(jì)算（軟件中對(duì)應(yīng)選項(xiàng)為“時(shí)間最短”）。

經(jīng)過權(quán)值配賦后，整個(gè)道路交通網(wǎng)就構(gòu)成了一個(gè)符合Dijkstra算法的賦權(quán)有向圖，且不存在負(fù)權(quán)值的情況。本文采用道路實(shí)際長(zhǎng)度作為權(quán)值進(jìn)行優(yōu)化線路的計(jì)算。

假設(shè)路徑網(wǎng)絡(luò)矩陣為T，車輛由路口m到n的距離存在直線行駛距離、環(huán)線行駛距離及轉(zhuǎn)彎距離等不同的情況。①直行長(zhǎng)度即為道路長(zhǎng)度，設(shè)為dij；②弧形道路長(zhǎng)度及轉(zhuǎn)彎長(zhǎng)度可根據(jù)弧長(zhǎng)公式進(jìn)行計(jì)算：l =απr/180°（α為圓心角），令其為Cij；③因?yàn)槁窙r等不確定因素還可能造成別的延長(zhǎng)路徑，需根據(jù)實(shí)際情況來確定，在此將其定為β。綜上所述，路徑權(quán)值可表達(dá)為：L=dij+Cij+β。若道路出現(xiàn)交通管制或封閉，此時(shí)車輛無法通過該路段，則該路徑權(quán)值可表達(dá)為：L=∞。

3.2 技術(shù)應(yīng)用

打車軟件司機(jī)端優(yōu)化技術(shù)中，除了路線優(yōu)化技術(shù)，還需實(shí)現(xiàn)無線數(shù)據(jù)鏈路通信模塊、移動(dòng)終端定位模塊、搜索模塊、搶單模塊等。本文主要針對(duì)如何采用最短路徑技術(shù)，幫助司機(jī)快速確定合理的候選乘客，并抵達(dá)乘客所在地為研究目標(biāo)，給出相應(yīng)的解決方案。

在實(shí)際打車軟件的使用中，存在服務(wù)端與司機(jī)端、乘客端的通信。其中，服務(wù)端與乘客端的通信不在本文討論之列，服務(wù)端與司機(jī)端的通信是為了：①確定的士的實(shí)時(shí)位置；②以的士所在的位置為中心，傳送一定范圍內(nèi)的下單乘客的數(shù)據(jù)，包括乘客位置、與當(dāng)前司機(jī)的距離、是否已被其他司機(jī)搶單等；③交易完成后，進(jìn)行資金結(jié)算。

本文主要是對(duì)上述的第②種情況進(jìn)行優(yōu)化。目前，大多數(shù)打車軟件司機(jī)端應(yīng)用中，服務(wù)端主要是依據(jù)的士與候選乘客之間的平面距離為參照，發(fā)送候選乘客的請(qǐng)求到司機(jī)端。這樣做的好處是服務(wù)端計(jì)算量小，便于快速處理海量的乘客請(qǐng)求。缺點(diǎn)是平面距離不能代表乘客與的士的實(shí)際路面距離，在某些特殊情況下，甚至出現(xiàn)非常大的偏差，從而誤導(dǎo)司機(jī)的選擇。下面以司機(jī)選擇乘客，軟件依據(jù)實(shí)際路面距離給出相應(yīng)選擇及最優(yōu)路線為例，來說明路線優(yōu)化算法的步驟及相關(guān)技術(shù)模塊的使用。

1）利用移動(dòng)終端定位模塊對(duì)車輛進(jìn)行定位

設(shè)在某一時(shí)刻t，車輛的坐標(biāo)為（x，y），記為點(diǎn)A，司機(jī)通過打車軟件的移動(dòng)終端定位模塊將所在坐標(biāo)傳至監(jiān)控中心，附近區(qū)域內(nèi)存在n個(gè)下單乘客，記第k個(gè)乘客為 Sk（k=1，2，…，n），其所在坐標(biāo)為（xk，yk）。

2）利用搜索模塊對(duì)附近乘客進(jìn)行搜索

Step1 令 k=1。

Step2 以點(diǎn)A為中心，R為半徑畫圓，圓內(nèi)區(qū)域即為搜索區(qū)域，記區(qū)域內(nèi)所有要打車乘客的集合為W，則有Sk?W，可根據(jù)實(shí)際情況放大或縮小R，計(jì)算ASk，若ASk≤R，則Sk?W，將這些乘客點(diǎn)反饋到司機(jī)用戶端上。若W={Sk|ASk≤R}=?，則適當(dāng)放大R，直至W={Sk|ASk≤R}≠?，再進(jìn)行下一步。

3）利用判斷訂單狀態(tài)模塊選擇候選乘客

Step1 附近區(qū)域下單乘客集合為W，令第k個(gè)乘客打車狀態(tài)為kp（k=1，2，…，n；p=1或0）。

Step2 判斷kp的取值，若p=1，則該乘客已經(jīng)接受到預(yù)訂，轉(zhuǎn)Step1；若p=0，保存該乘客位置信息Sk?W，判斷k=n，若成立則進(jìn)行下一步。

4）利用路線優(yōu)化技術(shù)規(guī)劃最優(yōu)路線

用Dijkstra方法計(jì)算賦權(quán)有向圖中，從司機(jī)所在點(diǎn)A到其周圍所有Sk的最短路徑，在得到的n個(gè)最短路徑中選擇最短者，其對(duì)應(yīng)的乘客就是司機(jī)應(yīng)選擇的乘客。再按照上述步驟給出最優(yōu)路徑，司機(jī)按照軟件所給出的指示即可到達(dá)。

[1]李春葆,尹為民,李蓉蓉,等.數(shù)據(jù)結(jié)構(gòu)教程 [M].北京:清華大學(xué)出版社,2009

[2](美)維斯.數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述[M].北京:人民郵電出版社,2007

[3]翟振,孫鑫,李志鋒.基于Dijkstra算法的車輛導(dǎo)航系統(tǒng)路線優(yōu)化技術(shù)[J].測(cè)繪科學(xué),2008(增刊):227-228

[4]付立家,巨永鋒.基于Dijkstra算法的停車誘導(dǎo)系統(tǒng)路線優(yōu)化技術(shù)研究[J].中國(guó)公共安全,2006(1):118-119

[5]王維民.我國(guó)城市智能交通系統(tǒng)的發(fā)展[J].黑龍江交通科技,2010(7): 234-235

[6]余冬梅,張秋余,馬少林,等.Dijkstra算法的優(yōu)化[J].計(jì)算機(jī)工程,2004(22): 145-146