Maximum throughput of a rail line

Post all other topics which do not belong to any other category.
mmmPI
Smart Inserter
Smart Inserter
Posts: 2572
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Maximum throughput of a rail line

Post by mmmPI »

farcast wrote:
Sun Dec 31, 2023 6:20 am
Most of my time spent on this graph was thinking about approximation functions, specifically for the inverse of the displacement of the train's stop point over time. For some reason, the formula for stop point is too hard for wolfram alpha to find an inverse of. I tried, but I can't figure it out either. I simplified it to (e^(-2x) + (a - 2)e^(-x) + ax) = y but couldn't get any further. 'a' is a variable that's based on train stats so I can't just replace it with a constant. I just decided to make my own approximation function.
mmmPI wrote:
Sun Dec 31, 2023 1:01 pm
i will try to make it so that desmos can reuse the value it approximate when drawing the curve that is "Braking distance overtime + displacement overtime" or maybe get to understand why it cant. Maybe i could get wolfram to find the inverse of the braking distance over time and try to make the sum of those 2 inverse function , inverse braking distance and inverse displacement. But at this point i'm not yet understanding the reasonning behind the operation.

I am quite excited because i think i found a hack in Desmos while playing with the etiquettes for points :D made me happy , i haven't progressed much using it yet, but i feel it was worth sharing right away in case it can help saving some time. was investigating why it's so hard to combine the inverse of displacement overtime, and the inverse of braking distance overtime, to get the inverse of displacement of the stop point over time. It's just not possible to sum the 2 inverse functions, at least from a rigorous mathematical point of view ^^ , it feel like additions are very bad for inverse functions, x^x has an inverse, x^x +x doesn't ... so here's what i did :


https://www.desmos.com/calculator/fiallnerqa
you got any problem with that desmos.png
you got any problem with that desmos.png (157.87 KiB) Viewed 556 times


Yep , i just cheated, i asked desmos to draw the function that wolfram alpha didn't find the inverse but not according to the X axis, but rather the Y axis. This is a visual representation of what the real inverse function if it existed looked like. I think it also show why it would be really hard to combine the 2 inverse function "according to x". But it is correct to combine the 2 functions if they are drawn based on the Y axis a simple sum is enough. Symmettry so powerful !

Then just drawing the function is not really helpful, because one need to be able to use that inverse to give it some input and know the output. So really now the question is " which input should i give to get [desired value] as output ?" Which is not how one is supposed to use a function but there is a way to make Desmos actually answer the question and for one user to be able to reuse that value.

That's the tilde ~ thing that enable in Desmos the regressions and it's being abused so that instead of trying to find coefficient of a polynomial or fitting curve to some datas it is attempting to find the parameter that would make the fake inverse function equal to the block length B. And it's doing it pretty accuratly.

This trick can also be used to find the maximum or the minimum of a function. If instead of B for block length, you write 1000000000000 , Desmos will try to find the parameter to give to the function so that the result is the closer possible to 1000000000000 , which in case the function is never reaching it, will just yield the parameter that yielded the highest output value from the function. ( thinking about the "max throughput" which has no analytical solution one could use this technique if you want to reuse the value of "max throughput".)

I'm not sure yet how this shall be used for more practical purposes, i'm still somewhat copying/following your reasonning and atm i'm a bit puzzled about the initial velocity, or rest speed. For now it's only based on an initial speed of 0 so that would model the stop and go traffic, or at least be a first step toward it. I think computing the braking time from the braking distance is also something i will have to add, and i will have a look at how you did it :)
farcast wrote:
Sun Dec 31, 2023 6:20 am
It's mostly set up so you just need to insert the derivatives of the function you want to approximate in the taylor series calculations.
Advanced alien : here you can use this spaceship it's almost ready to go back to your planet, just make sure to insert the standard galactic coordinate of your system.
in both case me => :| :| :| :? :?:
My technology hasn't reached that stage yet , but i'm taking this with me for studying purposes :D

