Abstract:

In order to maximize users’ satisfaction, the Long-Term Car Pooling Problem（LTCPP） is modeled as a multi-objective optimization problem. Then, according to historical carpooling data and user satisfaction information, random forest algorithm is used to calculate the importance of each feature on users’ satisfaction, and it is used as the weight of the corresponding optimization objective, so as to avoid the influence of artificial setting weight factor on the optimization results. Finally, a Variable Neighborhood Descent（VND） algorithm for LTCPP is proposed, and the optimal solution of the problem is obtained by sequentially searching in multiple neighborhoods. The experimental results show that the VND algorithm can provide a high quality solution for LTCPP, and has a high time efficiency.

Key words: carpooling problem, multi-objective optimization, random forest, Variable Neighborhood Descent（VND）

摘要：

为了最大化用户满意度，长期车辆合乘问题（LTCPP）被建模为多目标优化问题。然后，根据历史合乘数据以及用户满意度信息，使用随机森林算法计算每个指标对用户满意度的重要性影响，并作为对应优化目标的权重，以避免人为设定权重因子对优化结果的影响。提出了一种求解LTCPP的变邻域下降（VND）算法，通过顺序地在多个邻域内搜索得到问题的最优解。实验结果表明，结合随机森林和VND算法能为LTCPP提供高质量的解决方案，且具有很高的时间效率。

关键词: 车辆合乘, 多目标优化, 随机森林, 变邻域下降