基于直達(dá)客流量的公交路徑優(yōu)化模型及求解算法

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

（1.桂林電子科技大學(xué)機(jī)電工程學(xué)院，廣西桂林 541004；2.桂林電子科技大學(xué)廣西高校智能交通系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西桂林 541004）

基于直達(dá)客流量的公交路徑優(yōu)化模型及求解算法

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

（1.桂林電子科技大學(xué)機(jī)電工程學(xué)院，廣西桂林 541004；2.桂林電子科技大學(xué)廣西高校智能交通系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西桂林 541004）

針對(duì)已有公交線路優(yōu)化模型求解過程復(fù)雜的問題，從直達(dá)客流量的角度對(duì)公交最優(yōu)路徑進(jìn)行求解。采用公交線路必經(jīng)中間站點(diǎn)的選取方法，將最短路徑KSP算法進(jìn)行改進(jìn)，用于求解最大直達(dá)客流量路徑；以最大直達(dá)客流量、人均最小成本2個(gè)維度為優(yōu)化目標(biāo)，建立了基于網(wǎng)絡(luò)人均出行成本最小的公交線路優(yōu)化模型，并給出了模型求解的算法。實(shí)例證實(shí)，公交路徑優(yōu)化模型有效可行，降低了線路求解的難度。

公交線路優(yōu)化；直達(dá)客流量；人均出行成本

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

1 單條公交線路的優(yōu)化目標(biāo)

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

1.1 可通行公交的道路網(wǎng)

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

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

1.2 線路長度約束

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

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

1.3 線路的非直線約束

公交線路的實(shí)際長度與起終點(diǎn)間空間直線距離之比稱為線路的非直線系數(shù)，記為q，它可以對(duì)線路的合理性、快捷性進(jìn)行評(píng)定。公交線路的非直線系數(shù)不宜過大，理想值為1，一般取值1.2～1.4?！冻鞘械缆方煌ㄒ?guī)劃設(shè)計(jì)規(guī)范》明確指出，公共交通線路非直線系數(shù)不應(yīng)大于1.4，

1.4 公交線路首末站點(diǎn)設(shè)置

公交首末站的設(shè)置一般依據(jù)規(guī)劃區(qū)域內(nèi)高峰小時(shí)客流量與途經(jīng)該區(qū)域的所有公交線路的運(yùn)力對(duì)比來確定。當(dāng)高峰小時(shí)客流量大于途經(jīng)該站點(diǎn)所有公交線路的總運(yùn)力時(shí)，則在該區(qū)域設(shè)立首末站點(diǎn)，反之則不設(shè)立。

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

2 優(yōu)化模型的建立

2.1 公交線路必經(jīng)中間站點(diǎn)的求解方法

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

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

2.2 最大直達(dá)客流公交線路模型

依據(jù)公交線路的約束準(zhǔn)則式（1）～（7），參考文獻(xiàn)［4］，簡化后的最大直達(dá)客流量模型為：

其中：pij為網(wǎng)絡(luò)內(nèi)從節(jié)點(diǎn)i到節(jié)點(diǎn)j的直達(dá)乘客量；xij為決策變量，當(dāng)線路通過路段（i，j）時(shí)取值為1，否則取值為0；Zsd為s到d的直達(dá)客流量。

2.3 出行成本最小的公交線路優(yōu)化模型

將城市道路網(wǎng)絡(luò)簡化成一個(gè)抽象的無向圖問題。設(shè)G＝（N，A），其中N為道路節(jié)點(diǎn)集，A為?。ㄟ叄┘琒為起點(diǎn)集，D為終點(diǎn)集，S，D∈N，aij∈A為連接i、j的路段，P為線路所對(duì)應(yīng)的直達(dá)客流量矩陣，i，j∈N，構(gòu)造網(wǎng)絡(luò)下的任意節(jié)點(diǎn)間的出行時(shí)間阻抗矩陣T，tij為由i到j(luò)所需要的時(shí)間。節(jié)點(diǎn)間有邊連接時(shí)為其對(duì)應(yīng)的時(shí)間，無邊連接時(shí)為inf，表示無窮大。U為線路l的人均最小出行消耗時(shí)間成本。具體表示為：

3 模型的算法及求解

3.1 改進(jìn)的KSP算法

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

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

圖1 KSP算法改進(jìn)后求解流程圖Fig.1 Flow chart of improved KSP algorithm

