Topic: Ships optimalization

I don't know if this is a good place for that topic.

Probably everyone had noticed that ships don't go in the fastest way. The same with port: they don't put products into the storage of ships in optimized way.

I was thinking about it and have some ideas. But i have a problem: can anybody help me with the implementation to the code? I haven't written anything in C++ yet, so I need any help in that.

My idea is something like this:

1. Add to the ships object a route (are they an object?) . It can be a simple table with destinations.
2. Make a function changing the route into the optimized route.
3. Change the port settings of getting rid of products. (And calling the ships because of stocks)

And some explanation:

Ad. 1:

The destination route should be a table connected to the ship separately. It should have something like this:

(port A is a starting position, port B is first destination, port C is second destination)

control number is default 0.

Then it should be added to the ship "current destination" number. It is always more than 0 (we start from A, so it can't be a destination in the route).

Ad 2.

We should think if the route is optimized. How can we do that? Our PRIORITY (that is important) is to get to the port B. But we also need to go to the port C. We should compare two routes: A -> B -> C (it is now) and A -> C -> B (is it better?).

We are thinking all the time about our priority: port B. So what can we done?

I was thinking about the math rules and I realized that we can easily draw a line and a point not on the line. then from two ends of line make another lines to the point and make a triangle. The main line is route from A to B, point is a port C. Two other lines are routes through the port C. Two cases are below:

The route here has length of 8. Alternative ways has length of 10 and ~11.31 (8*sqrt(2))

First one is for me acceptable and the ratio is 10/8=1.2. In the second case is sqrt(2)~=1.41. We can name this ratio as "k" or anything else. If we assume that route A -> B is "n" units length, we can check if the route A -> C -> B is kn or below length. Equation: D_abk>=D_ac+D_cb, Where D_p1p2 means distance between point p1 and p2.

This condition makes an ellipse with centers on port A and port B and the width dependence on ratio "k" (more k, more width).

But cases, when port C is behind the port B in small distance is also included here. To exclude them we should add two more conditions: D_ab>D_ac and D_ab>D_bc. Then the ellipse has two ends cut like here:

The ports A and B are in points (-5,0) and (5,0). Factor k=1.2

If the port C is inside the ellipse, we can optimize the route. In other cases- we can't do anything.

And the equation for any number of ports (if all is true, it can be optimized that way):

1. Sum of routes: D_ac+D_cd+D_de+...+D_(n-1)(n)+D_(n)b<=D_ab*k, k=1.2 or another --> try different values
2. Port C not behind the port A or B: D_ac<D_ab and D_bc<D_ab
3. Port D not behind the port A or B: D_ad<D_ab and D_bd<D_ab
4. ...
5. Port (N) not behind the port A or B: D_a(n)<D_ab and D_b(n)<D_ab

But! If we can optimize the route...

We should make some changes into the table of destinations (point 1. of this "article"):

So now I can easily explain the control number working: The priority of destination is port B. Sometimes the route is not as simple as above. Going from A -> B through the port C is optimized, but not through the port C and D (A -> C -> D -> B is not working). But if we go to the port C and think about the route to port B it can be optimized with port D. This mistake is because we have another starting point. We can delete the starting point (control number =0 ) only when the ship reached the destination with control number equal to 0. Between that it is going only between ports "optimized, not priority", with control number more than 0.

Ad. 3

Ports has two major things:

a) Stocks in the queue

Now stocks brought to the port are in queue and from that order are given to the ship. But if the ship has a route, we can choose products we want to transport there. So the priority of products will change. Not first from the list, but first from the list going to the ports from route (ship).

For example in port A we have:

And the route of the ship is like above (in the ship are products, but there is some space too).

So at first the port should add wood and bread to the cargo of ship (if there is a place for that).

b) Adding products to the cargo which are not included in destination route.

We should think at first if it is possible to transport in fast way. How can we do that? We can use function described above to check if we can do that. We can check if the port D is on the way (from A to B through C with factor k=1.2). If so, just add and OPTIMIZE the route (make A -> C -> D -> B or A -> D -> C -> B route). Check if there are more products to port D and add them.

Second thing is that sometimes there are products going two different ways. How can we checked that? Route A -> B through D with factor k=2. If it is true- it's on the way, but not exact (we can't optimize the way so we have to add the route on the last position). If false- it is optimize to leave products to port D in port and wait for another ship.

To summarize:

a) adding the products to existing route

b) adding the products where route can be optimized (k=1.2)

c) adding the products where route can't be optimized, but this is on the way (k=2)

And last thing (to be exact): in complicated route we have to compare (in point c) ) with LAST position of route. More complicated example:

Port (the queue):

Ship (the destination route):

a) products on the way:

fish, coal, gold ore, stone

b) trying to optimize the route with port E and port F: port E failed, but port F optimized between ports B and D. Products:

wood, iron ore

new route:

c) adding to the last position. Check the route A -> E -> D with k=2. True- add the products:

bread, water

New route:

Any questions? Just ask. Any mistakes? Please point them!

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

Top

Quote

teppo wrote:

Should the priority setting of a ware at destination contribute?

Yes. It can be done by making 3 lists: one for high priority, second for middle priority and third for low priority. Which priority has products going to warehouse? Low? I would make that.

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

Top

Quote