Abstract: Car pooling is of great significance for reducing carbon emissions, parking space requirements, and relieving traffic pressure. For the long-term car pooling problem (LTCPP), a multi-objective optimization model with vehicle capacity and time window constraints is constructed. The model aims to minimize the total distance traveled by the user, the extra driving time generated by car pooling, the difference between the actual departure, arrival time and the user??s ideal time, and maximize the matching feasibility. LTCPP is a combination of clustering and routing problems. Based on this feature, an efficient distributed clustering ant colony algorithm (DCAC) is proposed to solve LTCPP. The algorithm generates car pools based on heuristic information and preference values during the ant travel process, and then finds the best path the drivers should follow by an enumeration method. Finally, the algorithm is paralleled and implemented in Apache Spark distributed computing framework. The experi-mental results prove that the proposed algorithm can provide high-quality solutions for LTCPP and has advantages in dealing with large-scale LTCPPs.

Key words: car pooling problem, matching feasibility, ant colony optimization (ACO), distributed computing, Spark

摘要： 车辆合乘对于减少碳排放、停车位需求以及缓解交通压力具有重要意义。针对长期车辆合乘问题（LTCPP），构建了带有车容量和时间窗约束的多目标优化模型。该模型以最小化用户行驶总距离、用户合乘产生的额外驾驶时间、用户实际启程到达时间与用户期望时间的差距以及最大化匹配可行性为目标。LTCPP是聚类和路由问题的组合，基于该特点，提出了一种分布式聚类蚁群算法（DCAC）求解LTCPP。该算法在蚂蚁行进中基于启发式信息与偏好值产生合乘组，继而采用枚举方法确定用户的最佳行驶路径。最后，在Apache Spark分布式计算框架中进行分布式实现。实验结果表明，该算法能为LTCPP提供高质量的解，并且在处理大规模LTCPP问题上具有明显优势。

关键词: 车辆合乘, 匹配可行性, 蚁群算法（ACO）, 分布式计算, Spark