farcast
Long Handed Inserter
Long Handed Inserter
Posts: 86
Joined: Fri Jul 06, 2018 8:25 am
Contact:

Re: Maximum throughput of a rail line

Post by farcast »

Yet another graph!
Here's what's different:

I learned how to make an actual approximation function for the inverse of stop point displacement. This didn't change the results of the graph at all, but is once again what I spent most of my time on.

I changed the train displacement over time formula to match mmmPI's displacement formula, though I shifted it to the left by one tick to match how in game trains move forward in the same tick they accelerate. It also made using the approximate inverse functions more complicated.

The functions for Acceleration, Velocity, train Displacement, and stop Point displacement should now all be accurate to the game, if you ignore the speed limit.




I ran some tests in the junction test map. I simulated the infinite straight track with one long straight track going from one end of the map to the other.
Start of track.jpg
Start of track.jpg (27.41 KiB) Viewed 378 times

At the start of the track, block size increases gradually to 34 tiles.
End of track.jpg
End of track.jpg (102.95 KiB) Viewed 378 times
At the end of the track, gate sensors are used to measure a train's braking distance, and the rail signals are set to close if too many gates are triggered. The combinators are for blocking gate signals triggered by different trains. This is how I controlled the speed trains have at the start of a cycle. You only need enough gated blocks to guide a few trains at a time.

Number-wise, the graph gets really close to the test results.

mmmPi, I think the speed limit mod you used is forcing trains to behave the way the first graph I made assumed they would. That is, moving at a constant speed with zero acceleration. Using that graph gets the same results as your speed limit test.
Test results
Stop and go traffic only appeared at very low speeds and with high braking force. Even then, throughput wasn't affected all that much, though maybe that would change for very, very low speeds. I think an even more complicated model is needed to predict this behavior.

The gate sensors weren't detecting trains going slower than ~36km/h, so that's the lowest speed I could test.

Something interesting I've noticed is that I can't really test high speeds if throughput would be less than optimal. Trains along most of the track would move at near optimal speeds for maximum throughput, while trains at the end of the track would get a little faster after each cycle until they disappeared. I couldn't make the trains run faster than what would be optimal the whole time.



Now on to how I made the approximation function. Lagrange inversion theorem is what you're supposed to use, but the first road block was how to use this when the first derivative is zero for the function f(x) I want to find the inverse of. As it turns out, there's a way around that. You instead take the nth root of f(x) - c, and find the inverse of that. 'n' is how many derivatives are needed to get a non-zero result, and 'c' is the value of f(x) at the point you're approximating.

Here, f(x) = e^(-2x) + (a-2)e^-x + ax - a + 1

You can use this graph to play around with the Lagrange inversion theorem as I understand it. I set this one up so you only have to change the function you want to approximate the inverse of.

Then I used wolfram alpha to get exact definitions for the coefficients of the Taylor series of the inverse of the square root of f(x) at x=0. I found out a little late that if you have the Taylor series of a function (again, with a non-zero first derivative!), this page about series reversion has equations for the coefficients of the inverse series.



Now with the Taylor series of the inverse function, I can actually use a Pade approximate.

I ended up not using this in the end but I figured I'd mention how it would be used.

Using the same idea as before, I want the degree of the numerator to be less than the denominator, so that the overall function approaches whatever I add to the rational function as x -> infinity. Adding the function for the asymptote also changes the overall function's behavior at x=0, so I also need to subtract the asymptote from the Taylor series used to calculate the Pade approximant. [1/M] Pade approximants worked best out of all the ones I've tested.

Finally, x needed to be replaced with sqrt(x) to get the approximate inverse of f(x) instead of sqrt(f(x)).

