基于多目标模拟退火的团队定向问题

Team Orienteering Problem Based on Multi-Objective Simulated Annealing

团队定向问题是车辆路径问题的一个重要衍生问题,是运筹学中著名的NP问题。然而,当前对于团队定向问题的研究主要集中在单目标优化,不利于体现代价和收益的折中取舍,也无法根据实际情况选择合适的方案。首先从代价和收益的角度,通过两个目标考察团队定向问题。然后运用基于Pareto支配接受准则的多目标模拟退火算法进行求解。在6个Chao数据集上的实验结果表明,基于Pareto支配接受准则的多目标模拟退火算法能有效求解团队定向问题,所得的极端解与单目标优化下的已知最优解相近,所得的Pareto前沿在各个目标函数上有较好的多样性和收敛性。

The team orienteering problem is an important variants of the vehicle routing problem, which is a famous NP problem in operations research. However, the current research on the team orienteering problem mainly focuses on single-objective optimization, which is not conducive to reflect the trade-off between price and profit, and cannot choose the suitable final solution according to the actual situation. Be aimed at these problems, two different views, cost and benefit are looked into the team orientation problem firstly. Then, the multiobjective simulated annealing using Pareto-domination based acceptance criterion is used to solve this problem. Experimental results on six Chao＇ s datasets show that, the muhiobjective simulated annealing using Pareto-domination based acceptance criterion can solve the team orienteering problem effectively. The extreme solution of Pareto front is closed to the known optimal solution under single objective optimization. And the obtained Pareto front has good diversity and convergence on each objective function.