一種多目標的公交線網規劃模型*

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

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

一種多目標的公交線網規劃模型*

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

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

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

交通工程；城市交通；公交線網規劃；禁忌搜索；模擬退火；公交網絡

0 引 言

隨著城市的發展，城市居民出行需求急劇增大，而公共交通發展卻相對滯后，引發了交通擁堵等問題[1]。要盡可能滿足城市居民出行需求，緩解交通擁堵現狀，需要一個高效的公共交通系統。公共交通系統的重要組成部分之一是公交線網[2]。科學合理地規劃公交線網，對提高公交系統的運營效率，減少換乘次數，縮短出行時間，改善服務水平，提高公交吸引力具有重要意義。并且能為后續公交調度問題的解決奠定基礎。

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

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

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

1 公交線網規劃模型

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

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

1.1 目標函數

根據線網規劃的基本原則，建立以尋求乘客出行時間最短，換乘次數最少，公交線網需求密度最大為總體目標的公交線網規劃模型。

1.1.1 乘客出行時間

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

(1)

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

(2)

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

1.1.2 乘客換乘次數

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

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

(3)

式中：tij為節點i到j的單個乘客的換乘次數。

1.1.3 線網需求密度

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

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

(4)

式中：lij為節點i到j的路徑長度；ω為換乘參數，反映換乘的重要程度；xij的取值為0或1，當路徑i，j為直達路徑時，取值為0，當i，j為換乘路徑時，取值為1。

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

Zmin=αZ1+βZ2-γZ3

(5)

式中：α、β、γ為效率均衡系數。

1.2 約束條件

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

1) 線網連通；

2) 不能有環線；

3) 線網中線路條數確定；

4) 換乘次數不超過兩次；

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

nmin≤ng≤nmax

(6)

式中：nmin為線路節點數的下限；nmax為線路節點數的上限；ng為公交線路g的長度。

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

7) 線網密度(公交線網的道路覆蓋率)大于預設值，如式(7)：

(7)

式中：d為線網密度；lR為公交線路總長度；lA為道路網絡總長度。

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

(8)

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

2 模型求解

大量研究發現，啟發式算法適合求解大規模的優化問題，比如禁忌搜索、模擬退火、遺傳算法、蜂群優化、蟻群優化等。經過比選，筆者采用禁忌搜索算法和模擬退火算法對模型進行求解，并對兩種算法結果進行對比分析。

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

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

圖1 線路改進方式Fig.1 Modified modes of bus line

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

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

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

3 實例驗證

3.1 數據說明

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

圖4 Sioux-falls 網絡Fig.4 Sioux-falls network

OD12345678910111210100100500200300500800500130050020021000100200100400200400200600200100310010002001003001002001003003002004500200200050040040070070012001400600520010010050002002005008001000500200630040030040020004008004008004002007500200100400200400010006001900500700880040020070050080010000800160080060095002001007008004006008000280014006001013006003001200100080019001600280004000200011500200300150050040050080014003900014001220010020060020020070060060020001400013500300100600200200400600600190010001300143001001005001001002004006002100160070015500100100500200200500600100040001400700165004002008005009001400220014004400140070017400200100500200500100014009003900100060018100001000100200300200700200200193001000200100200400700400180040030020300100030010030050090060025006005002110000200100100200400300120040030022400100100400200200500500700260011007002330001005001001002003005001800130070024100002000100100200200800600500

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

3.2 結果分析

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

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

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

隨著線路條數增加，線網的特征會發生變化，部分線網評價指標的變化趨勢如圖5。

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

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

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

綜上所述，模擬退火所得結果較為穩定，且用時較少。在以后的線網規劃中，可選擇模擬退火算法進行求解。

4 結 語

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

對于以后研究，筆者會在如下方面進行改進和完善：① 客流分配算法；② 結合實際，將線網進行分級規劃；③ 將此模型用于實際地區的線網規劃。

[1] 李軍，鄧紅平.基于公交IC卡數據的乘客出行分類研究[J].重慶交通大學學報(自然科學版)，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] 胡繼華，黃澤，程智鋒，等.公交乘客在商業中心區購物的時空效用變化分析[J].重慶交通大學學報(自然科學版)，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] 林柏梁，楊富社，李鵬.基于出行費用最小化的公交網絡優化模型[J].中國公路學報，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] 羅湘.公交線網規劃的模型與算法[D].長沙：中南大學，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] 張敖木翰.基于蟻群算法的城市公交線網優化設計研究[D].北京：北京交通大學，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] 于濱，楊永志，楊忠振，等.基于直達客流密度最大的公交線網優化[J].哈爾濱工業大學學報，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] 于濱，劉鴻婷，閆博，等.公交線路網優化的雙層模型及其解法[J].吉林大學學報(工學版)，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] 康凱.城市公交線網優化方法研究[D].廣州：華南理工大學，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] 王志棟.公交線網優化模型的建立[J].大連鐵道學院學報，1997，18(4)：31-34.

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

[20] 宋安.基于雙層規劃的城市公交線網優化研究[D].長沙：長沙理工大學，2010.

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

[21] 周媛，鄧衛，胡啟洲.基于遺傳禁忌算法的城市公交線網優化研究[J].武漢理工大學學報(交通科學與工程版)，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

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

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

U491.1+7

A

1674-0696(2017)12-102-08

劉韜)