基于客运需求的城乡公交动态路径问题研究

郗文彬 ，宋瑞* ，何必胜，刘星材

(1.北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京 100044;2.北京交通大学交通运输学院，北京 100044)

近年来，随着我国城镇化进程的加快，乡镇之间、城乡之间的联系日益紧密，带来了城乡之间、乡镇之间客流量的增加，同时显露了农村(乡镇)客运的一些问题。虽然现在农村的不少线路有了客运班车，但线路分布不够合理，有的线路客源少，车辆多;有的线路有一定的客流量，但配置不完善，居民出行有时无车可乘。由于现有的农村客运班车的营运路线、班次都是按平时的客流量进行配置的，而农村客流波动较大，班次过密，将增加运营成本;但是一旦班次减少，到客流高峰时期，又会造成居民出行无车可乘。许多学者针对城乡公交运营管理进行了研究，文献［1 -2］在对我国农村客运的发展现状进行分析的基础上，提出继续推进农村客运班线公交化改造、调整班车的运营线路或新增客运线路班次等发展对策;文献［3］对城乡公交线路特征进行了分析，对比了与城市公交的不同，并介绍了其客流特征;文献［4］提出利用农村公交区域化的发展模式解决城乡公交问题。城乡公交不同于城市公交，城市公交客流需求比较稳定，公交车辆行车路线固定;而城乡公交客流波动较大，人员比较分散，线路灵活。针对城乡公交的特点，结合现在的农村客运班车营运适时信息查询技术［5］，可以将动态路径公交服务应用于城乡公交系统中。客运中心根据出行居民发来的信息，安排发车数量及车辆的行驶路径，并不断调整行车路径。

目前，动态车辆路径问题(DVRP)是车辆路径问题研究的热点，很多学者都对该问题进行了模型和算法研究［6-7］。关于动态车辆路径在实际问题中的应用也得到了学者们的关注，文献［8］用动态车辆路径问题的思想处理物流配送问题;文献［9］介绍了基于实时信息的动态车辆路径问题及应用;文献［10］介绍了动态车辆路径问题在产品速递中的应用。但是，目前的研究中将动态车辆路径问题应用于公交调度的较少。本文将动态路径公交服务应用于城乡公交，在满足客运需求的前提下，找到公交运行的实时最短路径，合理安排发车车辆，以降低车辆运营成本。

1 问题描述

我国很多城市的公交呈3 级结构，分别为城区公交(服务城市内部)、城乡公交(服务城区与乡镇、乡镇内)和村镇公交(乡镇与农村、农村内)。从广义上讲，城乡公交包括城市与农村地区的公共客运交通。狭义上讲，城乡公交是指城区与乡镇或中心镇与村之间的公共客运系统。本文研究的城乡公交指的是乡镇与村之间的公共客运交通。城乡公交线路客流具有以下特征:(1)时间分布特征。农村客流的季节分布特征主要是节前进城务工人员、学生回家，节后务工人员、学生回城。乡村居民出行日分布特征是上午、中午、晚上形成高峰。(2)空间分布特征。不同农村客运线路的客流强度差别可能会很大，一条线路的不同区段或断面流量也会有很大的差异性，这种特性构成了客流的空间分布特征［11］。

针对农村客运存在的问题，综合考虑城乡居民出行特征，结合现在的农村客运班车营运适时信息查询技术，将动态车辆路径问题引入城乡公交研究中。将城乡公交区域内有客运需求的村庄看成一系列需求点，客运中心看成服务点，根据接收到的居民出行信息，确定合适的行车路径安排公交车辆通过。同时，如果在整个客流运送中适时动态需求很频繁，则计算很复杂，计算量很大。本文引入“时间段”［6］的概念，根据客流动态需求的特点，按照一定规则，将整个公交运营时间分为若干个相等或不等的时间段来处理，在每一个时间段的结束时刻，实行动态客流需求的插入。车辆发车前能获得新的客流需求信息，在每一个时间段已发出的车辆不再调整运行路线，将动态车辆路径问题转化为一系列静态问题，如图1 所示。由于客运中心的车辆数是有限的，每辆车的载客容量也有限制，所有车辆肯定是从客运中心出发途经各个村庄接送乘客后回到客运中心，因此必须考虑这些约束条件的限制。公交运营公司在满足客运需求和为居民提供便利的公交服务的前提下，最关心的是运营成本最小化，所以我们要到达的目标就是车辆的运营成本最小。

