# Showing that the gate-assignment problem can be solved as a shortest path problem

We want to assign airplanes to a specific gate we know the interval that a certain plane needs in the gate. The quality of the solution is determined by the amount of time between two consecutive planes if this is $t$ minutes this will result in a score of $f(t)$ where $f(t)=-\infty$ when $t\leq15$ and $f(t)$ is a non decreasing finite function for $t>15$. For each plane $v$ that was in the gate we get a bonus of $b(v)$. We now need to show that making the best sequence of planes can be solved like the shortest path problem.
I am really confused by this problem. I thought maybe represent the planes by nodes and then connect every plane with every other plane by an edge where on each edge we get a weight equal to $f(t)$ (the time needed between the two planes connected by that edge).
And then the best I could think of was to determine the minimal spanning tree but I don't know how many planes there are and not every plane has to go to this particular gate. Can anyone help me with this?

You are on the right track in assuming that each plane is a vertex of the graph. (There is also a not-so-subtle hint in the problem text: "every plane $v$".) Further, we assume that there are two special vertices, $s$ and $t$, which are going to be the source and destination of the shortest path or, alternatively, the beginning and end of the gate's schedule.

For every plane, suppose we know two times: its arrival and departure times. This is what I understand by "knowing the interval." So, each vertex corresponding to a plane is labeled with arrival and departure times of that plane. The source $s$ has a departure time at least $15$ minutes less that the arrival time of any plane. The destination $t$ has an arrival time larger by at least $15$ minutes than the largest departure time of any plane. The arrival time of $s$ and the departure time of $t$ don't matter because $s$ has no incoming edge and $t$ has no outgoing edge.

Concerning $f$ and $b$, we only need to know what we are told. The solution is supposed to work for all $f$ and $b$ functions that satisfy those requirements. For simplicity, we assume that the bonus for both $s$ and $t$ is $0$, though in reality it doesn't matter.

We are now ready to assign weights to the (directed) edges. We want a shortest path formulation; hence we want a large interval between two planes and a large bonus for a given plane to result in a really short edge.

Can you think of a simple way to achieve that?

Concerning your doubts: Clearly we don't know how many planes are there and not all planes may be assigned to this gate we are studying. The idea is that we are given a collection of planes, each with arrival and departure time, and we are given the functions $f$ and $b$. We come up with a solution that works for all such inputs and provides an optimal schedule for that gate with that collection of planes.

It is a somewhat artificial problem, because in practice you'll have more than one gate to assign to at once. Real scheduling problems may not be that simple and are not all reducible to a shortest path calculation. Moreover, in practice, there are delays, which make gate changes necessary. In this problem, however, you don't have to deal with any of that.

• I don't understand I though we wanted the shortest path so you want the smallest interval between planes so that you can land more planes at the gate and get higher bonus? Apr 1, 2017 at 15:48
• It's a trade off. A schedule with large intervals between planes is less likely to be disrupted by delays. On the other hand, as you say, more planes means more bonuses. So the specific choice of $f$ and $b$ determines how we weigh those two factors. For a given $f$, large bonuses will give schedules with more planes and shorter intervals between planes (more risky, but more rewarding if all goes well). Smaller bonuses will give a safer schedule, but less rewarding if all goes well. It's the ratio of $f$ and $b$ that really matters. Double both, and you get the same optimal solution. Apr 1, 2017 at 15:52