基于洪泛算法的單線校車路徑規(guī)劃問題研究

薛偉蓮，于 希，周 風，李倩影

（遼寧師范大學 管理學院，遼寧 大連 116029）

基于洪泛算法的單線校車路徑規(guī)劃問題研究

薛偉蓮，于 希，周 風，李倩影

（遼寧師范大學 管理學院，遼寧 大連 116029）

針對單線校車路徑規(guī)劃問題，在對相關研究成果進行綜述的基礎上，考慮校車行駛過程中道路長度、道路屬性和交通擁堵情況等影響因素，建立了單線校車路徑規(guī)劃模型，利用加入剪枝規(guī)則和禁忌表的改進洪泛算法進行求解，有效地提高了求解速度。以大連嘉匯陽光小學校車調度為例，對其某條線路進行優(yōu)化，仿真結果表明，該算法可以求得最優(yōu)解，且在求解效率上優(yōu)于傳統(tǒng)的精確算法。

校車路徑規(guī)劃；洪泛算法；剪枝算法

1 引言

進入21世紀以來，我國對中小學義務教育進行了結構性的調整，學校總數(shù)不斷減少，由此帶來學生因上下學的路程增加而導致的安全性降低問題，地方政府紛紛投資引進專業(yè)校車來保障學生就學的安全性。如何對校車路徑進行合理規(guī)劃，降低學生交通時間是校車運營者要考慮的問題。校車路徑的規(guī)劃要考慮資源、交通、資金、時間等很多復雜因素，在現(xiàn)有的研究中，已有很多學者借鑒求解車輛路徑問題（VRP）的算法，但是校車路徑規(guī)劃問題（SBRP）與VRP不同，學生在路上的時間越長就會多一分危險，所以時間因素、安全性是最重要的目標。

校車在國外的發(fā)展較早，線路設計規(guī)劃研究主要集中在車輛容載量、乘車站點、科學算法等單目標或者多目標的規(guī)劃。E.M.Bronshtein等[1]以最小化學生平均乘車時間為目標，使用精確算法和簡單的啟發(fā)式算法解決問題。Corberán等[2]采用分散搜索算法，首先對數(shù)據(jù)進行分區(qū)，構造初始可行解，接著按照相同路徑內或者不同路徑間的站點互相交換的方式更新可行解，最終通過匹配組合形成不同的方案，經(jīng)過比較得出最優(yōu)解。Arias-Rojas等[3]綜合車輛容量和數(shù)量因素，采用ACO優(yōu)化了路徑。Jalel Euchi和Rafaa Mraihi[4]將ACO與變鄰域搜索算法進行結合，建立了混合算法。Kevin M.Curtin等[5]利用禁忌搜索算法，探討針對站點的數(shù)量，用地

理信息系統(tǒng)（GIS）工具解決是否能得出最優(yōu)或者次優(yōu)的問題。Khalid A.ELDRANDALY等[6]結合GIS技術、聚類技術、網(wǎng)絡切割技術、混合蟻群優(yōu)化算法與改進的林和克尼漢啟發(fā)式結合，創(chuàng)造了一種新的GIS決策框架，并在GIS 9.2網(wǎng)絡環(huán)境下優(yōu)化了11條路線問題。

國內學者最初關于SBRP研究的時間起步較晚，成果較少。符卓[7]提出最遠者優(yōu)先啟發(fā)式算法，首先從離學校最遠的站點開始指派，然后就近訪問其余站點，直到滿載，之后再調整實現(xiàn)車輛最少、線路最短。劉丞等[8]建立了車輛路徑優(yōu)化模型，結合局部優(yōu)算方法2-opt方法，運用蟻群算法使運載路線相對均衡。呂騰捷[9]利用坐標拾取系統(tǒng)對學生進行坐標三點分析后劃分出三個區(qū)域，然后按照路程中距離、擁堵情況和高速三個因素匹配權重，利用Prim算法得出較優(yōu)的路徑。陳小潘[10]設計了學校上學時間優(yōu)化和校車調度的兩階段啟發(fā)式求解算法，在模擬退火算法框架下，采用VRP局部搜索算子進行路徑間和路徑內的調整優(yōu)化，實驗結果表明,針對大規(guī)模案例，啟發(fā)式算法的求解質量整體上優(yōu)于精確求解。

