HU Di,JIN Wenzhou.Flex-route demand response transit scheduling based on station optimization[J].Journal of Shenzhen University Science and Engineering,2022,39(02):209-215.[doi:10.3724/SP.J.1249.2022.02209]
School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, Guangdong Province, P. R. China
transportation engineering; public transit; demand response transit; flex-route; route planning; station location
DOI: 10.3724/SP.J.1249.2022.02209
备注
引言
需求响应公交（demand response transit，DRT）是指无固定运行线路及站点，依据乘客需求前往预约地点，为乘客提供出行服务的一种公共交通服务模式．线路可偏移式需求响应公交是一种改进的新型公交[1]，其结合了传统固定线路式公交低成本和需求响应公交灵活的特点，通常具有一条连接固定站点的线路，可服务固定站点上下车的乘客，同时可响应线路外的乘客预约需求．CURRIE等[2]通过研究近70年的需求响应公交发展情况，发现较多企业因高昂的运营成本而亏损，无法正常运营．因此，本研究考虑线路可偏移式需求响应公交，以更低的运营成本为乘客提供更好的公共交通出行服务，对提高公共交通系统的服务质量以及促进需求响应公交运营企业发展具有重要意义．
在线路可偏移式需求响应公交的研究方面，LI等[3]以乘客步行、等待及乘车时间最小为目标，研究了DRT和常规公交的适宜乘客需求密度区间，得到DRT适宜的密度为4～20人/km2．邱丰等[4]建立两阶段车辆调度模型，可处理乘客实时需求，并进行实例仿真，结果表明预约出行比例越高系统总成本越低．庞明宝等[5]研究响应公交站点外实时预约需求的公交调度系统，建立计划调度模型与响应实时需求的调度模型，并以单条线路进行实例分析，认为此调度系统可吸引更多乘客，从而提高企业经济效益．
在站点选址方面，叶秋君[6]考虑了固定站点乘客、备选站点乘客和运营企业的权益，建立了以系统总成本最低为目标的站点选址策略模型．靳文舟等[7]利用k-means聚类算法对乘客需求点进行聚类，获得有限个公交停靠站点，并建立以企业利润最大化为目标的DRT规划模型．庞明宝等[8]考虑到实际路网复杂性，引入节点重要度法，研究针对线路可偏移式DRT公交站点的评价方法，可有效评价站点布设合理性．
求解算法的改进方面，QUADRIFOGLI等[9-10]在模型中设计插入式算法，通过增加逻辑判断约束剔除低效解，最高可减少90%的计算时间，提高了求解效率．LIU等[11]设计分支切割算法求解模型，并使用实例验证算法的高效性．韩博文[12]将乘客需求分为静态需求和动态需求，建立考虑实时需求的公交调度模型，并运用遗传算法和精确算法求解．靳文舟等[13]研究考虑多车型和多运营模式的需求响应公交灵活调度模型，并设计混合遗传蚁群算法求解，提高了算法的精度和稳定性．
现有对于线路可偏移式需求响应公交的研究多以公交企业运营成本最低、乘客等待时间最少或服务乘客比例最高为优化目标建立模型，较少考虑以企业效益最大化为目标的模型；在站点选址方面，多以原有常规公交线路为基础，以原公交站点为固定站点，直接响应站外乘客需求，服务范围有限，而区域灵活性DRT由于计算量大，为提高求解效率而设计的算法复杂度高，导致研发成本与计算成本过高．为服务区域内的更多乘客，并降低服务成本，本研究考虑先以乘客需求确定固定站点和备选站点位置，再确定DRT基准运行线路，划定各个站点服务时段，针对服务时段内有限个站点需求，建立基于站点规划优化的需求响应公交调度模型．研究内容包括：①设计需求响应公交服务站点选取方法，使用以DBSCAN聚类算法和k-means聚类算法为基础的D-k-means聚类算法对乘客需求进行处理，根据聚类结果确定固定站点和备选站点；②设计新型预约机制，系统划定各区段的可被服务时间，乘客可选择合适的上车时间及站点；③建立线路可偏移式需求响应公交调度优化模型．
-
1 模型建立
1. 1 问题描述本研究提出的线路可偏移式需求响应公交服务模式如图1，根据预先收集的乘客预约情况，确定乘客预约需求量较多的固定站点和备选站点位置．在服务区域内规划连接所有固定站点的基准运营线路，备选站点分布在基准运营线路之外．公交车辆需依据乘客提出的乘车时间和地点要求，前往相应站点完成接送乘客出行的任务．
图1 服务模式Fig. 1 The operation mode
为提高运营调度效率，为服务区域添加服务时段划分层，即依据基准线路走向和长度，预估各固定站点间的运行时间，并基于乘客出行时间统计规律，初步划分服务时段与服务班次，乘客可选择合适的服务时间并提交预约信息，服务流程如图2．服务区域内的乘客在预约平台上提出预约请求，并选择上下车站点和上车时间．现有若干车辆从公交车场出发，为该服务区域内提出预约请求的部分乘客提供需求响应公交出行服务，需要根据乘客上下车站点位置和上车时间进行车辆路径规划，同时确定车辆的发车时刻及预计到达各站点的时间，并通知预约乘客乘车时间和预计到达时间．
图2 服务流程Fig. 2 The service flow
1. 2 模型假设本研究的线路可偏移式需求响应公交调度模型有如下基本假设：①乘客需在车辆发车前提交预约信息；②乘客提交预约信息后，不会更改或取消预约请求；③除了被拒绝的乘客，其他所有乘客将严格按照通知信息在约定时间窗内上车，并在预约下车站点下车；④乘客所需上车及下车时间保持恒定；⑤车辆运行条件良好，不考虑交通拥堵、交通事故及交通信号灯的影响，车辆启动和停车制动损失时间保持恒定，车辆运行速度恒定；⑥车辆车型与额定载客量已知；⑦车辆均从车场出发，完成运送任务后，回到车场；⑧为便于计算，以两点间直线距离作为车辆运行距离．
1. 3 参数变量设xij为0-1变量，当有车辆从i站点出发并到达j站点时， x ij=1，否则x ij=0； c 0为车辆的单位里程运行成本；Z为调度优化目标函数；V为区域内所有站点的集合；VG为所有固定站点的集合；Q为车辆的额定载客量；li为固定站点i计划最晚发车时间；tmax为基准线路相距最远的两个固定站点间的最长运行时间；ω为拒绝预约需求数量的惩罚权重系数；dij为计算得到的站点i与站点j间的直线距离；ti为车辆到达站点i的时间，特殊的是ta和tb分别为车辆到达相距最远的两固定站点的时间；tc为1名乘客上下车所需的时间；v为车辆在路段上的行驶速度；qi为在站点i上车的乘客数；di为在站点i下车的乘客人数；ui为离开站点i后，车上的乘客总数；N为所有站点总数；μi为站点序号．
1. 4 调度模型1. 4. 1 基准线路规划模型本研究线路可偏移式需求响应公交的基准线路规划模型为
约束条件为
其中，式（1）表示基准线路规划模型的优化目标是企业运营成本最小化；式（2）和式（3）表示必有车辆经过固定站点，且只经过1次；式（4）表示运行线路不会迂回；式（5）表示变量的取值限制．
1. 4. 2 线路可偏移式需求响应公交调度优化模型本研究建立的线路可偏移式需求响应公交调度优化模型为
约束条件为其中，式（6）表示线路可偏移式需求响应公交调度模型的优化目标为企业运营成本和拒绝预约需求数量最小化；式（7）和式（8）表示必有车辆经过固定站点，且只经过1次；式（9）和式（10）表示对于区域内所有站点，车辆至多到达并离开1次；式（11）表示站点p的前后状态一致，即有车辆到达并离开或无车辆经过该站点；式（12）表示运行线路不会迂回；式（13）表示车辆离开站点j后车上的乘客数量；式（14）表示车上的乘客数量始终小于车辆的额定载客量，并且大于在该站点上车的乘客数；式（15）表示被服务站点i和j之间的时间关系，车辆到达站点j的时间不会早于车辆离开站点i的时间、站点i乘客上下车花费时间及路段i、j间行驶时间之和；式（16）表示固定站点i的发车时间不晚于其最晚发车时间；式（17）表示基准线路相距最远的两点间实际运行时间小于限制的最大时间；式（18）表示变量的取值限制．
1. 5 模型求解1. 5. 1 站点聚类算法对需求数据进行筛选与聚类处理，确定固定站点和备选站点，从而提高需求响应公交路径规划效率，并降低计算成本和运营成本．由于k-means算法聚类结果受极端值影响较大[14]，本研究提出结合DBSCAN和k-means算法的D-k-means聚类算法，其可分为2个阶段：①使用DBSCAN聚类算法对原始需求点数据进行预处理，将需求点分为可聚类的点集与噪声点点集；②使用k-means算法对可聚类的点集进行聚类计算，将计算结果作为固定站点和备选站点．D-k-means算法的步骤如下．
输入 区域乘客历史出行点、预约出行点数据集A；参数邻域半径δ和最小数据点阈值Minpts，参数聚类数目k；
步骤1 计算数据集中每个点与其他各点间的距离；
步骤2 选取数据集中任意一点，若该点δ邻域内点的数量大于阈值Minpts，则将该点标记为核心点（class(i)≥1），并将其邻域内点划为一类（class(i)≥0），否 则 将 该 点 标 记 为 噪 声 点（class(i)=-1）；
步骤3 重复步骤2，直至所有点都被划分为类或被标记为噪声点；
步骤4 剔除数据集中的噪声点；
步骤5 选取包含核心点在内的k个点作为初始中心点；
步骤6 计算中心点和其他各点间的距离，将新数据集中的每个点划入与之距离最近的类；
步骤7 计算k类数据点中新的中心点；
步骤8 重复步骤6和步骤7，直至每一类中每个点与中心点之间的平方距离和收敛，所有数据点被划分入某一类并不再发生变化；
输出 聚类中心点坐标．
1. 5. 2 模型求解Gurobi是美国Gurobi公司开发的大规模优化器，具有良好求解性能，本研究通过编写python代码调用Gurobi优化求解器对调度模型进行求解．模型求解步骤如下．
输入 各站点位置、及乘客上下车人数与时间等信息；
步骤1 调用Model、GRB和quicksum模块；步骤2 创建模型；
步骤3 使用addVar设置变量和参数；
步骤4 使用setObjective和MINIMIZE创建企业运营成本和拒绝预约需求数量最小化目标函数；
步骤5 使用addConstr添加约束条件；
步骤6 使用optimize求解模型最优解；
输出 模型结果．
-
2 实例分析
为验证本模型的有效性，以中国广东省揭西县南部地区为例进行案例分析．通过互联网和实地调研的方式从揭西县南部获得部分乘客需求点地理位置信息，使用DBSCAN算法对乘客需求点数据进行预处理，将数据点划分为可聚类点和噪声点，使用Matlab软件绘制计算结果，如图3．
使用D-k-means算法筛选出6个噪声点，依据DBSCAN算法聚类结果和实际情况，取k=4，得到需求响应公交固定站点和备选站点，将固定站点和场站位置输入基准运行线路规划模型进行求解，得到基准运行线路长度为36. 57 km，如图4．
根据基准运行线路的长度和乘客在07∶00—09∶00的预约需求情况，假设车辆的运行速度为40 km/h，得到初始车辆调度时刻表，如表1．将乘客出行需求以站点序号表示，如表2．
将各时段乘客需求数据输入线路可偏移式需求响应公交调度模型，取拒绝预约需求数量的惩罚权重系数ω=1，得到车辆运行线路及实际调度时刻如表3和表4．
图3 乘客需求点位置Fig. 3 Passengersdemand locations
图4 基准运行线路Fig. 4 The basic vehicle route
表1 初始车辆调度时刻表Table 1 The initial vehicle schedule
表2 乘客出行需求统计1） Table 2 The passenger travel demand statistics
表3 上行班次调度时刻表Table 3 The up-line vehicle schedule
以上述64位乘客需求为例进行分析，假设车辆行驶速度为40 km/h，额定载客量为7人，固定成本为5元，变动成本为1元/km，每名乘客所需上下车时间为15 s，对常规公交、站点优化DRT和区域灵活式DRT服务效果进行对比，结果见表5．其中，常规公交、线路可偏移式DRT及区域灵活式DRT的服务乘客比例分别为92. 2%、 95. 3%及100%；常规公交的运行线路连接了4个固定站点和6个备选站点（站点5至站点10）；区域灵活式DRT响应了区域内所有乘客的需求．
表4 下行班次调度时刻表Table 4 The down-line vehicle schedule
表5 三种公交服务模式效果Table 5 Effects of the three bus service modes
算例通过服务乘客比例、运营成本及运行时间指标对3个系统的性能进行对比．①常规公交可服务于公交站点周边1 km的乘客，且无需乘客预约，但其服务比例较低，为92. 2%，无法满足部分乘客的特殊预约需求，如第2批次内从站点5出发的乘客和其他站外上下车的乘客；②线路可偏移式DRT的服务比例为95. 3%，无法服务位置偏远的乘客；③区域灵活式DRT的服务乘客比例为100%，可为服务区域内所有乘客提供接送服务，且不需要乘客前往服务站点．
以第1批服务为例对运营成本和运行时间进行说明：常规公交运营线路总长42. 4 km，需调度上行与下行两辆车服务每批次乘客，运营成本为94. 8元，单程固定运行时间为64 min，上下行车辆共用时128 min，需另加21名乘客5 min上下车时间，故服务总运行时间为133 min；站点优化DRT上行和下行车辆运行距离分别为41. 1 km和37. 0 km，运营成本为88. 1元，上行和下行运行时间分别为66 min和61 min；区域灵活DRT的上行和下行车辆运行距离分别为43. 7 km和44. 6 km，运营成本为98. 3元，上下行运行时间均为68 min．可见，站点优化DRT服务模式性能最优，且相较于区域灵活式DRT优势更为明显，运营成本由401. 7元降为365. 5元，下降了9%；运行时间由540 min降为513 min，下降了5%．此外，站点优化DRT求解时间平均约1 s；区域灵活式DRT求解时间波动较大，在需求数量较多时，求解时间较长，达到220 s．
-
结 语
针对需求响应公交运营成本高的问题，提出线路可偏移式需求响应公交服务模式，建立相应调度模型；提出了结合DBSCAN和k-means聚类算法的D-k-means聚类算法对乘客预约需求进行处理，以获得固定站点和备选站点位置，乘客可选取合适的站点并提出预约需求；本模型使用Gurobi求解器进行求解，可获得最优解．实例分析结果表明，线路可偏移式需求响应公交调度模型可行，算法求解速度较快且稳定，生成的调度方案具有较低的运营成本，可在需求密度较低的区域为乘客提供服务质量较高的公共交通出行服务．
- [1]BELLINI C, DELLEPIANE G, QUAGLIERINI C. The demand responsive transport services: Italian approach [M/OL]. Southampton, UK: Wit Press, 2003: 1-10. [2021-02-10]. https://www.witpress.com/elibrary/wit-transactions-on-the-built-environment/64/2707
- [2]CURRIE G, FOURNIER N. Why most DRT/Micro-Transits fail-What the survivors tell us about progress [J]. Research in Transportation Economics, 2020, 83: 100895.
- [3]LI Xiugang, QUADRIFOGLIO L. Feeder transit services:choosing between fixed and demand responsive policy [J]. Transportation Research Part C: Emerging Technologies, 2010, 18(5): 770-780.
- [4]邱 丰，李文权，沈金星. 可变线路式公交的两阶段车辆调度模型[J]. 东南大学学报自然科学版，2014， 44（5）：1078-1084. QIU Feng, LI Wenquan, SHEN Jinxing. Two-stage model for flex-route transit scheduling [J]. Journal of Southeast University, 2014, 44(5): 1078-1084. (in Chinese)
- [5]庞明宝，陈茂林，张 宁. 基于MAST的智慧公交优化调度研究[J]. 交通运输系统工程与信息，2017，17 （1）：143-149. PANG Mingbao, CHEN Maolin, ZHANG Ning. Scheduling optimization of intelligent public transport system based on MAST [J]. Journal of Transportation Systems Engi‐neering and Information Technology, 2017, 17(1): 143-149. (in Chinese)
- [6]叶秋君. 灵活式公交的响应站点选址问题研究[D]. 南京：东南大学，2017. YE Qiujun. Research on request stop location of flexible transit [D]. Nanjing: Southeast University, 2017. (in Chi‐nese)
- [7]靳文舟，郭献超，龚 隽. 基于精英选择遗传算法的需求响应公交规划[J]. 公路工程， 2020， 45（2）：44-49. JIN Wenzhou, GUO Xianchao, GONG Jun. Based on elitist selection genetic algorithm for demand responsive transit planning [J]. Highway Engineering, 2020, 45(2):44-49. (in Chinese)
- [8]庞明宝，张 宁，陈茂林. 基于节点重要度的MAST公交站布设评价研究[J]. 河北工业大学学报，2018， 47（6）：94-99，106. PANG Mingbao, ZHANG Ning, CHEN Maolin. Study on evaluation of MAST bus stop layout based on node impor‐tance [J]. Journal of Hebei University of Technology, 2018, 47(6): 94-99, 106. (in Chinese)
- [9]QUADRIFOGLIO L, DESSOUKY M M, PALMER K. An insertion heuristic for scheduling mobility allowance shuttle transit (MAST) services [J]. Journal of Scheduling, 2007, 10: 25-40.
- [10]QUADRIFOGLIO L, DESSOUKY M M, ORDÓÑEZ F. Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints [J]. European Journal of Operational Research, 2008, 185(2):481-494.
- [11]LIU Mengyang, LUO Zhixing, LIM A. A branch-and-cut algorithm for a realistic dial-a-ride problem [J]. Transpor‐tation Research Part B, 2015, 81(1): 267-288.
- [12]韩博文. 考虑实时需求的需求响应式公交调度方法研究[J]. 广西师范大学学报自然科学版，2019，37（3）：9-20. HAN Bowen. Demand responsive transit scheduling method considering real-time demand [J]. Journal of Guangxi Normal University Natural Science Edition, 2019, 37(3): 9-20. (in Chinese)
- [13]靳文舟，胡为洋，邓嘉怡，等. 基于混合算法的需求响应公交灵活调度模型[J]. 华南理工大学学报自然科学版，2021，49（1）：123-133. JIN Wenzhou， HU Weiyang， DENG Jiayi， et al. Flexible scheduling model of demand response transit based on hybrid algorithm [J]. Journal of South China Uni‐versity of Technology Natural Science Edition, 2021, 49 (1): 123-133. (in Chinese)
- [14]贺 玲，吴玲达，蔡益朝. 数据挖掘中的聚类算法综述[J]. 计算机应用研究，2007，24（1）：10-13. HE Ling, WU lingda, CAI Yichao. Survey of clustering algorithms in data mining [J]. Application Research of Computers, 2007, 24(1): 10-13. (in Chinese)
