Browsing by Author "Muller, Felipe Martins"

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemEmbargo
    An Ant Colony Optimization Based Memetic Algorithm for the Dynamic Travelling Salesman Problem
    (ACM, 2015-07) Mavrovouniotis, Michalis; Yang, Shengxiang; Muller, Felipe Martins
    Ant colony optimization (ACO) algorithms have proved to be able to adapt for solving dynamic optimization problems (DOPs). The integration of local search algorithms has also proved to significantly improve the output of ACO algorithms. However, almost all previous works consider stationary environments. In this paper, the MAX-MIN Ant System, one of the best ACO variations, is integrated with the unstringing and stringing (US) local search operator for the dynamic travelling salesman problem (DTSP). The best solution constructed by ACO is passed to the US operator for local search improvements. The proposed memetic algorithm aims to combine the adaptation capabilities of ACO for DOPs and the superior performance of the US operator on the static travelling salesman problem in order to tackle the DTSP. The experiments show that the MAX-MIN Ant System is able to provide good initial solutions to US and the proposed algorithm outperforms other peer ACO-based memetic algorithms on different DTSPs.
  • Thumbnail Image
    ItemOpen Access
    Ant colony optimization with local search for dynamic travelling salesman problems
    (IEEE, 2016-06-13) Mavrovouniotis, Michalis; Muller, Felipe Martins; Yang, Shengxiang
    For a dynamic travelling salesman problem, the weights (or travelling times) between two cities (or nodes) may be subject to changes. Ant colony optimization (ACO) algorithms have proved to be powerful methods to tackle such problems due to their adaptation capabilities. It has been shown that the integration of local search operators can significantly improve the performance of ACO. In this paper, a memetic ACO algorithm, where a local search operator (called unstring and string) is integrated into ACO, is proposed to address dynamic travelling salesman problems. The best solution from ACO is passed to the local search operator, which removes and inserts cities in such a way that improves the solution quality. The proposed memetic ACO algorithm is designed to address both symmetric and asymmetric dynamic travelling salesman problems. The experimental results show the efficiency of the proposed memetic algorithm for solving dynamic travelling salesman problems in comparison with other state-of-the-art algorithms.