基于直達客流量的公交路徑優化模型及求解算法

齊振濤，李文勇，2，余子威，賀軍杰

（1.桂林電子科技大學機電工程學院，廣西桂林 541004；2.桂林電子科技大學廣西高校智能交通系統重點實驗室，廣西桂林 541004）

基于直達客流量的公交路徑優化模型及求解算法

齊振濤1，李文勇1，2，余子威1，賀軍杰1

（1.桂林電子科技大學機電工程學院，廣西桂林 541004；2.桂林電子科技大學廣西高校智能交通系統重點實驗室，廣西桂林 541004）

針對已有公交線路優化模型求解過程復雜的問題，從直達客流量的角度對公交最優路徑進行求解。采用公交線路必經中間站點的選取方法，將最短路徑KSP算法進行改進，用于求解最大直達客流量路徑；以最大直達客流量、人均最小成本2個維度為優化目標，建立了基于網絡人均出行成本最小的公交線路優化模型，并給出了模型求解的算法。實例證實，公交路徑優化模型有效可行，降低了線路求解的難度。

公交線路優化；直達客流量；人均出行成本

隨著社會進程加速，公共交通在城市交通中的地位日趨重要，提升公交網絡的性能問題已成為科學研究與工程應用中的熱點和難點。公交線網的優化需要公交線路路徑搜尋理論作為支撐。研究公交路徑對整個公交線網的研究和開發有著重要意義。公交最優出行路徑的搜索與生成的根本在于網絡最優路徑模型的建立和算法求解問題。公交路徑優化方面的研究國內始于20世紀80年代，文獻［1-3］給出了公交路徑優化模型及具體求解方法，但均傾向于整個網絡，求解計算復雜；于濱等［4］以直達客流密度為目標對王煒等［1］提出的直達量優先的方法作了改進，但并未給出具體求解方法。目前已有的路徑尋優算法大部分適用于求解最短路徑問題，適合公交路徑優化的實用、有效的模型和求解算法研究較少。為此，建立結合實際乘客出行需求的公交路徑擇優模型，對起終點間的公交出行路徑進行優化。該模型將最大直達客流量、最小網絡出行成本和可行的路網等因素綜合考慮，在保證規劃原則的前提下，實現了起終點間的公交路徑求解。

1 單條公交線路的優化目標

單條公交線路在優化時應按照以下原則：1）線路的走向服務于主要客流，以滿足居民出行的需要；2）盡量提供直達運輸，使得乘客總換乘次數最少；3）盡量依照最短距離布設線路，使得所有乘客的總出行時間最小。公交線路的優化屬于多目標問題，以上原則在優化時并不能同時滿足，為此將模型的主要優化目標設為直達客流量最高和網絡中人均出行時間最小。

1.1 可通行公交的道路網

道路網是城市公共交通系統的基礎，可通行公交線路的道路必須具備一定的道路條件和交通條件。具體包括：為滿足雙向安全行車，道路路寬應大于某一值；道路暢通條件好，沒有無法排除的交通梗塞；道路長度應滿足公交設線的長度要求。

其中G′、G分別為可通行公交線網和城市道路網。

1.2 線路長度約束

公交線路的長度應滿足一定條件，線路過長，使得客流分布不均勻，產生運輸效率過低和公交線路的非直線系數過大等問題；線路過短，使得公交車輛的調車轉向總時間增加，降低了公交車輛的使用效率和公交車的運營車速，同時也增加了乘客的平均換乘次數。

其中：L為公交線路的實際長度；Lmin、Lmax為公交線路允許的最小長度和最大長度。

1.3 線路的非直線約束

公交線路的實際長度與起終點間空間直線距離之比稱為線路的非直線系數，記為q，它可以對線路的合理性、快捷性進行評定。公交線路的非直線系數不宜過大，理想值為1，一般取值1.2～1.4。《城市道路交通規劃設計規范》明確指出，公共交通線路非直線系數不應大于1.4，

1.4 公交線路首末站點設置

公交首末站的設置一般依據規劃區域內高峰小時客流量與途經該區域的所有公交線路的運力對比來確定。當高峰小時客流量大于途經該站點所有公交線路的總運力時，則在該區域設立首末站點，反之則不設立。

