用基于蚂蚁算法的混合方法求解不确定TSP问题

Solve Uncertain TSP Problems by Hybrid Approach Based on Ant Algorithm

首次提出不确定旅行商问题模型,此模型将路径长度看作动态可变的,并考虑了交通运行中的不确定因素,比经典旅行商(TSP)问题更具有灵活性及实用价值,利用此模型得到的结果更适于指导车辆对运行路线的选择.同时使用一种基于蚂蚁算法的混合方法求解不确定旅行商问题,即引入3-opt方法对问题求解进行局部优化.实验结果显示,该方法能够加速蚂蚁算法的收敛性.

This paper firstly proposes a uncertain traveling salesman problem （TSP） model. This model assumes that the distance between two vertices is dynamic. With the view of application, this model considers the uncertain situations in the traffic system. Co flexible and also has more application value. This mpared to the classical TSP problem, this model is more mode is more properly for vehicle to choose the best route This paper also proposes a hybrid approach which is based on the ant system to solve the problem of uncertain TSP, namely, a 3-opt method is used to do the local optimization. Experiment results show that this approach can accelerate the convergence.