This gets descent results across the whole function when 'a' is large, with a [1/3] approximate staying within +1.5% of the answer. It almost completely fails when 'a' is small, breaking +10% at a = 0.7. BUT! By design, this will still get descent results near x=0. As it turns out, small values of 'a' represent such extreme train stats that, in combination with the game's speed limit, the game only needs the near x=0 results.

Sadly, this still isn't good enough to avoid needing two rounds of Newton's method. Absolute difference matters more here than percent difference, and the precision needed to avoid random spikes and dips in the throughput graph is quite extreme.

I made a better graph for testing out an [L/3] Pade approximant. Again, you just have to change the function you want to approximate. 'L' can be whatever you want it to be, as I learned that the coefficients for the numerator are easy to calculate once you've calculated what the denominator should be.



That's how time from stop point displacement would be approximated with a Pade approximant. To explain what I actually used, I'll start with time from train displacement.

I went through all the steps needed to get an inverse series 'g(y)' of h(x) = e^-x + x - 1 at x=0 and for the domain x>=0, but instead of a Pade approximant, I combined the inverse series with a simplified round of Newton's method where the slope is assumed to always be 1.

This becomes N(y) = g(y) - ((e^-g(y) + g(y) - 1) - y) / 1 which simplifies to N(y) = -e^-g(y) + y + 1. Using the first four terms of the inverse series, g(y) loses effectiveness right about where h(x) becomes practically linear with a slope exponentially close to 1, so no matter how much higher g(y) is from the correct answer, a single round of Newton's method brings it spot on. This approximation stays within +- 0.005% of the correct answer, which is just enough to double some of the time calculations, or get negative results, when a train's max speed is limited by drag instead of the game, so one more round of Newton's method is still needed.

The inverse of f(x) I ended up using uses the same idea, with the difference being that the slope is assumed to always be 'a'. For a >= 2, the accuracy is near identical as with the inverse of h(x). The accuracy still plummets as 'a' approaches 0, but not nearly as quickly as with a Pade approximant, and I think it can be fixed by using more terms of the inverse series. The setup is much simpler, and it works better than everything else I tried.

Speed limiter blueprint:
Efficient inefficient design.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2572
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Maximum throughput of a rail line

Post by mmmPI »

I added an etiquette to show the max throughput and optimal speed. That didn't require to understand the method :)

I had run some other tests in game and found that your previous graph was (already) able to predict accuratly the throughput for values around the maximum that can be achieved, which was not with speed near 0, the closer to speed 0 the less accurate it was, i suppose this one is still very accurate for "high" speed , and better for low speed. I think i understand why, but i couldn't explain it in other word than "it is even more complicated to approximate around 0".

For it to make sense for everyone that would be interested, maybe it is useful to do quick sum up that from the original question "what is the maximum throughput of a rail line" ? at first the reasonning was to do some conjecture son how the trains would behave during such ideal situation, and then comparing the predicted throughput from those conjecture with in game, but it didn't quite match in some cases, it was possible to beat the conjectures or other problems of accuracies when increasing the signal spacing.

