公交车辆调度的超级时空网络模型及改进和声搜索算法

为了在公交车辆调度中减少车辆的空驶时间和在人车固定搭配模式下实现乘务组工作时间的公平性,建立了基于超级时空网络的车辆调度模型,并设计了求解模型的改进和声搜索算法.首先,将调度中涉及的车场、车次、接续、出场弧、入场弧和空驶车次转换为超级时空网络中的点或弧段;然后,基于构建的时空网络建立相应的公交车辆调度优化模型;接着,设计了综合利用和声记忆库和可行解空间信息来生成新和声的混生算子;同时,在时空网络中搜索回路式接续建立网络局部元素的指派网络,通过求解对应指派问题实现对声调的美化;最后,基于上述操作建立求解模型的改进和声搜索算法.研究发现:减少车辆的空驶时间和实现乘务组工作时间的公平性是一对相互制约的目标,同时优化时必须根据实际需求加以权衡;车次链之间的工作时间偏差大小与车队规模之间不存在单调依赖关系.

Super time-space network based transit vehicle scheduling model and modified harmony search algorithm

In order to reduce the deadheading time and realize the equality of working time among crews in transit vehicle scheduling, this paper proposed a super time-space network based model and designed a modified harmony search algorithm for transit vehicle scheduling. Firstly, this paper transformed the depot, trip, connector, pulling out arc, pulling in arc and deadheading trip into the nodes and arcs of a super time-space network. Secondly, this paper formulated a corresponding model of transit vehicle scheduling based on the constructed time-space network. Thirdly, this paper designed a mixed creation operator that makes use of the information from harmony memory and the field of feasible solution. Fourthly, by searching the connectors in a circle this paper built up an assignment network with local network elements and then realized the refinement of pitch by solving the above assignment problem. At last, based on the above operators, this paper presented a modified harmony search algorithm for the scheduling model. This research discovers the following: a) reducing deadheading trips and realizing the equality of working time are a pair of conflicted objectives, so optimizing them at same time needs a trade-off in view of the real life requirement; b) the size of deviation among trip chains has no monotonic dependent relation with the fleet size.