胡繼華，高立曉，梁嘉賢，蔡 銘

(1. 中山大學(xué) 智能交通研究中心，廣東 廣州 510006； 2. 廣東省智能交通系統(tǒng)重點實驗室，廣東 廣州 510006)

一種多目標(biāo)的公交線網(wǎng)規(guī)劃模型*

胡繼華1，2，高立曉1，2，梁嘉賢1，2，蔡 銘1，2

(1. 中山大學(xué) 智能交通研究中心，廣東 廣州 510006； 2. 廣東省智能交通系統(tǒng)重點實驗室，廣東 廣州 510006)

公交線網(wǎng)規(guī)劃是城市交通規(guī)劃的重要組成部分之一。針對公交線網(wǎng)規(guī)劃問題，提出一種多目標(biāo)的公交線網(wǎng)規(guī)劃模型，以最小化乘客總出行時間和總換乘次數(shù)，最大化線網(wǎng)的需求密度為目標(biāo)函數(shù)。利用禁忌搜索和模擬退火兩種算法對模型進(jìn)行求解，并利用Sioux-falls network對模型進(jìn)行驗證。結(jié)果表明：與前人的研究相比，本模型的結(jié)果直達(dá)率提高，換乘次數(shù)減少，公交的服務(wù)水平和吸引力提高；本研究的兩種算法相比，模擬退火所得結(jié)果直達(dá)率更高，需求密度更大，并且此算法效率更高。說明本模型能夠有效的適用于公交線網(wǎng)的規(guī)劃。

交通工程；城市交通；公交線網(wǎng)規(guī)劃；禁忌搜索；模擬退火；公交網(wǎng)絡(luò)

0 引 言

隨著城市的發(fā)展，城市居民出行需求急劇增大，而公共交通發(fā)展卻相對滯后，引發(fā)了交通擁堵等問題[1]。要盡可能滿足城市居民出行需求，緩解交通擁堵現(xiàn)狀，需要一個高效的公共交通系統(tǒng)。公共交通系統(tǒng)的重要組成部分之一是公交線網(wǎng)[2]?？茖W(xué)合理地規(guī)劃公交線網(wǎng)，對提高公交系統(tǒng)的運營效率，減少換乘次數(shù)，縮短出行時間，改善服務(wù)水平，提高公交吸引力具有重要意義。并且能為后續(xù)公交調(diào)度問題的解決奠定基礎(chǔ)。

自公共交通發(fā)展以來，交通規(guī)劃者和研究者們相繼提出了各種公交線網(wǎng)規(guī)劃模型及線路集生成算法。而真正在線網(wǎng)規(guī)劃研究方面開創(chuàng)先河的是C.MANDL。他以最小化車內(nèi)行駛時間為目標(biāo)建立模型，提出在所有節(jié)點之間找到最短路并建立包含絕大部分節(jié)點的線路集生成算法[3]。在公交線網(wǎng)規(guī)劃模型研究方面，模型目標(biāo)函數(shù)主要包括：最小化出行時間[4]；最小化出行時間和換乘數(shù)[5]；最小化出行時間，換乘數(shù)和不滿足需求數(shù)[6-8]；最小化出行時間和運營成本[9-11]；最大化需求密度[12-13]；最大化節(jié)省時間(規(guī)劃線網(wǎng)總時間減去現(xiàn)有網(wǎng)絡(luò)總時間)[14]；最小化出行時間及最大化直達(dá)密度[15-17]；最小化出行時間，運營成本，不滿足需求數(shù)和污染帶來的額外費用[18]；總出行時間最小，客流直達(dá)率最高，線網(wǎng)覆蓋率最高，線路重復(fù)系數(shù)最低，公交經(jīng)濟效益最高[19]等。在模型求解研究方面，主要是利用啟發(fā)式算法進(jìn)行求解，主要包括：禁忌搜索算法，模擬退火算法，蜂群優(yōu)化算法，蟻群優(yōu)化算法，遺傳算法等[20-21]。