Instead the reasonning shifted to simulating train displacement in game with math which means dealing with acceleration and braking-because-of-signals which require data about train composition and air resistance. Then optimizing those equations allow to find the answer for the best throughput possible. ( i still can't mentally picture what i should try to express as equation to deal with various signal spacing, let alone solving them).

The latest method yield results very close from some initial conjectures for the max throughput, but more is precise and is much better because it allow to predict no matter the signal spacing and for almost every speed, not only the ideals scenarios, what will happen in game, albeit being not a perfect ingame prediction tool for very low speed.

At this point more precision is refining the simulation, but not going toward different reasonning, those graphs are good to use, at least there is no debate from my side, unlike earlier when it was conjectures about what is the ideal situation. This method is approaching it closer and closer but i'm unable to follow how.

farcast wrote:
Sat Feb 10, 2024 7:48 am
Something interesting I've noticed is that I can't really test high speeds if throughput would be less than optimal. Trains along most of the track would move at near optimal speeds for maximum throughput, while trains at the end of the track would get a little faster after each cycle until they disappeared. I couldn't make the trains run faster than what would be optimal the whole time.
To me that makes me think of the way gas molecules which will equalize density are represented, the way train spread accross a track to occupy it so that there is equal space between them all when possible, which breaks into stop and go traffic, on a circular loop, when the block size create discontinuities in the space trains are allowed to have between each other. Their braking distance acting as if there was constant collision happening to maintain such density constant in room for molecules of a gas or trains on a loop. If you put 2 or 3 or 4 or 5 or 7 trains, on a large loop with very close signals. they can eventually create and maintain identical distance between them which should be their braking distance.

Now in your experiment the track is not a loop but still i'm wondering :

Isn't it a little similar showing the relation between optimal speed and braking distance and signal spacing? In that the optimal speed train should have for throughput depend on the relation between the signal spacing and its speed, as such trains couldn't go faster, their braking distance would have not match the signal spacing of the track they are in.
Or in other words if they were to go faster than a certain speed, they would have to brake too early due to their braking distance reaching the next block, and as such their "best" speed would not be maintained, they would take more time to cross a block, there is a "optimal" speed depending on the train composition and signal spacing, which the train will "naturally" reach or try to reach, which is a certain relation between their braking distance and the bloc length, so that it's as much as possible occupied.

This is considering "density" is made stable at all time because otherwise the trains would "disappear". There is always the same number of trains existing at all time during setup, when one disappear, one reappear.

I'm thinking it is related to your previous observation somehow :
farcast wrote:
Thu Dec 07, 2023 7:17 pm
Interestingly, throughput is always highest when braking distance = train length + block length, whatever speed that ends up being.
I've tried to read the math this WE, but i was still haunted by your previous graph, this is way beyond my current level, i'm not able to contribute much anymore i feel i'd better focus on trains and making some tests in game or illustrations that demonstrate situations that are predicted by the model, to go along with the graph you made so it's easier to use and understand when train behave in a predicted way, and what is outside the scope of the model. ( stop and go, like traffic jams, but also different trains compositions interactions or uneven signal spacing , and how to measure the expected throughput of a straight rail piece between 2 junctions, when or what is the limiting factor such things.

I'm not sure i ca handle the answers you gave there but i already have plenty of other questions for those tests :

What if i forgot a signal and it stays as ghost and i can't see it ? how is going to impact the throughput ? should i consider the smallest block ? or an average ? and can a junction be considered using those formula as 1 long block and then count the proportion of trains occupying it to try and predict the throughput ? , starting simple with just an X crossing without turns, then adding 1 turn possibilities and measuring each time ? the quest for knowledge is infinite maybe there are other direction i wouldn't feel lost :D

mrvn
Smart Inserter
Smart Inserter
Posts: 5578
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Maximum throughput of a rail line

Post by mrvn »

EustaceCS wrote:
Sat Dec 23, 2023 8:28 am
mrvn wrote:
Tue Dec 05, 2023 11:37 pm
Does anyone have a formula for the maximum throughput of a rail line?
Hot take:
Purely speed-derived train throughput means nothing if cargo is not being actually delivered anywhere.

For usual cargo max throughput is 27.69 items per second per stack inserter working, in ideal case (12 inserters) it'll be 332,28 items per second per wagon loading/unloading.
As unit count per wagon varies depending on cargo, exact load/offload time may vary. Worst case scenario (4000 items in wagon) = 12,04 seconds to fill/empty the wagon.

For liquids, it's ABOUT 12000 units per second per pump, ABOUT 36000 units per second per wagon w/ 3 pumps. Actual speed will be slower due to fluid mechanics peculiarities.
Wiki sez that three pumps are emptying full fluid wagon in 1.8 seconds.

Cheers!
You can have more than one loading/unloading station with a single rail line connecting them long distance.

Post Reply

Return to “General discussion”