## News:

Do you need help?
Simutrans Wiki Manual can help you to play and extend Simutrans. In 9 languages.

## Wrong Passengers get on the train

Started by dennosius, December 30, 2012, 07:04:12 PM

0 Members and 1 Guest are viewing this topic.

#### dennosius

Hi!
I'm having a problem with my simutrans game.

It's actually more complex, but it can be simplified to this:

A--B--C--D--E

These are 5 towns connected with a high-speed railway line. C in the center has the airport, which connects the network with the rest of the world, so that's where most passengers want to go, but of course, some are also heading to destinations within A to E. B and D are bigger cities, A and E are a bit smaller.

What I formerly had were trains connecting A to B and B to C and so on, so operating only between two stops. That was easily manageable and worked well. But to make it more realistic and more comfortable for my passengers, I decided to have trains going all the way through and stopping at each station. So I made 2 new lines, one A-B-C-D-E and return, and one only B-C-D and return, because those are the bigger cities and not all trains need to serve A and E.

The problem now is: Simutrans' logic seems to prefer passengers for the next stop. So when a train heading to E stops at the airport station at C, it first loads all passengers for D and only loads passengers for E if there are places left in the train.

So what happens is:
- The train with the capacity of 400 is loaded full with passengers to D, although there were only 450 passengers waiting for D and 4,500 for E
- The train operates almost empty between D and E, because it picked up noone for E at C (it of course picks some up at D)
- The next train that only operates from C to D is almost empty, because the former train picked almost everyone up
- The passengers for E queue up at C to an illusionary amount

Am I doing anything wrong? Or is this Simutrans' logic?

In my eyes, this doesn't make sense. It may make sense in circle lines (so passengers less likely travel all the way clockwise of their destination is the next counter-clockwise), but it does make no sense in straight lines. For best results, it could be the other way round, but most realistic would probably be a proportional loading, because passengers don't care where a train goes after their respective destinations. So of there are, at C, 450 passengers for D and 4,500 for E, a train with a capacity of 400 should load 40 to D and 360 to E.

#### kierongreen

Passengers board trains in the order of stops on that line - so the furthest stop away will be the last to board. The reason this was chosen was to deal with the following situation:
`Express: A--------DLocal:   A--B--C--D`
Here if we take station A as an example - the local service will primarily fill with passengers for B and C, only taking passengers for D if there is space, meaning that most passengers for D will travel on the express. This code also tends to work reasonably well for circular routes. Of course other loading strategies would be optimum for other line layouts - such as yours. No single strategy will be perfect, most will result in certain networks failing to work correctly, or excess capacity being required. For example your proportional loading would require excess capacity on local services (that's not to say there isn't merit in your suggested strategy, but processing power required and time to code would have to be factored in also).

#### prissi

But if passengers accumulate, then capacity is missing between C and D, no matter what. In such cases always passenger will accumulate.

#### Sarlock

Your easiest solution would be an express train from C to E that skips station D.  If you are servicing E with only one train, you could set up an alternating local/express service that runs C-D-E-D-C-E-C.  This will ensure that the passengers going to/from E will be serviced as well as any passengers wanting to go to/from D & E.
Current projects: Pak128 Trees, blender graphics

#### Fifty

If you put a wait for load on the B-C-D-C Train at station C, you should be fine: the train handling the full line will continue, pax will load onto the shorter train, and when it leaves, the train running the longer route will have more pax for the termini. You might need another platform, though,
Why do we park on the driveway and drive on the parkway?

#### dennosius

#5

Quote from: kierongreen on December 30, 2012, 08:41:14 PM
The reason this was chosen was to deal with the following situation:

Sometimes solving one problem makes another occur I still think that the problem you describe would not be that bad if there's enough capacity on the express line. Furthermore, this is not a classic network. Those lines do sometimes exist, but local trains usually operate in straight lines crossing at the center, the distance train station. This could also be solved by letting pax prefer a train with less stops to the destination.

Anyway, my suggestion would be making this an option in the simuconf file wheter I want proportional or first-stop-first-served-loading.

Quote from: prissi on December 30, 2012, 10:18:28 PM
But if passengers accumulate, then capacity is missing between C and D, no matter what. In such cases always passenger will accumulate.

No, as I explained, there's enough capacity between C and D. But pax for D are picked up by trains to E and C-D trains are running half empty. With the direct connections between each stop, I needed around 20 trains for the whole network and it worked perfectly, now I have 36 and it doesn't.

Edit: I understand that my new network (compared to direct connections only) necessarily causes overhead, because no concept can be as efficient as direct connections. But Simutrans' logic makes the overhead unnecessarily large.

Quote from: Sarlock on December 30, 2012, 10:29:58 PM
Your easiest solution would be an express train from C to E that skips station D.

Yes, that could solve the problem, but it's not nice nor realistic. Again, E is a smaller town. A realistic train network would - as I did - not have direct trains to E in this case.

Quote from: Fifty on December 31, 2012, 01:10:32 AM
If you put a wait for load on the B-C-D-C Train at station C, you should be fine:

That is what I actually did to fix it: I added another platform with a queue track and wait-for-load-trains from C to B and D. It somehow solves the problem, but I consider this a dirty work-around. And it does not fully solve my problem, as my network is actually more complex than my simplified example:

`                    /-E--F--G--HA--B--C--D--Airport<--I-/ \-J                        \-K`
So I'd have to add more wait-for-load-platforms at the airport, but there's not much space left and it's not nice.

#### kierongreen

If we go back to the original example, of two routes, one C-D and one C-D-E then we can calculate the optimum strategy for train services (you can skip to the end if you just want a summary). My calculations are based on a simple network - complex behaviour can quickly emergy in large networks so the only way to be sure how a particular method worked would be to implement it.
---
I assume that 4 times as many people want to travel to D as to E, that 100 passengers are generated per cycle for D and 25 for E.

If a train arrives every 8 cycles for each route (i.e. equal frequencies) then there is the following table (assuming all passengers are carried):
`Waiting D Waiting E Travelling D Travelling E200       50      300       75      400       100      100       125       400   200       150      300       175      400       200      100       25        400   200200       50      300       75      400       100      100       125       400   200       150      300       175      400       200      100       25        400   200`
In this example trains on route C-D should be 2/3 the length of those on route C-D-E if there is to not be excess capacity. Incidentally, this is the same whether we have existing code or proportional loading.

Maybe having different length units is not convenient, to avoid having wasted capacity we would want loadings like this:
`Waiting D Waiting E Travelling D Travelling E300       50      400       75      500       100      100       125       500   200       150      300       175      400       200      200       25        300   200300       50      400       75      500       100      100       125       500   200       150      300       175      400       200      200       25        300   200`

This doesn't happen with existing code though - passengers for D have priority so the number waiting for E builds up:
`300       50      400       75      500       100      100       125       500   200       150      300       175      400       200      100       125       400   100200       150      300       175      400       200      100       225       400   200       250      300       275      400       300      100       225       400   100`

Would proportional loading solve this? It turns out that it does, eventually, ending up with the following loadings:
`300       116      400       141      500       166      100       191       500   200       216      300       241      400       266      200       91        300   200300       116      400       141      500       166      100       191       500   `
That is, the number of passengers waiting for E has to build up  to a certain level before they will be transported, but it doesn't get out of control at least.

If you change the scenario so that routes are C-D-E and C-E, with 4 times as many passengers travelling to E as to D then proportional loading works in the same fashion, however the existing simutrans code actually works slightly better, with passengers having to wait less.

---

In summary - the existing code works as long as you are flexible on the length of each train (or are willing to tolerate empty capacity on some services). Proportional loading is more robust at balancing loads across trains, but at the expense of more waiting passengers in some situations.

#### Sarlock

You see, the citizens from city D are much larger and prone to violence than the passengers for city E... so when the train stops to pick everyone up, the city D citizens bully the citizen E people out of the way and fill the train and the poor city E citizens are left out in the cold waiting for the next train... where the same issue happens again.  Best to give those poor undersized people from city E their own direct train service
Current projects: Pak128 Trees, blender graphics

