[Bug?] Route Calculations

[Cyrus Hall]

Ciao-

I've been rather sick the last few days, so my simutrans time has been higher than normal.  I've been playing around with a Pak128 game, and have been enjoying managing the largest city I've ever attempted.  My tram networks were working wonders until one of the circulars got too long for the amount of traffic and passengers began to backup.  Literally.

My network looks something like this:

A ------ B
|           |
|           |
D ------ C

where the capital letters are stations.  Lets say the trams go CW.  What ends up happening is that the passengers at A bound for D do not get picked up until those bound for B and C are completely dealt with.  This is rather unrealistic, although it does make debugging one's routes a bit easier.

So, to fix the problem I put a pus on the A-D route (and, by symmetry, D-A), which added a fair amount of surplus capacity to the CW circular tram.  Nice!  Until suddenly it stops working, and the tram stops moving passengers from D to A.  This was mysterious behavior until I reread the simutrans about page, which says:

In Simutrans-Experimental, the journey time for each route is calculated, and passengers and goods will automatically take the route with the shortest journey time. The waiting time for goods and passengers bound for each station at each station is also calculated and added to the journey time when calculating the shortest route. ... Where passengers are within reach of more than one origin stop, they will first choose their destination, and then see which, if any, of the origin stops within reach connects to their destination, and then choose to depart from the one with the shortest route (measured in journey time (including waiting time)) to their destination. Passengers who have not been waiting very long at a station will wait for the line or convoy with the shortest journey time, but will board anything that gets them to their destination if they have been waiting a while (how long that they will wait for the best line or convoy is proportionate to the likely overall journey time)...

My suspicions were furthered when I noticed the "wrong" behavior started at the beginning of the mouth, and reverted to the old behavior at the beginning of the next month.  All of this together makes me suspect the new simtrans route selection code is doing something funky, and when route times are recalculated at the beginning of the month my wonderfully running routes get screwed.

To summarize, when things are working right passengers move on both the bus and trams from D to A, and only the bus from A to D (as the tram is unidirectional).  When they break, only the bus takes things from D to A.

No doubt, you'll want a save.  The trouble stations are Reedley central station ("D") and Reedley inner station ("A").  The bus is the RVg-KS 69 running between the two - the stations are the bus's only two stops.

http://simutrans-germany.com/files/upload/128-test.sve

When I saved that file the wrong behavior had not started.  When it's loaded, the wrong behavior starts immediately.  I'll venture a guess that route wait times are calculated on load and the beginning of each mouth.

Cheers,
Pugget

[jamespetts]

Pugget,

thank you very much for your report :-) This is not strictly a bug, but it does highlight an issue with the way in which passengers/goods select the best line or convoy. What appears to be happening is that what is considered the best line or convoy alternates every month because, whichever convoy is selected as the best will get all the passengers (except those who have had to wait a long time), and will be more overcrowded, and therefore have a higher waiting time, so every month, it changes between the tram and the 'bus. A fudged workaround would be to make the 'bus go via a distant waypoint on the way back, reducing its point to point average speed and making sure that the tram always wins and gets the D > A passengers, but this, obviously, is not ideal.

Ultimately, the solution would be to have a list of best lines and/or convoys, rather than a single best, but the trouble is that this would not only be complicated to implement, but would also potentially add such computational overhead that the game would be noticeably slower. I have currently frozen the features to try to get a stable version out, so I am not in a position to enhance this straight away, but it remains for consideration for the future.

Thank you very much for your testing - it is much appreciated :-)

Edit: On testing, it appears that making the 'bus stop at Reedley Greenfields on the way back cured the problem.

[Cyrus Hall]

James-

First off, I've switched to using my real name.  No reason to use a nick.

In the end, the behavoir was ok, as I just threw a couple buses onto the line.  The tramline was re-engineered shortly thereafter to increase capacity anyway.  Unexpectedly, rather than being annoying, I've found managing a large city to be a very satisfying challenge.  After almost eight years of game time I got my largest city running smoothly, and it's been handling additional load for a decade plus with only very minor tweaks (one new Tram car, some additional bus service).  I see a time in the near future where I will have to move to even more of a hub-spoke architecture, but the major elements are already in place, just waiting for the additional load (soon!).

