Release Visitor mission optimizer

You carry tourists around and all of them want to different locations? At the same time some of them want to the same location as others but not before they've been somewhere else? It annoys you that the destinations of a tourist have to be visited in the correct order or otherwise they don't count? You'd like to fly the shortest route possible but with the given restriction and many passengers this takes too much time to figure out?

As with my trade mission optimizer the other day I couldn't find a tool that optimizes tourist missions, Thus, (again) I wrote one myself and you can find it on GitHub under a GPL v3 license.

What the program does is the following.
In a separate file the user needs to state the system of origin and all destinations for each tourist in the correct order (and with correct spelling).
Afterwards the program fetches the coordinates of these systems from EDSM and calculates the shortest route under the given restriction that each tourist wants to visit the destinations in a specific order.

The latter means that the shortest route my require visiting a location twice (or more often). An example that illustrates this may be the following. One destination may e.g. be close to the origin system and first to be visited for one traveler but last for another. In that case it doesn't make sense to wait to visit the first point for the first visitor until the 2nd is "processed".

One last comment. The time required to find the exact solution to this problem grows (once again) factorial. Thus the exact solution is calculated just if 12 or less different destinations need to be visited. For 12 destinations the program needs approx. 1 minute.
If the sum of unique locations to be visited is greater than that, the order of travelers is permuted. This is basically a randomization of the starting locations under the above mentioned restriction that I can't simply randomize the complete order of destinations.
The program uses than a maximum allowed time to find a good enough solution. The default value for this time is 123 seconds, but can be changed by the user.
It is unlikely that this second method finds the very best solution but it finds a good enough solution without needing too much time.

Why I'm doing this is illustrated by the results of a simple test.
# of destinationsTime to find routeLength of routecomment
1248 secondsdoesn't matterexact solution
13646 seconds16289.33 lyexact solution
13123 seconds16328.53 lygood enough solution

So the good enough solution, found by randomizing the order of travelers, is less than 1 % longer than the exact solution but requires five times less time. For more points the time-"profit" will grow factorial!

More details on how to work with the program can be found in the description of the GitHub repository.

The program is written in python 3 and extensively commented.
It was tested on a Debian system and I really don't know if it will work in a proprietary OS.
If it doesn't the most likely point of failure is the default parameter for the mission file location. I haven't tested that and I don't care. But Hoorah! the source code is published under the GPL v3 and thus you can fix that yourself :)

Fly safe commanders (and do tourist missions efficiently)
schlowi123
 
Top Bottom