Evolutionary memetic algorithms supported by metaheuristic profiling effectively applied to the optimization of discrete routing problems

- Memetic algorithms (MA) composed of multiple metaheuristics aid the optimization of combinatorial routing problems.
- Metaheuristic profiling (MHP) aids development, tuning and performance monitoring of memetic algorithms in Excel-VBA models.
- Analysing information from each metaheuristic and each iteration of an optimization algorithm provides valuable insight.
- Synergies between metaheuristics enhance configuration and performance of memetic algorithms.
- TSP scenarios have direct relevance to drone and under-water vessel routing for surveillance purposes in the gas/oil sectors.

Optimizing the routing of resources to multiple remote sites is a complex issue confronting many sectors of the gas an oil industries with significant cost implications. When significant numbers of sites are involved the optimum solutions become difficult to find and require complex algorithms to do so. Memetic algorithms (MA), combining multiple metaheuristics and heuristics that can be easily activated or deactivated offer a potentially effective and flexible approach to complex routing optimization problems. By combining MAs with the recently proposed tool of metaheuristic profiling (MHP) it is possible to establish and monitor the contributions of the component metaheuristics and heuristics in finding the lowest-distance tour solutions for routing problems. MHP also facilitates the identification of synergies between specific metaheuristics, potential conflicts or duplication among others, and computational time consumption issues with certain combinations. Applying MHP as a monitoring tool during the development of MAs helps to develop balanced algorithms combining multiple metaheuristics focused on specific tasks, such as exploring the global solution space and/or exploiting the space locally around specific solutions. Memetic algorithms make it possible to consider the classic evolutionary algorithms and other well-known heuristics each as components in a “toolbox” of metaheuristics/heuristics available to be combined and configured to form flexible, fit-for-purpose optimization tools. A routing memetic algorithm is described in detail and tested using well-studied examples of the travelling salesman problem (TSP). MHP is applied, using the Excel-VBA platform, to reveal the relative contribution of the nine metaheuristics involved in the routing MA developed here, which incorporates some of the metaheuristics derived from bat-flight principles. The study identifies how these metaheuristics function together with integrational synergies. The MHP information is displayed in graphic and tabular form, alongside the optimum values obtained from multiple executions of the algorithm to illustrate the guidance and level of insight that can be provided by the MHP technique. Memetic algorithms typically involve multiple control variables that can be (and often need to be) tuned to improve their efficiency in finding the optima of specific problems. This makes them flexible, but potentially time consuming to setup and operate. The successful application of the MA to the TSP routing problem suggests scope for its development to address more complex routing problems.

Figures show selected results of metaheuristic profiling of BF-TSP algorithm applied to the Att48 problem highlighting the contribution of specific metaheuristics (Mh1 to Mh9) to locating optimum tour. Numbers in brackets in left graph refer to codes identifying specific heuristics.327