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

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