基于磁场描述的TSPTW问题模型及其蚁群优化算法

针对带有时间窗限制的旅行商问题 (travelling salesman problem with time windows, TSPTW) 提出了一种基于磁场模型的蚁群变异算法 (MFM-ACOMF) .它通过修正传统蚁群算法的启发函数, 满足用户的时间需求, 并降低算法陷入局部最优的可能性;在得到最终解后, 通过变异策略对未达到时间窗标准的顾客节点进行优化.仿真实验结果表明:MFM-ACOMF算法与传统ACOM算法相比, 在最优解质量和顾客满意率方面都有一定程度的提高.

Ant Colony Algorithm Based on Magnetic Field Representation for the Travelling Salesman Problem With Time Windows

To aim at the travelling salesman problem with time windows (TSPTW) , an ant colony optimization algorithm with Mutation Features based on Magnetic Field (MFM-ACOMF) was put forward.It improved the heuristic function in the traditional ant colony optimization (ACO) algorithm, to meet the time requirement of customers and reduce the probability of getting a local optimal.Moreover, when it obtained the preliminary solution after all the iterations, a mutation strategy was used to optimize the customer nodes that did not reach the time window limit.The simulation results show that the MFM-ACOMF algorithm has certain improvement on both the optimal solution quality and customer satisfaction, compared with the ACO algorithm.