雖然智能算法有許多優(yōu)點，但它也存在一些缺陷。智能算法的研究起步較晚，理論研究滯后于應用研究，容易出現(xiàn)停滯現(xiàn)象，當搜索進行到一定程度，所有個體發(fā)現(xiàn)一致解時，容易陷入局部最優(yōu)，不能進一步搜索，從而不能保證獲得的解是最優(yōu)解；對于大規(guī)模的求解問題，智能算法搜索時間較長。智能算法與其他傳統(tǒng)優(yōu)化技術相結合，一定程度上可以提高算法的性能，將會大大促進理論和計算方法在各個領域中的應用。

2 校車路徑問題的模型建立和算法設計

為了準確描述本文的研究問題，本只選取一所學校的一條校車行駛路線，要求校車經(jīng)過所有站點，以最短的時間將學生準時送達學校。

2.1 校車路徑規(guī)劃問題影響因素

在規(guī)劃校車路線時，主要考慮以下五個方面的因素：

（1）道路條件。道路條件是由道路狀況決定的，并能影響汽車行駛速率，這里只考慮道路等級。根據(jù)國家城市道路劃分標準，道路被劃分為4個等級，根據(jù)道路等級可以確定路質系數(shù)hij，見表1。

表1 路質系數(shù)hij的取值范圍表

（2）道路擁堵因素。在城市交通中，影響道路通暢能力的主要因素是擁堵情況。擁堵程度用路況系數(shù)rij表示，見表2。

表2 路況系數(shù)rij的取值范圍表

（3）節(jié)點間的路徑。多數(shù)車輛路徑規(guī)劃問題用兩個站點間的直線距離表示它們之間的距離，而現(xiàn)實中道路自身情況十分復雜，兩個站點間需要經(jīng)過多個節(jié)點、多條路段，選擇走主干路或是次干路，是單行還是雙行等，導致求出的實際時間與直線距離不同。本文中將所有的交叉口設置為節(jié)點，通過將每個路段實際距離dij與權系數(shù)相乘，得到擁堵距離見式（1）。

（4）行駛時間。本文的目標是車輛行駛時間最短,已知平均速度v0，路段通行時間的計算方式為：

（5）紅綠燈節(jié)點延遲時間。轉彎時等待信號燈的時間較長，所以納入考慮范圍。為方便研究，本文將每條路段延遲時間阻礙delay定為10s。陳虓[11]于2012年提出，通常節(jié)點可以概括為丁字節(jié)點和十字節(jié)點，不同的位置轉向在不同方向所受阻礙是不同的，按照國內右手交通規(guī)則，詳細說明這兩種情況。

當同樣等級的路段相交形成交叉口：

tr為右轉向阻礙，ts為直行阻礙，tl為左轉向阻礙，delay為阻礙單位。

當交叉的路段有主次分別時，如圖1所示，主要道路是123方向，而次要路是24方向時，此時轉向阻礙計算如下：

對于丁字節(jié)點（圖1a）：

對于十字節(jié)點（圖1b）：

tijq表示ij轉向iq的阻礙；delayij表示ij路段方向造成的阻礙。

圖1 節(jié)點結構示意圖

2.2 模型設計

為了使問題簡化，對模型做出如下假設：

（1）只考慮路段擁堵情況和道路本身的情況，不考慮不同時間段數(shù)據(jù)的變化，也就是假設hij、rij數(shù)據(jù)是穩(wěn)定的；

（2）每條路徑的路線不重復出現(xiàn)；

（3）假設車輛從較遠的學生乘車站點出發(fā)，開始時刻為0時刻，目標地點是學校。

交通網(wǎng)絡可以簡化成一個帶權的有向圖，要求從源節(jié)點出發(fā)，經(jīng)過所有乘車站點集合C，到達目的節(jié)點des。路網(wǎng)中的目的節(jié)點、乘車站點和交叉點構成圖的節(jié)點的集合，各個節(jié)點間的路徑作為圖的鏈路，鏈路有方向性。路網(wǎng)可描述為G=(V,E)，V是所有節(jié)點的集合點的坐標表示為乘車節(jié)點集合道路交叉口節(jié)點集合校車訪問完所有乘車點后直接返回學校。E是所有節(jié)點間鏈路的集合，對于每個eij，用三個值表示。禁忌表tabuk初始狀態(tài)包括全部乘車點，即tabuk=C，當路徑k經(jīng)過某站點后則將該站點從其禁忌表中移除，具體的參數(shù)見表3。

