Variable prices and multi-objective routing

[mopoona]

     One thing that makes balancing in Simutrans Experimental difficult is the system of prices with bonuses and refunds. I was thinking it is a good idea to allow the player to set prices (or price factors) for each route separately.


Let's say some Simutrans passengers are using the cheapest route and not the fastest (I'll come to this point later). The variable prices could allow players to offer a fast train and a cheap highway bus on the same route. Passengers that want to travel fast will use the train and pay more, the others will save money and use the slower bus.


Now we have to find a way to augment the routing system to use more objective functions than just travel time. I was thinking about using multi-objective optimization to do this. Instead of using just the time value on the graph you could use a scalarization of the objectives time, price and comfort. The shortest way algorithms would work the same way. The results are not necessary optimal, but yet "good" routes.
Additionally, you could separate all passengers in groups. Some might want to travel cheap, others fast or comfortable. Using different parameters of the scalarization, you could implement such a behavior.


If anyone is interested to read more about this, I could write a detailed description how this can be implemented (with formulas and examples).

[jamespetts]

Mopoona,

this interesting suggestion (or at least, its general theme) has been considered previously. My present view is to reject it on the grounds of its potentially excessive threefold complexity: (1) to the programmer (me); (2) to the user; and (3) to the computer (which would affect performance). The latter two issues are the most serious. The former could be overcome with sufficient time or readily if somebody else were to write the code.

The problems are these: firstly, to the computer, as far as performance is concerned, the current system for routing is highly optimised. The code was written by Knightly, and relies on there being only one value for rank ordering. He uses the Floyd-Warshall Algorithm for route finding to maximise efficiency. It would be theoretically possible to devise a function which would return a single number which was a composite of multiple factors (such as journey time and comfort), but this would greatly increase computational load, as, for each time that the value has to be returned (and for a large and well developed map, during a route finding session, this is a very, very large number of times), a formula (probably involving division) would have to be performed instead of simply returning a number.

However, what you are suggesting would require an even more radical overhaul than this. The current routing system is simply not built to contemplate the possibility of different passengers/goods taking different routes. It is built to calculate a single optimum route from everywhere to everywhere else. I can only begin to imagine the vastly increased complexity that would have to be introduced to the routefinding algorithm if this were to be made possible, and likewise the amount of computational effort that this would require. Routefinding is one of the most computationally intensive parts of Simutrans (this is why early games, such as Railroad Tycoon and Transport Tycoon simply let players transport passengers and goods anywhere - the computers of the day could not handle the routefinding involved), so any increase in complexity in this system would greatly increase the computational load and would very probably have a severely detrimental effect on performance.

Furthermore, there is conceptual complexity to resolve. How do we apportion which passengers are prepared to pay more for more speed or comfort? We would have to start generating passengers with different income levels (or at least, different priorities), which would increase the complexity of the passenger generation code in the cities. It would also create a micromanagement nightmare for the player. At present, players do not need to concern themselves with the actual prices charged. This is deliberate, as it makes things easy for players. If players had to set the level of prices (or even had the option to do so to change it from some default level), this would have two principal effects. Firstly, there would have to be implemented an entire (and doubtless extraordinarily) complicated system for determining how much passengers/freight are prepared to pay for any given journey. Competition as well as comfort/journey time and some sort of algorithm for working out whether it is worth travelling at all at any given price would have to be implemented, the latter of which would be by no means easy (where would one even start to calibrate it?). Secondly, players would now have to be concerned with the fares charged on every single route in the game (and, indeed, if one were to do it in a way that would not give players perverse incentives to split up routes that would be more efficiently run as one, prices from each point to each other point, just as with railway rate books in the old days). On an enormous network, the amount of micro-management that this would entail (especially where players are in competition with others) would be astronomical: if a player is serving hundreds of towns, having to worry about whether one has been undercut in one's 'bus fares from High Street to Lake Street in a small village on the other side of the map is really the last thing that a player who is working on expanding the network is going to be interested in doing. Indeed, so great would the work probably be, that, in all likelihood, players of large networks would have to spend all their time doing nothing but adjusting prices.