上述的研究模型中，基礎(chǔ)目標(biāo)函數(shù)是最小化總出行時間，其他都是在這個單目標(biāo)上進(jìn)行擴展，從而得到多種多目標(biāo)函數(shù)。但是上述模型或只是從乘客角度出發(fā)，最小化出行時間及換乘次數(shù)；或只考慮整個線網(wǎng)的運營效率，最大化需求密度；或考慮到乘客和線網(wǎng)運營效率，但是目標(biāo)只是最小化出行時間，最大化直達(dá)需求密度，忽略了換乘的影響。

因此，筆者在前人研究的基礎(chǔ)上，在考慮乘客和線網(wǎng)運營效率的同時，加入換乘的影響，提出一種多目標(biāo)的公交線網(wǎng)規(guī)劃模型，以最小化總出行時間和換乘次數(shù)，最大化線網(wǎng)的需求密度(直達(dá)和換乘)為目標(biāo)，利用禁忌搜索和模擬退火兩種算法進(jìn)行求解。

1 公交線網(wǎng)規(guī)劃模型

城市公交線網(wǎng)布設(shè)主要是為市民提供更加便利和經(jīng)濟的出行條件。因此公交線網(wǎng)規(guī)劃首要考慮到乘客的利益，滿足其出行需求。在此基礎(chǔ)上盡可能減小出行時間，減少換乘次數(shù)。還要考慮到整個公交線網(wǎng)的運營效率，盡量實現(xiàn)以更小地投入實現(xiàn)更大地運輸效率。因此筆者提出了一種基于乘客利益和公交線網(wǎng)運營效率的多目標(biāo)規(guī)劃模型。

筆者所研究的公交線網(wǎng)規(guī)劃問題是在給定OD需求，潛在站點以及潛在站點之間的路段長度或路段行駛時間的條件下，根據(jù)給定的公交線路數(shù)量和目標(biāo)函數(shù)，用禁忌搜索和模擬退火算法找到最優(yōu)的線路集。

1.1 目標(biāo)函數(shù)

根據(jù)線網(wǎng)規(guī)劃的基本原則，建立以尋求乘客出行時間最短，換乘次數(shù)最少，公交線網(wǎng)需求密度最大為總體目標(biāo)的公交線網(wǎng)規(guī)劃模型。

1.1.1 乘客出行時間

乘客出行時間主要包括：步行時間(出發(fā)地-公交站點，公交站點-目的地)、候車時間、乘車時間以及換乘的時間。單個乘客出行時間計算如式(1)：

(1)

故，乘客出行總時間Z1如式(2)：

(2)

式中：dij為節(jié)點i到j(luò)的需求量，通過將OD矩陣中的相應(yīng)需求量按照每條路徑i到j(luò)(直達(dá)和換乘)長度倒數(shù)的比例來分配，從而獲得dij。

1.1.2 乘客換乘次數(shù)

乘客換乘次數(shù)是指在乘客的一次出行中，乘坐公交車的換乘次數(shù)。

乘客總換乘次數(shù)Z2如式(3)：

(3)

式中：tij為節(jié)點i到j(luò)的單個乘客的換乘次數(shù)。

1.1.3 線網(wǎng)需求密度

公交需求包括直達(dá)需求和換乘需求，即直達(dá)乘客數(shù)和換乘乘客數(shù)。線路需求密度是指單位長度線路上分布的公交需求數(shù)(直達(dá)和換乘)。

線網(wǎng)需求密度Z3如式(4)：

(4)

式中：lij為節(jié)點i到j(luò)的路徑長度；ω為換乘參數(shù)，反映換乘的重要程度；xij的取值為0或1，當(dāng)路徑i，j為直達(dá)路徑時，取值為0，當(dāng)i，j為換乘路徑時，取值為1。

綜上所述，筆者建立的模型目標(biāo)函數(shù)如式(5)：

Zmin=αZ1+βZ2-γZ3

(5)

式中：α、β、γ為效率均衡系數(shù)。

1.2 約束條件

