Dijkstra算法的打車軟件司機端選擇最短距離乘客優(yōu)化問題

何其祎

（1.武漢工程大學，湖北 武漢 430205）

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

1 最短路徑

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

對于帶權的圖，考慮路徑各邊的權值，將一條路徑上所經過邊的權值之和定義為該路徑的帶權路徑長度，并將帶權路徑最短的那條稱為最短路徑，其權值之和稱為最短路徑長度或最短距離。

2 Dijkstra算法基本思想

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

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

圖1 Dijkstra算法示例圖

3 應 用

3.1 算法分析

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

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

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

3.2 技術應用

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

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

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

1）利用移動終端定位模塊對車輛進行定位

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

2）利用搜索模塊對附近乘客進行搜索

Step1 令 k=1。

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

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

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

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

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

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

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

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

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

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

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

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