通勤合乘路径优化模型与算法

Commuting rideshare routing optimization model and algorithm

中文关键词  交通工程  共享合乘  路径优化  启发式算法  通勤出行

英文关键词  traffic engineering  rideshare  route optimization  heuristic algorithm  commuting

中文摘要

      道路车辆的增多导致城市交通和环境问题日益严重, 共享合乘被认为是减少交通拥堵, 降低碳排放的有效方法, 特别是在新冠疫情持续影响下, 通勤者采用互助合乘出行意愿较高. 本文考虑到通勤时间的紧迫性, 通勤者存在通勤压力和合乘不适感, 在没有经济效益驱动的情况下, 限制合乘路径的匹配范围, 并加入惩罚因子以提高合乘配对成功率. 本文提出了一种基于最优时间插值的贪婪启发式算法, 添加了3种扰动算子来提高全局搜索能力, 采用多组不同规模案例测试扰动效果. 结果表明: 设计算法可以在短时间内求解出更优结果, 在解决大规模问题上,相比于精确算法、粒子群算法和遗传算法更具竞争力. 此外, 通过选取位置较远且分布均匀的职员作为接送者, 可以改善合乘效果.

英文摘要

      The increase in road vehicles has led to increasingly serious urban traffic and environmental problems. Ride sharing is considered an effective way to reduce traffic congestion and reduce carbon emissions. Especially under the continuous impact of the corona virus disease 2019 (COVID-19), commuters are more willing to use mutual assistance to travel. Considering the urgency of commuting time, commuters have commuting pressure and uncomfortable feeling of ride-sharing. In the absence of economic benefits, limits the matching range of ride-sharing routes, and adds penalty factors to improve the success rate of ride-sharing matching. In order to solve the larger scale problem, a greedy heuristic algorithm based on the optimal time interpolation is proposed, and three perturbation factors are added to improve the global search ability. Multiple groups of cases with different scales are used to test the disturbance effect. The results show that the designed algorithm can solve better results in a short time, and is more competitive than the exact algorithm, particle swarm algorithm and genetic algorithm in solving large-scale problems. In addition, the effect of ride-sharing can be improved by selecting employees who are far away and evenly distributed as pick-up.