Abstract:

With the development of smart cities and transport, the continuous improvement of mobile Internet and smart transport infrastructure and data, a new transport operation method in which users order transport services on their mobile phones-dynamic transport has become an important exploration direction for public transport development in several urban cities. However, studies in the field of modeling and algorithms for the dynamic transport problem are limited. Therefore, a dynamic transport problem model and a discrete hierarchical memory Particle Swarm Optimization(PSO) algorithm for dynamic public transport are proposed. This study mainly involves providing the objective function and constraint conditions for dynamic transport problems; providing the form of the solution to the dynamic transport problem and defining the editing distance of the solution; proposing an algorithm for generating high-quality initial solutions for the PSO algorithm using data-driven precomputed path sets; providing the calculation method of particle mutation probability and adaptive convergence coefficient in the PSO algorithm based on the edit distance of the solution; and proposing a hierarchical solution method for PSO in which lower-level particles can be reused and inherited, thereby reducing the performance loss caused by copying and re-initialization within a single time slice and between time slices. Based on a real scene and historical data from Caijiagang Street in Beibei District, Chongqing, a simulation environment is established for the experiments. Experiments have demonstrated that compared to non-hierarchical PSO algorithms, the hierarchical PSO algorithm can reduce computational time by more than 80% through reuse and inheritance, and adaptive parameters and mutation mechanisms can help algorithms converge to additional optimal solutions more stably than traditional public transport systems. Dynamic public transport can increase passenger order acceptance rate by 22% and save passenger travel time by 39.1% under the same capacity constraints. Moreover, the algorithm proposed in this study can meet the needs of transport operators for dynamic public transport scheduling within the area. Compared to non-hierarchical PSO algorithms, the algorithm proposed in this study reduced the calculation time by an average of 85.3% and improved the order acceptance rate by at least 12% while consuming only 80% of the mileage.

Key words: smart transport, dynamic public transport problem, Dial-a-Ride Problem(DARP), Particle Swarm Optimization(PSO) algorithm, precomputed path set, adaptive mutation

摘要：

随着智慧城市、智慧交通的发展, 移动互联网和公交智能基础设施以及相关数据的不断完善, 通过用户手机预约公交服务的新型公交运营方式——动态公交, 已经成为许多城市公交发展的重要探索方向。但目前, 对动态公交问题的建模、算法研究不足。基于这一研究现状, 提出动态公交问题模型和面向动态公交的离散分层记忆粒子群优化(PSO)算法。首先给出动态公交问题的目标函数和约束条件, 给出动态公交问题的解的形式, 并定义解的编辑距离; 其次提出使用数据驱动的预计算路径集生成PSO算法的优质初始解的方法, 给出基于解的编辑距离的PSO算法中粒子的变异概率和自适应收敛系数的计算方式; 最后提出将粒子群分层求解的方法, 其中低层粒子群可复用、可继承, 从而减少单时间片内、时间片间复制和重初始化带来的性能损耗。基于重庆市北碚区蔡家岗街道的真实场景和亿级历史数据建立仿真环境进行实验, 实验结果表明: 相对于不分层PSO算法, 分层PSO算法通过复用和继承能缩短超80%计算用时; 自适应参数和变异机制能帮助算法更稳定地收敛到更优解; 相对于传统公交系统, 动态公交能在同等运力限制下, 提高22%的乘客接单率, 节省39.1%的乘客出行时间, 所提算法能满足公交运营商在片区内进行动态公交调度的需求; 相对于对比算法, 所提算法平均缩短了85.3%的计算用时, 并且在仅耗用80%里程的情况下提高了至少12%的接单率。

关键词: 智慧交通, 动态公交问题, 电召问题, 粒子群优化算法, 预计算路径集, 自适应变异