基于偏好矩阵遗传算法求解长期车辆合乘问题

来源：计算机应用杂志2017年第2期北京时间：

作者：郭羽含, 张美琪, 周楠

单位：辽宁工程技术大学 软件学院, 辽宁 葫芦岛 125105

摘要：针对长期车辆合乘问题（LTCPP），提出带有偏好矩阵的遗传算法（PMGA），将拥有私家车且目的地相同的用户群体分配到产生总花费最少的合乘小组。首先，建立计算基于全体用户费用成本的目标函数，构建以用户时间窗和车容量为约束的长期车辆合乘模型；然后，结合模型特点，在传统遗传算法（GA）的基础上，通过在交叉算子与变异算子中添加偏好矩阵记录并更新用户间的偏好信息来提高可行解的数量和质量。实验结果表明，在相同计算环境下，当用户数量小于200时，通过PMGA所获得的20个解中的最优解的值与最优化算法相同；而处理大规模的实例时，PMGA可以获得更高质量的解。所提算法可以明显提高长期车辆合乘问题的求解质量，在降低汽车尾气污染和减少交通拥挤等方面具有重要作用。

关键词：组合优化,车辆调度问题,启发式算法,遗传算法,长期车辆合乘问题

基金资助：辽宁省自然科学基金资助项目（2015020095）。