lovasoa / salesman.js Goto Github PK

Is it possible to get the shortest path without having to return to the first point?

One where the last point is the furthest away so the salesman doesn't have to return all the way back to the starting point?

I got different result with same input points.
Correct Result

Incorrect result

Currently the first point in the path is never moved. This should be configurable.

Hello,

Firstly, I'm asking myself how this algorithm would compete with a brute force one? Like this one for example. My understanding is that your simulated annealing algorithm returns an approximation using probabilities, which means you won't always get the same output for the same input (while brute force will always find the perfect solution because it will try all possible paths). On the other hand, simulated annealing will be faster than brute force. Am I right?

Secondly, being able to define a fixed starting point and destination point would be amazing. I've no idea how this problem should be called, maybe the "divorced salesman" as seen on StackOverflow.
In this same question, they're talking about adding a dummy city whose distances to every other points is 0. Would that be a good option? Is it possible to go that way using your repository?

I will make a fork of your repository anyway because I need to change the distance calculation algorithm to take the earth's radius in account (in my case it won't be x/y but lat/lon instead).

Thank you for your help.

Since the simulated annealing temperature has a known start and end value (from 100 * distance from point 0 to point 1 to 1e-6), progress can be represented by the size of the current temperature.

Not sure of the best way to calculate the percentage from that, but the result can be passed to the callback function to be used for progress bars.

I've tried various things here now, but the resulting array does neither end nor start with "0", which is part of the point of the algorithm, isn't it? (it is suppsoed to return to the origin .. most of the time it just seems to pass by the origin)

e.g. test script

let salesman = require('salesman.js');
let a = [[0, 0], [20000, 200], [100, 0], [100, 100], [100, 0]];
let b = a.map(p => new salesman.Point(p[0], p[1]));
let sol = salesman.solve(b);
console.dir(sol);

Ran multiple times:

[ 1, 3, 0, 4, 2 ]
[ 4, 2, 0, 3, 1 ]
[ 4, 1, 3, 0, 2 ]
[ 0, 3, 1, 4, 2 ]
[ 3, 0, 4, 2, 1 ]

I've tried closing the loop also (duplicating the first elem last) without any big amount of luck...