摘要

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