COPYRIGHT

[tcat]

Hi,

Apologies for changing topic slightly. Not knowing much about `TSP' algo, trying to think of the roots of it's name. As it does not take inventor's credentials, I can almost imagine the idea came from the trading business, where really a salesman had to cover certain area to make his sales, planing optimal route to call on each town at least once, while travelling optimal milleage. May seem trivial for a couple of towns and straight routes.
Remember CocaCola bottler company put this sort of problem for their applicants to solve. Not knowing the whole story, I would attribute it to Hoover company, but that is my pure guess.

Tomas

[stevepoole]

Hi Tcat,
TSP is the acronym for 'Travelling Salesman problem' or, in the USA, 'Thrift Saving Plan'.
The former is a famous mathematical problem, (See Wikpidia for details), defined in the 19th C and one of the six 'Millenium problems' of the Clay Maths Institute.
The problem is simple to define : Join all cities to visit with the shortest closed circuit.
There is no known 100% precise solution, (in a reasonable 'polynomial' time). If you can find one, there is a 1 million dollar prize offered...
Several 'heuristic' (approximate) program have been written, and 'Concorde' gets 100%, but is very slow.
The QL 'Shrink' demo solution gets 90%, fast, and as such is a heuristic. The full version gets 99%, but is 90ko, compared to 11ko for the demo.
It has taken several years for three Qlers to adapt the superbasic code to C68, C++ and now html.
We expect to release the app version within a month or two, as soon a slight problem improving smartphone tactile numberpad access is cured.
The app works as it stands, but the numberpad access means screen messages get overwritten rapidly, hence our appeal for anyone who can advise...
We have only been learning javascript since april, so there is probably a simple solution to the glitch, that we have yet to find
An article may appear in the Quanta Bulletin soon... on how to convert QL programs to run ony any devices....
Regards,
Steve Poole.

[tcat]

Hi,

Thank you for explaining.

The QL 'Shrink' demo solution gets 90%, fast, and as such is a heuristic.

This is great, not having much knowledge about, I would consider even 80% of the goal a very good result.

Now I am thinking, what are typical real life applications making use of `TSP'?

I remember, many years ago, I was at an Austrian company, they specialised on warehouse optimisations.

Their optimal software directed a robot picking in a homogenous store, which really is 3D, robot has to go x,y,z in the warehouse alleys, up and down. Typically used for components having similar size.

They used a `Monte Carlo' method (the name escapes me, but probably nothing to do with gambling nor speed cars), to get fairly good results. Robot is commanded to pick these components from different locations. Worst case not optimal, it goes back and forth fetching a single component at a time. Not wanted, as it consumes more energy also picking time is long. Close to optimal, it plans the route beforehand using e.g. `Monte Carlo'.

Tomas

[stevepoole]

Hi Tcat,
Uses for TSPs include : sat_navs, robot movement controlling, 3d printing, gene analysis etc...

The shrink program is 2D.... 3D may be possible, we just haven't had the time to try it yet !

( 3D printer-heads, like warehouse alleys, are basically multi-layer 2D systems.)

It took several years for us to do shrink 2D, in our spare time, because we had to transcode 80 ko of superbasic into C++ , to be able to compare it to mainstream TSPs. That was essential to have any idea of its efficiency, which we wanted to evaluate.

Quanta will probably do an article on the 'Shrink TSP app' in the june-july issue. We still seek any advice on tactile num_pad handling...

Regards,
Steve Poole.

[stevepoole]

Hi,
Shrink_16, the html demo version of our 'Travelling Salesman Program' has now been released. Just PM me to get it. It is public domain !

To run it, just click on the program attatched to the email I will send you. Enter the number of towns you want. Then you get the graphics with the total distance.

It will run on most devices, unless you have some blocking options activated. It is very fast and achieves 90% of the optimal tour, good enough for many purposes.

The full C++ version is available for PCs : It is faster and much more accurate, (but weighs in at over 80ko), and accepts your input, and can run on VLSI test DATA.

SHRINK was a QL project, transposed to C68, then C++ , and finally html so it could run on desktops, laptops, tablets and smartphones.

Feel free to distribute it further, simply by email !

Steve Poole, (for the Shrink Team).

[stevepoole]

Hi,
I see that a thousand people have read the last message on this post, but none have asked to see the program.

This is no doubt because SHRINK is a very specialised program, useful for niche applications, such as 3D printing etc.

We rewrote it in html so that it can be freely distributed as an email attchment to run on any device...

At 11ko of html code, the program is too long to put on the forum. But it does make a neat demonstration of a very fast TSP heuristic !

Should you know of any interested parties, contact me at steve.poole@orange.fr to get the demo. But no spam, please !

The QL version of this demonstration is also available..... for tinkerers.

Regards, Steve Poole.