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

摘要

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