Dear Rafael,

we have made some good results with our proposed algorithm AN EFFECTIVE USE OF HYBRID METAHEURISTICS ALGORITHM FOR JOB SHOP SCHEDULING PROBLEM.

You can found Full paper on: http://www.ijsimm.com/Full_Papers/Fulltext2017/text16-4_644-657.pdf

Regards, Robert

Dear Rafael,

i suggest you to see links and attached files in topics.

- Metaheuristics and combinatorial optimization ... - RIT Scholar Works

scholarworks.rit.edu/cgi/viewcontent.cgi?article=1075&context... -Solving Permutation Constraint Satisfaction Problems with ... - Lirmm

www.lirmm.fr/~jq/Cours/3cycle/module/p0118.pdf -parallel hybrid optimization methods for permutation based problems

https://tel.archives-ouvertes.fr/tel-00841962/document

- Technical Report A review on Estimation of Distribution ... - Addi

https://addi.ehu.es/bitstream/handle/10810/4764/tr11-5.pdf?...

- A Multi-Agent based Optimization Method for Combinatorial ...

https://tel.archives-ouvertes.fr/tel-01427171/document

Best regards

Dear Rafael,

In my experience Simulated Annealing, Tabu Search and Memetic Algorithms are metaheuristics that have proved to be effective for approximating globally optimal solutions to many permutation-based combinatorial optimization problems. All of them use the direct encoding of the permutation (solution).

However, DE can also be used to solve this kind of problems by employing an appropriate representation of the solutions.

By the way, what is the problem you are trying to solve?

Best Regards,

Eduardo

When it comes to permutation problems it is better first to try classical Genetic Algorithms and after that to try adaptation of Differential Evolution.

We applied Bacterial Memetic Algorithm.

http://www.ijicic.org/isme09-si22.pdf

Thank you very much, everyone, for your recommendations.

Dr. Eduardo, I applied DE to look for decision trees, where I first make an initial estimate of the size of the tree and then assign the attributes that are going to be evaluated in each internal node. In that sense, it can be considered a problem of permutation of nodes, since when exchanging them, it can improve the accuracy of the tree.

Thank you for your answer Rafael. It seems to be an interesting problem.

Regards,

Eduardo

Hello Rafael, I would not point out to one specific metaheuristic, since many recent metaheuristics use different names and terminologies but boil down to similar concepts. I can encourage you to check the discussion about these points in this paper: Article Metaheuristics -- the metaphor exposed

My expertise principally relates to traveling salesman (TSP) and vehicle routing problems (VRP) as well as other permutation problems. These problems have been the focus of a considerable number of studies related to metaheuristics. All efficient metaheuristics for these problems come from a clever combination of diversification techniques (e.g., crossover, population concepts, long-term memories) with efficient local or large-neighborhood searches. As such, the best methods are often hybrids.

For the TSP, one of the most efficient algorithm is that of Nagata and Kobayashi:

Article A Powerful Genetic Algorithm Using Edge Assembly Crossover f...

It relies on the Lin-Kernighan algorithm for an efficient local search after crossover. You can find a very nice implementation of this procedure HERE:

Article An Effective Implementation of the Lin-Kernighan Traveling S...

For the VRP, you can check the Unified Hybrid Genetic Search, which has produced state-of-the-art solutions for over 50 problem variants, again based on a sophisticated combination of population-based exploration and efficient local search. Here are two references related to that algorithm:

Article A Hybrid Genetic Algorithm for Multidepot and Periodic Vehic...

Article A Unified Solution Framework for Multi-Attribute Vehicle Rou...

as well as a good surveys that discusses the main factors of success for the application of metaheuristics to these problem types:

Article Metaheuristics in Combinatorial Optimization: Overview and C...

Article Heuristics for Multi-Attribute Vehicle Routing Problems : A ...

Good luck ;)

Hello Rafael, as mentioned in previous answers, it's difficult to specify a particular metaheuristic as each one has its pros and cons. However, simulated annealing is one of the robust algorithms that fits many combinatorial optimization problems. In addition, I find variable neighborhood search to work pretty well on different problems, especially vehicle routing and its variants.

There is no optimizer to solve all optimization problems, satisfactorily. Each metaheuristic has some advantages and disadvantages. Generally, the single solution technique is better than population-based one for solving scheduling problems. In this regard, I have designed a new single solution metaheuristic, namely, Social Engineering Optimizer (SEO) which shows a robust behavior in solving scheduling and routing problems. This algorithm is too simple and has a few collaborated parameters.

Fathollahi-Fard, A. M., Hajiaghaei-Keshteli, M., & Tavakkoli-Moghaddam, R. (2018). The Social Engineering Optimizer (SEO). Engineering Applications of Artificial Intelligence, 72, 267-293.

Its related codes are available in my RG page.

In the case of Oversubscribed Scheduling Problems, the MH algorithm named Squeaky Wheel is known to be one of the bests (and simpler).

Conference Paper Understanding Performance Tradeoffs in Algorithms for Solvin...

Thank you all for your answers and suggestions. Dear Thibaut Vidal, your suggestions to solve TSP and VRP are very interesting, I will carefully review the Nagata and Kobayashi approach. Dear Eduardo Romero and Amir Mohammad Fathollahi-Fard, their approaches are very interesting. As several indicate in their answers, Simulated Annealing is a powerful approach to solve hard problems. I think I must first study the similarities of my problem with the classical problems and then concentrate on evaluating the metaheuristic that I will use.

It is necesary to experiment with several approaches. It is imposible to know a priori the results of a metaheuristc method without tested.