多班型公交调度的超级时空网络模型及双层邻域搜索算法_何胜学.pdf

第 40 卷第 2 期2023 年 2 月公路交通科技Journal of Highway and Transportation esearch and DevelopmentVol.40No.2Feb 2023收稿日期:20210322基金项目:国家自然科学基金项目(71801153，71871144);上海市自然科学基金项目(18Z1426200)作者简介:何胜学(1976)，男，陕西三原人，副教授，博士(lovellhe )。doi:10.3969/j.issn.10020268.2023.02.020多班型公交调度的超级时空网络模型及双层邻域搜索算法何胜学(上海理工大学管理学院，上海200093)摘要:为了在多班型条件下减少公交车空驶时间和在人车固定搭配模式下实现乘务组之间工作时间的平衡，建立了基于超级时空网络的公交调度模型，并设计了具有 2 层邻域搜索的模型求解算法。通过构建调度的超级时空网络，将不同值班类型利用车场的不同时空起终点对加以区分，并将车辆的出入车场、发车点停留和空驶转化为对应的时空网络节点或弧段。根据不同班型工作时间范围的差异，在单一班型对应的车次链集合上通过车次链的分割与重组设计了贪婪式邻域搜索。通过分割当前的车次间的联接，并搜索所有可行关联车次，得到一个指派问题。通过求解上述指派问题，得到对应当前分割的最佳替代新联接。而在不同班型的车次链之间，设计了重叠时段内的车次链整体交换式随机优化邻域搜索。这里需首先确定不同班型间的重叠时段，并建立重叠时段内部分车次链集合。通过在上述集合内部分车次链的随机交换，搜索了具有较好目标值的新一组的整体车次链。整合 2 个不同层面的邻域搜索，构建了新的双层邻域搜索算法。实证分析证实了模型与算法的有效性。结果表明:最小化空驶时间和平衡车次链间的工作时间之间存在相互制约的矛盾关系，实际应用时需加以权衡;2 类邻域搜索可分别加以应用，也可组合使用，而组合的效果最佳，单独应用同一班型内邻域搜索的效果次之。关键词:交通工程;超级网络;组合优化;车辆调度;乘务调度;邻域搜索中图分类号:U491，TP391文献标识码:A文章编号:10020268(2023)02016209Super Spatio-temporal Network Model with Multiple Working Types andIts Bi-level Neighborhood Search AlgorithmHE Sheng-xue(School of Business，University of Shanghai for Science and Technology，Shanghai 200093，China)Abstract:In order to reduce deadheading time and balance the working time between crew members in thefixed matching mode of people and vehicles in the situation of multiple working types，a transit schedulingmodel based on super time-space network is formulated and an algorithm with bi-level neighborhood search isdesigned to solve the model.By constructing the super time-space network associated with scheduling，thedifferent working types are distinguished by using the different nodes of depot in the time-space network，andthe pulling out/in depot，stopping at departure station and deadheading travel are transformed into nodes andarcs of the time-space network.According to the difference of working time range of different working types，a greedy neighborhood search based on partitioning and combining trip chains associated with a given workingtype on the set of trip chains is designed.By partitioning the connection between current trips and searchingall feasible associated trips，an assignment problem is obtained，and the new optimal connection associatedwith the current partition is obtained by solving the above assignment problem.Among the trip chains第 2 期何胜学:多班型公交调度的超级时空网络模型及双层邻域搜索算法corresponding to different working types，a stochastic optimization neighborhood search based on exchangingthe overall trip chain in the overlapping time interval is designed.The overlapping time intervals betweendifferent working types should be determined first and then the partial of trip chains in the overlapping timeinterval should be formed.By randomly exchanging the partial trip chains in above set，a new group of tripchains with better objective values is searched Combing the 2 neighborhood searches in different levels，anew bi-level neighborhood search algorithm is established.The Empirical analysis proved the effectiveness thenew model and algorithm.The result shows that(1)there is a contradicted relationship between minimizingthe deadheading time and balancing the working time among trip chains，and a trade-off is required when dealwith them in practice;(2)two neighborhood searches can be implemented separately or together，thecombination application can achieve the best performance followed by the performance of only carrying outneighborhood search in a given working type.Key words:traffic engineering;super-network;combinational optimization;vehicle scheduling;crewscheduling;neighborhood search0引言公交车辆和乘务调度是公交运营管理的核心业务，也是公交规划管理的研究热点之一。以人车固定搭配为主、多种值班类型共存的公交运营模式在我国许多城市被广泛采用。尽管针对公交调度的文献众多，但是针对上述模式的公交调度研究甚少，鲜有针对多种值班模式的深入建模分析，这也造成实践中该类模式下公交调度的随意性和无效率。针对上述问题，本研究尝试利用超级网络理念，将问题转化为超级网络中的特殊网络流路径问题，并通过分析问题可行解的网络拓扑形式，从同一班型内部和不同班型之间 2 个层面对车次链进行分割重组操作，实现调度中减少车辆空驶时间和平衡各乘务组之间工作量的目标。下面从公交车辆调度和车辆与乘务组合调度 2个方面简要介绍当前的国内外相关研究。在一般化的公交车辆调度研究方面，针对交通拥堵等随机因素对车辆运行计划的影响，文献 1 提出了一种 3阶段解决方法。针对给定的乘车需求的降低，文献 2 建立了相应的线性优化模型来在多种车辆条件下确定最小的车辆数。在假设司机开始工作时间无限制和休息时间不固定条件下，文献 3 建立了公交车辆和乘务调度的混合整数规划模型。在多车场条件下，文献 4 提出了通过微调部分车辆的发车时间进一步提升公交车辆的利用率。文献 5 在多车场条件下比较了数种启发式车辆调度方法，并给出了一种修复不可行解的方法。为提高计算效率，文献 6 提出在利用列生成算法求解多车场车辆调度问题时改用基于车次的分解方法。为了减少由于时刻表制订与车辆调度分开决策而可能增加的车辆需求，文献 7 建立了将二者统一决策的优化模型。文献 8 提出利用跳站策略在减少乘客等车时间和车辆数目条件下协同决策自动驾驶班车的时刻表和车辆的调度。以班次时间接续、乘务组劳动强度、车场能力等为约束条件，以最小化乘务组的车场驶入与驶出成本、停留等待成本和空驶成本为目标函数。文献 9 建立了多车场公交乘务排班问题的数学模型。文献 10 提出通过交换 2 条已定车辆路线来恢复和处理多车场条件下的车辆的延误和额外增加的任务。另外，近年来研究者也分别从电动公交的数量、充电约束、半自动和自动驾驶差异、无人驾驶公交的调度策略选择等不同角度对特殊类型公交车的调度问题进行了深入研究1118。在车辆与乘务的组合调度方面，文献 19 在考虑用餐时间窗约束条件下，给出了整合公交车辆和乘务调度的优化模型。针对由于搜索二叉树的节点数呈指数级增长所导致的传统列生成方法难以有效处理较大规模乘务调度的问题，文献 20 提出利用线性松弛解信息，逐次确定不被使用的换班机会集，将问题转化为一系列规模逐次缩小的乘务调度问题。文献 21 基于裁剪变邻域搜索算法求解乘务调度问题，在模拟退火算法中设计了 2 种带概率的复合邻域结构以增加搜索的多样性，帮助算法跳出局部最优。文献 22 对公共交通驾驶员调度研究进行了系统的梳理和总结。与现有研究相比，本研究的特色主要表现为:(1)通过超级时空网络区分公交调度的不同值班类型，并利用网络元素间的关联关系刻画公交调度中车辆出入车场、站点停留、空驶和实际车次运行的361公路交通科技第 40 卷逻辑关系，深化对公交调度的认识，为设计有效调度方法提供新的视角。(2)以联接 2 个车次的接续为着眼点，在相同班型车次链中搜索可替换的接续，通过车次链的分割重组，生成使得目标函数为局部最优的新替代车次链。(3)针对不同值班类型规定的工作时间范围差异，在 2 个给定班型的重叠时间段内，确定可交换的部分车次链，通过部