Re-routing of goods at each stop?

Topic: Re-routing of goods at each stop? (Read 10442 times) previous topic - next topic

Re-routing of goods at each stop?

January 26, 2009, 12:37:03 am

In my work to implement a revised revenue system, I have been looking at the code in the haltestelle_t cl****, and I have noticed that goods are routed in the following way: at their origin station, they find a route to their destination. ****uming that there is a good route, they store both the destination and the immediate next transfer in the ware_t object, then board the next vehicle heading for the next immediate transfer.

When the vehicle arrives at any stop, the goods check whether they are at their next immediate transfer. If they are, they call a disembarking method, which adds them to the stop. They then check whether the stop is their final destination: if they are, it deletes them and registers that the goods have arrived; if they are not, it re-runs the entire route search, and finds the next immediate destination, and repeats the whole process until the goods reach their final destination.

May I ask - is there a reason that the entire route is searched at every transfer? Would it not be less demanding on the CPU to store in ware_t, not just the handle to the next immediate stop, but a list of handles to all stops on the route, so that it only needs to re-calculate the route if something changes? I know that this would take more memory, but surely not having to call one of the most CPU-intensive functions in the entire program quite so many times would more than make up for it? Or is there a reason that I am missing somewhere...? (And if there is, it might be very useful to know it when undertaking future work on the code).

Re: Re-routing of goods at each stop?

Reply #1 – January 26, 2009, 02:50:36 am

The cl****ical space-time dichotomy in programming

What if two packets with the same destination and different routes arrive?
Is you proposal compatible with you dynamic routing patches? Wouldn't that cached routes get stale and not reflect present state of the system?

Re: Re-routing of goods at each stop?

Reply #2 – January 26, 2009, 06:10:31 am

Quote from: jamespetts – on January 26, 2009, 12:37:03 am

it re-runs the entire route search, and finds the next immediate destination, and repeats the whole process until the goods reach their final destination.

Afaik, if there are good packets with the same destination at the station, the packets are merged, hence no recalculation. If packets leave the station, sometimes a packet with 0 goods in it is kept at the station to cache the route.

You might want to have a look at this thread:
http://forum.simutrans.com/index.php?topic=1016.msg9403#msg9403
There, gerw is developing a patch for speeding up the route search. I dont know the current status of his work.

Re: Re-routing of goods at each stop?

Reply #3 – January 26, 2009, 09:23:15 am

Quote from: jamespetts – on January 26, 2009, 12:37:03 am

May I ask - is there a reason that the entire route is searched at every transfer?

It was used to adapt to changing networks. New connections can be introduced any time, or connections can be removed. The re-routing on each stop ensures that (a) goods always use the best currently existing route and (b) goods are proeprly removed from the system if there is no route anymore.

It could also be done by storing the complete routing graph, and updating that one upon each change to the network. I've chosen the method of re-routing because it seemed more simple and more robust.

Re: Re-routing of goods at each stop?

Reply #4 – January 26, 2009, 10:03:13 am

If the point is to keep track of network changes, i think we could store the route in one cache and recalculate it every time the player(s) do(es) create/delete/update a line (or, if stored, the waiting time for a packet is too long and it tries to get another route or leave the station, as in isidoro's patch).

Re: Re-routing of goods at each stop?

Reply #5 – January 26, 2009, 10:09:15 am

I think a patch like this is in the works. But cached data is not "robust" in the same sense as calling the method is. But it might be more efficient, and one can always argue, if the code is correct, cached data will never be corrupted. Just there is too much evidence against that, so I favored the other approach.

Re: Re-routing of goods at each stop?

Reply #6 – January 26, 2009, 12:30:08 pm

The cached version did not perform much better during profiling. Thus I am more with Hajo on this; albeit the final word is not said in this.

Re: Re-routing of goods at each stop?

Reply #7 – January 26, 2009, 12:41:55 pm

Quote from: prissi – on January 26, 2009, 12:30:08 pm

The cached version did not perform much better during profiling. Thus I am more with Hajo on this; albeit the final word is not said in this.

Can you post your profiles in the other thread? I think, at least for me, the caching saved some computation time.

Re: Re-routing of goods at each stop?

Reply #8 – January 26, 2009, 01:19:31 pm

The last ones you posted I could not compile even with ordered vector template. Thus the thing is still open.

Re: Re-routing of goods at each stop?

Reply #9 – January 26, 2009, 02:14:30 pm

Quote from: prissi – on January 26, 2009, 01:19:31 pm

The last ones you posted I could not compile even with ordered vector template. Thus the thing is still open.

My last patch http://forum.simutrans.com/index.php?topic=1016.msg11548#msg11548 compiles fine for me with r2227 and ordered_vector_tpl.h.

Re: Re-routing of goods at each stop?

Reply #10 – January 26, 2009, 09:13:33 pm

Interesting discussion - thank you to everyone for all the interesting information :-) One of the reasons that I am asking is, in the new revenue system that I am developing for Simutrans-Experimental, in which the actual journey time is measured, there will be far less merging of goods packets, because they will be more likely to be unique. With searching the route again at every stop, that is likely to take a great toll on performance. Two possibilities present themselves as solutions: (1) adopt Gerw's patch (or something like it), and have goods packets store their entire route; or (2) have some sort of meta-packet of goods, one for each destination, containing all the other packets, which is the only thing that searches for a route.

I am currently leaning towards (1), but I should be interested in any thoughts on the matter.

Edit: Having seen Gerw's post in the above link, it seems that there are a number of missing features from the patch that make it unsuitable for immediate use (including a memory leak) - Gerw, do you have any plans to fix those issues and re-issue the patch?

Incidentally, Isidoro, you mentioned "my dynamic routing patches": I am not quite sure what you mean, since I do not have any dynamic routing patches. It would, of course, need to be compatible with your patch for checking crowdedness of the stations, but none of my patches involve re-routing goods already in transit any more than they are re-routed now.

Re: Re-routing of goods at each stop?

Reply #11 – January 26, 2009, 10:33:58 pm

Quote from: jamespetts – on January 26, 2009, 09:13:33 pm

Edit: Having seen Gerw's post in the above link, it seems that there are a number of missing features from the patch that make it unsuitable for immediate use (including a memory leak) - Gerw, do you have any plans to fix those issues and re-issue the patch?

I will re-issue the patch, if prissi considers to include it into trunk. There are still features missing and it isn't working with a new revision.

Re: Re-routing of goods at each stop?

Reply #12 – January 26, 2009, 10:44:45 pm

@James: perhaps I should have said your ideas about dynamic routing...

Re: Re-routing of goods at each stop?

Reply #13 – January 27, 2009, 12:29:04 am

Gerw,

it might be very useful for Simutrans-Experimental if it could be reissued whether or not it goes into the trunk; even if it doesn't improve speed in default Simutrans, it may very well improve speed in Simutrans-Experimental.

Incidentally, does anyone have any views on the caching method versus the meta-packet method?

Re: Re-routing of goods at each stop?

Reply #14 – January 27, 2009, 07:33:26 am

Quote

Incidentally, does anyone have any views on the caching method versus the meta-packet method?

I do not see the difference between (1) and (2).

In gerw's patch, afaik at each station for each destination and goods category the next stop is stored. That means that the entire route is stored, but the data is distributed along the route.

Re: Re-routing of goods at each stop?

Reply #15 – January 27, 2009, 10:25:39 am

Dwachs,

ahh, interesting. That's different to my original thought, then, of just having a sorted list in each goods packet with all of the intermediate destinations, the first item of which is removed from the list at each transfer.