Optimize distribute resources evenly

[ikagod]

Motivation

The distribute resources function does exactly what the name implies, it distributes any one type of resource evenly among all cities. It does this by calculating the resource average, and then sending whatever is above that threshold from cities that have a surplus to cities that have a lack of those resources. The problem that usually occurs with this function is that it tends to create a shipment schedule that is very unoptimized. It tends to send resources from islands that are very far apart, despite there being an island with a surplus of resources closer to the destination city. Only the distribute resources evenly function is affected by this, because every other resource transportation function in ikabot is guided by the infinite wisdom of the user himself to know from where to send resources and to what destination.

Problem

What we have here is a perfect example of the Transportation Problem in which we have n sources that have some amount of resources and m sinks which require that amount of resources, with each source being able to transport to every sink at a certain transportation cost. The aim of solving this problem is to supply all sinks with the requested resources from the sources, using transportation lines that cost the least amount of time.

Solution

I might get to working on this after I find time to finish the new logging and process status systems and other more pressing issues. In the mean time if anyone is willing to work on it, feel free to share your code and maybe even create a pull request if you manage to implement it fully into ikabot.

The only thing I would like to ask of anyone attempting to solve this problem is TO NOT introduce ANY additional libraries into ikabot in order to solve this problem. We do not need 50MB of heavy duty, incredibly optimized number crunching libraries like scipy just to solve a basic linear programming problem!

Here is some additional information about this specific problem as it pertains to ikariam:

• This problem is DIFFERENT than the optimization problem defined in #79. That problem is a problem of optimizing one shipment (from island A to island B). It is hypothetically possible to make some gains by splitting the fleet into multiple batches and sending them one by one. In this way the trading port can be kept busy loading a number of ships while some other ships are traveling. This problem is much more complex to solve as it involves managing action points and calculating whether the gains would be worth it considering the distance between the two islands. This problem should be solved separately from the one defined in this issue, and it should be solved at a lower level in the ikabot codebase (in the function that actually executes ONE transportation route)

• The changes necessary to implement this should only affect the ikabot/function/distributeResources.py file

• Usually the discreet transportation problem is solved by finding an initial feasible solution, and then optimizing it. the guide on how to do this can be found here : Transportation problem solution

  The best algorithm that finds an initial feasible solution that is closest to the optimal solution is the "Vogel’s Approximation Method", as it is not a greedy algorithm and instead takes into account the second lowest cost of transport as well for each source and sink.

• In our case the sources are islands that have a surplus of the resource (above average resource level) and the sinks are islands that have a lack of resources (below average resource level), the costs should be computed as a sum of the time it takes to load one resource in the source's trading port and the time it takes to transfer one unit of resource from the source to the sink.

• Make sure that once you have all the optimal transportation routes, you execute them in ascending order by temporal cost (fastest routes first)

• Bonus points if you manage to optimize this further by making use of the fact that you can send ships at less than 100% capacity in order to make gains on travel time.