New TSP Solver

[steve...@orange.fr]

Hi,
I have just joined the OR Forum. Our small team have finished developping a TSP heuristic using a new 'Shrink' method, tested by Keld Helsgaun. It was written in Basic and has been transcoded into C++, (and can handle tens of thousands of nodes, up to 360 times faster than LKH). We wonder what steps need to be taken to see if it could be of any use in applications software.
We need to know which heuristic(s) Google is currently using, as we can then make speed comparisons, having up-to-date data on the subject. As we are not native C++ programmers, it is very likely that our code could be optimised further.
Please do not think we are cranks! The whole demonstration program took three years to finalise, and was in the pipeline since 1987...
Your comments and suggestions on how to proceed will be greatly appreciated.
Respectfully yours,
Stephen Poole.
 

[Vincent Furnon]

Hi,

Currently OR Tools does not target large TSP solvers. It does a descent job at solving medium size TSPs but does not compete with Concorde or advanced versions of LKH. The target is more generic Vehicle Routing Problems.

That being said, is your new "Shrink" method published or is the code open-sourced ?

Regards,

Vincent

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[majush philip]

Hi ,

 What is the max stops routes supported/ succesfully optimized using OR tools?

Evaluating if OR tools is suitable for my need .

Any leads welcome.

[steve...@orange.fr]

Hi Vincent,
1 : Does 'medium-size TSP' refer to program length,or the number of nodes handled? Our program can load data files in TspLib format, and currently uses 2D integer distances, calculated from coordinates, as does LKH. I see that OR Tools has functions to convert to polar coordinates etc, which would be perfectly compatible with our FP code. 
2 : An early 'Shrink' version was published in the 'Sinclair QL user-group 'Quanta' bulletin', and also more fully described in the Oct-Nov 2017 issue. We are looking for a more wide-scale publication, and have approached some mainstream journals recently to this end.
3 : Our latest demonstration version (664ko) contains LKH code supplied by courtesy of UWaterloo, but previous much shorter versions do not use LKH or any other source. We are prepared to share our own code, as stated in the bulletin article. That code gets between 84 to 99% precision, depending on the execution speed requested in the menu.   
Regards,
Stephen Poole.
 ____________________________________________________________

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[steve...@orange.fr]

Hi everyone,
I have just cobbled together a short video of the 'Shrink' TSP demo executing in real-time @ 1.8Ghz under Windows 8.1.
You can take a look at it at :
                   https://1drv.ms/v/s!AiyNuhEqpD_Xlz1u3WMVeLJQrOgM
Anyone interested can contact me for the shrink.exe file, Basic or C++source code.
Happy New Year!
Stephen Poole.

[steve...@orange.fr]

Hi Vincent Furnon,
I have been advised to produce a C++ Open_Source version of the 'Shrink' TSP.
 
This is in preparation and will soon be available. If anyone is interested in seeing the code, please contact me.
A detailed description is also being written for publication, and copies will soon become available.

Regards,
Stephen Poole. 
________________________________________________________

[steve...@orange.fr]

Hi,
The C++ source code for our 'Shrink' TSP was compiled using the QUINCY compiler with a Borland Graphics Interface library. This meant that it was incompatible with other compilers. We are now rewriting the code to be compatible with Visual Studio Community C++, which should make it fully OpenSource.
More news as soon as the new code is ready.
Regards,
Stephen Poole.

__________________________________________________________

[steve...@orange.fr]

Hi Vincent Furnon,

Our 'SHRINK' new TSP program has now beeen thoroughly overhauled and rewritten using VisualStudio 2017 C++, so as to be OpenSource code.
It is many times faster than on the video available on an earlier posting in this thread. 
It can work on standard TSP file format, using from 3 to 20,000 nodes.
Please contact me should you wish to have an advanced copy.
It will be placed on GitHub after a short review period.
Total publication is being considered.
Stephen Poole.
(For the Shrink Team).

________________________________________________________