一個合理的公交線網(wǎng)，不僅要求每條線路都滿足一定的約束條件，還考慮整個線網(wǎng)的分布性能及其運行效率。約束條件有：

1) 線網(wǎng)連通；

2) 不能有環(huán)線；

3) 線網(wǎng)中線路條數(shù)確定；

4) 換乘次數(shù)不超過兩次；

5) 每一條線路的節(jié)點數(shù)要小于預(yù)設(shè)最大值，大于預(yù)設(shè)最小值，如式(6)：

nmin≤ng≤nmax

(6)

式中：nmin為線路節(jié)點數(shù)的下限；nmax為線路節(jié)點數(shù)的上限；ng為公交線路g的長度。

6) 復(fù)線條數(shù)m(某條路段上設(shè)置的公交線路數(shù))小于預(yù)設(shè)條數(shù)，m≤5；

7) 線網(wǎng)密度(公交線網(wǎng)的道路覆蓋率)大于預(yù)設(shè)值，如式(7)：

(7)

式中：d為線網(wǎng)密度；lR為公交線路總長度；lA為道路網(wǎng)絡(luò)總長度。

8) 線路非直線系數(shù)(公交線路長度與起、終站點間直線距離之比)小于預(yù)設(shè)值，如式(8)：

(8)

式中：α為線網(wǎng)密度；lg為公交線路長度；ls為線路的起、終站點間的直線距離。

2 模型求解

大量研究發(fā)現(xiàn)，啟發(fā)式算法適合求解大規(guī)模的優(yōu)化問題，比如禁忌搜索、模擬退火、遺傳算法、蜂群優(yōu)化、蟻群優(yōu)化等。經(jīng)過比選，筆者采用禁忌搜索算法和模擬退火算法對模型進(jìn)行求解，并對兩種算法結(jié)果進(jìn)行對比分析。

模型求解的基礎(chǔ)是構(gòu)造初始可行解。筆者利用隨機生成算法構(gòu)建初始可行解，其核心思想是通過隨機起始邊和隨機線路節(jié)點數(shù)，通過邊的延伸來生成一條線路，然后生成預(yù)設(shè)條數(shù)的初始線網(wǎng)。由于初始解集質(zhì)量直接影響到最終的結(jié)果，因此筆者采用多個初始解集的策略，能夠在多個最終結(jié)果中優(yōu)中選優(yōu)，從而得到最優(yōu)線網(wǎng)。

其次是鄰域解集的生成。其核心思想是對當(dāng)前解集隨機選擇一種方案進(jìn)行修改，修改后的線網(wǎng)只要滿足約束條件，就替換當(dāng)前線網(wǎng)。鄰域解生成方案有4種，如圖1。其中，虛線表示刪除。插入節(jié)點是在線路中間插入一個外節(jié)點；添加節(jié)點是在線路的首或尾添加一個外節(jié)點；刪除節(jié)點是刪除線路的首節(jié)點或尾節(jié)點；交換節(jié)點是線路外節(jié)點與線路某個中間節(jié)點進(jìn)行交換。選擇哪一種線路修改方式是隨機的。

圖1 線路改進(jìn)方式Fig.1 Modified modes of bus line

基于初始解和鄰域解生成，求解本模型的模擬退火算法流程如圖2，禁忌搜索算法流程如圖3。

圖2 模擬退火算法Fig.2 Simulated annealing algorithm

圖3 禁忌搜索算法Fig.3 Taboo search algorithm

3 實例驗證

3.1 數(shù)據(jù)說明

使用Sioux-falls network對本模型進(jìn)行驗證。Sioux-falls network是線網(wǎng)規(guī)劃問題的一個基準(zhǔn)測試網(wǎng)絡(luò)，包含24個節(jié)點，76條有向邊，528個OD對。原OD量乘以100得到本研究所用的OD矩陣表，共360 600個乘客需求。網(wǎng)絡(luò)如圖4，邊上的數(shù)字代表公交車區(qū)間運行時間或路段長度，單位為min或km。OD需求如表1、2。