In terms of passengers and routes, I would be interested in seeing if there isn't a way to more realistically handle the situation.  My current understanding, from gameplay, is that there are two levels of routing: end-to-end, from the beginning to end of an entire trip, and point-to-point within that trip.  Ie, an initial route is found, and then each hop of that route is scheduled such that the best connection between the intermediate points is taken.

In this case, we are only concerned with the point-to-point level.  From what I can tell from the interface, trip-times to stops in connected lines are already kept live.  It seems like it should be easy to generalize what ever underlying data structure is used to do that and then attach some probability to each entry, or use FCFS policy across the top-k.

Curiously, I just realized that simutrans could be an interesting proving ground for various ACO or Q-learning algorithms.  Instead of running Dijkstra's (which is what I assume happens once a month, on an end-to-end basis), use the passengers like ants in ant colony optimization and find the (probabilistic) shortest paths as part of the game.  It would distribute the computation over the entire simulation, would behave dynamically throughout time as routes got congested, and generally just be cool (never a good reason).

Although, now that I've hit the 1950's and EMD F7s have hit the scene, it's hard to stop wanting to just play. :-)  This is the first game I've played where I finally managed to hit the critical tipping point in PAK128 and have started to take in more money then I can immediately dispose of (I have ideas, no worries).  The F7 is a very sweet engine in PAK128...sporting that lovely Santa Fe livery I saw as I child several times (more likely it was an F9).

Cheers,
Cyrus

[cwlau9]

James,

I have also suggested it also. But with my poor English, somethings are not clearly expressed.

I think to get the passengers to use both routes, it is not necessary to find more than one best line and / or best convoy. The current logic can be used for finding them. Once the best line and / or best convoy is found, the transfer stops are in the list. I assume that within a single line, the travelling times between the stops are already stored. Then the only code that needs to be modified is the logic to decide whether the line can be used by the passenger. And the comparison is not time consuming. It just checks if the line can go to its next transfer stop and the travelling time is acceptable by the passenger.

Take, for an example, the passengers would like to go from A to C. In which, the best line is to Line 1 and Line 3 and to transfer at B. There are 2 lines that go from A to B and 2 lines that go from B to C, as the folllowing figure.

      Line 1 (wait 5 min travel 5 min)       Line 3 (wait 3 min travel 5 min) 
     ------------------------------>    ------------------------------>
A                                               B                                               C
     ------------------------------>    ------------------------------>
      Line 2 (wait 5 min travel 6 min)       Line 4 (wait 5 min travel 6 min)

When a passenger arrives at A, it will wait for Line 1 and expected to wait for 5 minutes. However, after one minute, Line B arrives first. As Line 2 can also go to B and the travel time (6 min) is less than the remaining waiting time (4 min) plus the travel time (5 min), therefore, the passenger rides on Line 2 and go to B.

When the passenger arrives at B, it will wait for Line 3 and expected to wait for 3 minutes. This time, Line 3 comes first and the passenger rides on Line 3 and go to C.


In fact, there should be 3 cases.

Waiting time of the best line: a
Travelling time of the best line: b
Already waited time of the passenger: c
Travelling time of the line to be taken: d

Case I: (c - a) + b >= d  --> Take the line
Case II: (c - a) + b < d --> Wait for the best line
Case III: the best line arrive --> Take the line

I think it should be easy to implement.

[jamespetts]

Cwlau,

the real issue with doing this is the amount of memory that it takes in otherwise very lightweight classes needed for use in intensive route searching algorithms. Knightly has recently produced some major changes to the route searching system to improve performance - I am not sure how a system of having, in effect, a vector of best lines/convoys would fit in with that system. I'd be interested in Knightly's views on the subject..

[knightly]

Hi James,

If I understand Cwlau correctly, I think what he proposes above isn't checked during path searching. Rather, it is checked in hole_ab(), the same place where you check if a ware packet has been waiting too long for the best convoy (or one of best line's convoys) and have to decide whether you will board the currently arrived but less optimal convoy.

So, what Cwlau means is, if taking the currently arrived, non-optimal convoy is faster than waiting for the best convoy (even when max wait time has not been reached), the pax will board the convoy regardless.

I think this is a good suggestion. In reality, if the fastest bus has left just before we arrive at the bus stop, we may take a slower bus if it arrives shortly, given that the travelling time of the slower bus is shorter than the remaining expected waiting time plus travelling time of the next fastest bus.

Knightly

[jamespetts]