Not to be smart alecky - not meaning to be at all - but for me the best course of action in a game as complex as Simutrans is to look at all possibilities that exist - not what you would like it to be.  Sometimes you will find something even more interesting than you originally had in mind.

#### dennosius

Quote from: kierongreen on December 31, 2012, 06:35:10 PM
In summary - the existing code works as long as you are flexible on the length of each train (or are willing to tolerate empty capacity on some services). Proportional loading is more robust at balancing loads across trains, but at the expense of more waiting passengers in some situations.

Sorry to say, but your calculation is right only in theory under lab conditions. What you calculated is pretty much what I calculated myself (I used frequency instead of train length, but wouldn't mind 1/3 empty trains).

In practice, this does not work at all, because there is absolutely no way to predict in which order the C-D and C-D-E trains operate at C. What we can calculate (what I did by measuring travel durations between stops) is a statistical frequency which we can multiply with the capacity (in other words: For the same frequency, we need much less C-D trains than C-D-E trains, because travelling C-D-C is much shorter than C-D-E-D-C). But we can in practice never predict what train will operate at C next.

Also, Pax at C are not really generated consistently. It's an airport. Sometimes, two A380 have landed between two train departures, sometimes one and sometimes none. So even if the D:E ratio was consistent in each airplane, we don't know whether the ratio of waiting passengers for D has risen since the last train departure (because an airplane landed with more pax to D) or dropped (because no airplane landed and the last train took preferred passengers to D).

Each time when the C-D-E train comes in the "wrong" moment when many Pax for D are waiting, the whole cycle is wasted.

Without (unrealistic) wait-for-load trains, the only way is to have all trains operating to D and E (then, it doesn't matter where passengers want to go, if the capacity meets the total arrivals at C) or way too many operating just to D to minimize the chance that the C-D-E train picks up too many Pax for D. Both is a waste of capacity.

Just to look at it from the other side:
- I have no problems with capacity in D. Trains leaving D (in either direction) are almost never full.
- I have no problems with capacity in E. Trains leaving E are really never full.
- I do have problems with capacity in C. This means, that the whole problem obviously must be the loading logic in C.

Quote from: Roads on January 01, 2013, 02:51:03 PM
Not to be smart alecky - not meaning to be at all - but for me the best course of action in a game as complex as Simutrans is to look at all possibilities that exist - not what you would like it to be.  Sometimes you will find something even more interesting than you originally had in mind.

I just want to have a realistic simulation. Of course, computer games have limitations in realism, but this one is wilful. There are other possibilities, of course. As I said, I had direct connections from C to D and from D to E before, which worked fine. But is is not nice for Pax having to change at D. And I have wait-for-load trains at C to D now. But that's not realistic, because passenger trains don't wait at stations for load, and a passenger to D would in reality rather not enter this train and calmly wait there while the C-D-E train operates. The realistic (and calculable) solution is what I have: a train C-D-E-D-C that skips the smaller E from time to time.

#### kierongreen

QuoteI just want to have a realistic simulation.
A realistic simulation is very difficult to achieve - to do this you have to not only consider the current train which is stopped at a station, but every other train that could carry a passenger to their destination. Passengers then have to "know" whether it is better to get on the current train, or wait, factoring in whether there will be capacity on other services to accommodate them, and how long each service is likely to take to get them to their destination. As well as being more complicated to code this is slower to run. Simutrans-experimental tries to do more complicated routing and it is one of the major reasons it is slower than standard simutrans. Even with the more complicated routing there are still situations where the routing doesn't behave in the way anticipated.

QuoteSorry to say, but your calculation is right only in theory under lab conditions.
I didn't claim otherwise. In fact I specifically said the only way to find out how this would work in game would be to code it.

Features do not get added to trunk because they are coded, they get added because they will improve the game for players. Therefore before starting coding on a feature it makes sense to have a good idea that it is likely to improve how the game works. I showed my calculations so that there was evidence to substantiate my summary, that is that proportional loading would result in a more robust handling of passengers, but at the expense of a manageable increase in waiting passengers in certain circumstances.

It is important to have evidence to support any changes to simutrans. In a few simple cases it is obvious but more often this must be researched - this isn't just limited to your suggestion; bugfixes should show they have fixed a problem, optimisations should be supported by benchmarks, new graphics code should have screenshots so that people can judge whether they think this is an improvement, so also more complex routing should be supported by calculations to show it will actually improve routing and that the performance hit will not be too great.

As far as I'm concerned there is a case for investigating proportional loading, and I might well try coding it. But it will then need to be run on various (large) games to see how it actually affects real games before being added to trunk.

#### dennosius

As I initially pointed out: Under certain circumstances, specific loading logics are more efficient. Actually, in the scenario we are discussing, it would be most efficient to have the passengers for the last (and not first) station loaded first. If it's impossible (or not implemented) to find the right principle, it's the best to use an average one - which is proportional loading. The disadvantage for the scenario discussed here is at least as big as the advantage in the scenario the current Simutrans logic was made for (A-B-C-D with big stations at A and D and one fast A-D and one regional A-B-C-D train). It's pretty easy: Whenever the smaller destinations come before the major destination, the current first-stop-preferred logic works better. Whenever the major destination comes before the smaller destinations, it messes things up.

#### kierongreen

I thought ages writing a reply but I realised there really wasn't any point trying to convince you. Even taking into account proportional loading being more flexible it's still debatable whether it is better overall than first-stop-loading. You think it is, but for example, circular lines most definitely would be adversely affected by proportional loading. Actually if you have sufficient excess capacity then any loading strategy is fine, it's only when you have little or no excess capacity you run into problems. So the simplest option for you is to increase capacity on the line.

In terms of code though we actually have several options here:
1) Keep existing code
2) Change to proportional loading, if someone codes it
3) Have an option in simuconf
4) Give players ability to choose which method of loading - either by stop or by schedule, or by both.

1) is the simplest, and as such most likely option by far
2) will improve the game for some players, but will also result in complaints
3) will get unnoticed by most people
4) is the compromise option which results in an ever more complex GUI

I am looking into coding a proportional loading routine, however as I've already stated this by no means guarantees it will be incorporated into trunk.

#### dennosius

Quote from: kierongreen on January 01, 2013, 09:25:43 PM
I thought ages writing a reply but I realised there really wasn't any point trying to convince you. Even taking into account proportional loading being more flexible it's still debatable whether it is better overall than first-stop-loading. You think it is, but for example, circular lines most definitely would be adversely affected by proportional loading.

You are right. But I think the loading logic is the wrong point to address this. If we have a too high number of Pax at a station (or bus stop or where ever) that WANT to enter the vehicle, then everyone has a proportional chance to get on in real life. This is not debatable, is it? So the point to address issues would be whether Pax WANT or DON'T WANT to enter. In a circular line, a Pax for the next stop in real life would not enter the bus in the wrong direction and go all the way, even if the bus is half empty. So it should be a matter that has to be solved in routing logic and not in loading logic.

QuoteActually if you have sufficient excess capacity then any loading strategy is fine, it's only when you have little or no excess capacity you run into problems. So the simplest option for you is to increase capacity on the line.

The overhead required by this loading logic is excessive. As I said: If I have all my trains serve E and have enough trains to pick up the whole number of Pax at C, then of course everything is fine. But each train will be 75% empty between D and E. Of course, one doesn't have to care, there's enough money and everything. But the fun of the game is making transportation efficient, isn't it?

Quote
2) Change to proportional loading, if someone codes it
Shouldn't it be in there? I think proportional loading was there before and is still there for freight?

Quote
3) Have an option in simuconf

Yes, definitely. Although many people don't use simuconf, dropping a loading logic wouldn't be necessary.

#### kierongreen

Simutrans has no way of determining which line passengers or goods should be routed over. It routes between stops, and providing a line serves the destination or via stop for a packet it will travel along that line. Hence packets can travel either way round a circle - currently the first-stop-loading means that packets automatically travel the right way round a circle (unless there is excess capacity).