圖4 Sioux-falls 網(wǎng)絡(luò)Fig.4 Sioux-falls network

OD12345678910111210100100500200300500800500130050020021000100200100400200400200600200100310010002001003001002001003003002004500200200050040040070070012001400600520010010050002002005008001000500200630040030040020004008004008004002007500200100400200400010006001900500700880040020070050080010000800160080060095002001007008004006008000280014006001013006003001200100080019001600280004000200011500200300150050040050080014003900014001220010020060020020070060060020001400013500300100600200200400600600190010001300143001001005001001002004006002100160070015500100100500200200500600100040001400700165004002008005009001400220014004400140070017400200100500200500100014009003900100060018100001000100200300200700200200193001000200100200400700400180040030020300100030010030050090060025006005002110000200100100200400300120040030022400100100400200200500500700260011007002330001005001001002003005001800130070024100002000100100200200800600500

表2 Sioux-falls network OD需求人數(shù)Table 2 Sioux-falls network OD demand number of people

3.2 結(jié)果分析

本案例中目標(biāo)函數(shù)的效率均衡系數(shù)均設(shè)置為1，每條線路的節(jié)點數(shù)閾值設(shè)置為5、12，線路條數(shù)為6～10條。設(shè)置200個初始解，模擬退火算法有141個逐漸遞減的溫度值，每個溫度下迭代50次；禁忌搜索算法的內(nèi)迭代也是50次，取200次試驗中的最優(yōu)值。最終結(jié)果如表3。

表3 最終線路集Table 3 Final route set

在公交線網(wǎng)規(guī)劃中，常用直達(dá)率等評價指標(biāo)對所規(guī)劃線網(wǎng)進(jìn)行評估，表4給出了本研究生成的線網(wǎng)與之前研究所得線網(wǎng)在直達(dá)率等指標(biāo)上的比較。結(jié)果表明：本模型的結(jié)果要優(yōu)于前人研究。筆者所用的兩種求解算法所得結(jié)果也略有差異。從表4中可以看出：模擬退火結(jié)果直達(dá)率更高，直達(dá)密度更大，但是兩次換乘率略高，總線網(wǎng)長度略長，總出行時間較大。

隨著線路條數(shù)增加，線網(wǎng)的特征會發(fā)生變化，部分線網(wǎng)評價指標(biāo)的變化趨勢如圖5。

由圖5(a)可看出：禁忌搜索和模擬退火兩種算法中，直達(dá)客流量都隨著線路條數(shù)的增加而增大；但當(dāng)線路條數(shù)為7～9條時，禁忌搜索結(jié)果的直達(dá)率變化很小，當(dāng)線路條數(shù)為7條時，禁忌搜索結(jié)果直達(dá)率更大；而其他的線路條數(shù)下，模擬退火結(jié)果直達(dá)率更大。

由圖5(b)可看出：模擬退火結(jié)果的平均換乘次數(shù)隨著線路條數(shù)增加而逐漸減小，比較穩(wěn)定，而禁忌搜索在線路條數(shù)為9條時的結(jié)果平均換乘次數(shù)突然增加，說明此線網(wǎng)兩次換乘率比較高，就換乘方面而言，該線網(wǎng)不是最優(yōu)。

由圖5(c)可看出：隨著線路條數(shù)增加，禁忌搜索結(jié)果的直達(dá)需求密度逐漸增大，而模擬退火在線路為7條時的結(jié)果直達(dá)密度減少。

綜上所述，模擬退火所得結(jié)果較為穩(wěn)定，且用時較少。在以后的線網(wǎng)規(guī)劃中，可選擇模擬退火算法進(jìn)行求解。

4 結(jié) 語

