公共自行车多目标动态调度建模与算法研究

Research on the dynamic model with multi-objective and algorithm for public bicycle rebalancing problem

针对公共自行车系统自行车时空分布不均衡的问题,对公共自行车调度过程中自助服务点调度优先级、动态需求特性、服务时间窗等进行了研究,建立了统筹用户满意度与企业调度成本的公共自行车系统动态调度多目标优化模型。结合禁忌搜索算法的爬山性能和遗传算法算子交叉、变异功能,设计了一种禁忌遗传混合算法对动态调度模型进行了求解。以杭州市某区域公共自行车系统为研究对象,对上述模型与算法进行了实验验证。研究结果表明,所得到的调度方案能够在较大程度上满足公共自行车系统服务点的租赁需求,可以减少调度车辆的行驶距离,降低调度的成本。

Aiming at the problem of the public bicycle system bicycles distributing imbalanced in temporal and spatial,the repositioning priority,dynamic ride demand and time window of the self-service station in redistribution process were analyzed. Then a dynamic public bicycle repositioning model with multi-objective optimization including user satisfaction and transportation cost was established. Combining hillclimbing performance of tabu search algorithm with crossover function of genetic algorithm,a tabu genetic hybrid algorithm for solving dynamic redistribution model was designed. The above model and algorithm were applied in Hangzhou public bicycle system. The results indicate that the repositioning model can meet the ride demand of self-service station in a great degree,and also reduce the repositioning distance and vehicle cost.