In short, therefore, whilst such a proposal would considerably add realism to the game, I cannot at present see a way of achieving that result in a practical manner that does not involve causing rather more problems than it solves. One small concession to relative pricing that I had considered in the past, and which might prove more practical, although about which I still have considerable doubt, is setting the speed bonus based on local competition rather than a global fixed figure for a given time, although even this would require considerable complexity to implement.

If anyone has any ingenious suggestions as to how to overcome all of these various problems and still produce the desirable elements of the results suggested, however, I should be very interested.

On an aside, the main difficulties in balancing Simutrans (both Standard and Experimental) come from a lack of emulation of certain dynamics (principally those relating to cost of asset utilisation) which I am planning to implement in the code as soon as I am able. I have developed specific proposals and detailed specifications for doing so (see here), and hope to begin making progress towards implementing them following the next Experimental release.

[archchancellor]

Hi,

I've thought about this at various times and agree that it would be nice.

I'm not sure the additional computational complexity is quite as bad as you fear. I haven't looked at the code myself (so I'm probably overlooking something), but I assume that when Floyd-Warshall is run on the network graph, that the resulting shortest-path routing matrix is constructed at the same time and only re-built if a new line / vehicle is added or at predefined intervals and that the graph edge weights are based on the travel time? In that case you could add a second weight to each edge that represents the cost of taking that edge. When it comes to re-building the shortest-path matrix, you simply run Floyd-Warshall twice, once with the time weight and once with the cost weight (and if you want a third time with some kind of weighted sum of the two) and create two (or three) shortest-path matrices. As the calculation for all three could be folded into the main calculation loop (the difference is only in the matrix values, not the actual graph), the computational complexity increase should be manageable. The memory requirement goes up of course.

When generating passengers you could then simply randomly assign to one of two (or three) groups (again proportion could be configurable). Fastest route or cheapest route (or mixed) and look up the routing in the respective shortest-path table. Where only one route exists, all passengers will take that route, where a fast, expensive and a slow, cheap route exists, they will split up.

Best Regards,
Mark

[jamespetts]

This is an interesting idea. I suspect that it would take somebody with more programming/mathematical skill than I to implement, however. Could you imagine comfort being included in this system, too, within manageable bounds?

[archchancellor]

Hi,

I've messed around with small parts of the simutrans code and would be happy to look into this. As I'm not overly familiar with the source code, could you point me to the file / function that handles the route finding, that would speed up getting started?

Comfort can probably be integrated into this as well. If I understand the current set-up then if the journey is longer than threshold X and the comfort on the trip lower than threshold Y, then the passenger will not make the journey, correct? In that case it should be possible to just have different thresholds for the different types of passengers.

Best Regards,
Mark

[jamespetts]

Mark,

the routing is all found in path_explorer.cc. Be extremely careful with this, however, as it is very complicated and exceedingly highly optimised by Knightly some time ago. By all means have a go at changing the system on a branch if you like, but you will really need to know what you are doing if it has any prospect of working, and working within an acceptable performance envelope (which means being able to run without obvious slow-downs due to routing on a massive (4096 x 4096 or above) and very highly developed map - a very stiff challenge), as this is very complicated. Be very aware also of non-obvious consequences of any changes, which might be far more far-reaching than at first appear. I suggest making the minimum possible changes.

As to comfort, it currently has no effect on routing at all: only speed affects routing. One of the very many potential complexities of adding comfort is that passengersstill need to be able to compare journey times without comparing comfort when considering whether to board the immediately available transport or wait for something faster, which is a complicated area of the code all by itself. Currently, journey times are cached, and these very data are used for path-finding.

I should, in fairness to you, make clear that such a substantial change would need many months of very rigorous testing before being implemented, and might not be included at all if, following testing, it either cannot be made to work as fast or reliably as the current system, or it has too many adverse side-effects on gameplay. However, if you are interested in working on this matter in the knowledge of all that, then such a modification would be considered seriously for inclusion following rigorous testing.

Thank you for showing an interest in working on the code (although if you are keen to help with Experimental generally, you might want to consider working on one of these higher priority projects first, which I consider to be of greater benefit to Experimental, although you are of course free to choose to work on what you prefer).

[archchancellor]

Hi James,

Thanks for the information. I know it's a pretty scaly issue and at this point the only thing I aim to do is to look at the code and check whether any modifications are at all feasible. I'll keep you in the loop.

Best Regards,
Mark

[jamespetts]

Let me know how you get on!