其中：Q為公交站點小時最大客流的生成量和吸引量之和；Qmax為公交站點可以承載的小時最大乘客量。

2 優化模型的建立

2.1 公交線路必經中間站點的求解方法

公交線路必經中間站點指線路必須通過的站點，如大型商場、車站等具有明顯客流產生量的地點。當線路途經站點和路段較多時，可選線路規模很大，此時不易確定公交線路的走向。若能在求解線路時設定必經中間站點，則只有少數線路是可選的，這樣將大大縮小求解范圍。為了減小搜索解空間，使求解簡化，建立如下尋找必經中間站點的方法［7］。

對于已經確定的居民出行結構，在網絡中找到線路起終點的中點位置坐標，將線路中某節點產生的出行量乘以節點到中點的距離，記為fil（x，y），并記線路上所有節點的fil（x，y）之和為。用單節點對應的fil（x，y）除以線路上所有節點的，所求得的值中最小的點即為網絡的必經節點。計算方法為：首先建立坐標系，將網絡中各個節點位置進行標記。設必經節點的位置為（x，y），l為起點si（si∈S，i＝1，2，…）到終點di（di∈D，i＝1，2，…）的可行線路編號，bil為線路l上第i個節點的總出行量，xi，yi為可行線路l上的節點編號，（xs，ys）為起點的坐標，（xd，yd）為終點的坐標，為中點的坐標，fil（x，y）為第l條可行線路對應的第i個節點到中點坐標距離與bil的乘積。模型如下：

2.2 最大直達客流公交線路模型

依據公交線路的約束準則式（1）～（7），參考文獻［4］，簡化后的最大直達客流量模型為：

其中：pij為網絡內從節點i到節點j的直達乘客量；xij為決策變量，當線路通過路段（i，j）時取值為1，否則取值為0；Zsd為s到d的直達客流量。

2.3 出行成本最小的公交線路優化模型

將城市道路網絡簡化成一個抽象的無向圖問題。設G＝（N，A），其中N為道路節點集，A為弧（邊）集，S為起點集，D為終點集，S，D∈N，aij∈A為連接i、j的路段，P為線路所對應的直達客流量矩陣，i，j∈N，構造網絡下的任意節點間的出行時間阻抗矩陣T，tij為由i到j所需要的時間。節點間有邊連接時為其對應的時間，無邊連接時為inf，表示無窮大。U為線路l的人均最小出行消耗時間成本。具體表示為：

3 模型的算法及求解

3.1 改進的KSP算法

智能搜索算法作為公交線路優化的有力工具，其典型代表是最短路徑搜索法。K條最短路徑（KSP）算法由Yen［8］于1972年提出，已被廣泛用于求解網絡中最短路徑問題。

公交路徑優化其實是路徑選擇問題，其根本是確定線路途經過的站點和路段。傳統KSP算法只能搜索網絡中的最短路徑，因此需要對KSP算法進行改進（見圖1）。具體方法是：將城市道路網絡簡化為抽象的無向圖，分別建立居民出行矩陣M、出行時間阻抗矩陣T。引入一個空矩陣V，先將居民出行矩陣M中的非零項客流數據求導后賦給V。然后將出行時間阻抗矩陣T中值為inf的賦給V，此時得到的矩陣稱為過渡矩陣V。用KSP算法對過渡矩陣搜索，搜索的結果就是最大直達量客流的線路。引入過渡矩陣后，最大直達客流的公交線路布設問題轉換為在過渡矩陣下的KSP路徑求解問題。

圖1 KSP算法改進后求解流程圖Fig.1 Flow chart of improved KSP algorithm

3.2 模型求解

結合KSP改進算法，對網絡出行成本最小的公交線路模型進行優化求解。依據流程圖（見圖2），具體步驟為：

1）選擇公交起終點，求解線路必經中間站點。

2）在首末站間通過改進的KSP算法搜索最大直達客流量路徑，對搜到的路徑編號為i。

3）判斷第i條路徑是否符合約束，若符合，則存入線路集，搜索第i＋1條路徑；否則，終止。

