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

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

Genetic algorithm with preference matrix for solving long-term carpooling problem

A Preference Matrix based Genetic Algorithm (PMGA) was introduced for solving the Long-Term Car Pooling Problem (LTCPP), and a group of users with both vehicle and the same destination was assigned to the co-generation group to minimize the total travel cost. First, the objective function of calculating the cost of all users was set up, and a long-term car pooling model with constraints of user time window and car capacity was designed. Then based on the characteristics of the model and classic Genetic Algorithm (GA), a preference matrix mechanism was adapted into the crossover and mutation operators to memorize and update the preference information among different users, thus improving the quantity and the quality of feasible solutions. The experimental results show that in the same computing environment, the optimal solution value of 20 solutions obtained by PMGA is the same as that of the exact algorithm when the number of users is less than 200. Moreover, PMGA is remarkable in solution quality when dealing with large size of instances. The proposed algorithm can significantly improve the solution quality of the long-term car pooling problem, and play an important role in reducing vehicle emission and traffic congestion.