A population based metaheuristic for traveling salesman type problems

摘要

In this paper we present a metaheuristic method, called DBMEA. It combines the bacterial evolutionary algorithm with local search techniques. Based on our test results it can be used for solving efficiently more discrete optimization problems. The algorithm was tested on Traveling Salesman Problem and Traveling Repairman Problem (TRP) benchmark instances found in the literature. In the case of TSP the DBMEA algorithm produced optimal or near-optimal solutions for all tested instances. Although the most efficient TSP solver method, the Helsgaun's Lin-Kernighan heuristic was faster than DBMEA, but in the case of DBMEA the runtime was more predictable than it the case of other methods. In the case of TRP the results are competitive in terms of accuracy and runtimes with the state-of-the art methods. Except two instances our algorithm found the best-known solutions, and for the biggest tested instance it found new best solution. The runtime was on average 30% faster than the most efficient heuristic in the literature.