Author Topic: Load the farthest cargo first  (Read 965 times)

0 Members and 1 Guest are viewing this topic.

Offline Train-catcher

Load the farthest cargo first
« on: July 23, 2017, 01:57:57 PM »
Hello again!

There's another patch from me.

Here the changes:
- by default, convoy will load the farthest cargo/pax/mail at the current stop first (against to trunk where nearest loads first).
- You can still change this behaviour: just append a '!' symbol to the name of a single convoy or a whole line. There are nearest will load first, just as in the trunk. Yes, you should rename a single convoy or a whole line

Yes, now it carries a payload in the names. If this feature will be usefull, I could make a normal GUI switch for this.

Why you need this? E.g. it's useful on commuter lines which carries pax from some main hub to some perifery. If line became overcrowded, the main hub will accumulate pax to the nearest stops from the main hub (against 'trunk' behavior, when the main hub will accumulate pax to the farthest destinations). It's easy to resolve such a crowd congestion by introducing some line with duplicated nearest stops.
And flexibility is good, yeah!

But be careful with asymmetrical lines (e.g. circle lines). The first cargo will be loaded to the farthest stop in this shedule!

See my other topic to obtain a binary with this feature. There's also a link to my the Github repo fork.
http://forum.simutrans.com/index.php?topic=17256.0

In that binary there two features bundled: this one and auto-unbunching

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #1 on: July 23, 2017, 02:13:52 PM »
This has been discussed several times earlier, but has always ended up with nothing. I have forgotten why, but I think it might be that it is not as simple as it seems. Maybe due to circular lines, as you briefly touch upon.

Offline Vladki

Re: Load the farthest cargo first
« Reply #2 on: July 24, 2017, 07:01:06 AM »
Not only discussed, I have seen a patch for this a few years ago.




Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #3 on: July 24, 2017, 04:42:41 PM »
You don't remember why it was rejected either?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8795
  • Total likes: 319
  • Helpful: 229
  • Languages: De,EN,JP
Re: Load the farthest cargo first
« Reply #4 on: July 24, 2017, 05:12:02 PM »
Because it will lead to congestion very very quickly, because all intermediate stops will be congested faster too. Also it stops the ability to have express and local lines, since lading farest first the same passenger will step into local and express lines.

So now, when the passenger to far destinations start to accumulate, you can run an express line only serving fast destinations without any special line names.

Other than that, I am not perfectly sure I understood the target of the first request corretly.

Offline Vladki

Re: Load the farthest cargo first
« Reply #5 on: July 24, 2017, 05:57:17 PM »
I tried the patch that was available some time ago. It had a nice toggle to set whether far or near going pax have preference. But it was useful only i  some very specific cases.




Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #6 on: July 24, 2017, 06:01:54 PM »
It has been my understanding that it is impossible, or at least very difficult, to have express and local lines now. Local trains end up picking up long distance passengers because there are no short distance passengers (by random chance, or because it is difficult to get the balance or timing just right). The express trains arrives shortly after, and finds only short distance passengers, which arrived in the meantime. But they can't use the express, so the express leaves empty. Nobody on the intermediate local stops can board the local train, because it is full with passengers going all the way to the end, leading to crowding, and the express runs empty and at a huge loss.

I don't think changing loading order will solve this example, though. The long distance passengers would have to ignore the local train completely.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8795
  • Total likes: 319
  • Helpful: 229
  • Languages: De,EN,JP
Re: Load the farthest cargo first
« Reply #7 on: August 01, 2017, 10:21:20 AM »
No, the curetn system favours local passengers and leaving more long distance for the express. But the bigger problem is, that if far away passengers are loaded first, all passengers in the intermediate stops have to wait until no long distance passngers are left. These will overcrowd much faster.

(Simutrans had that system for a short time, but it was really not working well back then.)

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #8 on: August 01, 2017, 02:47:23 PM »
It doesn't matter if it favors local passengers over long distance passengers if there happens to be no local passengers at the moment. If the local train arrives first, then you also get exactly the problem you describe. The intermediate stops get overcrowded because the local train is full of long distance passengers and the (nearly) empty express train doesn't stop. Changing loading preference for either train changes nothing in this case. That only becomes effective when there is more than one train-load each of express and local passengers waiting at the station served by both local and express, which might not be ideal to begin with.

