允许局部路径重复的共享单车调度模型

Genetic Algorithm Based Shared Bicycle Scheduling Model

运营商自主调度能够有效解决共享单车供需失衡问题,使车辆分布与用户需求分布更加吻合,提高系统的运转效率和用户满意度。共享单车调度是允许存在局部路径重复的多旅行商问题,引入动态路径规划优化模型对共享单车调度问题进行描述,主要考虑如何以最少调度车数量、最短的总运输里程实现总调度成本最小,并设计遗传算法进行求解。最后以北京地区为例,采用300多万条摩拜单车订单数据进行实证分析,多次实验后得出最优调度方案,并确定最少调度车数量和最小总调度成本,表明了模型和算法的有效性。

Scheduling can effectively solve the problem of imbalance between supply and demand of shared bicycles,which makes the distribution of vehicles more consistent with the distribution of user needs,and improves the system′s operational efficiency and customer satisfaction.Considering that shared bicycle scheduling is a multiple traveling salesman problem that allows local path repetition,the dynamic path planning optimization model was used to describe the shared bicycle scheduling problem.Dedicated to minimizing the total dispatching cost with the minimum number of dispatched vehicles and the shortest total transport distance,a genetic algorithm was designed to solve the problem.Finally,taking Beijing area as an example,more than 3 million Mobike bicycle order data were used for empirical analysis.The results show the optimal scheduling scheme,the minimum number of dispatched vehicles and the minimum total dispatching cost,indicating the validity of the model and algorithm.