基于随机森林与变邻域下降的车辆合乘问题求解

• 作 者: 胡德甲
• 出 处: 辽宁工程技术大学
• 发表日期: 2020年07期
• 关键词: 车辆合乘 变邻域下降 启发式算法 随机森林

随着我国经济的迅猛发展,私家车数量与日俱增,车辆数量的增加使得交通压力和环境污染日益严重。通过车辆合乘模式出行可以有效缓解上述问题,但目前车辆合乘模式多为临时性匹配,同时匹配因素只考虑用户间距离,得到的合乘方案忽略了用户对额外驾驶时间和对合乘组成员的要求,在实际应用中缺乏可行性,此外针对此问题的求解算法在解决大型算例问题中均存在求解时间长、求解质量差等情况。本文针对上述问题,建立了一种基于考虑匹配可行性的长期车辆合乘问题(Long-Term Carpooling Problem,LTCPP)的数学模型,并提出基于随机森林与变邻域下降的启发式求解算法。该算法根据历史合乘数据以及用户满意度信息,使用随机森林算法计算每个指标对用户满意度的重要性影响,并作为对应优化目标的权重,利用加权表示最终的目标函数模型,以避免人为设定权重因子对优化结果的主观性影响。在此基础上,针对本问题模型设计了变邻域下降算法(Variable Neighborhood Descent,VND)对目标函数进行优化求解。该算法可在短时间内得到最优解或较优解,具有高效快速的特点。采用VND算法获得的解决方案,每日私家车出行量可以减少72%,每日行驶的总里程数减少67%,合乘组成员的满意度显著提高。实验结果表明,结合随机森林算法和VND算法能为长期车辆合乘问题高效地提供高质量的解决方案。该论文有图15幅,表10个,参考文献50篇。