表3 參數(shù)及說明

目標函數(shù)：

約束條件：

式（6）是目標函數(shù)，求解用時最短的路徑，式（7）表示路徑k必須滿足容量約束，式（8）表示路徑k行駛時間約束Tc，式（9）是路徑k的總長度。

在地圖上標出學生乘車站點和交叉口道路節(jié)點，得出每段路的路長dij、路質系數(shù)hij，參考實時動態(tài)地圖得出路況系數(shù)rij,分別從距離學校最遠的站點中選取起點，記錄每個起點運行所用時間、總路程和路徑，每個乘車站點僅訪問一次，最后比較不同起點的結果，選取最優(yōu)方案。

2.3 算法設計

隨著節(jié)點數(shù)增多，洪泛算法的時間和空間復雜度成指數(shù)增長。本文提出一種改進算法，通過引入剪枝算法和禁忌表來降低洪泛算法的盲目性和冗余性,有效減少候選解的規(guī)模。其核心思想是通過洪泛算法設定起點

和禁忌表后求解路徑，利用剪枝規(guī)則和禁忌表刪去不符合條件的路徑，最先到達目的節(jié)點的有效路徑即為最優(yōu)路徑，洪泛算法的詳細流程如圖2所示。

圖2 算法流程

剪枝規(guī)則：

（1）記錄路徑訪問過的節(jié)點，到達終點后禁忌表為空的路徑為有效路徑，若禁忌表不為空，表示有乘車點沒有經(jīng)過，則剪枝該路徑；

（2）將重復出現(xiàn)相同的節(jié)點的路徑剪枝；

（3）每條路徑行駛時間大于Tc時剪枝；

（4）減少回溯洪泛的方式：

將剛經(jīng)過的節(jié)點記為j，若為乘車點則將此站點從tabuk中刪除，判斷 j的縱坐標是否大于tabuk中所有點的縱坐標，若全部大于，說明j上方?jīng)]有乘車節(jié)點，其余tabuk中的點在下方，此時，洪泛范圍定義為 j的縱坐標向上延伸w（回溯范圍變量）千米范圍內的點；若j的縱坐標不大于tabuk中所有點的縱坐標，則說明還有乘車點在j的上方，此時不加限制。

3 案例分析—以大連嘉匯陽光小學為例

3.1 案例描述

大連嘉匯教育發(fā)展有限公司主要從事基礎教育，是一個全面綜合現(xiàn)代化的教育公司，嘉匯陽光小學是公司管轄的五所中小學校之一，其良好的教育師資吸引了眾多學子。為保障學生上下學安全，學校專門配備了校車，本文選取校車路線中的一條進行優(yōu)化。參考地圖，圖中五角星標明了嘉匯·陽光學?！腋家線路中的8個乘車點，編號和乘車人數(shù)見表4。從站點0到8的總長為3.7km，其余交叉口節(jié)點編號為9到110，如圖3所示。為節(jié)省篇幅，其中圖3(a)是圖的上半部分，圖3(b)是圖的下半部分，五角星代表乘車點。

嘉匯陽光小學根據(jù)經(jīng)驗設定的路線為：1→16→15→24→4→25→29→30→3→81→91→90→89→2→88→82→83→84→85→98→102→9→33→47→31→48→74→5→72→71→42→43→6→44→46→50→49→70→7→69→8→0。實際總長度為：12.31km，全程行駛時間約為44min。

表4 站點編號和上車人數(shù)

3.2 試驗結果及分析

模型假設條件與主要參數(shù)的設定同上，定義學校為目的節(jié)點，des={0}，學生乘車站點共8個，C={1,2,3,4,5,6, 7,8}，交叉節(jié)點為J={9,10，…，110}，定義Tc=45min= 0.75h。

3.2.1 實驗結果。將大連嘉匯陽光小學的交通數(shù)據(jù)導入Matlab中，因站點1、2、3、4距離學校都比較遠，因此分別設定為起點，0為終點，綜合各方面因素，設定w= 1。行駛路徑見表5，路程和時間見表6。