图1 适时客流信息处理流程图Fig.1 In-time processing flowchart of passenger flow information

2 优化模型的建立及求解

本文研究的动态路径公交服务问题为:一个中心客运站，拥有容量为Q 的车辆K 辆，负责对N 个村庄进行旅客接送工作。其中村庄数为i(i=1，2，…，N)，划分时间段t，在每个时间段发车前能获得各个村庄的客运需求信息，如果村庄i 有客运需求则安排车辆途经此村庄，反之则不途经此村庄，据此调整车辆的行车路径和发车数量。求在满足客运需求的前提下，在每个时间段t 使车辆的总运营成本最小。

模型存在以下几个假设:(1)只存在村庄到乡镇之间的客流，村庄与村庄之间的客流由于客流量较小，距离短不作考虑;(2)居民不是很关心出行时间，只要在此时间段上车就行;(3)在每个时间段若客流量较小(一般低于车辆载客量的一半)则暂不发车，并将当前客流累积到下一个时间段，但每小时至少发一班车。

2.1 符号说明

参数和变量的一般定义:O 表示中心客运站，N 表示服务的村庄点的数目，K 表示中心客运站的车辆总数，Kt表示在t 时间段客运中心剩余车辆数，rt表示在t 时间段回到客运中心的车辆数，Q 表示车辆的最大载客容量，t 表示时间段，git表示村庄点i 在t 时间段的客运需求量，qtik表示第k 辆车在时间段t 在村庄i 的载运客流量，c 表示单公里油耗成本，lij表示村庄i 到村庄j 之间的距离，v 表示车速，sij表示从村庄i 到村庄j 之间的运营成本，

2.2 约束条件和目标函数

综合考虑车辆数限制，车辆载客容量限制，车辆由客运中心出发、再回到客运中心的约束，以总运营成本最小为目标函数的动态车辆路径问题优化模型如下:

其中，式(4)表示在任意t 时间段所有接送旅客的车辆数目不能超过客运中心剩余车辆数;式(5)表示在任意t 时间段更新客运中心车辆数;式(6)～(7)表示保证车辆都是从客运中心出发，再回到客运中心;式(8)表示网络流平衡约束;式(9)表示每个有客运需求的村庄乘客被接送;式(10)表示每辆车在t 时间段的所有载客量不能超过车辆的最大载客容量;式(11)表示决策变量。

2.3 模型求解

上述模型为0-1 整数规划模型，且模型针对的是城乡公交。由于将问题分解为每个时间段，因此解空间相对较小，商业数学优化软件就可以满足求解需求，不必设计算法，因此，本文采用Lingo12.0 优化软件进行求解。而且在满足所有约束的条件下，在任意时间段总能找到途经各个需求村庄的最佳行驶路径并确定发车数量，所以一定存在最优解。

3 算例

选择留史镇城乡公交作为实例研究，验证本文设计模型的有效性。

3.1 算例数据

留史镇面积59.62 km2，人口5.36 万人。管辖西王村、朱佐、中白楼、南白楼、北白楼、缪家营、杜家庄、大王村、李家佐、代家庄、曹佐、臧家营、东侯佐、刘家营、西侯佐15 个行政村，为了简便15 个行政村分别用数字1～15 表示，客运中心用0 表示。划分时间段t，考虑出行客流高峰时期，选取早上7:00～8:00 和下午13:00～14:00 两个客流高峰时段，每10 min 划分一个时间段;N 为15;K 为10;Q 为32;c 为2.355 元/km。村庄i到村庄j 之间的距离(km)lij见表1。

