A MAX-MIN Ant System with Short-term Memory Applied to the Dynamic and Asymmetric Traveling Salesman Problem

Real-world transportation systems should deal with dynamism and asymmetry to find good solutions for logistics companies. In this scenario, the inefficiency of exact methods to solve complex optimization problems like Travelling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) rise the opportunity to use methods like those provided by meta-heuristics as ant-based systems. Despite the improvements reached by adopting meta-heuristics in TSP and VRP, due to its intrinsically complex and time-consuming solutions, there are still opportunities to improve the problem-solving performance by adding some extra characteristics in the ant-based system solution. Therefore, this study proposes the use of short-term memory in the MAX-MIN Ant System algorithm, named MMAS(MEM), applied in the asymmetric and dynamic traveling salesman problem (ADTSP) with moving vehicle. To evaluate the proposed method, a comparison is made with the EIACO and with the canonical MMAS algorithms in benchmarks and real-world instances. Results pointed out that MMAS(MEM) is better than EIACO and MMAS to solve such complex problems. Hence, it can be considered the most suitable for moving vehicle scenarios.