Dabbling in airport slot scheduling
16th June 2016
It is been a while since I have written anything of worth on this blog. So I thought it was a good time to change my style and try something different. The aim is to be more frequent by having shorter blogs. I will aim for once a week, but I will guess that it will be more like once a fortnight. Lets see how this goes!!!
This week I have ventured into the new world (well new for me) of airport slot scheduling. This is a very important topic in regards to improving efficiency when using a heavily constrained scarce resource. The reason for venturing into this topic is that I have joined a research group at Lancaster that has a very large project focusing on this. Specifically, I am part of CENTRAL at the Lancaster University Management School. Just to get all of the acronyms out of the way, the project that will be looking at airport capacity management is OR-MASTER.
What is airport capacity management?
This is something that I have been trying to work out this week. The paper by Zografos et al.(2017) provides with a good overview of current techniques in airport capacity management. This paper has been the starting point for my investigation. From my reading I have discovered that airport capacity management loosely describes the management of the scarce resources of runways and gates. It seems that in most cases the use of the term focuses on the management of the runways, and the gates are left to some other area of research.
Why do we focus on runways and not gates? The answer to this could come from answering the question "who is the owner of the resource?" Now this is my own intuition, so please do your own research, but I believe that the gates are managed by the airlines themselves. As such, the airport has no influence in the management of this resource.
In the area of airport capacity management, we are able to focus on the allocation of time to use the runways for departures and arrivals. This problem is termed the airport slot scheduling problem, and it appears to be an area of growing interest.
Airport slot scheduling
We should get some definitions out of the way. An airport is an airport (I hope that you know this one). A slot is a period of time that an airline is able to use the airport for a take off or landing. In the slot scheduling process it doesn't particularly matter whether it is a take off or landing, since they are all described as requests.
The slot scheduling problem is only interesting when there are restrictions placed on the number of available slots. Coming from Sydney, this is something that is well knows as SYD is very close to capacity. The airports that are slot restricted are called Level 3 airports. There is also Level 2 and Level 1 airports, the former are self managed and place restrictions as the airport deems necessary and the latter have no restrictions at all. To put this is a global perspective, Europe has 103 Level 3 and 75 Level 2 airports, the US has 1 Level 3 airport and 6 Level 2 airports and back to Australia all state capital cities (baring Hobart) have Level 3 airports.
There are a couple of really interesting things about the slot scheduling problem. First, this problem is closely related to scheduling problems with time dependant resource constraints. So there is a wealth of literature available in regards to solution techniques. However, it is different enough to cause some difficulties in finding the optimal solution. Another thing that I found interesting is that there is very little work in this area. In regards to the single airport model Zografos et al.(2017) cite two papers that focus on this problem, Zografos et al.(2012) and Jacquillat and Odoni(2015).
My reasons for why there has not been much interest in the single airport model are these: the single airport model is not as interesting, or potentially as useful, as the network model (which is significantly harder) and the US does not have many airports that are slot controlled. However, the work that has been performed has been very interesting. First, Zografos et al.(2012) presented a very effective technique at handling the many different capacity constraints. Second, Jacquillat and Odoni(2015) describe an integrated problem that combines strategic and operational decisions.
At this stage I have not delved into the network problem, that will come over the next couple of weeks.
What makes this problem complicated?
This is probably summed up in one word: constraints. There are a large number of constraints in this problem to manage the capacity restrictions over different time intervals. These can be 5 minutes, 20 minutes or 1 hour. The network model by Pellegrini et al.(2017) has a nice description of the capacity constraints. In this paper, it is stated that there are three types: 1) 20 minute window starting every 5 minutes, 2) 1 hour window starting every 5 minutes and 3) 1 hour window starting every hour. So just from this you can see that there are a large number of constraints that are needed in the model. However, it is expected that not all of these are tight, so a row generation scheme could be used. In fact, that is exactly the solution approach described by Zografos et al.(2012).
Where to next?
So I am now interested in this topic and it seems like there are some complicated problems to try and solve. I am going to try my hand at these and see whether there are any algorithmic improvements that can be found. Being very interested in decomposition techniques, I believe that will be one of the first things that I will look into.