考虑出行时间窗的定制公交线路车辆调度方法

为提高定制公交系统的运行效率，研究了带乘客出行时间窗约束的多条定制公交线路车辆调度方法。给出了乘客出行站点合并方法，将公交车早到、晚到站点所造成的乘客损失转变为当量运营里程，以多辆公交车总运营里程最小为目标，考虑乘客的站点约束、公交车容量约束以及乘客的出行时间窗，建立了定制公交车辆调度优化模型。其次分析了乘客出行起点、终点对模型求解的影响，通过提出虚拟源站点，将多辆定制公交车的调度问题转换为多旅行商问题；基于后向推导原则设计贪心算法求得模型的可行解；之后基于遗传算法，采用自然数编码机制，将每个站点作为基因位，按照访问次序排列成染色体对应问题的解；最后给出了贪心算法和遗传算法的流程。在理论研究的基础上以定制公交线路为例对建模过程和模型的求解过程进行了阐述。研究结果表明：所建立的优化模型能够输出合理的多条定制公交线路车辆调度方案，不仅可以给出每辆定制公交的途经站点、运营里程，还可以给出每个站点的准点程度以及由于公交早到、晚到折算得到的当量运营里程；在求解算法质量方面，与可行解相比，相对最优解输出的方案能够使综合运营里程降低10.4%；模型求解时间为30.3 s，可以满足定制公交企业的实时性需求。

Customized Bus Route Vehicle Schedule Method Considering Travel Time Windows

To improve the operational efficiency of customized bus systems, the schedule method of buses for multiple customized routes was studied considering the time windows of passengers. The merging method for passenger travel stops was considered firstly. The late or early arrivals of customized buses at stops were converted to equivalent bus travel distances. Taking the minimum total travel distance of multiple buses as the objective, a customized bus schedule model was developed based on the passenger stop constraint, bus capacity constraint, and passenger travel time windows. The impacts of passenger travel origin and destination on the model solution were analyzed. By proposing dummy origin stops, the scheduling problem of multiple buses was converted to a multiple traveling salesman problem. A greedy algorithm was designed based on the backward inference principle to obtain a feasible solution of the optimization model. Then based on genetic algorithm, a natural number coding mechanism was then adopted and each stop was set as a gene. The solution to the corresponding problem of chromosomes is lined according to the order of access. The flow of the greedy algorithm and genetic algorithm was given. Finally, a customized bus route was taken as an example to explain the model development process and the solution process. The results show that the developed model in this paper can output reasonable multiple customized bus routes as a schedule plan. It not only outputs the through stops and travel distance, but also the punctuality rate at each stop and the equivalent travel distance due to early or late arrivals. As for the solution quality, compared with the feasible solution, the relative optimal solution can decrease the comprehensive travel distance by 10.4%. The solution time of the model is 30.3 s, which can satisfy the real-time requirements of bus companies.