To get somewhat realistic behavior, the loading algorithm would probable have to take into account passengers waiting for the same vehicle/schedule/line on stations down the line, as well as the presence of other vehicles serving the passengers waiting. That gets complicated quickly.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 8795
  • Total likes: 319
  • Helpful: 229
  • Languages: De,EN,JP
Re: Load the farthest cargo first
« Reply #9 on: August 07, 2017, 02:31:09 PM »
Just to add to this discussion, here are the other two patches on loading behaviour.
http://forum.simutrans.com/index.php?topic=13983.0
http://forum.simutrans.com/index.php?topic=11194.0
As noted towards the end of the first thread, in principle you could have a per stop decision, if the largest waiting group, (emulated proportional loaded) neared (in coords or stops) or whatever should be preferred. In the end the gain versus the current implementation seems always apply for very special line setups.

Offline hreintke

Re: Load the farthest cargo first
« Reply #10 on: August 09, 2017, 07:18:04 AM »
What about this option :

Create an option to designate a line as "express line" with this behavior.

Local line   : A>B>C>D>E>F
Express line : A>  C>    F

Unload/Load algorithm for "this line" (generic)

1. Unload all cargo/pass with destination "this station" (as it now now).
2. If there is any expressline visiting "this station" and "this line" is a "non express line"
   -> unload cargo/pass which have destination on any "express line"
   -> load only cargo/pass which have destination not on any "express line" (using current procedure)
   else
    -> load using current procedure
   
This would lead to
 -> "express line destinations" not being served by "non express lines"
 -> cargo/pass transfer to "express line" when possible
 
Benefit
  -> Not complex ?
  -> Full backward compatibility when not using "express lines"
 
Less realistic
  ->  Not taken into account that there is a possibility to go "A>C>(D,E)" using "express line" first and then transfer to "non express line"
 
« Last Edit: August 09, 2017, 08:49:52 AM by hreintke »

Offline Leartin

  • Devotee
  • *
  • Posts: 796
  • Total likes: 287
  • Helpful: 44
  • !!!!!This user was banned for double posting!!!!!
  • Languages: DE, EN
Re: Load the farthest cargo first
« Reply #11 on: August 09, 2017, 01:04:14 PM »
Why isn't there a natural distinction between the lines in the first place?

Say you have a few lines:
1) A-B-C-D
2) A-D
3) A-E-F
4) D-G
5) F-G

If you were looking for a route A to G, There are 3 choices:
1+4 or 2+4, which both switch at D, and
3+5, which switches at F

In routing, the number of stations a line stops at do count. 3+5 would be better than 1+4, but is beaten by 2+4. However, the pax only remembers to go via D, not to use line 2. Since line 1 goes to D, they will take it if available first.
You could even abuse this. Line 2 only needs to exist technically, it does not matter if it's vehicles never actually arrive at either station. As long as pax think it exists they will attempt to use it and end up in line 1 instead.

It can be even worse. Assume you have 2 lines:
1) A-B-C-[...]-X-Y-Z
2) A-Z

