Abstract: Combined-taxi is an important means to alleviate the increasingly severe traffic congestion in our country. In order to solve the combined-taxi problem efficiently, the total number of taxi vehicles, waiting time of passengers and the total mileage of vehicles are considered. A mathematical model is proposed to optimize these three objectives in this paper. Further, a multi-objective genetic algorithm for solving this optimization model is designed based on the basic NSGA-II algorithms. Finally, the proposed model and algorithm are evaluated on 3-minutes taxi demand data on a certain day in a certain city. The experimental results show that the proposed model and algorithm have better benefit of combined-taxi, they can bring higher generation rate and better profit margin of combined-taxi.

Key words: combined-taxi, multi-objective optimization, fast non-dominated sorting, genetic algorithm

摘要： 出租车合乘是缓解我国日益严峻的交通拥堵问题的重要手段。为高效解决出租车合乘问题，综合考虑出租车车辆总数、乘客等待时长、车辆运输总里程数三个指标，建立了优化这三个指标的数学模型。在此基础上，基于NSGA-II算法设计和实现了解决该优化问题的多目标遗传算法。最后，在某城市某日某时刻3 min之内的打车需求数据上对模型和算法进行了实验验证。实验结果表明，该模型与算法能带来较高的合乘发生率和较满意的合乘利润率，具有较好的合乘效益。

关键词: 出租车合乘, 多目标优化, 快速非支配排序, 遗传算法