If this could be made to work efficiently, it is a good idea indeed. But wouldn't this require storing the route times to each destination for all convoys and lines at each halt, rather than just the fastest one?

[knightly]

I don't suggest storing journey times for all convoys/lines. I think looking into the current schedule of the currently arrived, sub-optimal convoy and calculate the journey time from the current halt to the next halt should not require too much calculation, I suppose?

Edit :

Just want to make my point clearer : calculating the journey time from the current to next halt should only be calculated *once* when the convoy parks at the halt, instead of calculating it again and again for each ware packet during loading.

[jamespetts]

Why to the next halt? It would have to be to the next transfer for all the goods, so the calculation would have to be performed as many times as there are halts in the schedule (minus one).

[knightly]

Oh, sorry. You are right, need to calculate for all halts in the schedule.

But the calculation should be a bit different from add_connexion(). Instead of resetting journey time during calculation whenever the currently parked halt is encountered, accumulation should continue.

Assuming the following halt set up :

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

and the arrived convoy has a schedule as below :

A > B > C > D > E > D > C > B

Let's assume that the convoy is currently at the *first* C in the schedule. If a pax board this convoy to go to transfer A, it needs to travel C > D > E > D > C > B > A. On the other hand, if the convoy is currently at the *second* C in the schedule, the pax only needs to travel C > B > A which is shorter.

Edit :

I think journey times between 2 successive halts can be precalculated (for lines, stores in line's schedule; for lineless convoys, stores in its own schedule), because speed is only recalculated each month. If this info is stored, add_connexions() can also be speeded up. The only problem is, lines / lineless convoys without previous month's average speed cannot use current, still changing average speed. Need to use your estimate formula instead.

[jamespetts]

Hmm, interesting thoughts - thank you for that! I have been busy to-day with work on Pak128.Britain, but I shall have to look into that when I have some time. That might be a very useful way of optimising routing.

[jamespetts]

I have now completed a first attempt at this, which will be in the next version. Thank you to everyone for the suggestions :-)

[knightly]

James,

I think the following code for checking whether to board the current convoy :

if(tmp.get_besch()->get_speed_bonus() > 0)
{                                    
   // Try to ascertain whether it would be quicker to board this convoy, or wait for a faster one.

   bool is_preferred = true;
   if(cnv->get_line().is_bound())
   {
      const linehandle_t best_line = get_preferred_line(tmp.get_zwischenziel(), tmp.get_besch()->get_catg_index());
      if(best_line.is_bound() && best_line != cnv->get_line())
      {
         is_preferred = false;
      }
   }
   else
   {
      const convoihandle_t best_convoy = get_preferred_convoy(tmp.get_zwischenziel(), tmp.get_besch()->get_catg_index());
      if(best_convoy.is_bound() && best_convoy.get_rep() != cnv)
      {
         is_preferred = false;
      }
   }

   // Thanks to cwlau9 for suggesting this formula.
   // July 2009
   if(!is_preferred)
   {
      const uint16 preferred_waiting_minutes = connexions[tmp.get_besch()->get_catg_index()].get(tmp.get_zwischenziel()) != NULL ? connexions[tmp.get_besch()->get_catg_index()].get(tmp.get_zwischenziel())->waiting_time : 15;
      const uint16 preferred_travelling_minutes = connexions[tmp.get_besch()->get_catg_index()].get(tmp.get_zwischenziel()) != NULL ? connexions[tmp.get_besch()->get_catg_index()].get(tmp.get_zwischenziel())->journey_time : 15;
      const uint16 waiting_minutes = get_waiting_minutes(welt->get_zeit_ms() - tmp.arrival_time);

      if((waiting_minutes - preferred_waiting_minutes) + preferred_travelling_minutes < accumulated_journey_time)
      {
         continue;
      }
   }   
}

should be relocated within the following if condition :

if(  tmp.get_zwischenziel() == plan_halt  )
{
    Insert your code here
    ...
}

If the next transfer is not the currently examined halt of the schedule, it is just a waste of time to perform such elaborate check.

Besides, I can see that you call the same functions many times [ like tmp.get_zwischenziel() & tmp.get_besch()->get_catg_index() ] instead of calling them once and save the return values in local variables. This will incur extra overhead of repeated function calls, and will reduce code readability -- they make the program statements long and difficult to read. I often need to scroll to the right while reading your code.

Knightly

[jamespetts]

Knightly,