表1 村庄到村庄之间的距离(单位:km)Table 1 The distance between villages i and j (Unit:km)

当天各个村庄在每个时间段的客运需求量git见表2。

表2 各个村庄在每个时间段的客运需求量(单位:人次)Table 2 Passenger transport demand of all villages at every time section

3.2 算例求解及结果分析

用lingo12.0 求解，最终求解结果见表3。

表3 算例求解结果Table 3 Solution result of a computation case

在上午7:00～8:00，第一个时间段客流量为4，累积到第二个时间段客流量为11，低于车辆载客量的一半，暂不发车，客流量累积到第三个时间段。在第三个时间段客流量为31，发出一辆车。第四个时间段客流量为32，发出一辆车。第五个时间段客流量为7，客流量较小暂不发车，客流量累积到第六个时间段。第六个时间段客流量为31，发出一辆车。在下午13:00～14:00，第一个时间段客流量为58，发出两辆车。第二个时间段客流量为31，发出一辆车。第三个时间段客流量为23，发出一辆车。第四个时间段客流量为28，发出一辆车。第五个时间段客流量为13，低于车辆载客量的一半，暂不发车，客流量累积到第六个时间段。第六个时间段客流量为60，发出两辆车。

客运中心在每个时间段内根据适时信息客流量的大小决定是否发车，若客流量较小，一般低于车辆载客量的一半则暂不发车，但是每小时最少发一班车。实现了根据客流的波动安排发车，同时由于得到每个村庄的适时客流需求信息，总能找到适时最短路径。如在上午7:00～8:00 第三个时间段原来的行车路线为0 -1 -8-14 -6 -12 -5 -3 -4 -9 -2 -10 -11 -15 -13 -0运营成本为85.25，大于优化后的目标值80.07，优化前后的线路如图2 所示。

图2 第三个时间段优化前后对比分析Fig.2 Comparison analysis of pre-optimization and prooptimization at the third time section

4 结语

本文将动态路径公交服务应用于乡镇与村之间的城乡公交，构建了城乡公交动态路径优化模型，并以留史镇为实例验证模型的有效性。验证结果表明，这种动态路径城乡公交能在满足客运需求的前提下，为居民提供便利的公交服务。结合适时信息查询技术，在每个时间段根据适时信息客流量的大小安排发车，并为车辆安排成本最小路径运行，可以降低公共交通部门的运营成本。

［1］闫淑华.农村客运现状与发展探讨［J］.中国城市经济，2011(18):320 -323.

［2］翁志新.新时期农村道路客运发展的现状与对策［J］.交通世界(运输.车辆)，2011(6):184 -186.

［3］周业利，李鹏飞，杨超.城乡公交线路特征及其客流特征分析［J］.交通标准化，2011(21):59 -63.

［4］沈吟东.农村客运改革:公交化及区域模式［J］.中国软科学，2009(S1):40 -46.

［5］郑长安，张起森，黎茂盛.农村客运班车运营适时信息手机查询技术及其应用［J］.湖南交通科技，2011，37(4):180 -182.

［6］钱艳婷，王鹏涛，魏国利.动态车辆路径问题的算法研究［J］.天津理工大学学报，2010，26(6):72 -74.

［7］胡明伟，唐浩.动态车辆路径问题的多目标优化模型与算法［J］.深圳大学学报:理工版，2010，24(2):230 -234.

［8］WEN M，CORDEAUB J F，LAPORTE G，et al.The dynamic multi-period vehicle routing problem［J］.Computers ＆ Operations Research，2010，37(9):1615 -1623.

［9］LIAO T Y，HU T Y.An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information［J］.Expert Systems with Applications，2011，38(10):12548 -12558.

［10］FERRUCCI F，BOCK S，GENDREAU M.A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods［J］.European Journal of Operational Research，2013，225(1):130 -141.

［11］王建军，过秀成，吴能萍，等.农村客运客流特征及班线组织方式分析［C］//交通与物流:第六届交通运输领域国际学术会议论文集，大连:大连理工大学出版社，2006.