筆者提出了以總出行時間最短，總換乘次數(shù)最少，線網(wǎng)需求密度最大化為目標(biāo)的線網(wǎng)規(guī)劃模型；并采用禁忌搜索和模擬退火兩種算法進(jìn)行求解，并利用經(jīng)典網(wǎng)絡(luò)Sioux-Falls Network進(jìn)行驗證。當(dāng)線路條數(shù)為8時，結(jié)果表明：本研究模型得到的結(jié)果與前人相比，直達(dá)率提高了7.8%，總換乘次數(shù)減少，直達(dá)需求密度提高，公交服務(wù)水平和吸引力提高。同時，本研究所采用的兩種不同算法結(jié)果稍有差異，模擬退火直達(dá)率較高，需求密度較大，并且效率較高。

對于以后研究，筆者會在如下方面進(jìn)行改進(jìn)和完善：① 客流分配算法；② 結(jié)合實際，將線網(wǎng)進(jìn)行分級規(guī)劃；③ 將此模型用于實際地區(qū)的線網(wǎng)規(guī)劃。

[1] 李軍，鄧紅平.基于公交IC卡數(shù)據(jù)的乘客出行分類研究[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版)，2016，35(6)：109-114.

LI Jun，DENG Hongping. Classification of passenger’s travel behavior based on IC card data[J].JournalofChongqingJiaotongUniversity(NaturalScience)，2016，35(6)：109-114.

[2] 胡繼華，黃澤，程智鋒，等.公交乘客在商業(yè)中心區(qū)購物的時空效用變化分析[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版)，2015，34(6)：101-105.

HU Jihua，HUANG Ze，CHENG Zhifeng，et al. Analysis on space-time benefit change of bus passengers’ shopping in commercial center[J].JournalofChongqingJiaotongUniversity(NaturalScience)，2015，34(6)：101-105.

[3] MANDL C.AppliedNetworkOptimization[M]. London：Academic Press，1979.

[4] CANCELA H，MAUTTONE A，URQUHART M E. Mathematical programming formulations for transit network design[J].TransportationResearchPartB：Methodological，2015，77：17-37.

[5] KILIC F，G?K M. A demand based route generation algorithm for public transit network design[J].Computers&OperationsResearch，2014，51：21-29.

[6] CHAKROBORTY P，WIVEDI T. Optimal route network design for transit systems using genetic algorithms[J].EngineeringOptimization，2002，34(1)：83-100.

[8] NAYEEM M A，RAHMAN M K，RAHMAN M S. Transit network design by genetic algorithm with elitism[J].TransportationResearchPartC：EmergingTechnologies，2014，46：30-45.

[9] An K，LO H K. Robust transit network design with stochastic demand considering development density[J].TransportationResearchPartB：Methodological，2015，81：737-754.

[10] 林柏梁，楊富社，李鵬.基于出行費用最小化的公交網(wǎng)絡(luò)優(yōu)化模型[J].中國公路學(xué)報，1999，12(1)：79-83.

LIN Boliang，YANG Fushe，LI Peng. Designing optimal bus network for minimizing trip times of passenger flows[J].ChinaJournalofHighwayandTransport，1999，12(1)：79-83.

[11] 羅湘.公交線網(wǎng)規(guī)劃的模型與算法[D].長沙：中南大學(xué)，2011.

LUO Xiang.ModelandAlgorithmofPublicTransitNetworkPlanning[D]. Changsha：Central South University，2011.

[12] YU Bin，YANG Zhongzhen，JIN Penghuan，et al. Transit route network design-maximizing direct and transfer demand density[J].TransportationResearchPartC：EmergingTechnologies，2012，22：58-75.

[13] 張敖木翰.基于蟻群算法的城市公交線網(wǎng)優(yōu)化設(shè)計研究[D].北京：北京交通大學(xué)，2008.

ZHANGAO Muhan.StudyonOptimalDesignofUrbanTransitNetworkBasedonAntColonyMethod[D]. Beijing：Beijing Jiaotong University，2008.

[14] BAGLOEE S A，CEDER A. Transit-network design methodology for actual-size road networks[J].TransportationResearchPartB：Methodological，2011，45(10)：1787-1804.

[15] 于濱，楊永志，楊忠振，等.基于直達(dá)客流密度最大的公交線網(wǎng)優(yōu)化[J].哈爾濱工業(yè)大學(xué)學(xué)報，2009，41(2)：205-207.