thank you very much for the suggestion :-) That will be implemented in 5.1.

[knightly]

Hi James,

First of all, thanks for relocating the code .

Looking at the following code again :

const uint16 preferred_waiting_minutes = connexions[catg_index]->get(next_transfer) != NULL ? connexions[catg_index]->get(next_transfer)->waiting_time : 15;
const uint16 preferred_travelling_minutes = connexions[catg_index]->get(next_transfer) != NULL ? connexions[catg_index]->get(next_transfer)->journey_time : 15;
const uint16 waiting_minutes = get_waiting_minutes(welt->get_zeit_ms() - tmp.arrival_time);

if((waiting_minutes - preferred_waiting_minutes) + preferred_travelling_minutes < accumulated_journey_time)
{
   continue;
}

I think you are trying to compare
(1) expected remaining waiting time + expected journey time of preferred line/conoy
against
(2) expected journey time of current convoy
Please correct me if I am wrong, but I believe the expected remaining waiting time should be (preferred_waiting_minutes - waiting_minutes)?

Besides, there is a problem regarding sign : all your variables are unsigned integers, but taking the difference between preferred_waiting_time and waiting minutes may result in a negative figure, causing variable underflow.

Casting to signed integer alone cannot solve this variable underflow problem, because if the remaining waiting time is negative (that is, the pax has waited longer than the expected waiting time), only expected journey time should be counted (instead of offsetting the negative difference against the expected journey time); otherwise, the time needed for the preferred convoy will be understated.

Edit 1 :

Just a minor suggestion : maybe it's better to name the variable "waited_minutes" or "minutes_waited" rather than "waiting_minutes"?

Edit 2 :

My suggestion is to replace the blue portion with :
( preferred_waiting_minutes > minutes_waited ?  preferred_waiting_minutes - minutes_waitied : 0 )

Edit 3 :

After second thought, although the above suggestion solves the bugs, it is not good. If the pax has waited longer than the preferred waiting time, comparison will always be only between preferred travelling time and expected journey time of the current convoy. Since preferred line/convoy is by definition faster, other convoys will not likely be considered. So, I would suggest changing the whole IF condition from

if((waiting_minutes - preferred_waiting_minutes) + preferred_travelling_minutes < accumulated_journey_time)

to

if ( preferred_waiting_minutes > minutes_waited && ( preferred_waiting_minutes - minutes_waited + preferred_journey_minutes ) < accumulated_journey_time )

Translated into words, that means the pax will not board the current convoy only if (1) they have not waited longer than the expected waiting time AND (2) it is better to wait for the best line/convoy than to travel with the current convoy.

Edit 4 :

A deeper thought. The waiting time stored in the connexion object is, IIRC, the average waiting time for any pax packet which boards any convoy that stops at the current halt as well as another directly reachable halt. Assuming there are Line X and Line Y, each with 1 convoy, that travels between Halt A and Halt B, and Line X is the preferred line. It is possible that the calculated average waiting time from A to B is 5mins (because we have 2 convoys in total from the 2 lines), but the actual frequency of Line X alone is 10mins. So, wouldn't this completely undermine any formula that tries to add remaining waiting time to preferred journey time, as the remaining waiting time will become understated? Besides, if waiting time is only an average covering all convoys serving between 2 halts, if one of these convoys arrive (albeit not the preferred one), shouldn't we expect to wait the expected amount of waiting time again before the next convoy arrives?



Knightly

[jamespetts]

Knightly,

thank you for your analysis and help of this one :-) Your suggested amendment will be in 5.1.

[knightly]

You are most welcome, James.

But, just to make sure you have not overlooked -- have your read my 4th edit?

[jamespetts]

Ahh, I hadn't seen the fourth edit, actually - thank you for checking. That is one of the drawbacks of using an average waiting time: it is a tradeoff between coding and computing complexity (and therefore performance) and accuracy of the simulation. Having anything other than one waiting figure per destination per stop would greatly increase complexity. There is some mitigation in the fact that the average waiting times include passengers (etc.) who wait longer to take their preferred convoy, but the problem will not fully be addressed unless there is a way of storing the waiting times for each and every convoy or line to each destination from each halt.

[knightly]

So, can you think of any change to the formula that makes it more compatible with the average waiting time?

[jamespetts]

