Monday, March 4, 2013

How (not) to fill a train

I wrote a simple Python script to simulate customers attempting to book passage on a 100-seat train making journeys of anywhere between two stops and 40 stops (each number of stops was simulated 20 times). Each customer chose a random start and end point for their journey. Seats are filled on a first-come, first-served basis: The first passenger always gets seat "0". As each customer comes along, the program checks to see if seat "0" is occupied for any portion of the planned trip. If it is, then the program moves on to seat "1". The process repeats as necessary until the list of seats is exhausted. I set up the program so that 500 attempts would be made for every test—for a stop count of 2, 100 passengers were able to get seats, but 400 other customers were rejected.

That's a very simplistic algorithm which doesn't work very well. It becomes difficult to add more passengers after just 5 stops. Amtrak does better than this, though it's also worth noting that Amtrak reservations are typically on a per-car basis rather than per-seat (per-seat was more straightforward for me to model), so some of the seat conflicts are resolved naturally.

There are a lot of computer performance graphs out there which look exactly like this. In particular, I think of multi-processor systems of yore (i.e., 10–15 years ago). Today, well-written software is much better at scaling almost linearly with the number of processor cores. Some better scheduling software would probably help Amtrak on routes with many stops, but unlike computer programs, people can't be moved around in the same ways.

Here are graphs using both a normal and log scale for the number of stops:

No comments:

Post a Comment