Last update 08-31-15

Hi!

After reading this thread, especially this post and next posts, I've decided to make special project where any ideas can be tested and compared in a proper way.

Few words about project

My project is written in python 2.7, for newer versions I have to test it first.

How to run your own experiment? Very simple:

git clone https://github.com/einstein13/wl_ship_optimization.git
cd wl_ship_optimization
python execute_one.py

The goal for now is to make efficient and math-like algorithm for work of ships and ports in Widelands before build 20.

What is included now?

1. Ships:
   • Simple ship algorithm (old Widelands)
   • Tibor's ship algorithm (based on his python project)
   • Tibor's ship algorithm (his branch, currently here, almost identical to python one)
   • Einstein's ship algorithm (for example here)
   • Einstein's ship algorithm, change: next destination can be the one after next while calculating new route
   • Einstein's ship algorithm, change: calculating k factor based on wares on the ship
2. Ports:
   • Simple port algorithm (old Widelands)
   • Einstein's patch for port based on this
3. Test cases:
   • Line test (ports in line: A---B---C, one ship, 200 wares to transport)
   • Triangle test (ports in regular triangle, one ship, 300 wares)
   • Hexagon test (6 ports, 2 ships, 300 wares)
   • Rectangular test (4 ports: 2 pairs with long distance between, 2 ships, 300 wares)
   • Nonsymmetrical situation, more likely to be in game, huge amount of wares (6 ports, 2 ships, 1200 wares)
4. Test difficulties:
   • "1" - Slow mode - long time between appearing wares, mostly to see if algorithms aren't working in very strange way
   • "2" - Standard mode - middle time between appearing wares, middle distances, mostly to see if everything is working fine with more complex problems, plus if the algorithm is just wrong (much worse than basic one)
   • "3" - Stressed mode - lots of wares at once, long distances, mostly to see the difference in very complex situations
5. Statistics:
   • Total simulation time (taken to fulfill test cases)
   • mean/max utilization of ships
   • mean/max wares waiting in ports
   • min/mean/max journey distance for ware
   • min/mean/max existence time for ware (waiting at port + travelling)
   • max/mean/min efficiency of journey for ware
   • min/mean/max time waiting for ware in port (to be taken by a ship)
6. Statistics display:
   • Statistics every each experiment (test case)
   • Statistics in markdown tables after all experiments for each set of tests
   • Optimization through given value with markdown table of results for each set of tests

Do you want to suggest something?

Feel free to write it down here, on this thread. Now I am developing the code. It needs lots of work. Then you will be able to add any algorithm you want to test.

I will edit this post to keep it up-to-date

einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top

Quote

Mean existence time: 178.47 Max existence time: 401.4

I think this is what we are after - these should correspond to seafaring delivery time - I mean time from delivery a ware to starting port till delivery to destination port....

Have you implemented also another algorithms for ship movements?

Top

Quote

You know, also small differences in algorithm can matter. Also number and layout of ports, number of ships and so on..

Top

Quote

Finally I've found the problem: Tibor's algorithm for finding new path. The problem was with finding best solution for next destination. When the distances were very long (you can think as a very big and complicated map), sometimes carrying the wares to distant ports is very inefficient. That produce "count" value beneath the zero and no maximum is found (Tibor assumed that the minimum is above zero).

When I run the tests again, another issue was found. Here is an output (slightly modified):

======
TEST CASE 5
======

PORTS:
Very basic port class.
SHIPS:
Tibor's algorithm for ship
------
END OF SIMULATION: time interrupt
150/1200 (12.5%) delivered
------
Total time: 40001.4
Mean utilization: 29.8092946171
Mean journey distance: 1092.15
Mean journey efficiency: 9.55608305016
Min journey efficiency: 273.455696203

PORTS:
First einstein's patch
SHIPS:
Tibor's algorithm for ship
------
END OF SIMULATION: time interrupt
86/1200 (7%) delivered
------
Total time: 40001.4
Mean utilization: 29.8099504514
Mean journey distance: 1095.425
Mean journey efficiency: 10.6925650075
Min journey efficiency: 274.544303797

PORTS:
Very basic port class.
SHIPS:
Very basic ship class.
------
Total time: 20334.6
Mean utilization: 17.5978586335
Mean journey distance: 323.243333333
Mean journey efficiency: 1.84243832456
Min journey efficiency: 10.6582278481

PORTS:
Very basic port class.
SHIPS:
Einstein's ships algorithm
------
Total time: 19864.8
Mean utilization: 17.9751887314
Mean journey distance: 325.410833333
Mean journey efficiency: 1.75600830263
Min journey efficiency: 6.7731092437

PORTS:
First einstein's patch
SHIPS:
Very basic ship class.
------
Total time: 18684.0
Mean utilization: 17.1782591415
Mean journey distance: 288.136666667
Mean journey efficiency: 1.57103443669
Min journey efficiency: 10.6582278481

PORTS:
First einstein's patch
SHIPS:
Einstein's ships algorithm
------
Total time: 19994.4
Mean utilization: 19.0557622525
Mean journey distance: 345.719166667
Mean journey efficiency: 1.92729432396
Min journey efficiency: 12.8571428571

First two outputs are about Tibor's ship algorithm with two algorithms for ports. In both cases simulation was interruped by time limits. My idea is that: full ship (30 wares) is going to the port where are many wares, AND all the wares are to other ports. Then the ship can go to other port where are many wares too and the situation is the same as before. The ship is going around two ports and nothing happens.

I am not sure if it happens now, but I will try to fix it in some time in the future.

So my conclusion is that Tibor's algorithm for ships needs some revision. I don't know if it is only python version, but C++ needs to be checked too.

Another conclusion is that my simpliest patch to port algorithm (here is the link) is making some mess. For example mixing it with algorithm for ships is not a good idea (worse results!), but mixing it with basic ships algorithm is making very good results! In this test even better than my algorithm for ships! Mixing this algorithm with new algorithm for ships is not a good idea- it makes lots of problems and efficiency is lower. Maybe in the future I will find another, better algorithm, more suited for ships?

EDIT:

I've provided simple patch: if there is more than 80% of capacity for a ship, it doesn't go to other ports than those that are in ship's wares list.

And to be more specific: plain Tibor's algorithm (without any other patch) is not the best approach for extreme cases (lots of wares at once + large distances). As I can imagine, most of cases where people are not happy with ships are those ones.

Simple tests modifications shows that for most of cases current approach (very simple port & ship algorithms) are good enough. For more complicated and extreme cases modifications can be helpful.

einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top

Quote

Hey, I was away for couple of days, I could read (on a mobile) but had no comfort way to respond :)

I think you stress your ships too much. Mean number of wares waiting in ports above 60 and Maximum number of wares waiting in ports above 400???? But this is totaly unrealistic! Please recalibrate your test so that average number of wares in port is in range 10-20 and maximum wares in port about 50. That reasonably mimics games conditions.

in regard to your einst1 port algorighm (picking specific wares from a port when loading a ship) - It for sure has huge effect when ports are overloaded by wares, but in more normal conditions - like I indicated above - its effect will be probably lesser.

Top

Quote