Simutrans has never had proportional loading as such. Currently the code loops over waiting goods/passenger packets starting with nearest stop and proceeding until the last stop on the line. In the past there was no ordering by stop, hence packets were just processed in an effectively random order (when goods are added to a halt simutrans first checks for 0 entries in the ware list, and if there are none it adds an entry, this means that goods arriving at a halt can be added at the start, middle or end of the ware list). Roughly speaking this would have given a form of proportional loading but by accident rather than design. Making sure it is truly proportional would need new code, removing halt sorting would be quicker and require much less coding but would result in rather random behaviour.

#### dennosius

Quote from: kierongreen on January 01, 2013, 10:10:40 PM
Simutrans has no way of determining which line passengers or goods should be routed over.
I know, but that's not a principle, is it?

As I understand the routing logic, Simutrans knows which stations are connected to which (probably for each type of freight). This is (again, I'm guessing, but cannot think different) calculated by using the lines (and vehicle schedules). The only additional information that would need to be stored in memory is the line and the number of hops (maybe with a factor, so bus hops count more than airline hops). When there's another line connecting two stations with less hops, the line information is overwritten. And then, loading checks this information (or maybe the information can be attached to the 'packet' of freight).

This would solve all problems: In circular lines, Pax would not travel the wrong direction (and really not and not just not likely). And Pax would prefer the fast train over the regional train.

What does simutrans do with the hops, by the way? There's a max hops setting in simuconf, that I always wondered what it was good for (not the option as such, but what simutrans is calculating with hops).

#### kierongreen

Hops is number of transfers, not number of stations passed through.

Unfortunately routing all passengers via the line with fewest stops isn't necessarily the solution. If one train has no stops and the other 10 you would always take the one with no stops, but what if one has 5 stops, the other 6 - then it gets a bit more complicated. Also if there were two lines with the same number of stops you'd want passengers to take either... So storing one line to take for each destination/via station is not the way forward. simutrans-experimental went down the route of more complex routing and as I previously mentioned, it resulted in passenger routing taking much more CPU time.

#### Iluvalar

Right now, all this talk make me consider a weighted pseudo-random distribution. That would consider :

*Distance/maximum speed
*Number of lines avalaible
*Amount of people waiting
*Number of transfer

To take the above exemple (C-D-E vs C-D). The distance would make the pax going to D enter first in both trains if they have the same speed. But, the amount of line avalaible would make the pax going to E "push" some of the Ds from the C-D-E train. If nobody is waiting, the result would be a 50-50 distribution in the C-D-E train.

However, if the train C-D-E do not take all pax to E. The waiting amount of pax for E would increase and the amount traveling in that train would then increase proportionally until all the network find an equilibrium.

Pro : This seems to find equilibrium with good results in all the scenarii I can imagine. It will also look pretty much "natural".
Con : As it is a random distribution, there will always be some fraction of stubborn pax that refuse to do what you want them to. Like one passenger that en up going the wrong way in a circle pattern (only to see the country    ). thankfully they would be a minority. The problem could also be minimized by increaseing the power of the weight ( W^2 or W^3 ). Which would reduce greatly the number of those.

#### Ters

Another con is increased processing demands, perhaps also memory.

#### dennosius

#19
All this makes sense, somehow, but will probably not happen in the near future (or only in experimental). Circular lines are indeed an issue. If there's no (easy implementable) way for Simutrans to discover what a circular line is and apply a different loading logic automatically (would not be that complicated: a circular line is a line that has no stop twice - this also applies for point-to-point lines, but loading logic doesn't matter for those), capacities on circular lines would become an enormous problem with proportional loading.