YU Bin，YANG Yongzhi，YANG Zhongzhen，et al. Transit network optimization based on direct passenger flow density maximization[J].JournalofHarbinInstituteofTechnology，2009，41(2)：205-207.

[16] 于濱，劉鴻婷，閆博，等.公交線路網(wǎng)優(yōu)化的雙層模型及其解法[J].吉林大學(xué)學(xué)報(工學(xué)版)，2010，40(2)：402-405.

YU Bin，LIU Hongting，YAN Bo，et al. Bi-level model for bus route network optimization and its solution[J].JournalofJilinUniversity(EngineeringandTechnologyEdition)，2010，40(2)：402-405.

[17] 康凱.城市公交線網(wǎng)優(yōu)化方法研究[D].廣州：華南理工大學(xué)，2011.

KANG Kai.StudyofOptimizationMethodforUrbanPublicTransitNetwork[D]. Guangzhou：South China University of Technology，2011.

[18] PTEMEA M，KEPAPTSOGLOU K，KARLAFTIS M G. Sustainable urban transit network design[J].TransportationResearchPartA：PolicyandPractice，2015，77：276-291.

[19] 王志棟.公交線網(wǎng)優(yōu)化模型的建立[J].大連鐵道學(xué)院學(xué)報，1997，18(4)：31-34.

WANG Zhidong. Mode setting-up of public traffic line network[J].JournalofDalianRailwayInstitute，1997，18(4)：31-34.

[20] 宋安.基于雙層規(guī)劃的城市公交線網(wǎng)優(yōu)化研究[D].長沙：長沙理工大學(xué)，2010.

SONG An.AnOptimizationResearchoftheUrbanPublicTransportationNetworkBasedonBi-levelProgramming[D]. Changsha：Changsha University of Science & Technology，2010.

[21] 周媛，鄧衛(wèi)，胡啟洲.基于遺傳禁忌算法的城市公交線網(wǎng)優(yōu)化研究[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版)，2011，35(1)：42-45.

ZHOU Yuan，DENG Wei，HU Qizhou. Study on the optimization of public transit network based on genetic algorithm and tabu search algorithm[J].JournalofWuhanUniversityofTechnology(TransportationScience&Engineering)，2011，35(1)：42-45.

A Multi-objective Public Transit Network Planning Model

HU Jihua1，2，GAO Lixiao1，2，LIANG Jiaxian1，2，CAI Ming1，2

(1. Research Centre of Intelligent Transportation，Sun Yat-sen University，Guangzhou 510006，Guangdong，P. R. China; 2. Guangdong Provincial Key Laboratory of Intelligent Transportation System，Guangzhou 510006，Guangdong，P. R. China)

Transit network planning is one of the important parts of urban traffic planning. A multi-objective programming model for public transit network was proposed to address the transit network planning problem. The objective function of the proposed model was to minimize the total travel time and the total numbers of transfers as well as to maximize the demand density of the network. Taboo search and simulated annealing algorithms were used to solve the proposed model. The proposed model and algorithms were tested by using the Sioux-falls network. The results show that compared with previous studies，the results of the proposed model have higher nonstop ratio，less transfer times，better service level and attractiveness of public transport. Compared with the taboo search algorithm，the simulated annealing results have higher nonstop ratio，larger demand density and higher efficiency. Therefore，the proposed model can be effectively applied to the planning of public transport network.

traffic engineering; urban traffic; transit network planning; taboo search; simulated annealing; transit network

10.3969/j.issn.1674-0696.2017.12.17

2016-06-15；

2016-09-18

國家自然科學(xué)基金項目(41271181)；廣東省科技計劃項目(2015B010110005)

胡繼華(1971—)，男，河南信陽人，講師，博士，主要從事地圖學(xué)、地理信息系統(tǒng)和時態(tài)GIS方面的研究。E-mail：hujihua@mail.sysu.edu.cn。

U491.1+7

A

1674-0696(2017)12-102-08

劉韜)