These forums have been archived and are now read-only.

The new forums are live and can be found at https://forums.eveonline.com/

Player Features and Ideas Discussion

 
  • Topic is locked indefinitely.
 

option to exclude the last waypoint when Optimizing Route
Author
Previous Topic Next Topic
Never Enough
The Candle Factory
#1 - 2015-11-23 02:55:27 UTC
When you try to optimize route, the game will reorder your waypoints.
It would be nice to have an option to exclude the final waypoint from this reordering.
Examples:
1. You pick up delivery contracts going to the same destination
2. You pick up a bazilion of FW missions, and want to run them as fast as possible, returning to the same base station in the end.

Discuss.
Iain Cariaba
#2 - 2015-11-23 05:11:57 UTC
Optimizing route before adding final waypoint seems reasonable to me.
Never Enough
The Candle Factory
#3 - 2015-11-23 05:17:40 UTC
Iain Cariaba wrote:
Optimizing route before adding final waypoint seems reasonable to me.

This way the final point on Optimized route can be very far from my destination.
Gregor Parud
Imperial Academy
#4 - 2015-11-23 06:10:50 UTC
It's an interesting idea and the question is valid, it could however result in calculation problems but not sure on that. If not then I'd hope that the devs would add it as an option.
Xe'Cara'eos
A Big Enough Lever
#5 - 2015-11-23 06:16:15 UTC
don't optimize route excluding final waypoint - optimise route distinguishing between waypoints and final destination - and don't alter destination.

For posting an idea into F&I: come up with idea, try and think how people could abuse this, try to fix your idea - loop the process until you can't see how it could be abused, then post to the forums to let us figure out how to abuse it..... If your idea can be abused, it [u]WILL[/u] be.
Tabyll Altol
Viziam
Amarr Empire
#6 - 2015-11-24 09:20:38 UTC
Never Enough wrote:
When you try to optimize route, the game will reorder your waypoints.
It would be nice to have an option to exclude the final waypoint from this reordering.
Examples:
1. You pick up delivery contracts going to the same destination
2. You pick up a bazilion of FW missions, and want to run them as fast as possible, returning to the same base station in the end.

Discuss.


Go and check the map (it will take some time) but then you have the perfect route 4 ever.

-1
Rivr Luzade
Coreli Corporation
Pandemic Legion
#7 - 2015-11-24 09:31:18 UTC
Xe'Cara'eos wrote:
don't optimize route excluding final waypoint - optimise route distinguishing between waypoints and final destination - and don't alter destination.

That would be awesome. And if we are at it: CCP, get working on making "Shortest Route" actually the shortest route. Kaaputenen to Josameto is not shortest via Nomaa-Poinen or Kamio-Sarekuwa, it is shortest via Urlen-Jita/Niyabainen. Both other routes have a significantly longer total warp distance than via Urlen. And yet, the game is switching between these 3 routes randomly.

UI Improvement Collective

My ridicule, heavy criticism and general pale outlook about your or CCP's ideas is nothing but an encouragement to prove me wrong. Give it a try.
Black Pedro
Mine.
#8 - 2015-11-24 09:53:31 UTC
Maybe the solution is to enable autopilot route import via CREST? Then, third-party developers can implement all sorts of route planning innovations (like ones that correctly work or that can use a fixed endpoint) that can be imported into the game with a couple clicks.

The 8 Golden Rules of Eve

Why Do They Gank?
Xe'Cara'eos
A Big Enough Lever
#9 - 2015-11-25 15:19:15 UTC
Tabyll Altol wrote:
Never Enough wrote:
When you try to optimize route, the game will reorder your waypoints.
It would be nice to have an option to exclude the final waypoint from this reordering.
Examples:
1. You pick up delivery contracts going to the same destination
2. You pick up a bazilion of FW missions, and want to run them as fast as possible, returning to the same base station in the end.

Discuss.


Go and check the map (it will take some time) but then you have the perfect route 4 ever.

-1


I would like to point out that all of the above examples will have different waypoints nearly every time you do this.

For posting an idea into F&I: come up with idea, try and think how people could abuse this, try to fix your idea - loop the process until you can't see how it could be abused, then post to the forums to let us figure out how to abuse it..... If your idea can be abused, it [u]WILL[/u] be.
Varyah
Caldari Provisions
Caldari State
#10 - 2015-11-25 16:58:51 UTC  |  Edited by: Varyah
Route optimization is a slightly modified instance of

https://en.wikipedia.org/wiki/Travelling_salesman_problem


The problem is NP-complete (meaning pretty time consuming to solve with lots of waypoints), thus the warning if you have more than 12 (?) waypoints.

As far as I understood the route optimization algorithm of the EVE client from its behaviour it should be some sort of derivation of an algorithm for TSP, i.e. with variable weighting of security status (prefer (less) safe/shorter) but no weights for distances between gates, ie. time spent in warp and with some interesting artefacts, e.g. same waypoints (including start) but in the reverse direction often result in different routes.

Brute force search for shortest path runs in O(n!) time, where n is the number of waypoints (and in TSP you only have those waypoints in the graph, while in EVE you have a gigantic map as the underlying graph - probably shortest routes between each pair of systems in the list of waypoints are precomputed and their length used as weights - and all this adjusted by safe/not safe/shortest option).

Of course there are algorithms for TSP that perform better then O(n!), but still take time exponential in the number of waypoints (and that will stay that way unless someone proves P=NP). Unfortunately route optimization as in EVE is slightly different, I don't know if it is really just compution of suitable short routes between each pair of waypoints and then blap it with a staple TSP algorithm. Most likely there are some heuristics depending on the topology of EVE at work.
Edit: A more prominent difference is that in the original TSP no waypoint can be visited twice and start and endpoint has to be the same.

TL;DR: Route optimization is really hard to solve - even for a computer. I doubt there are many people at CCP - if any - that would want to touch this algorithm (but I would be interested in what the exact algorithm is behind it).
Never Enough
The Candle Factory
#11 - 2015-11-25 23:28:36 UTC  |  Edited by: Never Enough
Varyah wrote:
TL;DR: Route optimization is really hard to solve - even for a computer.

Although it is not the point of this topic,
I will comment on problem complexity.

Yes, it is hard,
but I believe it is done on client computer anyway, not affecting server at all.

It can be arranged like this:
1.
For short trips (let's say less than 10 waypoints) we get the solution immediately (just like it is now).
2.
For longer trips, a separate route optimization thread is spawned and it does its job in the background.
Current "best so far" result is displayed with two buttons: "Accept and use current result" and "Cancel".