Hmm, I'm afraid not... the only possibility is to add an arbitrary amount to the average waiting time in the calculation, but I doubt that that would do much good. I can't see any way around having to have a full list of destination/waiting time pairs if that part of the calculation is to be made more than a rough approximation. Being a rough approximation is not a serious problem in itself - the amount of time that passengers spend waiting to take their preferred line or convoy need not be particularly exact.

One change that I have made, however, to mitigate the issue that you raised is that passengers will not automatically board any convoy that will take them to their next transfer until at least one third of their maximum waiting minutes have expired: see this code:

Code Select Expand


if(!is_preferred)
{
const uint16 preferred_waiting_minutes = connexions[catg_index]->get(next_transfer) != NULL ? connexions[catg_index]->get(next_transfer)->waiting_time : 15;
const uint16 base_max_minutes = ((welt->get_einstellungen()->get_passenger_max_wait() / tmp.get_besch()->get_speed_bonus()) * 10) / 3;  // Minutes are recorded in tenths. One third max for this purpose.
const uint16 max_minutes = preferred_waiting_minutes > base_max_minutes ? preferred_waiting_minutes : base_max_minutes;
const uint16 preferred_travelling_minutes = connexions[catg_index]->get(next_transfer) != NULL ? connexions[catg_index]->get(next_transfer)->journey_time : 15;
const uint16 waiting_minutes = get_waiting_minutes(welt->get_zeit_ms() - tmp.arrival_time);

if(max_minutes > waiting_minutes && ((preferred_waiting_minutes * 1.5F) - waiting_minutes + preferred_travelling_minutes) < accumulated_journey_time)
{
continue;
}
}


This is probably a reasonable compromise for the time being. Thank you for all your input :-)

[knightly]

James,

Currently, the connexion object is inherently inconsistent -- it stores the best line/convoy and the travelling time with that best line/convoy. But the waiting time is determined by any convoy that stops at the current halt and the reachable halt.

I am just thinking : how about discarding the current waiting time mechanism, and estimate the waiting time using line/convoy's average speed?

For instance, if a line has 4 convoys supporting certain ware category, and given its average speed, takes 20 mins to go through all halts in its schedule, the estimated waiting time will be (20 mins / 4 convoys) = 5 mins for all halts on the line's schedule. Since average speed already takes into consideration factors like loading, unloading, minimum load, month wait time, congestion, etc, this estimate should be rather accurate. Lineless convoys can be dealt with in the same way, only that it is all by itself and thus its travelling time for a round trip will already be the waiting time.

In this way, waiting time in the connexions object will really be the waiting time of the best line/convoy. This approach increases consistency of connexion object, saves memory for storing waiting times, and the whether-or-not-to-board-the-current-convoy formula will become correct. You can even remove the 1/3 waiting time check too.

Knightly

[jamespetts]

Knightly,

the problem with that is that it does not take into account overcrowding: if a station is overcrowded, passengers cannot necessarily board the first convoy that comes, so have to wait longer. This must be taken into account when calculating total journey times. Also, if it only uses the best line/convoy to calculate the waiting time, then that, too, might be inaccurate, as some passengers may get to their destination faster using something other than the best/line convoy (and therefore wait less time), depending on the time at which they arrive.

[knightly]

the problem with that is that it does not take into account overcrowding

I see. I forgot this factor.

Also, if it only uses the best line/convoy to calculate the waiting time, then that, too, might be inaccurate, as some passengers may get to their destination faster using something other than the best/line convoy (and therefore wait less time), depending on the time at which they arrive.

I have already considered this. That's why my suggestion is to discard the current waiting time system instead of changing it to record only waiting times of best line/convoy.


Okay, probably there is really no better way to handle waiting times. I will stop thinking about it anymore

[jamespetts]

Thank you for trying... :-)

[Cyrus Hall]

Wow, I go on vacation, and come back to simutrans 5.1 and my passengers are taking multiple lines!  I really like the feel of the changes; things seem to behave pretty naturally.  Once I have some time to play a bit more I'll try and give a larger impression, but this is a really wonderful addition.  Thanks!

[jamespetts]

Cyrus,

I am very glad that you are pleased. Do let me know of any more detailed feedback that you have. Do you now find that it has gone too far the other way, for example, and passengers do not seem to care which line that they take, or does it seem to be balanced correctly? Do you find a big difference between short- and long-distance passengers in whether they will take a preferred or lesser line?

Thank you very much for your feedback, and I hope that you had a good holiday :-)