一种多目标的公交线网规划模型*

胡继华，高立晓，梁嘉贤，蔡 铭

(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

刘韬)