关键词: 变邻域搜索, 车辆合乘问题, 智能交通, 启发式算法, 优化匹配, 车辆调度问题

Abstract: A distributed hybrid variable neighborhood search algorithm is proposed for a specific type of carpooling problem where users maintain a long-term carpooling relationship (LTCPP). Benefited from the distributed computing, the approach can solve large-scale instances rapidly. First of all, a mathematical model with time window and vehicle capacity constraints is constructed and a cost based objective function is built. Then, all users are assigned to carpools accordingly by a hybrid distance priority algorithm in order to get the initial carpooling scheme with satisfying all the constraints. Finally, a variable neighborhood search algorithm is designed with the aid of distributed computing architecture, so that the algorithm can iteratively optimize the initial carpooling scheme in parallel and obtain the final long-term carpooling scheme. Experimental results show that the proposed algorithm has significant advantages in calculating speed and solving large-scale instances.

Key words: variable neighborhood search, carpooling problem, intelligent transportation, heuristics algorithm, optimal matching, vehicle scheduling problem