分析試驗結果發(fā)現(xiàn)，以1為起點得到的優(yōu)化后路線和學校人工制定的相同，以4為起點用時最少，而以1和2為起點的路線走的是所有路線中的外圍，即83→84→85→98→102→9→33→47→31→48→74→5，而不是直接 從 83→86→96→99→100→103→105→107→108→109→32→73→48→74→5，分析可得，由于圖3中內側道路的擁堵程度較大，模擬時間偏長，所以走外圍的時間相對短。綜上，最優(yōu)的選擇是以4為起點的路線，比原路線減少了2.4min。

3.2.2 回溯范圍變量w分析。當w取值減小，算法的運

行時間t也會隨之減少，以本文案例中1為起點進行說明。

圖3 參考路線和節(jié)點

表5 仿真結果

表6 路程和時間

表7 w和t的對照表

采用基本的洪泛算法，沒有w限制時，運行時間很長；本文算法中w為0.2時，不能保證得到最優(yōu)解，大于0.5時可以得到最優(yōu)解；用蟻群算法求解時，一共運行20次，平均每次運行時間為178s，但只有5次得出最優(yōu)解，正確率只有25%。因此當設定的w值適當時，能以較少的時間代價得到最優(yōu)解。

4 結語

本文考慮校車行駛過程中道路長度、道路屬性和交通擁堵情況等影響因素，構建了單線校車路徑規(guī)劃模型，并用融入了禁忌表和剪枝算法的改進洪泛算法進行求解，選取大連嘉匯陽光小學的一條校車路線，對模型算法進行驗證，將路程行駛時間縮短了2.4min。雖然相對于元啟發(fā)算法效率偏低，但是通過控制回溯因子，可以較低的代價獲得最優(yōu)解，為路徑規(guī)劃問題的求解提供了一個新思路。

[1]E M Bronshtein,D M Vagapova,A V Nazmutdinova.On constructing a family of student delivery routes in minimal time[J]. Automation and Remote Control,2014,75(7):1 195-1 202.

[2]Corberán A,Fernández E,Laguna M,et al.Heuristic solutions to the problem of routing school buses with multiple objectives[J].Journal of Operational Research Society,2002,53: 427-435.

[3]Arias-Rojas J S,Jiménez,Montoya-Torres J R.Solving of school bus routing problem by ant colony optimization[J].Revista EIA,2012,(17):193-208.

[4]Jalel Euchi,Rafaa Mraihi.The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm[J]. Swarm and Evolutionary Computation,2011,(2):15-24.[5]Kevin M Curtin,Gabriela Voicu,Matthew T Rice,Anthony Stefanidis.A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems[J].Transactions in GIS,2014,18(2):286-301.

[6]K Eldrandaly,A M Abdallah.A novel GIS-based decisionmaking framework for the school bus routing problem[J].Geospatial Information Science,2012,15(1):51-59.

[7]符卓.開放式車輛路徑問題及其應用研究[D].長沙:中南大學,2003.

[8]劉丞,喬金友,金鑫.基于蟻群算法的通勤車路徑問題優(yōu)化研究[J].物流技術,2013,32(3):278-280.

[9]呂騰捷.校車路徑規(guī)劃問題分析[J].新經(jīng)濟,2014,(23):15-16.

[10]陳小潘,孔云峰,牛寧,等.一種基于學校上學時間調整的校車調度算法[J].小型微型計算機系統(tǒng),2015,36(9):2 159-2 165.

[11]陳虓.交通網(wǎng)絡最優(yōu)路徑分析研究[D].鄭州:解放軍信息工程大學,2012.

Study on Single-track School Bus Route Planning Problem Based on Flooding Algorithm

Xue Weilian,Yu Xi,Zhou Feng,Li Qianying
(School of Management,Liaoning Normal University,Dalian 116029,China)

In this paper,in view of the single-track school bus route planning problem,on the basis of a review of relevant literatures, we considered the major influence factors such as route length,road attribute and traffic congestion,etc.,established the single-track school bus route planning model and solved it using the flooding algorithm modified by the addition of the pruning rule and tabu list.Then in the case of the Dalian Jiahui Sunshine Elementary School,we optimized one of its school bus routes and demonstrated that the efficiency of the method proposed in this paper was superior to the traditional exact algorithm.

school bus route planning;flooding algorithm;pruning algorithm

U116.2;F224.0

A

1005-152X(2016)10-0048-05

10.3969/j.issn.1005-152X.2016.10.013

2016-09-03

國家自然科學基金項目（61272417）

薛偉蓮（1966-），女，回族，遼寧營口人，教授，博士，研究方向：無線網(wǎng)絡、智能計算。