3.2 模型求解

結(jié)合KSP改進(jìn)算法，對(duì)網(wǎng)絡(luò)出行成本最小的公交線路模型進(jìn)行優(yōu)化求解。依據(jù)流程圖（見圖2），具體步驟為：

1）選擇公交起終點(diǎn)，求解線路必經(jīng)中間站點(diǎn)。

2）在首末站間通過改進(jìn)的KSP算法搜索最大直達(dá)客流量路徑，對(duì)搜到的路徑編號(hào)為i。

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

4）以網(wǎng)絡(luò)中人均最小消耗時(shí)間成本值最小為目標(biāo)，在生成的可行線路集中求解。

圖2 最優(yōu)線路求解流程圖Fig.2 Flow chart of best line optimization

4 算例分析

圖3 模擬路網(wǎng)Fig.3 Simulation graph of road network

圖3為簡化的模擬路網(wǎng)。實(shí)線表示路段，實(shí)線上的數(shù)字表示公交車的行駛時(shí)間，單位為min，圓圈中數(shù)字代表道路節(jié)點(diǎn)。已知節(jié)點(diǎn)間的乘客出行量，求重新調(diào)整節(jié)點(diǎn)4到節(jié)點(diǎn)22點(diǎn)間的公交線路。由必經(jīng)節(jié)點(diǎn)計(jì)算方法可知，節(jié)點(diǎn)11為必經(jīng)節(jié)點(diǎn)。

模型求解偽代碼：

計(jì)算的線路直達(dá)客流量及人均出行成本見表1。

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

由傳統(tǒng)方法可知，節(jié)點(diǎn)4到節(jié)點(diǎn)22應(yīng)該布設(shè)的線路為4-11-14-23-22，但從表1可看出，線路4-11-14-23-22實(shí)際并不是客流最密集的線路。從總直達(dá)客流量和該路網(wǎng)的人均出行成本層面分析，線路4-11-10-17-19-20-22最符合公交布設(shè)的原則，因此線路4-11-10-17-19-20-22應(yīng)優(yōu)先考慮。

5 結(jié)束語

依照公交線路布設(shè)的宗旨，建立了直達(dá)客流優(yōu)先的公交線路優(yōu)化模型，并通過改進(jìn)的KSP算法，對(duì)公交路徑進(jìn)行了優(yōu)化求解，求解結(jié)果驗(yàn)證可行。改進(jìn)的算法以最大客流走向作為搜索方向，符合公交線路徑布設(shè)原則。模型實(shí)現(xiàn)了求解最大直達(dá)客流量最大和網(wǎng)絡(luò)人均成本最小的公交出行目標(biāo)。初步考慮直達(dá)客流量等主要參數(shù)，在站點(diǎn)延誤、換乘時(shí)間等問題上還有待研究。

［1］ 王煒，陳學(xué)武，楊新苗.城市公共交通系統(tǒng)規(guī)劃方法與管理技術(shù)［M］.北京：科學(xué)出版社，2002：67-75.

［2］ 陳洪仁，馮樹民.分層限制的公交線網(wǎng)優(yōu)化模型［J］.哈爾濱建筑大學(xué)學(xué)報(bào)，2001，34（5）：113-115.

［3］ 王志棟.公交線網(wǎng)優(yōu)化模型的建立［J］.大連鐵道學(xué)院學(xué)報(bào)，1997，18（4）：33-36.

［4］ 于濱，楊永志，楊忠振，等.基于直達(dá)客流密度最大的公交線網(wǎng)優(yōu)化［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009.41（2）：205-207.

［5］ 張蕾，PAULO S C.公交線網(wǎng)優(yōu)化新技術(shù)的應(yīng)用研究［J］.交通標(biāo)準(zhǔn)化，2013，18（21）：15-20.

［6］ 王佳，符卓，杜靖毅.基于遺傳算法的城市公交骨架線網(wǎng)優(yōu)化設(shè)計(jì)［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（12）：4518-4521.

［7］ 武苗苗.城市微循環(huán)公交客流特性分析及站點(diǎn)規(guī)劃方法研究［D］.西安：長安大學(xué)，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

國家自然科學(xué)基金（51268006）

李文勇（1976-），男，河南南陽人，教授，博士，研究方向?yàn)榻煌ㄒ?guī)劃與管理、智能交通系統(tǒng)。E-mail：traffic＠guet.edu.cn

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