基于遗传算法的网约出租车合乘路径优化模型研究

• 作 者: 李金洋
• 出 处: 大连交通大学
• 发表日期: 2020年01期
• 关键词: 交通工程 出租车合乘 路径优化 遗传算法 分支定界法

随着我国社会经济的快速发展,城市居民出行量不断增加,交通拥堵与打车难问题日益严重。出租车作为灵活便捷的交通方式,在城市交通中扮演着重要角色。然而,由于运营成本偏高等原因,使其在平峰时段经常处于空载状态;在高峰时段又常因大量出租车只承载一位乘客而出现打车难的问题。尽管目前出租车合乘出行模式在某些城市有一定的发展,但由于合乘乘客与驾驶员之间就顺路与否的问题容易产生纠纷,且因合乘绕行而产生的附加运营成本承担方不明确而难以推广应用。鉴于上述问题,本文针对网约出租车出行模式,研究合乘路径优化模型及算法,以期提高出租车承载率与运营效率,缓解城市打车难问题。针对路网中某一时段内出现的多个乘客需求与多个可提供服务的出租车,以系统路径最短为优化目标建立目标函数。考虑出租车核定载客量、路径合理性、乘客与驾驶员收益及时间窗等因素,建立约束条件。基于遗传算法思想,研究设计了上述模型的优化求解算法。针对大连市两处局部路网及出租车合乘信息,利用网约出租车合乘路径优化模型及算法进行优化求解。通过对比遗传算法和分支定界算法所得解,分析了论文研究模型与算法的有效性和求解效率。通过对比分析合乘路径优化方案与非合乘出行方案,讨论了出租车合乘出行在运营效率和成本收益方面的优越性。研究表明,构建的出租车合乘路径优化模型及遗传算法,可以得到合乘路径近似最优解;对于规模较大的路网及合乘需求,遗传算法在运算效率方面明显优于分支定界等精确算法;与传统的非合乘出行方式相比,合乘出行在出租车资源节省、总运营里程降低、驾驶员收益提高及乘客成本减少等方面具有明显优势。