随机旅行时间的区域公交车调度模型及算法

Model and Algorithm for Regional Bus Scheduling with Stochastic Travel Time

研究一类随机旅行时间的区域公交车辆调度问题,将该问题看作为"部分班次被一辆车完成"的集合划分问题,考虑不同车场容量和补充燃料等约束因素,建立以营运费用最小为目标的机会约束规划数学模型。将该模型转化为一类确定性数学模型,设计求解该问题的改进遗传算法,根据问题特征定义染色体编码、产生初始种群的启发式算法、交叉和变异操作等。最后,通过一个算例验证了模型和算法的正确性。

Regional bus scheduling problem with stochastic travel time, treated as the set-partitioning problem of ＂part of trips completed by a vehicle＂, was formulated as a chance-constrained programming model to minimize operating cost for all vehicles, considering some side constraints such as depots capacities and fuelling. The model was converted into respective deterministic equivalents. Solutions were obtained using improved genetic algorithm which redesigns chromosome coding, heuristic procedure to initialize population, and crossover and mutation operation, etc. according to the features of bus scheduling. Finally, an example shows the correctness and effectiveness of the model and its algorithm.