4）以網絡中人均最小消耗時間成本值最小為目標，在生成的可行線路集中求解。

圖2 最優線路求解流程圖Fig.2 Flow chart of best line optimization

4 算例分析

圖3 模擬路網Fig.3 Simulation graph of road network

圖3為簡化的模擬路網。實線表示路段，實線上的數字表示公交車的行駛時間，單位為min，圓圈中數字代表道路節點。已知節點間的乘客出行量，求重新調整節點4到節點22點間的公交線路。由必經節點計算方法可知，節點11為必經節點。

模型求解偽代碼：

計算的線路直達客流量及人均出行成本見表1。

表1 直達客流及人均出行成本Tab.1 Direct passenger flow and per capita travel cost

由傳統方法可知，節點4到節點22應該布設的線路為4-11-14-23-22，但從表1可看出，線路4-11-14-23-22實際并不是客流最密集的線路。從總直達客流量和該路網的人均出行成本層面分析，線路4-11-10-17-19-20-22最符合公交布設的原則，因此線路4-11-10-17-19-20-22應優先考慮。

5 結束語

依照公交線路布設的宗旨，建立了直達客流優先的公交線路優化模型，并通過改進的KSP算法，對公交路徑進行了優化求解，求解結果驗證可行。改進的算法以最大客流走向作為搜索方向，符合公交線路徑布設原則。模型實現了求解最大直達客流量最大和網絡人均成本最小的公交出行目標。初步考慮直達客流量等主要參數，在站點延誤、換乘時間等問題上還有待研究。

［1］ 王煒，陳學武，楊新苗.城市公共交通系統規劃方法與管理技術［M］.北京：科學出版社，2002：67-75.

［2］ 陳洪仁，馮樹民.分層限制的公交線網優化模型［J］.哈爾濱建筑大學學報，2001，34（5）：113-115.

［3］ 王志棟.公交線網優化模型的建立［J］.大連鐵道學院學報，1997，18（4）：33-36.

［4］ 于濱，楊永志，楊忠振，等.基于直達客流密度最大的公交線網優化［J］.哈爾濱工業大學學報，2009.41（2）：205-207.

［5］ 張蕾，PAULO S C.公交線網優化新技術的應用研究［J］.交通標準化，2013，18（21）：15-20.

［6］ 王佳，符卓，杜靖毅.基于遺傳算法的城市公交骨架線網優化設計［J］.計算機應用研究，2012，29（12）：4518-4521.

［7］ 武苗苗.城市微循環公交客流特性分析及站點規劃方法研究［D］.西安：長安大學，2014：79-82.

［8］ YEN J Y.Finding the lengths of all shortest paths in NNode nonnegative-distance complete networks usingadditions andN3comparisons［J］.Journal of the ACM，1972，19（3）：423-424.

編輯：張所濱

Bus route optimization model and algorithm based on direct passenger flow volume

QI Zhentao1，LI Wenyong1，2，YU Ziwei1，HE Junjie1
（1.School of Mechatronic Engineering，Guilin University of Electronic Technology，Guilin 541004，China；2.Guangxi College Laboratory of Intelligent Transportation System，Guilin University of Electronic Technology，Guilin 541004，China）

In view of the complicated problems in the process of solving the optimization model of bus lines，the optimal path of the bus line is studied in term of direct passenger flow.The study shows that a bus line must pass through node selected model.KSP algorithm is improved for solving the direct flow viable of bus lines.Finally a minimum per capita travel cost bus route optimization model is established based on direct passenger volume and the average per capita minimum cost as the optimization goal.The algorithm for calculating the model is given.The model is verified by apractical example and the model reduces the difficulty of bus line optimization.

bus route optimization；direct passenger flow volume；average travel cost

U491.1

：A

：1673-808X（2016）05-0412-04

2015-12-28

國家自然科學基金（51268006）

李文勇（1976-），男，河南南陽人，教授，博士，研究方向為交通規劃與管理、智能交通系統。E-mail：traffic＠guet.edu.cn

齊振濤，李文勇，余子威，等.基于直達客流量的公交路徑優化模型及求解算法［J］.桂林電子科技大學學報，2016，36（5）：412-415.