In previous entries we saw there are cases in which Integer Linear Programming is not the most appropriate approach to solve routing problems, and we proposed the option of using metaheuristic algorithms to obtain feasible solutions, and in many cases close to the optimal solution. This entry provides a more comprehensive analysis of how the solutions provided by these metaheuristic techniques can be improved.
Improved solutions: the local search.
One of the characteristics of metaheuristic techniques is that they do not guarantee that the optimal solution will be found. In fact, even if a solution is found, you cannot often tell if it is optimal or how far it is from the optimal solution.
As a result it is common to try to improve the solution proposed with metaheuristics by conducting a local search. A local search is considered a metaheuristic technique per se, where you start with a feasible solution and then move around various solutions in the search space (feasible solutions) applying local changes, until you find a solution to your problem corresponding to a maximum/minimum that can be local or global, or else, after a predefined running time is completed. It is important to note that not only changes improving the benefits of your solution are acceptable, but most probably, changes will be accepted that worsen the solution in terms of target function, in order to avoid local minimums/maximums and explore other areas in the search space.
Local Search and Routing
To calculate routes, there are two types of local searches commonly used, known as “2-opt“, “3-opt“, in general “k-opt”.
To introduce these techniques, here is a case example:
Suppose the points in the diagram below represent cities someone has to go through, without going twice through any and starting and ending at their home, which is point 1.
Running a metaheuristic technique, the best solution found is:
As this is a metaheuristic technique, you can’t be certain this is an optimal solution therefore you can try to improve the solution proposed.
A common alternative to improve this solution is with a local search known as 2-opt, which deletes two trails from the solution proposed, exchanging them.
Suppose that during running of algorithm 2-opt, you select the trails connecting nodes 2-4 and 7-8, and you find that the local search improves the solution proposed by the metaheuristic, providing the following route:
Another alternative just as useful would be to run the 3-opt technique instead of 2-opt. In the case of 3-opt, 3 trails from the solution are exchanged generating all possible combinations. If while running the local search, you decide the trails to be exchanged are the ones connecting nodes 2-4, 7-8 and 1-5, you would get:
Conclusions
Metaheuristic techniques do not guarantee that the optimal solution will be found; in general, you don’t even know how far the proposed solution is from the optimal solution.
Therefore, it is common to use local search algorithms to try and improve the solutions over a certain period of time.
There are specific local searches for routing, known as “k-opt”, which consist of deleting k trails from the proposed solution and recombining the remaining segments.
In general, when you run a metaheuristic technique, and in particular when you run a local search, you may end up “jumping” to apparently worse solutions in order to avoid the local minimums/maximums.