If you want to go A-X, because Line 1 has so many stops, the routing would be smart enough to use the second line to reach Z and then go back to X. But since both lines go to Z, they might use the first line to reach Z, get out, get in again and move back to X. (I don't think they can just leave at X even though they would already be at their destination). This would only get worst if furthest stop would get picked up first.


Theory time - I assumethat the game does not constantly recalculate every possible connection for each train, but rather has 'distances' (shortest sum value for stops and hops) somewhat stored in a distance matrix, only recalculating them when a line is created or deleted. I assume that a vehicle loops through each further station and checks if there are pax for that destination in the current station, if so loads them up - until there are no further stations to loop through or the loop is broken because the vehicle is full. Couldn't it count the loops and check the loop count against the distance in the matrix for each station, to see if it's actually the best vehicle for that connection, and take the pax only if it is?

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #12 on: August 09, 2017, 02:16:23 PM »
The thing is that goods routing only selects which stop to go to next to reach the final destination, not which line to use (or rather vehicle, since there might not even be a formal line). Vehicles then simply load everything going to one of the stops it serves.

I think number of stops only makes a difference if there is a tie at number of transfers. Hence in your last example, a direct connection A to X will beat making a transfer at Z. It might even be cheaper and faster for the passenger, but the game can not know that without doing much more advanced calculations. That was one of the things Simutrans Experimental was made for, wasn't it?

Offline Leartin

  • Devotee
  • *
  • Posts: 796
  • Total likes: 287
  • Helpful: 44
  • !!!!!This user was banned for double posting!!!!!
  • Languages: DE, EN
Re: Load the farthest cargo first
« Reply #13 on: August 09, 2017, 03:48:25 PM »
I think number of stops only makes a difference if there is a tie at number of transfers. Hence in your last example, a direct connection A to X will beat making a transfer at Z. It might even be cheaper and faster for the passenger, but the game can not know that without doing much more advanced calculations. That was one of the things Simutrans Experimental was made for, wasn't it?
I thought it even was a setting, you could give each hop and each stop a value, and routing just adds them together. So an additional hop could beat a bunch of stops.

The thing is that goods routing only selects which stop to go to next to reach the final destination, not which line to use (or rather vehicle, since there might not even be a formal line). Vehicles then simply load everything going to one of the stops it serves.
Exactly - that's why the vehicle should check before loading whether it actually is the best vehicle for the destinaton the pax (or goods) want to go.
Say, you have Line 1, A-B-C-D-C-B, Line 2, A-C-D-C and Line 3, A-B-D-B. Each stop has a value of 1. So, you have a distance matrix like this:
Code: [Select]
  A B C D
A 0 1 1 2
B 1 0 1 1
C 1 1 0 1
D 2 1 1 0

So let's assume Line 1 arrives at A. It iterates through all following stops to check if pax are here. So add one to a Distance Counter(DC), next Stop is B with DC 1. In the Matrix, A-B has 1 as well, so take on all pax to B. Add one to the Counter. Next Stop is C with DC 2. In the Matrix, A-C has 1 due to the second line, so the DC is higher and no pax are taken. Add one to the Counter, next stop is D with DC3, it has 2 in the matrix, no pax are taken... done.
At B, Line one would take pax to C (or A if it's on the way back), but not to D. And so on.
All of this would be a check during "loading stuff into a vehicle", which is a step that might take a second longer without the player noticing outright, and routing would not be affected at all.

Of course, this is not something that could be changed without the player knowing, because it might be there is only one A-D vehicle among a hundred others, and all pax would wait for this vehicle, while currently, they would not. So it would change active maps, potentially destroy them. However, such behaviour would be much in line with current routing - If there are a hundret vehicles via X and only one slow horse via Y, but via Y is shorter, the same thing happens - it's just a bit easier to see if you check "via". Perhaps if the player could see the distance matrix somehow? (Which, even with no changes, might be a really good tool to have anyway ;))

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #14 on: August 09, 2017, 04:34:39 PM »
I thought it even was a setting, you could give each hop and each stop a value, and routing just adds them together. So an additional hop could beat a bunch of stops.

I just had some vague recollection of some discussion at some uncertain time in the past. Maybe that is how it is implemented, despite being meant as a tie-breaker.

To be able to say what is the best algorithm, I would have to see some simulations of different scenarios run with each of them. Unfortunately, Simutrans is a monolith where one cannot easily mock stuff. Not that doing such stuff is as easy in C or C++ as it is in Java or Python in the first place.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4247
  • Total likes: 175
  • Helpful: 149
  • Languages: EN, DE, AT
Re: Load the farthest cargo first
« Reply #15 on: August 10, 2017, 06:33:01 AM »
I do not see how such a change to the loading algorithm 'improves' anything. At the end, the players still have to adopt their style of play to the algorithm.
Parsley, sage, rosemary, and maggikraut.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 4806
  • Total likes: 191
  • Helpful: 108
  • Languages: EN, NO
Re: Load the farthest cargo first
« Reply #16 on: August 10, 2017, 07:41:48 AM »
Which I have. My trains only call at two stations, except for circular inner-city lines. (Sometimes I bend this rule, and suffer every time.) And no stop is serviced by more than one passenger line and one mail line, except hubs. (I count lines that serve the same stops, just in the opposite order as the same line here.) And there is never more than one direct link between hubs. That is the only way I can make it work. Not exactly realistic.

In addition, hubs are interconnected so that there are no circles with an even number of lines. The "only one direct link" is kind of a specialization of this rule.