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

摘要

为了在多班型条件下减少公交车空驶时间和在人车固定搭配模式下实现乘务组之间工作时间的平衡,建立了基于超级时空网络的公交调度模型,并设计了具有2层邻域搜索的模型求解算法。通过构建调度的超级时空网络,将不同值班类型利用车场的不同时空起终点对加以区分,并将车辆的出入车场、发车点停留和空驶转化为对应的时空网络节点或弧段。根据不同班型工作时间范围的差异,在单一班型对应的车次链集合上通过车次链的分割与重组设计了贪婪式邻域搜索。通过分割当前的车次间的联接,并搜索所有可行关联车次,得到一个指派问题。通过求解上述指派问题,得到对应当前分割的最佳替代新联接。而在不同班型的车次链之间,设计了重叠时段内的车次链整体交换式随机优化邻域搜索。这里需首先确定不同班型间的重叠时段,并建立重叠时段内部分车次链集合。通过在上述集合内部分车次链的随机交换,搜索了具有较好目标值的新一组的整体车次链。整合2个不同层面的邻域搜索,构建了新的双层邻域搜索算法。实证分析证实了模型与算法的有效性。结果表明:最小化空驶时间和平衡车次链间的工作时间之间存在相互制约的矛盾关系,实际应用时需加以权衡;2类邻域搜索可分别加以应用,也可组合使用,而组合的效果最佳,单独应用同一班型内邻域搜索的效果次之。

Abstract

In order to reduce deadheading time and balance the working time between crew members in the fixed matching mode of people and vehicles in the situation of multiple working types, a transit scheduling model based on super time-space network is formulated and an algorithm with bi-level neighborhood search is designed to solve the model. By constructing the super time-space network associated with scheduling, the different working types are distinguished by using the different nodes of depot in the time-space network, and the pulling out/in depot, stopping at departure station and deadheading travel are transformed into nodes and arcs 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 working type on the set of trip chains is designed. By partitioning the connection between current trips and searching all feasible associated trips, an assignment problem is obtained, and the new optimal connection associated with the current partition is obtained by solving the above assignment problem. Among the trip chains corresponding to different working types, a stochastic optimization neighborhood search based on exchanging the overall trip chain in the overlapping time interval is designed. The overlapping time intervals between different working types should be determined first and then the partial of trip chains in the overlapping time interval should be formed. By randomly exchanging the partial trip chains in above set, a new group of trip chains with better objective values is searched. Combing the 2 neighborhood searches in different levels, a new bi-level neighborhood search algorithm is established. The Empirical analysis proved the effectiveness the new model and algorithm. The result shows that (1) there is a contradicted relationship between minimizing the deadheading time and balancing the working time among trip chains, and a trade-off is required when deal with them in practice; (2) two neighborhood searches can be implemented separately or together, the combination application can achieve the best performance followed by the performance of only carrying out neighborhood search in a given working type.

关键词

交通工程 / 超级网络 / 组合优化 / 车辆调度 / 乘务调度 / 邻域搜索

Key words

traffic engineering / super-network / combinational optimization / vehicle scheduling / crew scheduling / neighborhood search

引用本文

导出引用

何胜学. 多班型公交调度的超级时空网络模型及双层邻域搜索算法. 公路交通科技. 2023, 40(2): 162-170,245 https://doi.org/10.3969/j.issn.1002-0268.2023.02.020

何胜学. Super Spatio-temporal Network Model with Multiple Working Types and Its Bi-level Neighborhood Search Algorithm. Journal of Highway and Transportation Research and Development. 2023, 40(2): 162-170,245 https://doi.org/10.3969/j.issn.1002-0268.2023.02.020