Mission-Oriented Ant-Team ACO for Min-Max MTSP

摘要

Multiple Traveling Salesman Problem (MTSP) is a combinatorial optimization problem and is an extension of the famous Traveling Salesman Problem (TSP). Not only does MTSP possess academic research value, its application is also quite extensive. For example, Vehicle Routing Problem (VRP) and Operations Scheduling, etc., can all be reduced to MTSP solutions. MTSP is an NP-Hard problem and is worth carrying out discussions from different facets to tackle the said problem. This research adopts the Ant Colony Optimization Algorithm (ACO). A certain amount of Mission-Coordinated Ant-Teams are included in this approach, and missions are appointed to the ants in the Ant-Teams before they set out (each ant has a different focal search direction). In addition to attempting to complete his or her own mission, each ant will use the Max-Min philosophy to work together to optimize the quality of the solution. The goal of the appointment of missions is to reduce the total distance, while the Max-Min search method for paths is to achieve Min-Max, which is the goal of labor balance. During the solving process, each ant will refer to the pheromone concentration on the paths and the mission tips as their action guidelines. After each round, the mission configuration will be changed in accordance with the state of solution obtained from each mission-coordinated team and the pheromone concentration on the path will be reconfigured.