动态共乘系统中一种高效的插入操作方法

针对现有插入操作方法因时间复杂度高而降低动态共乘系统的运行效率,设计了一种以最小化车辆绕行距离为优化目标的线性时间插入操作方法,考虑乘客上车、下车时间约束和车辆容量限制等条件的动态共乘路线优化问题.建立共乘路线模型,采用动态规划技术和固定源节点插入位置的策略,以及利用位置向量的计算结果,可在常量时间内找到车辆绕行距离最小的目标节点的插入位置.理论分析表明:方法能够在线性时间内找到源节点和目标节点的最佳插入位置.仿真结果表明,基于线性时间的插入操作方法能够迅速地得到共乘优化路线,显著提高了动态共乘系统的运行效率.

High efficient insertion operation method in dynamic ridesharing system

This paper designed a linear time insertion operation method to overcome defects of the existing insertion operation methods with the high time complexity and the low operation efficiency in the dynamic ridesharing system. With the optimization objective of minimizing the vehicle detour distance, the proposed method addressed the dynamic carpooling route optimization problem considering the passengers''s boarding and alighting time constraints and vehicle capacity limitation. It constructed a dynamic ridesharing route model. By using the dynamic programming technology and the strategy of fixing the insertion position of the source node, as well as the calculation results of the location vector, the insertion position of the target node with the minimum vehicle detour distance could be found with a constant time. Theoretical analysis shows that the method can find the best insertion position of source node and target node in linear time. The simulation results show that the method can quickly get the optimal ridesharing route, and significantly improve the operation efficiency of dynamic ridesharing system.