Why only 10 to 12 waypoints for optimization?

When planning a route the waypoint limitation for optimization seems to be 10. Though i managed to fit 12 into it, but the calculation took a while.
How can it be improved? On my side or on the server side?

Edit. SPOILER: fascinating technobabble ahead. :grin:

1 Like

The Traveling Salesman Problem

I think the calculation exponentially increases every time you add a waypoint, until you break the server :grinning:

6 Likes

The route is calculated locally, not on the server

1 Like

No, it isn’t. It’s calculated on the server.

Proof is the fact that you can use ESI to plot a course …
… aka start, end, waypoints …
… and ESI sends you back the route.

Hmm, prolly I missed smth here. I see only 2 endpoints:

  • GET /route/{origin}/{destination}/ - route between 2 system. These routes are static more ore less (guess they can be affected by user’s avoidance lists / automilot settings? - too lazy to check this)

  • POST /ui/autopilot/waypoint - adds a waypoint to the end of already existing route

For server calcualtion there should be an endpoint that would accept a list of desired waypoints and return them in some “optimized” order and I don’t see such endpoint

I’ve checked my webgl map code, which has routes implemented, and apparently you’re right! My memory tricked me into believing otherwise! Seems I’ve just connected seperate routes as if they had waypoints. To be fair, it’s been a while since I’ve been working on this.

The server still can be used to “solve” any particular travelling-salesman-problem, though.
Thank you for the idea, I will try this some day. :blush:

And it just hit me that you MUST be right, because in the end it’s the client that’s literally halting because of it. Ah, man, ■■■■■■ up this one really badly. :slight_smile:

1 Like

But how?
Btw. I tried dotlan, but the optimize button did nothing to help. Or did i do it wrong? And experiences?

Any other third party programs for that problem available?
Or should i ask again in 10 years or so, to give the nerds time, to figure it out?

Slightly offtopic.

If you set the right systems in the avoid list it’s possible to be 2,147,483,647 jumps from your destination. WH’s are always that far away from anywhere, confused the hell out of me first time I saw it.

32 bit integers ftw.

3 Likes

If anyone works out how to do travelling salesman in linear time, UPS would like a word.

4 Likes

:joy::joy::joy::joy::joy:

I’ll try it out first, then talk about it later. Currently busy with other things, but when I need distraction, I’m going to try it. I do believe, though, that you can figure it out for yourself. The reason for this is not because I’m not going to try it, despite saying, but for the same reason I never released my script that’s downloading the war data from ESI.

I hog bandwidth, and processing power, like I own it. : - )

I’d like to add that I didn’t mention anything about reasonable timeframes! :blush:

Sadly i have no idea how to use ESI(whatever that techno babble means) :grin: or the other technical stuff here.

https://esi.evetech.net/

It’s the database and, indirectly, processing power available to players. There’s examples in every of these foldable/clickable thingies, see “Try it out”. Only needs a “curl”, which you need to download seperately for windows. It’s a command line utility.

I apologize for blindly assuming you’re using windows just because you don’t know ESI.

Thanks. I’ll read into it.

In any case would I advise against brute forcing it by hammering ESI. Which I would never do either and have never done. Nope. Not at all.

Pedro once challenged me with the travelling salesman problem, and I don’t think that there is a way of solving many jumps in reasonable a short time.

Why would you care anyway? It’s seems silly to think that throwing 1000s of hours of compute at the optimization of a route is going to help you, because it’s not worth it saving one or two jumps compared to the time wasted with this.

Still … fascinating topic. Now I hate you.

2 Likes

:joy::joy::joy:
I’m sorry to hear this, though it made me laugh pretty hard.

I looked into that esi thing and i decided to use, what the route planer allowes me to do with it.

Btw. the plan was a weekly trip to all ice systems in high sec for a new project. I’ll figure something out.

Thanks for the help. To all of you. :blush::blush::blush:

2 Likes

I doubt anyone would “outbid” the NSA for such a method.

The image of Jesse at the end of Breaking Bad (on the leash) comes to mind…

1 Like

SPOILERS GODDAMMIT.

Oh, wait. I don’t care. Never watched it. :sunglasses:

Why the NSA now?