基于超级时空网络的公交车辆调度模型及3M进化算法

何胜学

摘要： 针对在时刻表给定条件下如何减少空驶车次和实现具有工作时间公平性的公交车辆调度问题，建立了基千超级时空网络的模型，并设计了一种具有混生、变异和成长三种基本操作的进化求解算法。首先利用超级网络理念，将出场弧、入场弧、接续、实际车次和空驶车次在时空上整合为一个连通的有向超级时空网络。基千超级网络中流量守恒概念，建立了公交车辆调度模型，并通过合理转化将工作时间公平性约束变为具有简单加和特征的目标函数项。利用可行车次覆盖集合的拓扑结构特征，设计了将多个可行解混合后生成新解的混生算子；通过搜索具有回路特征的接续，实现对可行解构成元素的变异操作；通过建构指派网络、计算指派网络中联接的费用，并利用匈牙利算法求解对应指派问题，实现对可行解的成长操作。以上述操作为基础提出了一种新的“3M"进化算法。通过实证分析，验证了模型的合理性与算法的有效性。研究发现：减少空驶车次与平衡车次链之间的实际车次运行时间之间存在相互制约的矛盾，但是与所需的公交车总数不存在必然联系。

关键词   公共交通，车辆调度，超级网络，智能优化，自适应

Transit  vehicle  scheduling  model  and  3M  evolutionary algorithm  based  on  super  

spatiotemporal  network

HE   Shengxue

Abstract:   In order to reduce the number of deadheading trips and realize the equality of working hours with the given bus timetable, this paper formulated a super spatiotemporal-based transit vehicle scheduling model and designed an evolutionary algorithm including mixed creation, mutation, and mature operators. Firstly, this study used the super-network conception to combine pulling out arcs, pulling in arcs, connectors, actual trips, and deadheading trips into a super spatiotemporal network. Based on the flow conservation conception in the super-network, this study built a vehicle scheduling model and transformed the constraint of working time equality into an addable item of objective. In view of the topological feature of the set of trip coverings, this paper designed a mixed creation operator to generate a new solution with several known feasible solutions. By searching the connectors with loop feature, this paper realized the mutation operator to the elements of feasible solution. The mature operator consists of formulating an assignment network, computing the cost of links in the assignment network, and obtaining the optimal match by the Hungarian algorithm. Based on the above three operators, this paper proposed a new/3M0evolutionary algorithm. The numerical analysis verified the rationality of the new model and the effectiveness of the new algorithm. This research discovers that there is a mutual restriction relationship between reducing deadheading trips and equalizing the actual trip times among trip chains, but they both have no obvious connection with the fleet size.

Keywords: public transportation, vehicle scheduling, super-network, intelligent optimization, self-adaptation

运筹学学报

Operations Research Transactions

网络首发时间：2022-04-25 14:48:21

网络首发地址：https://kns.cnki.net/kcms/detail/31.1732.O1.20220424.1048.002.html