Thinking about it, I like the idea to set the loading logic in the schedule (by stop doesn't make much sense, as there can be and at central stations usually are circular and non-circular lines). Either by a checkbox 'circular line' (people that like to may still 'abuse' it for the regional train case to make things easier) or by a drop-down-box that could also include last-station-first-served (which makes things unrealistically easier for my case, just as the current loading for the regional train case).

Edit: And I promise: If who ever invests his time to code this, I'll invest my time to document this in the Wiki in German and English. Also because my question was (as far as I can see) not documented there, although loading logic is an important factor for network planning.

#### Ters

Mostly, but not strictly circular lines can have a stop twice, like A-B-C-D-C-E-A or A-B-C-D-E-F-C-G-A (figure . Do they benefit from circular logic, default logic, or something unique to them? There are lots of possible layouts that must be taken into account.

#### Iluvalar

Quote from: Ters on January 02, 2013, 02:05:27 PM
Another con is increased processing demands, perhaps also memory.
We already have distance and maximum speed avalaible on a per convoy basis. The remaining must be already polled to figure the pax that jump into the train.

As I conceive it, it would demand only a couple more multiplications. I dont believe it would be anything as demanding as the pathfinding itself or such.

#### kierongreen

It would, it really would. Even a 'simple' calculation like working out how many passengers are waiting for a line at a particular station may take a few milliseconds. Doesn't sound like much but multiply that by many lines and many stations and the processing requirements quickly become too great.

#### Ters

Quote from: Iluvalar on January 02, 2013, 09:32:36 PM
We already have distance and maximum speed avalaible on a per convoy basis. The remaining must be already polled to figure the pax that jump into the train.

As I conceive it, it would demand only a couple more multiplications. I dont believe it would be anything as demanding as the pathfinding itself or such.

AFAIK, the only thing that is currently read is which stations the currently loading train stops at. Once the game needs to start taking other trains into account, the game needs to operate on a much bigger data set, and the cost of that isn't so much dictated by the calculations done on them, as that the game must find those trains and load them from RAM into the CPU.

Someone has to actually write an implementation and measure it to see if it's just wasted work or not, though.

#### dennosius

#24
I think Simutrans does the calculations already in routing (correct me if I'm wrong).

When you connect a factory (or whatever) to two stations and connect one to the destination with a bus line with 5 stops and the other one with a direct bus line, pax would take the latter one. Simutrans calculates with the number of stops and even weights the type of transport (airplanes preferred over trains preferred over buses) and the number of transfers. This just doesn't work within the same station, because the routing calculation is not connected to (or stored for or accessed by) the loading mechanism.

Quote from: kierongreen on January 01, 2013, 10:42:03 PM
Hops is number of transfers, not number of stations passed through.

Then, documentation in simuconf is wrong:

`# Max number of steps in goods pathfinding# This should be equal or greater than the biggest group# of interconnected stations in your game.## If you set it too low, some goods might not find a route# if the route is too complex. If you set it too high, the# search will take a lot of CPU power, particularly if searches# often fail because there is no route.## Depending on your CPU power, you might want to limit the search# depth.max_hops = 2000# Passengers and goods will change vehicles at most "max_transfer"# times to reach their destination.max_transfers = 9`

Quote from: Ters on January 02, 2013, 06:47:39 PM
Mostly, but not strictly circular lines can have a stop twice, like A-B-C-D-C-E-A or A-B-C-D-E-F-C-G-A (figure . Do they benefit from circular logic, default logic, or something unique to them? There are lots of possible layouts that must be taken into account.

There's obviously another loading principle in simutrans: Freight is not loaded for destination if vehicle stops here again before destination. This should of course be kept. And this makes half-circle lines work. 8-lines need both. So definition could be "circular lines are lines where no or one stop occurs more often than once". This also applies to point-to-point lines (loading principles don't matter for those), triangular lines (doesn't matter either for the usual use cases) and half-circles (it's okay for them).

I also think that the effect on circular lines may be over-estimated. Because loading and the transfer station prefers pax for the earlier stops. But there, pax will be unloaded which frees room for pax heading towards the transfer station (which should go the other direction); they'll be loaded last, but if the amount is equal (which it statistically should be) and the frequency on the line not very high, they'll be loaded. So on circular lines, only pax travelling within the circle benefit from the logic and not pax to/from the transfer station within the circle, which should usually be the majority.

#### prissi

The routing only take into account the number of stops. Transfer stops count as 8 normal stops, the mode of transport is not considered. At a station each passenger only know their destination and their next stop. Not line/convoi information is stored. (Considering that millions already travel on average maps, you do not want to increase this).

If you look at how real life works: People will try to get on whatever train goes first into their direction. Shear probability will result (in overcrowded situations) into something like "proportional loading". Thus I am no saying you are wrong, but this proportional loading will (in the far more common situation A-B-C-D-E and A-E) more likely produce the situation that local and express line are not treated differently, i.e. both loading mostly for E and A and starving intermediate stops.

#### dennosius

#26
Quote from: kierongreen on December 31, 2012, 06:35:10 PM
If we go back to the original example, of two routes, one C-D and one C-D-E then we can calculate the optimum strategy for train services (you can skip to the end if you just want a summary).
Sorry, I recalculated your figures and they are not just wrong because under lab conditions, but wrong in substance. I think it's because you didn't take the time momentum into account properly.

Let me show you my calculation (again, lab conditions and just looking at getting the pax from C to D and E, not back and not between D and E).

We have 1.000 pax/month in C for D and E (and the same amounts in the other direction), of which 800 (4/5) are for D and 200 (1/5) for E. Let's assume a convoy capacity of 200.

For easier calculation, we also assume that distances between C and D and E are all equal (let's say 50 tiles each) and a train goes 100 tiles/month.

So the starting point is:
We have 5 trains/month leaving C and going all the way to E. The distance for each train is 200 tiles, so we need 10 convoys for this. Over-capacity is 800 between D and E, so on 100 tiles, makes a over-capacity of 80'000 units ('tileseats per month').

The required tileseat capacity is 800*100+200*200=120'000. The 5 trains offer 5*200*200=200'000. The difference of course is the 80'000 again (makes 40% over-capacity).

I claim that the (technically, not gameplaywise) best loading strategy here would be the other way round than it is, so last-stop-first-served. We could only have 1 of the 5 trains a month going through to E ('E-train') and 4 of 5 just going to D ('D-train'). Statistically, there are - at each train arrival - 160 pax for D and 40 for E. Again statistically, there will always be 200 pax for E waiting when the one E-train arrives (at least from the second cycle on), and so it will not take any passengers to D. The 160 D-pax that this train leaves are well distributed to the four D-trains (next cycle). This way, all trains are always full, over-capacity is zero.  D-trains only go 100 tiles, so we need 4 convoys for them, and the E-train still goes 200 tiles which requires 2 convoys of them, so we need 6 convoys instead of 10.

Lets try the same with proportional loading: Having 1 E-train and 4 D-trains a month. Again, statistically there are 160 pax for D and 40 for E at each train departure. So, D-trains go 20% empty in the first cycle. When the E-train comes last in the first cycle, there will be 160D:200E Pax waiting, so the train would load proportionally 89D:111E, leaving 71D and 89E. The pax to D will easily be picked up by the four other trains in the next cycle. But pax to E will accumulate, so the E-train will load more and more of them, but never 100%, because there will statistically always be 160 new Pax to D when it departs (unless there are so many pax for E that rounding leaves zero to D on the E-train, but we don't want so many waiting). Anyway, we see that a half departure to E would already solve the problem. We just set up one more convoys on the E-line, so 3 instead of 2. Together with the 4 E-trains, it makes 7 convoys. Tileseat capacity is 4*100*200+1.5*200*200=140.000, making only 20'000 overhead (14%), which is perfectly realistic (will be around 20% under non-lab-conditions).

Now let's try again the same with the current first-stop-first-served logic (one departure on the E-line, four on the D-line): There are always 160 new pax to D when the E-train arrives, which will be loaded first. So there will always be only 40 Pax carried to E. As the E-train only serves C once a month, there will be 160 pax/month left for E, while all D-trains are 1/5 empty. There will statistically always be new Pax to D, so we need more E-trains, just as with proportional loading. So let's add the half monthly service to E, just as in the proportional calculations. So we have 5.5 departures/month, which leaves 145 D-pax for each train which again leaves 55 seats for E-pax in the E-trains, but we need 200/1.5=133. To have 133 free seats, statistical average for D-pax must be only 67, which requires in total 10.5 D-trains (800/67-1.5)! So this is evidently worse than just having all trains operate do E (requires 13.5 convoys)!

Let's try the other way round and add more E-trains instead. Now, we don't add a half E-line-service per month, but one full E-line services to have 2. So required capacity for E is 200/2=100 in each E-train, leaving 100 for D. We now have 6 services/month, which means 133 new pax to D for each E-train. Too many. We need 6 D-trains (800/100-2). So it works, but 6 D-trains plus 2 E-trains/month requires 10 convoys, so nothing saved. Maybe add another E-train? Required capacity would only be 67 to E (200/3), leaving 133 for D, making 6 D-trains necessary (800/133). But it's 12 convoys.

In other words: Under lab conditions, the best possible result of not having all trains go through to E is as bad as having all trains go through to E. Under practical conditions, the result will always be worse.

Quote from: prissi on January 04, 2013, 04:16:14 PM
If you look at how real life works: People will try to get on whatever train goes first into their direction. Shear probability will result (in overcrowded situations) into something like "proportional loading". Thus I am no saying you are wrong, but this proportional loading will (in the far more common situation A-B-C-D-E and A-E) more likely produce the situation that local and express line are not treated differently, i.e. both loading mostly for E and A and starving intermediate stops.

First of all: aren't you contradicting yourself? If people try to get on whatever train, why shouldn't they get on the local train in your example? I also question that this was 'far more common'. Local trains usually do not operate between major stations, but they usually cross one.  Almost all subway, tram and local train networks I know (plus city and regional bus networks) build on this principle (sometimes with additional circle lines or other connections, but in core). If local trains operate between major stations, it's where population is very dense. But in this areas, pax (i.e. commuters) do use the local trains, just because they're cheaper.

#### kierongreen

#27
In simutrans passengers for a stop served by both local and express routes will get on the local train if there is capacity available. So prissi was correct and was not contradicting himself. I would suggest if you think proportional loading is a priority you create a working patch so that the benefits and drawbacks in gameplay and performance can be evaluated.

#### dennosius

Quote from: kierongreen on January 05, 2013, 02:13:43 AM
In simutrans passengers for a stop served by both local and express routes will get on the local train if there is capacity available.

Prissi was referring to real life, but I may have misunderstood him. And in Simutrans, this only works in a A-b-C line (caps are express train stops). In a A-b-C-d-E line, it again wouldn't. So in non-circular lines, the one and only use case for first-stop-first-served is any number of regional train stops in between exactly two express train stops. And in this use case, the loading logic minimizes overhead unrealistically (as I showed above, just the other way round; the overhead is theoretically zero).

Quote from: kierongreen on January 05, 2013, 02:13:43 AM
I would suggest if you think proportional loading is a priority you create a working patch so that the benefits and drawbacks in gameplay and performance can be evaluated.

I'm not saying anything is a priority. But I again want to summarize the result of my calculation above:

Whenever lines serve a smaller destination behind a larger destination (A-B-c, but not limited to Pax, also delivering glass to an electronics factory behind a brewery in Pak128 could be another example, as the brewery needs more glass), there is no way in Simutrans to reduce the overhead by having some convoys serve A-B-c and some only A-B (neither works with the same convoys alternating in schedule, of course).

Because no matter how many convoys serve A-B-c or A-B, it needs exactly as many convoys (capacity) as having all convoys serve c (under lab conditions, in practice it'll be always better to always serve c). And this is not realistic and the only reason for it is the loading logic.

Am I the only one that finds this problematic? Having only some convoys serve c is at least one of the obvious and realistic solutions. So it should be possible (ad reduce overhead and not create additional one, practically). Of course, the problem can be worked around. One can just bare the overhead and have all convoys serve c, or create point-to-point lines (A-B, and B-c or A-c). But a simulation game should try to make it possible to take all obvious realistic steps in planning, shouldn't it?

What is a working patch and how do I create it? Is there any chance it'll be successful, if noone of the experiences guys here seconds it?

#### dennosius

Ah. I thought I made clear that I can't code. I promised to document the loading in the Wiki in German and English if someone who can code takes his time to do so.

#### prissi

I still fail to see why proportional loading will work better in the A-B-C-D-E and A-C-E situation? It will starve at least B/D more of transport capacity than loading for next (B/D) first. Proportional loading is only required, if the busiest point is not the terminus of a line. However, most simutrans games I have every seen build automatically lines which terminate at major hubs.

#### dennosius

#32
Quote from: prissi on January 06, 2013, 11:12:55 PM
I still fail to see why proportional loading will work better in the A-B-C-D-E and A-C-E situation? It will starve at least B/D more of transport capacity than loading for next (B/D) first. Proportional loading is only required, if the busiest point is not the terminus of a line. However, most simutrans games I have every seen build automatically lines which terminate at major hubs.

You mean, if you leave out stops in the middle rather than at the end? In this case, it depends what you call "working better".

The current loading makes it unrealistically easy to leave out stops in the middle, because - as I have proven in the calculation - it reduces overhead to zero (theoretically under lab conditions). If 'as easy as possible' is 'working better' in your eyes, then it isn't any better. But then, last-stop-first-served should still be (optionally) integrated for lines that leave out stops at the end, because they'll be easier with that.

In the A-b-C-d-E case (I use small caps for stations that are sometimes left out), some Pax in Real Life would take the A-B-C-D-E train, even if they want to travel from A to E. If it's the same train class, just because it leaves earlier and will arrive earlier, although it stops in B and D. If it's a lower train class (regional train), just because it's cheaper (Simutrans would even simulate this by the speedbonus, if implemented in pak; also, even a slower train can arrive earlier if it departs much earlier, so there are good reasons for some people to take the regional train in this example).

What we had ages ago through the random loading (any packet was loaded that was in memory first) was not proportional. Of course, random loading is statistically proportional, but only after a long time, but (usually) not during one 'cycle' of trains arriving. This caused much overhead. True proportional loading would work just fine. Just set up A-C-E trains a little bit below the necessary capacity and A-B-C-D-E trains slightly above the necessary capacity. It depends on the actual case, but in practice it'll require around 15 to 20 percent more capacity on the A-B-C-D-E line than now.

The balancing under non-lab conditions is a bit tricky (but realistic). Because if pax for B and D queue up, the first thought then is: If pax queue up for B and D, I need more A-B-C-D-E trains. But more probably more A-C-E trains would solve the problem, as they free up capacity in the A-B-C-D-E trains for pax to B and D (the more pax the A-C-E trains take, the less A-C-E pax go on the A-B-C-D-E trains, leaving more space on those for B/D pax).

The two cases (leaving out stops in the middle or at the end) are two sides of the same medal. Mathematically, the current loading is optimized for leaving out stops in the middle, for the cost of making it unattractive (useless) to leave out stops at the end (because there's no way so save spare capacity/resources). If the loading logic was the other way round (last-stop-first-served), it would be just the other way round, leaving stops out at the end would produce unrealistically low overhead, and leaving stops out in the middle would become useless.

Again, this is the mathematical way of seeing it. But Simutrans should not optimize loading mathematically, but realistically. If any railway company in real life could steer their customers' behaviour as Simutrans does, they'd be well off (or bankrupt, if they leave out stops at the end ). Realistically, if there are more pax waiting for a train than the train can take, then everyone has an equal chance to get in (as long as Simutrans doesn't know who is the grandma that uses her handbag as a weapon).

Another way of explaining it without maths, but with pure logic is: What the current loading does in circular lines is simulating (or imitating, as good as possible) the 'will' of the pax not to travel the circle in the wrong direction ('not' here always means: only last). What it does when stops in the middle are left out is simulating the will of the pax that could use the fast train not to take the regional train (that will is - at least as absolute as simutrans does it - not even realistic, but with proportional loading, the will will follow the capacity offered, which is much more realistic: the more fast trains go, the less pax will choose the regional train for a fast train destination). Now, what the loading logic does when some trains leave out stops at the end: It simulates a will of the pax to the minor destination at the end, not to enter any train - and this of course doesn't make any sense and leads to bad results.

As we are talking about circles: The argument that lines that leave out stops at the end are less common is a closed circle argument. Something that doesn't work can't be common (maybe regional trains between major stations are only much more common in Simutrans than in real life because those are easier manageable than in real life). Anyway, we do agree that serving a later stop with only a portion of the vehicles is a standard measure in planning and operating transport networks, don't we? And a transportation simulation game should not prevent standard measures of transport operations, should it?

By the way, proportional loading also works better on any straight line, let's say A-B-C-D-E. The required capacity is in any case determined by the largest demand on the line, but if capacity is too low, the 'right' pax would queue up at the 'right' stations, and not all the pax for the last station (A and E). Apart from being unrealistic, this causes problems when you solve the queue by adding more trains, because the number of waiting pax can already be large and cannot be distributed further at A and E, giving wrong impressions of pseudo-under-capacity of local distribution lines at A and E.

Except for circular lines (current logic should be kept for those), proportional loading is realistic, reliable and calculable. All kinds of lines are well manageable with proportional loading, while lines that leave out stops at the end are currently unmanageable (at least if it's a bit more complex than just A-B-c, like in my case where I recognized this it's rather like a-b-C-D-E-F-G-h-i). Proportional loading would allow more realistic and complex lines and open up more opportunities for players to optimize lines.

#### yoshi

Let's assume following trains with capacity of 500 passengers each;

Train 1 serving A-B-C-B-A
Train 2 serving A-B-A

If there are 500 waiting passenger going from A to B and 500 waiting passengers going from A to C,

Case 1
With the current loading logic, train 1 takes 500 passengers to B, then no passenger will be carried by train 2.
There will be still 500 waiting passengers to C.

Case 2
With the proportional loading logic, train 1 takes 250 passengers to B and 250 passengers to C.
Train 2 carries 250 passengers to B.
There will be 250 waiting passengers to B.

In this case, proportional loading works better.
But of cource, the current logic works better if there is an express service serving A-C-A, as local trains don't carry many passengers going to C.

My conclusion: There is no perfectly realistic logic, as Simutrans passengers don't know the train timetable or train frequency or best connections to their destinations. Players should build a network which works best with the current logic.

#### dennosius

Your calculation approach is insufficient, because it disregards the time momentum.

Anyway, your result is just like what I said, but only, if "better" includes irrealistically easier. As I also said, "last-stop-first served" would work (mathematically) even better than proportional for the case you calculated, but it would still not be a nice solution as it was unrealistic.

By the way, one more argument not to favour lines that leave out stops in the middle for the cost of lines that leave out stops at the end:

In the first case, any 'overhead' is just mathematical. So some pax will use the 'wrong' train, but they'll still travel and reach their destination. In the latter case, it's true overhead (too many trains running empty too much and pax do not travel).

#### dennosius

I put all the pros and cons into a table for better understanding:

#### prissi

I really wonder about one thing you remarked. You said that in you example in D was always enough capacity and the same for all other outgoing stops. Since simutrans intercity passengers are generated symmetrically (same number travel in one direction than in the other) this points to that either lot of passengers in D are not generated (due to overfull stops). Otherwise there would capacity lacking between D-C as well as between C-D. (Hence my remark about missing capacity.) Or you did not played long enough and the overflow at C will be gone just after some years by itself.

It could also be, that there is a second, almost equally good route for passengers to leave D going via F; but then you will always have to built excess capacities in one directions, no matter what loading. That would occur no matter what loading is done.

The current loading came from the request of many players who wanted to create distinct local and express lines. As yoshi pointed out, this is most easily done with first loading (and also very efficent). Since currently you advocate proportional loading and at least more than 10 people in the past requested distint local and express lines (as "realistic") I have no big incentive to introduce proportional loading.

Proportional loading will also require much more computations, because first a list is needed to sort passengers after next stops of the vehicle, then find of those pakets a fair share of the actualy passengers (since thos packets must be integer). It will generate many lonely packets with only ine passenger per destinations, making chae misses more frequent and increases memory demand. However, this was just my envelop backside though of implementations. If someone comes up with something decent, I would be open for a simuconf.tab option.

#### dennosius

#37
In the model calculation, there was the line C-D-e. The model calculation took into account only pax that travel from C to D or E (just for the overhead calculation, I assumed the train goes back as full or empty as on the way there, which corresponds with what you said that the number of pax that travel from D or E to C should be just the same).

I did not take into account pax that travel between D and E. So in practice (and even in theory, if considered), the capacity would not be sufficient, but this applies to all loading logics. But this does in no way question the logic result. Because the logic result is right as long as the amount of pax that want to travel from D to E does not reach the difference between C-D and C-E passengers (so as long as they don't fill all empty seats in every train that occur when the C-D pax depart at D in case all trains serve E). And if they do, it obviously makes no sense to sometimes not serve E, so it's not the use case we are talking about.

But what you say is actually how I discovered that something goes wrong with current loading in this case,  I also assumed that demand should be equal for both directions. I did leave out E sometimes. So pax for E queued up in C. My first thought of course was, I just need more trains, but then I discovered that no one queued up at E, but trains were already leaving E almost empty (like 1/4 to 1/3 filled) and did not even fill up at D on their way to C. This is because if you look from the perspective of E, no stop is left out (all trains that leave from E serve all stops), so loading doesn't matter at E as long as there's enough capacity, and there was enough (already too much) capacity, as trains were leaving E so empty. So it became obvious to me that pax at C only queue up because the wrong pax are loaded and not because capacity was insufficient. This is how I discovered the whole problem.

So it's not about overcrowded stops, passengers not generated or a temporary thing. Just because of the loading, although all pax are carried from E to C (and D),  pax for E queue up at C. I know this sounds illogic. But this is reality, because the loading is illogic. That's exactly my point.

#### Iluvalar

Quote from: Ters on January 03, 2013, 05:32:48 AM
Someone has to actually write an implementation and measure it to see if it's just wasted work or not, though.
I'd like to, but I can't figure out where to look since I don't speak german. I guess it's a feature that the code is protected against me XD .

#### Combuijs

Quote from: Iluvalar on January 08, 2013, 07:22:47 PM
I'd like to, but I can't figure out where to look since I don't speak german. I guess it's a feature that the code is protected against me XD .

You would have to adjust the haltestelle_t::hole_ab routine in simhalt.cc. Only one comment in German, rest is in English. But you will see that it is not really easy, not because of the language, but because the code is a little tricky, thanks to a few exceptions in the load-handling (avoid overcrowded option, can load different goods in one vehicle and the fact that the loading takes place per vehicle, not per convoi). It is called from vehikel_t::load_freight in simvehikel.cc, which is called from convoi_t::hat_gehalten in simconvoi.cc. Other complication is that you have to round down the amount of freight to the nearest number when loading proportionally, which leaves you with a remaining capacity to be loaded (you could take one freight-item extra from each of the first destinations in the list).

In short, the complication is not the language but proportional loading itself, because it is quite processor-intensive.
Bob Marley: No woman, no cry

Programmer: No user, no bugs

#### hreintke

#40
Combuijs, Iluvalar,

Quote
In short, the complication is not the language but proportional loading itself, because it is quite processor-intensive

That is exactly right. I made a first implemetation of proportial loading in hole_ab. Initially it looked easy but now I am looking into methods of getting the remaining capacity distributed.

I attached working copy of the hole_ab with a lot of intermediate and trial code in.

Original post had wrong attachement. Now updated to the correct one.

Herman

#### Combuijs

#41
QuoteInitially it looked easy but now I am looking into methods of getting the remaining capacity distributed.

Remaining capacity should be less or equal to the number of different station destinations, so you could add one freight unit to the first "remaining capacity" station destinations.
Bob Marley: No woman, no cry

Programmer: No user, no bugs

#### Iluvalar

I dont get it, in this function there is 2 for loop that reset and use the same "i" int. Is that normal ?
hreintke, i dont see any change in your file. You probably posted the original one.[/size]

#### dennosius

Loading per vehicle (and not per convoy) probably increases CPU load. Maybe it is possible to add up capacity for the convoy (by load type, of course) first, and then load the vehicles after the proportional calculation? Vehicles within a convoy do of course not have to be loaded proportionally, there's no reason at all to do this.

This would also allow to check first whether we need to calculate at all, because we don't need to do any calculations if freight to be loaded is not more than available capacity (or available capacity is zero).

Also, loading per vehicle makes rounding a slightly bigger issue, because the smaller the numbers are, the bigger become the rounding effects. There are dozens of possible approaches to deal with proportional distributions if number of indicators is larger than number of distributable items (most of them developed for distributing seats in parliaments).

It's possible to round down first. Then, one easy approach is to distribute remaining capacity in the order of the rounded decimals (for the last seat, randomly if equal decimals). But afaik, ordering always causes CPU load. Maybe it's good enough to just load anything (as Simutrans did some time ago, so what is in memory/array/whatever first) on remaining capacity.

Does anyone know which rounding causes less cases where too few/many capacity is distributed? My guess is that financial rounding leads to a correct number not necessarily, but in more cases than rounding down. So it may save CPU load to do financial rounding and correct the result only if necessary.

Another approach is, instead of rounding: All numbers of waiting pax (or whatever, I'm using pax as an example) for served destinations are divided by all numbers up to the available capacity. Each result is marked with the destination it comes from. Seats in train are distributed in the order of results. For small vehicles/convoys, this might be even better than rounding, but I don't have a good idea of what calculations cause more or less CPU load.

#### Iluvalar

I still don't get why it's supposed to be CPU intensive. Here is what to do (sorry i'm coding in PHP most of the time so it's in pseudo-code):

instead of this part :
` if(  tmp.menge > maxi  ) { // not all can be loaded neu.menge = maxi; tmp.menge -= maxi; maxi = 0; } else { maxi -= tmp.menge; // leave an empty entry => joining will more often work tmp.menge = 0; }`
You do something like this :
`weight=tmp.menge; // let's weight only on quantity right nownewArray[0]=i; //save the freight IDnewArray[1]=weight;totWeight+=weigtht;validPosibilities[]=newArray;`
Then you totaly exit the for loop, and start another one based on validPosibilities. This way you know totWeight which is necessary.[size=78%] After recovering the same environement, inside you do :[/size]
`toLoad=floor(newArray[1]*maxi/totWeight); // maxi/totWeight should be cached actually since it is constant in that loopif(toLoad>tmp.menge){ toLoad=tmp.menge;}neu.menge +=  toLoad;tmp.menge -= toLoad;[...]`
Finaly, cycle again [size=78%]validPosibilities with a random offset to fill the last seats with it. The first possibilty should be enough[/size] unless there is very few freight in the stop.

I don't see what in that would be so CPU intensive. We have to store 2 short int in an arrray and there is 2 more addition and 1 more multiplication per freight. Unless there is hundreds of freight in the stop. Should be quick...

Or i'm completly wrong ?

#### dennosius

#45
This should be right. CPU load is a bit higher, if there are many stops on the line and/or many different load types in a convoy. But convoys with this constellation shouldn't be loaded every millisecond even on very large maps.

I'm also trying it with PHP-like pseudo code and human language:

`/*\$array[loadtype][destination][waiting|load] is the array that stores by load type and destination\$totalwaiting[loadtype] is the array that stores the total amount of waiting load (so the sum of all \$array[loadtype][x][waiting])\$loadedcapacity[loadtype] is the array that stores the total amount of what we actually want to load (so the sum of all \$array[loadtype][x][loaded])\$availablecapacity[loadtype] is the array that stores the total amount of available capacity for each loadtype*/if loading_logic=='proportional' { //comes from GUI setting for line or simuconf parameter    //First check what capacity is free in the convoy   foreach vehicle { (check load type and add up free capacity for each,  add up in \$availablecapacity) }   //if there's no free capacity at all, skip going through schedule   if (count(\$availablecapacity)) while (go through schedule until current stop is reached, even if another occurrence of current stop in schedule, or until a depot is reached) {         (collect waiting load for each stop only for load types available in convoy; also add up total waiting load for each load type; store in \$array and \$totalwaiting)   } //end if while   //do loading calculation only if we have anything to load   if (count(\$availablecapacity) && count(\$array)) foreach \$availablecapacity[loadtype as \$thisloadtype] {      foreach (\$array[\$thisloadtype][destination as \$thisdestination]) {            //Load proportionally if required, but load everything if capacity is sufficient      \$array[\$thisloadtype][\$thisdestination][load] = if (\$totalwaiting[\$thisloadtype] > \$totalcapacity[\$thisloadtype])  round(totalcapacity[\$thisloadtype]/totalwaiting[\$thisloadtype]* \$array[\$thisloadtype][\$thisdestination][waiting] ) else \$array[\$thisloadtype][\$thisdestination][waiting]            \$loadedcapacity[\$thisloadtype] +=  \$array[\$thisloadtype][\$thisdestination][load]         } // end foreach destination         //now deal with rounding error         //check whether to add or substract         if ((\$availablecapacity[\$thisloadtype] < \$totalwaiting[\$loadtype) && (\$loadedcapacity[\$thisloadtype] > \$availablecapacity[\$thisloadtype])) { //need to substract            \$i = 0;            while (\$loadedcapacity[\$thisloadtype] > \$availablecapacity[\$thisloadtype]) {               if (\$array[\$thisloadtype][\$i][load] > 0) { //we can't substract if nothing loaded already for this destination                  \$array[\$thisloadtype][\$i][load] -= 1                  \$loadedcapacity[\$thisloadtype] -= 1               } //end if actually substract               if (\$i < (\$count(\$array[\$thisloadtype])-1)) \$i++ else \$i=0 //go to next stop or back to first            } //end while substraction         } //end if substract         elseif    ((\$availablecapacity[\$thisloadtype] < \$totalwaiting[\$loadtype) && (\$loadedcapacity[\$thisloadtype] < \$availablecapacity[\$thisloadtype])) { //need to add            \$i = 0;            while (\$loadedcapacity[\$thisloadtype] < \$availablecapacity[\$thisloadtype]) {               if (\$array[\$thisloadtype][\$i][load] < \$array[\$thisloadtype][\$i][waiting]) { //we can't add if already everything for destination loaded                  \$array[\$thisloadtype][\$i][load] += 1                  \$loadedcapacity[\$thisloadtype] += 1               } //end if actually add                 if (\$i < (\$count(\$array[\$thisloadtype])-1)) \$i++ else \$i=0 //go to next stop or back to first            } //end while addition         } //end elseif add         //add here the actual loading on vehicles of that load type   } //end foreach load with free capacity} else { //current loading}`

Weight calculation has to be added, if that happens in loading. I have no idea how that works.

I think the effect for the capacity left free by rounding with this solution is that it also prefers early stops, but if there are 2 items free capacity, 1 will go to the first and one to the second stop (etc).

This can most probably be optimized by people who know coding better than me, but it should work this way. I think I considered everything in regard to dealing with the rounding errors (i.e. we can't repair rounding errors by substraction if there's already nothing to be loaded and we can't repair by addition if already everything is loaded for a destination).

#### hreintke

LS,

Quote
hreintke, i dont see any change in your file. You probably posted the original one.

Sorry for the wrong post yesterday. Attached is the hole_ab including my current work.
I will update my original post also for "late viewers".

Herman

#### dennosius

#47
I just had a look at the code.

As I said, I don't have a good idea of what uses more CPU load or not. But the solution seems to go through all stops/waiting load and then check if the vehicle is compatible. Isn't it better to check vehicles first and disregard mismatching waiting load? Because it's much more likely that the stop has more waiting load types than the convoy has load types.

Another tiny idea for it (probably also applies to current loading): There should be no loading to stops behind a depot on the schedule (before the current stop is on the schedule again). It is possible to set depots on the schedule manually on any position, and as all load gets lost in depots, so there should be no loading for destinations behind the depot.

#### hreintke

You are correct. First iteration is on stops then on goods. But as the comment says :

` // prissi: first iterate over the next stop, then over the ware // might be a little slower, but ensures that passengers to nearest stop are served first // this allows for separate high speed and normal service`

This is to make the current implementation work and

1/ The use in proportional loading in this loop is only to find out possible goods for loading
2/ I want to avoid duplicate code on other checkings already done in the current loop.
3/ The CPU intensive task comes afterwards anyhow when deciding what to actually load

Herman

#### dennosius

#49
I see. I don't know whether avoiding duplicate code has advantages in performance (or usability).

The whole hole_ab thing is called for each car? So if we wanted to load by convoy, we'd also need to change whatever calls hole_ab?

In the current loading, doing it by car is probably (almost) as good as doing it by convoy. You just fill up one car and then the next, without iterating through the stops again and again, because loading is stop-by-stop.

In proportional loading, iterating through the stops is needed for each car, if we load by car, isn't it? This wasn't effective.

Another question: What happens to load of the same load type, but different style (or how is the terminology? What I mean is, for example, books, glass, paper, beer etc require the same cars in pak128).

#### prissi

#50
It is more CPU intensive, since if the vehicle is fully loaded after the first package the loading is finished and the other packets does not need to be touched. Not to mention the allocation of vectors and freeing them again.

The proportional loading has first to find out how many passengers are able to go with the convoi (first loop over all matching catg in the stop). In a second loop the loading can be done. Doing this in one run with the total number waiting will not give a proportional loading but rather something like the algorithm which was in place before. (Of course the results of the first loop could be cached.)

However, you implementation has a serious problem: If maxi << total_waiting, then the chances are very height that menge*loading_percentage<0.5 = 0. In this case nothing would be loaded at all. In any case it seems that the convois will never be fully loaded with the intended number. You need some management for fractions, either sum them up and then take an extra passenger every xxx packets. And the routine must be using exclusively integers, since the results of floating point operations can deviate between compilers and implementations.

#### hreintke

Prissi,

I know about the "issue" that vehicles/convoys are not fully loaded when maxi<total_waiting.
That happens not only when "menge*loading_percentage<0.5 = 0" but due to rounding also at all other.
In fact you "loose" every fraction of  "menge*loading_percentage" for each of the goods you are loading

That is why I commented

`// need to update with additional loading due to rounding`
in the updated hole_ab.

The current is definitely only a working copy in which I wanted too show the way I was going.

Herman

#### dennosius

Having thought about it during lunch I am convinced that financial rounding will do better than rounding down. Rounding down will almost certainly lead to a result we need to 'repair' afterwards by another distribution, while there's a good chance with financial rounding that the result fits exactly the free capacity, so we can skip the second distribution step, or the rounding effect is at least small.

Also, 'repairing' the result (which may require to add or substract) will lead to a pseudo-proportional (because it's random whether and where we need to add or substract) distribution even for the rounding effect over time.
I'll modify my 'code' right now.

#### hreintke

Two updates in the new hole_ab with proportial routing.

1/ Solved an error that caused goods not to be removed from the halt
2/ Used financial rounding.

Financial routing indeed make the "reloading" less but in circomstances where limited number passengers can board on a vehicle it still leaves a lot to reload. An there is the possibility to "overload" in this version.

Next version will follow.

Herman

#### dennosius

#54
I'm really not good at even reading/understanding object-oriented code, so I already now apologize in case I misunderstood it.

But as it looks to me, you are making one calculation step too much by calculating percentage first and then applying percentage on waiting goods. The amount to be loaded for each destination is (capacity / all_waiting * waiting_for_destination). This may also cause additional rounding errors.

And do you actually add 0.5? Why? Is that a left-over from rounding down? Or are you trying to 'help' small amounts becoming loaded (the latter is not useful for small vehicles, I think, and not necessary for big ones)?

And yes, rounding still makes a difference and requires correction. Anyway, with financial loading, the probabilities of having to reload, having to remove load and having the right amount should be equal for any number, shouldn't they (again, I have not thought this to an end yet, but with financial rounding, it's at least possible that the amount fits, which is impossible with rounding down)?

Because of rounding effects, this all makes less sense the smaller the vehicles are and the more destinations they serve at the same time. That's why I propose to change loading so that it is done by convoy (but let's solve proportional by car first).

#### Ters

Quote from: dennosius on January 13, 2013, 05:35:08 PM
Worst thing that could happen is that different handling of fractions leads to one different loaded item, and probability even for this is really little (like once in billions of loadings).

From what I understand, that is very bad in networked games as it causes players to be kicked out. Game state must be equal for all players, or things get ugly.

#### dennosius

Then let's think whether it can actually happen. rounding (integer1/integer2*integer3) to the nearest integer cannot actually lead to different results, can it? I mean, no matter how the compiler deals with fractions, there's only one result that is mathematically correct.

And does, in network play, really each client do the loading? Or is it done by the server?

I can't imagine the whole Simutrans code works without fractional numbers to avoid differences.

#### Ters

Integer divisions are OK, but in general, the multiplication should come first. (integer1*integer3/integer2) I was (wrongfully) thinking of numbers like 0.5, which computer normally don't do mathematically correct.

#### hreintke

dennosius,

I am doing exactly (capacity / all_waiting * waiting_for_destination) but doing it in two steps as capacity/all_waiting (= loading_percentage) is constant as soon as we know the two figures -> only calculate one time instead of inside the loop.

The addition of 0.5 get us from rounding down to financial rounding, this way no additional rounding routine needs to be called.

if outcome = 2.4
> rounding down leads to 2
> rounding down leads to 2

if outcome = 2.6
> rounding down leads to 2
> rounding down leads to 3

Herman

#### hreintke

LS,

Took some more time as expected to get some special situations sorted out.

Attached is a updated proportial routing routine using only integer arithmetic.
It uses financial rounding to minimize the amount of goods to be loaded in the second phase.

For the last goods to load, for now I just took one by one from the availables.
Can be made much more fancy to get a really good proportial distribution.

Another possible optimization is to remember whether a destination halt already has been processed.

Herman

#### dennosius

Looks really good.

When doing the additional loading, are you checking whether everything for that destination is loaded already? Or is that a special situation you sorted out? I'm thinking whether this couldn't happen, but my first thought is it can.

#### hreintke

LS,

Yes, that can happen and is avoided by the line :

`if (loading_goods[i]->menge > 0)`

The special situation I encountered was that a halt can be multiple times in the schedule.
In proportial loading we first have to get a distinct list of goods which is available for loading.
My first versions were not prepared for that and counted those goods more than once, giving issues when actual loading.

Herman

#### dennosius

Alright. Subtracting if overloaded by rounding should be easy now (but I don't want to mess with your code).

Oh, a stop twice on the schedule is something I didn't think of. Additional entries for the same stop should of course be skipped.

What do you think of when you say 'make it more fancy'? What I can imagine is loading for destinations with the 'worst' rounding effect (rounded down most/up least) first. But that's probably a too intensive calculation. Any other idea?

#### hreintke

Subtracting if overloaded by rounding is handled by not loading more than maxi in the line :

`uint32 prop_load = min(maxi,((load_perc*lw->menge+50)/100));`

The fancy one is indeed getting the additional loading more proportional using something like largest divider but expect that also to be too intensive. Then you come into sorting lists and I think that should be avoided.

What needs to be done anyhow is getting it embedded in overall simutrans code. This code just sets
`bool use_proportial_loading = true;`
but that needs to be simuconf.tab and maybe even line gui configurable.

Herman

#### dennosius

Yes, it'll need a GUI setting, probably in the schedule, if we want the current loading to be preserved for circular lines. But a simuconf setting may do for testing as a first step.

Is there any chance to get one step higher in the code and have convoys (and not vehicles) loaded? This doesn't matter much for the current loading, but it does for proportional loading (smaller numbers make rounding effects bigger).

#### prissi

Since the lenght of a convoi is important and can cause different loading of different cars, the answer is a clear in principle yes but ...

#### Dwachs

I would not care about rounding errors that much.

First, one can use
`uint32 load_perc = min(XXX,((XXX*maxi)/loading_total));`
with any XXX, preferably a power of 2.

Second, one can keep track of accumulated rounding errors like
`// outside of loopuint32 remainder = 0; // or XXX -1 ??// inside loopuint32 prop_load = min(maxi,  ((load_perc*lw->menge+remainder) / XXX));remainder = (load_perc*lw->menge+remainder) % XXX; `

Parsley, sage, rosemary, and maggikraut.

#### hreintke

Dwachs,

I understand that you are calculating the remainder of goods still to be loaded because of rounding.

That is what I do in my code by keeping track of
- the amount actually loaded in the intial lop in "loaded"

Then using that in the second fase with

`while ((maxi > 0) && (loading_total > loaded))`

Or do you have something else in mind calculating the remainder ?

Herman

#### Dwachs

#68
Quote from: hreintke on January 23, 2013, 10:01:28 AM
Or do you have something else in mind calculating the remainder ?
The idea is, to calculate the remainder during the first loop. With the goal, that after end of the loop the remainder is close to zero. Then the second loop can be omitted. This routine (hole_ab) is called very often and thus critical to performance.

Edit: here is the complete loop:
` uint32 load_perc = min(100,((100*maxi)/loading_total));                        uint32 remainder = 0; // or 99 ?? FOR(vector_tpl<ware_t*>,  lw, loading_goods) { uint32 prop_load = min(maxi,((load_perc*lw->menge+remainder)/100));                                remainder = (load_perc*lw->menge+remainder ) %100; if (prop_load > 0) {  // proportional part can be too small                                         .... }; }          // no second loop, as remainder is already too small ... hopefully`
Parsley, sage, rosemary, and maggikraut.

#### hreintke

OK, I understand your idea.

Will do some theoretical and pratical tests with it and see how it works out.

Herman

#### dennosius

Quote from: prissi on January 22, 2013, 11:21:17 PM
Since the lenght of a convoi is important and can cause different loading of different cars, the answer is a clear in principle yes but ...

Why is it relevant in which car of a convoy something is loaded? Convoys never change (without loosing what is loaded). As I understand current loading, it is more or less random in which car something goes (something for early stops goes to front cars if those are free, but does this have any use?). Is load changed in loading (unloaded from one and loaded to another car), i.e. in order to combine load packets for the same destination?

It's mainly about rounding errors.

Quote from: Dwachs on January 23, 2013, 08:00:53 AM
I would not care about rounding errors that much.

Well, first of all we should not leave capacity empty, or, even worse, overload. So we have care about the rounding errors somehow, don't we?

I wonder how rounding affects loading. Of course, if we have large capacities and not so many destinations, it doesn't matter much whether we load one item more or less. But if we have a small bus or an early railway car with a capacity of ~20 that serve 5 destinations (for goods, even modern cars have a capacity around 25, they just usually don't serve that many destinations), rounding makes some difference. The probability of being rounded up or down doesn't change (or does it?), so if a convoy has 5 cars, numbers for a destination can be rounded down 5 times and for another destination rounded up 5 times. On the other hand, if this happens, there'll be more waiting for the first and less for the latter destination, preferring the first in the next proportional loading.

I still think that loading by convoy could have some advantage. In my understanding, it would also create less packets, thus saving some memory.

I like the idea of taking care of the remainder during loading. Effect should not be systematically different from that Herman did (it's more random). Does the proposed code take care of the cases that a) we cannot add a positive remainder as everything is loaded for that destination anyway and b) we cannot add a negative remainder because nothing is loaded for that destination already?

#### Combuijs

Quote from: dennosius on January 23, 2013, 12:50:05 PM
Why is it relevant in which car of a convoy something is loaded? Convoys never change (without loosing what is loaded). As I understand current loading, it is more or less random in which car something goes (something for early stops goes to front cars if those are free, but does this have any use?). Is load changed in loading (unloaded from one and loaded to another car), i.e. in order to combine load packets for the same destination?

Convoys never change, but can have vehicles that transport different good types. In order to get that right you need to group the vehicles of a convoi by good type and then change this in a chain of functions leading to hole_ab. That is simply a lot of work, where a lot can go wrong in a (time-) critical routine. A lot of effort for small gain (the current change in hole_ab is very simple). I think that explains the "but" in Prissi's answer...
Bob Marley: No woman, no cry

Programmer: No user, no bugs

#### dennosius

Of course, when I say convoy I mean cars of the same type in a convoy. I think also current loading could profit from this, as currently loading by car requires going through the schedule again and again. Also, we could have (more likely) load for the same destination in the same car, and hole_ab had to be called much less often (of course, combining the loading capacity requires actual loading into the cars afterwards, but this also has to be done only once per convoy). When performance becomes an issue, it'll be on large maps with complex networks, and there we usually use more and longer convoys (and for 1-vehicle-convoys like most buses and ships, nothing changes).