Alternate routes

Topic: Alternate routes (Read 25712 times) previous topic - next topic

Alternate routes

January 06, 2009, 01:52:53 pm

It's long time i think of this.

Let's take two cities, A and B, at two corners of the map.

There can be a railways line between them.
There can be a bus line.
And there can be a flight route.

Now, in RL, there can be (and often there are) all three.
In Simutrans, only one of them will be used.
I would like to see different routes competing (maybe run by competing players).

Once one or more routes are found, we could extimate:
- the fare ticket
- the extimated time
- the number of transfers

A 20% of the p****engers will always choose the fastest route (Business travellers)
A 30% of the p****engers will always choose the cheapest route (Low Cost travellers)
A 50% of the p****engers will choose weighting speed, price and number of transfers (Ordinary travellers)

Re: Alternate routes

Reply #1 – January 06, 2009, 02:00:57 pm

I like the idea. It's simple, reasonable and would give more variety to p****engers transport. I support it, although I'm not sure about the percentages. Would be possible to modify them dinamically depeding on the situation of each area or zone?

Re: Alternate routes

Reply #2 – January 06, 2009, 02:11:17 pm

Of course,,,, this will be ideal simulation.
But I kind of remember this being said that, to do this, it requires heavy calculation each time p****engers are
created.

Re: Alternate routes

Reply #3 – January 06, 2009, 02:20:22 pm

I don't think I like the idea, because this will slow down Simutrans very significantly. Most of the time is spent on route-finding and its quickness is one of the main reasons that Simutrans is a succes. As far as I know route-finding will slow considerably if all possible routes must be examined instead of just one of the best (e.g. one with the least transfers).

Further on, fare ticket price (I think fabio means that) could be revenue/km * tiledistance, but estimated time is simply not known (or do you mean tiledistance / maxspeed, but that is really something different).

By slowing down I don't mean just 2 times slower, but depending on your network it could be 100 times to 10000 times (or worse) slower! Maybe things are easier if you are always looking for the least transfers and then take revenue and/or estimated time in account, but I'm not sure.

Re: Alternate routes

Reply #4 – January 06, 2009, 02:33:30 pm

@ Combuijs, i perfectly understand your point.

Probably my check could be limited to the 3 to 5 best routes with the least transfers.
The fare ticket price could be revenue/km * tiledistance.
THe estimated time, for our purpose, can be as well tiledistance / maxspeed

@ vilvoh, you're right, my percentage were just to give an idea.
the best solution would be to link the percentage to the level of the building generating the p****enger

Re: Alternate routes

Reply #5 – January 06, 2009, 02:40:49 pm

I hope there is a way to make this work. I reckon choice of top 3-5 routes (by current calculations) should be plenty.

Re: Alternate routes

Reply #6 – January 06, 2009, 03:16:04 pm

Another interesting idea. As to the speed of the simulation: it could simply be made optional so that people can have a choice between simulation depth and computation speed: after all, some people use much faster computers than others.

However, given that the AI is fairly basic at present, and that network multiplayer is a long way off, this is perhaps not a top priority for the time being.

Re: Alternate routes

Reply #7 – January 06, 2009, 03:19:38 pm

true, but also a single player can make, say, a train connection and a direct flight between two destinations

Re: Alternate routes

Reply #8 – January 06, 2009, 03:40:48 pm

I have just been looking at the code. The way that it works now is that p****engers search for a starting station before looking for a destination. Any station within range that is served by at least one line and is not overcrowded will do. If there are more than one that match, it chooses the first that it finds.

Then the p****engers that have a suitable start look for a destination at random anywhere on the map. Then they check to see whether they can get from their origin stop to their destination. If they can, they travel. If they cannot, they turn out as "no route".

To make this suggestion work, p****engers would have to be ****igned a destination before being ****igned an origin stop. They would then check whether there are any stops in the area that are not overcrowded, and then check, for each stop, whether it serves their desired destination. This is what would take the extra computational time: the number of route checks (which are computationally intensive) for each p****enger would be equal to the number of non-overcrowded origin stops within range, rather than equal to one.

Now, most p****engers do not actually go straight to a railway station or an airport from their origin station. Because the tile coverage of each station is only 2, most p****engers start and end their journey on a 'bus or a tram. P****engers will usually determine the best route to get from their origin to their destination (mainly in terms of the number of transfers), and so, every step of the journey after the initial 'bus or tram ride will indeed work in more or less the way suggested in any case (and the speed at which Simutrans runs already takes that into account).

