考虑时间窗的通勤定制公交线路优化_杜太升.pdf

第21卷 第1期2023年03月交通运输工程与信息学报Journal of Transportation Engineering and InformationVol.21 No.1Mar.2023文章编号：1672-4747（2023）01-0011-12考虑时间窗的通勤定制公交线路优化考虑时间窗的通勤定制公交线路优化杜太升，陈明明*（兰州交通大学，交通运输学院，兰州 730070）摘要：针对常规定制公交线路规划方法不能满足乘客高峰通勤需求等问题，在考虑乘客期望时间窗和最大容忍时间窗的基础上，引入柔性时间窗的概念，基于通勤者居住地与工作地时空分布差异性特点分别设置上下车站点罚函数，以车辆固定成本、车辆运行成本、车辆延误惩罚成本和未提供乘车服务惩罚成本之和最小为优化目标，以时间窗、运行距离和最大站点数量等为约束，建立考虑柔性时间窗的通勤定制公交线路优化模型。在兰州市通勤乘客数据基础上，选取两组大小不同规模的算例集，使用Gurobi和传统TS算法求解小规模算例与基于目标控制原则的动态禁忌长度TS算法求解大规模算例验证模型有效性。结果表明，在小规模算例中Gurobi求解可得到较优的目标值，但随着数据规模的增加其求解效率逐渐劣于TS算法，设置柔性时间窗车辆提供乘车服务的人数比硬时间窗背景下增加了276人，且有效规避了软时间窗背景下车辆到达末站点的时刻波动。本文所提方法在均衡乘客和运营方利益的同时，可通过调节柔性系数产生多元化的运行方案，能够为通勤定制公交运营及管理提供决策支持。关键词：交通工程；柔性时间窗；禁忌搜索算法；定制公交；路径优化中图分类号：U491.1+2文献标志码：ADOI:10.19961/ki.1672-4747.2022.08.010Optimization of customized bus routes for commuting consideringtime windowsDU Tai-sheng,CHEN Ming-ming*(School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China)Abstract:Conventional customized bus route planning methods cannot meet the peak commutingdemand of passengers.Therefore,to address this shortcoming,the concept of a flexible time windowis introduced based on passenger expectation time window and maximum tolerance time window.The penalty function of boarding and alighting stations is set separately based on the spatial and tem-poral distribution differences between commutersresidences and workplaces.The sum of vehiclefixed cost,vehicle operation cost,and vehicle delay penalty cost and failure to provide ride serviceare set as the optimization objectives,whilst the flexible time window,operating distance,and maxi-mum number of stops are used as constraints to establish the optimization model of customized com-muter bus routes considering the flexible time window.Based on the data of commuter passengers inLanzhou City,two small-scale and large-scale cases were selected,and the proposed model was veri-fied using Gurobi and the traditional TS algorithm to solve the small-scale cases and the dynamic ta-boo length TS algorithm based on the objective control principle to solve the large-scale cases.Theresults show that,as the data size increases,the Gurobi solution can obtain better target values in收稿日期：2022-08-17录用日期：2022-10-28网络首发：2022-11-27审稿日期：2022-08-1708-22；08-2809-06；10-0310-14；10-2410-28基金项目：甘肃省自然科学基金项目（21JR1RA244）作者简介：杜太升（1996），男，硕士研究生，研究方向为公交运营与管理，E-mail：通信作者：陈明明（1982），男，副教授，博士，研究方向为公交运营与管理，E-mail：引文格式：杜太升，陈明明.考虑时间窗的通勤定制公交线路优化J.交通运输工程与信息学报，2023，21(1)：152-163.DU Tai-sheng,CHEN Ming-ming.Optimization of customized bus routes for commuting considering time windowsJ.Journal ofTransportation Engineering and Information，2023，21(1)：152-163.small-scale cases,however,its solution efficiency becomes progressively inferior to that of the TS al-gorithm.In addition,the number of rides provided by vehicles in the flexible time window increasedby 276 people compared with that in the hard time window background,and the fluctuation of the ve-hicle arrival time at the end station in the soft time window background was effectively avoided.Themethod proposed in this paper can balance the interests of passengers and operators,whilst simulta-neously generating diversified operation schemes by adjusting the flexibility factor,which can pro-vide decision support for customized commuter bus operation and management.Key words：traffic engineering;flexible time window;tabu search algorithm;customized bus;routeoptimization0引言定制公交通过集合个体出行需求，为乘客提供定制的专线或者规划合乘线路的高品质出行服务，根据其功能特性可将定制公交分为通勤定制公交、交通客流集散地定制公交、商务定制公交和其他类型定制公交，其中通勤定制公交是以通勤乘客出行需求为导向，响应高峰时段居民通勤出行的运营模式。时间特性和空间特性是通勤乘客出行研究中最为基本的指标，也是通勤定制公交线路设计中的基础，国内外很多学者都从时空特征出发对通勤定制公交线路优化问题进行了深入的研究，其大致可分为以下几方面：（1）考虑通勤出行需求空间特征的路径优化问题。陈汐等1构建了多区域通勤定制公交线路优化模型并设计两阶段启发式算法进行求解；柳伍生等2构建了多需求响应机制下的定制公交线网优化模型，设计上车线网和下车线网相结合的分层线网算法。（2）以通勤乘客时间特性为基础的路径优化问题。如Guo等3考虑了公交站点时间窗的影响，在线路和乘客分配同时优化的基础上建立了混合整数规划模型，通过精确算法（分支定界法）和启发式方法（遗传算法和禁忌搜索算法）对模型求解并进行数值比较；杨明等4构建了一个考虑软时间窗，兼顾运营公司和乘客利益、满足多个上下车站点和多车型的定制公交线网优化模型；王健等5将因公交准点率差所造成的乘客损失转化为当量运营里程，建立了考虑时间窗的定制公交调度优化模型，基于虚拟源站点将问题转换为多旅行商问题，并设计了贪心算法和遗传算法对问题进行求解；Lang6基于乘客出行时间窗和运营成本对定制公交线网进行优化，利用 Lingo 软件对模型求解。（3）基于时空特性的定制公交线路优化问题。如温冬等7根据出行需求的时空离散特性，构建了考虑时间窗的定制公交时空分层优化模型，通过遗传算法对模型进行求解；程仁辉8从时空角度出发，建立了通勤定制公交线路双层规划模型并设计了一种改进的遗传算法；吴镇宇9基于分时段时间窗特性构建了上车区域的路径优化模型和单车辆的下车区域行车路径优化模型，并设计启发式算法和遗传算法进行求解。乘客的出行具有差异性，定制公交需发展多元化的运营模式满足不同场景下乘客的出行需求，如Li等10构建混合整数线性规划（MILP）模型以满足多样化的通勤出行请求，提出了一种基于列生成的启发式方法验证模型和算法的有效性。胡郁葱等11结合定制公交运营特征，构建了多起终点、多车型和乘客混载等运行模式下的多目标组合优化模型。Sun等12基于估计的时空乘客需求以总成本最小化为目标的混合整数非线性模型，采用多车型提高车辆利用率、降低供应商成本，提出了一种混合遗传算法。申婵等13提出一种基于可靠性最短路的线路优化方法，以乘客和定制公交运营商总成本最小为目标，使用禁忌搜索算法对模型进行求解。上述研究大部分是在静态需求场景下进行的，随着信息技术的发展，定制公交需响应一定范围动态乘客的出行请求，针对此，Huang等14提出了一种由两阶段组成的优化模型动态插入乘客请求（动态阶段）和基于整体需求静态优化服务网络（静态阶段），解决了预约背景下实时预约乘客的线网优化问题；Wang等15研究了基于静态乘客和动态乘客请求的实时定制公交多目标优化模型，设计了两阶段NSGA-II算法求解。定制公交可以根据乘客需求灵活安排站点、线路和时刻表，因此可以为出行者提供高质量的公交服务，根据通勤者出行起讫点的时空特性提供准时的通勤服务是其运营的核心16，现有文献中，通勤定制公交的路径优化问题未能体现出行起终点的时空差异性，且大部分模型仅通过常规杜太升 等：考虑时间窗的通勤定制公交线路优化153第1期运行模式中设置软时间窗罚函数或硬时间窗约束提高通勤准时性，无法满足通勤乘客的出行需求。本研究根据乘客通勤场景将出行区域划分为上车站点和下车站点并分别设置上下车站点罚函数，引入柔性系数刻画柔性时间窗，构建以总成本最少为优化目标的考虑柔性时间