A closely knit plan
From the dawn of civilization, humanity has always made great efforts in trying to improve transportation: getting to a place faster and moving more goods in less time have always been a critical part of economic development.
In our society, connections fit tightly: on and off, millions of commuters switch their means of transporattion. But how exactly is this possible? What mechanism is in place to make sure that the system is not clogged at the first delay?
Not surprisingly, the answer lies in computing. All over the world, machines make sure that, given a very specific set of rules, the planning for our transportation is executed at the best of our knowledge.
What I find to be the most fascinating step in the computation of these schedules, is how the original problem is translated into a set of quantities that can be processed and computed. The so-called modeling.
A time perspective
Let’s consider a simplified version of a very famous problem: the computation of train schedules. Historically speaking, trains and the their ability of transporting goods (and people) much faster than before, have been one of the biggest catalyzer to economic development, bringing what is known as Transport Revolution. It is easy to grasp that, the more complex the railways networks becomes, the harder it is to make sure that everything works flawlessy.
This problem can be tackled using different perspectives: the first one that comes to mind is to look at times. Our goal is to have trains in our network that closely suit the patterns in the movements of people (commuters, attendee of events). There still a lot to consider, before we proceed:
- you want to ensure availability of connections (no one wants to wait a lot of time because his/her connection just left!),
- you want to take into consideration that the busiest nodes in your network will probably be congested (and the bottleneck of the whole system), so you might want your solution to be somewhat tolerant of delays at these nodes.
While these are merely a couple of examples, it is clear that modeling such a problem is not a trivial task. A lot of things have to be accounted for.
A spatial perspective
Now, let us consider another way of looking at this problem: suppose you are the manager of a railway station and you receive an already made timetable for your station, which you cannot change.
Even though the timetable problem is already solved, something else has to be decided, still: platforms.
Except from stations which are sufficiently small, this is also not a trivial problem: there are still a lot of variables and constraints to be taken into account.
- some platforms require a rail exchange and some are directly joined to the rail network;
- some trains are merely passing through and do not need to stop (cargo, fast trains such as intercity’s);
- people have to be able to walk to their connections in enough time, without causing delays, which would then propagate to the whole network.
A matter of money
These constraints are, in general, not absolute: delay in due to a poor schedule, despite being unfavorable, can be tolerated.
In some countries, there is a penalty system: a train within 3 minutes of its scheduled arrival/departure is considered on time, otherwise the railway company has to pay a fine that scales with the extra time.
Similarly, user discomfort is not an absolute constraint: we can tolerate making a small amount of people unhappy, if it is more convenient that way: any unsatisfied customer directly translates to a cost.
This consider happens in most of the cases: in these circumstances, it is not possible at all to realize a schedule that satisfies all of the constraints: it is always the matter of minimizing the costs / maximizing the profits.
In our previous example, we merely discussed about coming up with a feasible solution: sometimes it is indeed the case, but more often we are interested in (monetary) efficiency: we would like to minimize the numbers of trains running or personnel needed (greatly reducing costs), while maximzing the number of passengers or cargo that we bring to destination.
This is basically the whole deal about the branch of mathematics known as optimization.
Next time, we will look at the techniques used to translate this problem into a mathematical language.
While studying these topics during my Mathematics MSc in Utrecht, we were given a case study for the Schiphol Airport, in Amsterdam: the problem was finding a good, robust (more on this topic another time) solution to the “gate assignment problem”, i.e. assigning each scheduled flight to a gate.
Some of the imposed constraints of the problem are interesting and sometimes very funny:
- Plane size has to be taken into account (bigger planes require gates with more space between each other)
- Intercontinental flights have to be separated from domestic / european flights (different security restrictions, need to keep passengers separated)
- Some air carriers want a gate next to the Bar for their passengers
- Some carriers do not want to be placed next to another particular carrier (nationalism or bad blood between companies, I presume)
- Some air carriers have a proven record of being unreliable (and therefore are likely to be late, causing problems, which make it favorable to put them somewhere very far by themselves)
- Some air carriers prefer to beas close to the baggage hall as possible
- Some air carriers do not want their passenger to use a shuttle to get to the terminal, but rather walk to it.
While these constraints might be hard to believe (some more than others), they are equally likely: modeling a solution for the real world often includes details that we hardly think about, but are nonetheless important to delivering a good experience or an monetary efficience.