So, making this change would not have a very big effect on gameplay (because most p****engers start their journey on a local 'bus or tram and make the more important decisions about how to travel at a later stage), but would also not have a particularly great overall effect on speed (because there would not be many origin buildings within two tiles of more than one p****enger stop that is not overcrowded). Furthermore, it would not be too hard to code.

I am currently working on a patch to make the number of p****engers willing to use public transport dependant on the level of private car ownership (defined in a private_car.tab in a similar way to the speedbonus.tab) and the level of local congestion, and I shall see if I can incorporate this change into that patch.

Re: Alternate routes

Reply #9 – January 06, 2009, 05:48:46 pm

I think the point Fabio states is not exactly that. For Fabio, the problem is not to choose one station or another, there can only be one for example. The problem is, once in a station, with a destination, to choose one vehicle, line, etc. or another.

There can be a solution not costly (in terms of simulation time). Calculate for each vehicle an average speed (only an integer updated each time a travel ends). The p****enger is presented three quantities: price of ticket, average speed and time he has been waiting so far. Based on that, p****engers go on or not.

This should be easy to try. I'll try.

Re: Alternate routes

Reply #10 – January 06, 2009, 06:06:12 pm

Quote

To make this suggestion work, p****engers would have to be ****igned a destination before being ****igned an origin stop

No, that's not the root of the problem, James. The problem is: Given a starting station and given a destination, what route will the p****engers select. Now it takes the one with the least transfers (and I think that, of the possible routes with the same number of transfers, just one is selected, the first it encounters). If you want to take the most efficient route (in estimated revenue or estimated time or whatever) you have to consider every possible route. That's a lot, I can ****ure you.

The solution you describe handles another problem: what start station should the p****enger take to get to a ****igned destination. In fact that's the same kind of problem as described above (given a starting station and given a destination), but then you ****ume that the position the p****enger is on is a station and there are routes (infinitely fast...) to each station in reach.

Quote

time he has been waiting so far

That was not in Fabio's proposal. You want to get rid of the p****enger if it takes too long? No one knows how long a p****enger is waiting!!!

Re: Alternate routes

Reply #11 – January 06, 2009, 06:34:11 pm

Quote from: Combuijs – on January 06, 2009, 06:06:12 pm

That was not in Fabio's proposal. You want to get rid of the p****enger if it takes too long? No one knows how long a p****enger is waiting!!!

I know, I know. I agree with you in that searching for a different/optimal route can be too time consuming, so my starting point is:

A p****enger is at a specific station with an already chosen destination and a route (with a already chosen transfer)
Depending on how expensive is the vehicle there, how fast (in reality, not maximum speed) and how much time he has been waiting, decide to go on or not

I think it doesn't depart too much from Fabio's proposal. This way you can have competing players for a fair share on p****engers. Some will choose the plane, others, the boat, etc.

What about waiting time then? There has to be an aging mechanism so that if there are no competing companies, all p****engers would end going on...

I know that now nobody knows how much time a p****enger has waited, but I have a devil idea in mind...

Edit: grammar

Re: Alternate routes

Reply #12 – January 06, 2009, 06:42:16 pm

Ahh, yes, the problem of choosing a station at random is easier to solve than the simplistic method of determining the best route, since changing the latter is likely to require a great deal of care, and might make the whole thing much slower. I am currently working on a patch to simulate competition between public transport and private cars that will also de-randomise the start station (will use the existing algorithm to find the best journey between any start station within range (up to a maximum of 5) and the chosen destination. I should be interested to see Isidoro's work on the patch to change the way in which p****engers compute their route...

Re: Alternate routes

Reply #13 – January 06, 2009, 06:56:01 pm

Quote from: isidoro – on January 06, 2009, 05:48:46 pm

This should be easy to try. I'll try.

wow, thank you, i'm very glad!

anyway, isidoro and combuijs got my point.

i think the only thing p****engers should have when they are generated is a flag which gives the the "business", "lowcost" or "normal" status and, once they choose a destination, the route is chosen according to this.

later, if this works, there could be facilities for business travellers to allow them to use a station (but not a bus or tram stop) and they would take into consideration the catering level of the vehicles in a line.

Re: Alternate routes

Reply #14 – January 06, 2009, 07:57:25 pm

Just to add a small suggestion... When deciding whether a p****enger is business/leisure/ordinary the type of origin tile and destination tile could be taken into account.
So commercial/industrial -> commercial/industrial would always be business.
residential -> commercial/industrial and vice versa would be ordinary (people going to work).
residential -> residential would be leisure.

factories would count as industrial, monuments and attractions as residential for the purposes of these calculations...

Re: Alternate routes

Reply #15 – January 06, 2009, 08:27:26 pm

I L O V E that idea kierogreen.....
I L O V E it!
I can't remember since when I hoped for that would be possible.
Just being mentioned some one other is happy enough.

Re: Alternate routes

Reply #16 – January 06, 2009, 09:19:59 pm

great! this is the idea i was waiting for!!!

Re: Alternate routes

Reply #17 – January 07, 2009, 03:50:15 am

Here's a patch that adds waiting time to p****engers as well as goods. In the station window the number of days waiting will appear in parenthesis if greater than zero. Since I'm playing with it, waiting time is neither saved not restored from saved games and counts from the loading time.

Next: add a real average speed for convois (not max speed), so that p****engers can decide on what vehicle they want to get on.

Re: Alternate routes

Reply #18 – January 07, 2009, 08:42:47 am

Quote from: fabio – on January 06, 2009, 01:52:53 pm

There can be a railways line between them.
There can be a bus line.
And there can be a flight route.

A 20% of the p****engers will always choose the fastest route (Business travellers)
A 30% of the p****engers will always choose the cheapest route (Low Cost travellers)
A 50% of the p****engers will choose weighting speed, price and number of transfers (Ordinary travellers)

We may try to solve this in another way:

If we have various types of cargo, why not to have various types of p****engers:
1. p****engers preferring trains
2. p****engers preferring planes
3. p****engers preferring boats and ships
4. p****engers preferring buses
5. etc.

Each p****enger will look for his favorite vehicle (yes, you may have p****engers preferring particular vehicle/engine/locomotive),
if it is not available then he take another one.

Just an idea ...

Re: Alternate routes

Reply #19 – January 07, 2009, 10:05:20 am

Quote from: isidoro – on January 07, 2009, 03:50:15 am

Next: add a real average speed for convois (not max speed), so that p****engers can decide on what vehicle they want to get on.

What about a commercial speed of a line? i think the whole line should be considered rather than only one vehicle (if a vehicle has no line, its commercial speed will be calculated as half or one third of max speed).
Commercial speed could be calculated as the number of tiles (km) to complete the whole schedule divided by the total time needed to complete it. It should be stored in line infos and possibly displayed in line statistics as well.

Re: Alternate routes

Reply #20 – January 07, 2009, 10:38:47 am

It might be good to have some kind of rating system for lines ("service quality" or something similar), which is calculated for each line every month, so that p****engers when they try to find a route only need to access that one field, the service quality, and then balance that with the number of steps for the individual journey, rather than each packet of p****engers trying to compute all of the service quality metrics each time that they want to travel - otherwise, the speed of the computation could be greatly slowed.

Re: Alternate routes

Reply #21 – January 07, 2009, 10:56:07 am

True. well, the line could have such parameters as
- commercial speed (as above)
- fare ticket price (it should be different for busses, trains, ships, airplanes, etc...)
- average catering level (when implemented)

every pack of p****engers would just use these statistics, stored within the line, to choose their favourite route

Re: Alternate routes

Reply #22 – January 07, 2009, 11:00:13 am

One thing about the ticket price, though: how would that be set? Currently in the game (and no doubt deliberately), players do not have to set an individual ticket price. Indeed, there is not a specific "ticket price" factor in the game at all: the revenues are calculated based on a highly abstracted means of working out what the employees of the company would set the ticket price at in order to maximise revenues. However, if there is now a possibility of p****engers choosing not to use a particular line because of the ticket price, that would not work, and the player would have to have more control; but is that level of control desirable? Some might perhaps consider it "micromanagement". One could simplify it by giving the player, per line, say, three levels of price (low, normal and high), the low and high variants of which would simply apply a divider/multiplier to the normal price.

Re: Alternate routes

Reply #23 – January 07, 2009, 11:23:29 am

For sure more expensive means (airplanes) gives more money to the player, so their fare IS higher.

On the other hand, i like the idea fo dividers/multipliers, given by line (maybe a percentage of normal price).

In this case, though, some travellers could decide not to travel (or to travel with their private means) if the ticket is too high and there are no alternative routes.

Re: Alternate routes

Reply #24 – January 07, 2009, 11:34:43 am

I very much like the idea of service quality. This would encourage the development of efficient networks (if your network is overcrowded and trains/buses have to keep stopping for congestion, this will lower service quality, and then in turn lower revenue).

Service quality could be based on one or more of the following factors:
- commercial speed as defined above (best as an average for past month or year or last 5-10 completed lines)
- frequency of route (how many services on that route completed the route in a certain timeframe)
- overcrowding on route - if convoy is regularly 100% full, decrease quality
- fares level (probably best just having low-med-high as Jamespetts suggests)
- catering level

Just one question about current behaviour though. Suppose journey A-B-C-D involves a train leg B-C. The train route B-C is served by Line 1 (W-B-C-X) and Line 2 (Y-B-C-Z). In current behaviour, does the game chose line 1 or line 2 before the start of the journey (so that the p****enger will only get on line 1 when he arrives at B), or does he get on the first of line 1 or line 2 which arrives at B, as line 1 and line 2 are the same between B and C?

Re: Alternate routes

Reply #25 – January 07, 2009, 11:46:46 am

Quote

In current behaviour, does the game chose line 1 or line 2 before the start of the journey

The system notes that the p****enger will go to D, and needs a transfer at B. The p****enger takes the first convoi that goes directly to B from A. Having arrived in B, it recalculates the route, and the system notes that the p****enger will go to D, and needs to transfer at C. The p****engers takes the first train going to C from B.

So in general, p****engers travel from station to station, not by line.

Re: Alternate routes

Reply #26 – January 07, 2009, 12:07:57 pm

Quote from: The Hood – on January 07, 2009, 11:34:43 am

I very much like the idea of service quality. This would encourage the development of efficient networks

I agree, although i would like to see different p****engers evaluating differently these different parameters: business will value the most the speed and the catering, but less the fare; leisure will valuse more the fare than the catering and the speed; ordinare will value the global quality of service.
I would still like to have two different lines both with p****engers, and both profitable.

Re: Alternate routes

Reply #27 – January 07, 2009, 08:18:00 pm

My idea is that the "real average speed" is on a convoi basis, since in a line, there can be very different vehicles. Is a line has 25 nice comfortable buses with sauna and ping-pong table and two donkeys, service of the line can be quite high but when in the station, if you see the donkey, would you go on it?

The second reason in favor of convois is the way I have thought to implement the price of the ticket. The price of the ticket will be the money I get divided by the number of p****engers I have transported. And that depends on convois, not on lines.

My idea follows like this: there would be a quality measure per station. That, and waiting time, would influence the behavior of p****engers to ride or not. And that also would make that a new company opening a new line on a public station with better vehicles will get nearly all p****engers while if there are no competitors, p****engers would ride at once.

EDIT: below is the second version of the patch. There will appear a real average speed for convois in the information window. Some preventions, though:

As things are not saved/restored, the speed will not appear until the vehicle reaches two stations after loading a game
To calculate speed, the Manhattan distance is used, as it is customary in ST. This can lead to better average speeds for vehicles running in diagonals, instead of squaring.

I've tried to be as economical as possible. The convoi stores the time when reaching a station. When reaching another, the speed is calculated as distance/time. Distance is known since the position of the last station is already stored. To calculate the average, a weighed average is used: new_average= 0.15*new_speed+0.85*old_average. This allows to have a running average but only store one value. The price is thus two more integers in the convoi cl****.

NEXT: devise a QoS (Quality of service) function based on price and average speed and make p****engers get on vehicles depending on that.

EDIT2: minor bug correction in patch

Re: Alternate routes

Reply #28 – January 08, 2009, 04:23:57 pm

Since you have the route, you can (at least in principle) also get the speed per tile. However, p****enger are anyway more interested in the speed between stations.

Re: Alternate routes

Reply #29 – January 08, 2009, 05:26:06 pm

One question.
If a line has 1 concord - fast but running once per month - and many standard airplanes - slow but running once per hour, people keep waiting concord ?

Re: Alternate routes

Reply #30 – January 08, 2009, 07:57:29 pm

Quote from: prissi – on January 08, 2009, 04:23:57 pm

Since you have the route, you can (at least in principle) also get the speed per tile. However, p****enger are anyway more interested in the speed between stations.

And it is less calculations too.

Quote from: z9999 – on January 08, 2009, 05:26:06 pm

One question.
If a line has 1 concord - fast but running once per month - and many standard airplanes - slow but running once per hour, people keep waiting concord ?

I'm thinking about a suitable formula now. The idea is that the concord will have (if price not too high) a QoS higher than standard airplanes. So, if at the station, p****engers will get on the concord at once. And if not, p****engers will wait some time to see if the concord arrives and, if waiting time gets high, they will ride on the vehicle with less QoS. I will work on it now and see because one thing is theory and another practice...

Re: Alternate routes

Reply #31 – January 08, 2009, 08:38:38 pm

Thinking about Isidoro's luxury coaches and donkey example for a moment: generally, p****engers decide which route to take based on generalised information about the service on that route, and then stick with the route despite the fact that it might not live up to their expectations (after all, if they are waiting in one company's station, they will not arrive in time if they have to go all the way to another company's station and wait for a train (etc.) there from scratch again). So the people not getting on the donkey is not a particularly good example.

A better way of representing that idea is to take into account whether a line has any obsolete vehicles running on it as a metric of service quality. There is already a specific function to test whether a line has obsolete vehicles, I think, used in setting the line's status colour to blue to indicate the presence of obsolete vehicles. A line with obsolete vehicles could be considered worse than one without. Choices should probably be made per line, since it is a particular set of lines' routes for which p****engers search.

Re: Alternate routes

Reply #32 – January 09, 2009, 05:52:27 am

It all depends on the example, as usual. You can mix donkeys in a line with ultra-modern buses in ST. If I'm said that line A has a QoS of luxury buses and I'm presented with a donkey, with all my respects to the donkey, I won't get on and go the consumers' office at once.

But things always get complicated,... that's where I've reached today:

My QoS indicator is average_speed/price_of_ticket. In the attached patch, you can see the ticket price for p****enger convois in their Details window (it is very nice to compare that with cost per km to see how many p****engers are needed to make profit).

This QoS is greater when high speed and low fares.

An now, the model: when a convoi arrives to load p****engers, it presents its QoS. The station has an average QoS. If the QoS of the vehicle is greater than the average QoS of the station, p****engers ride at once.

But, what if less? Well, it depends. If p****engers have been waiting too long, they are hopeless and will go on. If they have just arrived, they will wait. So, I needed a time to compare up to how long they will wait. And what have we got at hand? The average interval of convois arriving at the station is a nice time. After some thought, I came to the following procedure:

When a p****enger vehicle arrives at a station, this time is calculated: average_interval_of_convois*(average_QoS_of_station/QoS_of_vehicle-1)
If a p****enger has been waiting more than that time, he goes on; otherwise, he doesn't and wait.

If you apply the patch, you can see the average interval of convois arriving at a station in the details window of the station.

I was so happy... It seemed to work... But...

The problem I have not experienced yet but I fear it can happen:
A-B-C, three cities, A-B connection by plane, B-C connection by boat, a transfer station at B.

Average QoS at B is raised by planes but influences p****engers trying to go on slower boats to other destination. They wait for another vehicle to C in the hope there is a quicker one, but there isn't. That is not a problem of being planes and boats but that the QoS should be measured in connection transfers, instead of whole stations.

And now the question for all of you: is it worth the effort to work on improving the patch, and (specially to prissi) do you think is it worth the more data added if improved (one float per p****enger transfer connection) and do you think performance would be an issue?

In this version of the patch, the overcrowding patch is included, since I'm testing with both activated, but can be separated if need be later.

Re: Alternate routes

Reply #33 – January 09, 2009, 12:07:22 pm

Isidoro,

very interesting! Have not had a chance to test your patch so far, but it looks promising. It could fit in well with the patch that I am about to release relating to competition between the player's (and the AI's) transport and private cars for p****engers, in that your quality of service metric could be used for that, too. Do you think that you could add to your QoS metric the fact of obsolete vehicles on the line?

However, proper competition based on quality of service is an excellent idea, and could substantially enhance gameplay. It might work particularly well if the station radius coverage was increased from 2 to 3 tiles, or, even better, if different stations were given different coverage radii, specified in their .dat files (a large railway terminal therefore having more coverage than a small 'bus shelter).

Re: Alternate routes

Reply #34 – January 09, 2009, 12:57:29 pm

i'm glad of where my proposal is leading. thank you guys, keep on going!

but i can't see if my main point is still considered: can p****engers have different needs/tastes/profiles and choose different routes (also with the same company)?