| Pages: 1 :: [one page] |
|
|
| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
Caroline Rendus
Science and Trade Institute
Caldari State
0
   |
Posted - 2012.04.20 12:59:00 -
[1] - Quote
The other day I went out to pick up my Data Cores and ran into a problem that has always frustrated me about EvE.
I need to go to multiple stations in multiple solar systems. I'd like to calculate the quickest overall route.
I try setting Waypoints, then a Destination, all of my Waypoints disappear and I'm left with just the Destination.
If I try setting Destination first, then all the Waypoints and hit "optimize route" it still has me going to the Destination first.
It's really simple CCP:: Waypoints go in the middle, and Destination is the Last Stop not the first one.
Starting point - Waypoint1 - Waypoint2 - Waypoint(n) - Destination.
Then use Optimize Route to calculate out any possible faster (fewer jumps) route. Shuffle the order of Waypoints as needed, but leave the Destination as the last stop.
Thank you
CR |
Callic Veratar
Power of the Phoenix
177
|
Posted - 2012.04.20 16:01:00 -
[2] - Quote
If you can figure out a solution to this problem that does not involve dedicating the entire cluster to solving it, you will be one rich computer scientist.
http://en.wikipedia.org/wiki/Travelling_salesman_problem |
mxzf
Shovel Bros
1287
|
Posted - 2012.04.20 16:51:00 -
[3] - Quote
Yeah, I agree that the "set destination" behavior is buggy. It'd be nice to see it behaving better, but I don't think it's the highest priority ATM. |
Caroline Rendus
Science and Trade Institute
Caldari State
1
|
Posted - 2012.04.20 18:36:00 -
[4] - Quote
Interesting Page, thanks!
Actually the Map already has an integrated Route Optimization feature, so I won't have to re-invent that wheel.
And in general when I go out I'm not going to be doing 89k stops as in the T.S.P.
I rarely exceed 6 or 7 Waypoints.
Just a correction of the way Waypoints and Destinations are ordered, that's all I'm looking for.
Thank you
CR |
Quade Warren
Urban Mining Corp
Rising Phoenix Alliance
21
|
Posted - 2012.04.20 19:14:00 -
[5] - Quote
The traveling salesman problem only applies when you do not have a starting point nor an end point. It exists to determine both a starting point and an end point and the shortest/fastest route between all waypoints in between. Google does waypoint mapping very quickly, so this exemplifies my point.
Since she would have a starting point AND has set waypoints, it's not that computationally intensive.
Edit: Also, the most important part is that you cannot travel from one system to every system. That's really what makes this not the traveling salesman problem. |
Callic Veratar
Power of the Phoenix
179
|
Posted - 2012.04.20 19:44:00 -
[6] - Quote
No, it's not identical to the travelling salesman problem but it follows the same lines. You're defining an explicit starting point and end point, which fixes two of the points in the path, but the middle points are still arbitrary.
If this is not an NP Hard (or at best NP Complete) problem, please explain how. |
Callic Veratar
Power of the Phoenix
179
|
Posted - 2012.04.20 19:46:00 -
[7] - Quote
Quade Warren wrote:Also, the most important part is that you cannot travel from one system to every system. That's really what makes this not the traveling salesman problem.
The edges of the route are not gate to gate, the edges are the optimized system to system in the existing routing system. |
|
|
| |
|
| Pages: 1 :: [one page] |