search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.26k stars 2.13k forks source link

In need of some clarity regarding how neighbouring solutions are generated for ATSP? #2115

Closed mga-97 closed 4 years ago

mga-97 commented 4 years ago

I am using OR-tools to solve an asymmetric travelling salesman problem. It seems to be working well as the problem is not too big (about 300 nodes), however I have a very basic question, I understand that neighbouring solutions are generated and then some kind of small change is made to generate neighbours which are then evaluated through say Simulated Annealing, What I am not certain of is how this neighbouring solutions are generated, are two edges randomly swapped or is it something else? I realise the question is quite basic but any help would be appreciated.

lperron commented 4 years ago

Please use the mailing list.

Mizux commented 4 years ago

Not sure for simulated annealing but for LNS you can see here the list of operators: https://github.com/google/or-tools/blob/45770b833997f827d322e929b1ed4781c4e60d44/ortools/constraint_solver/routing_parameters.proto#L91-L335

mga-97 commented 4 years ago

Thank you Mizux ended up finding that after I posted, just in case someone else sees this, the manual has more detail of how the operators are cycled through (http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/user_manual/manual/ls/ls_operators.html).