Consider a small airport operation where your airline has 7 gates numbered 1-7. The passenger bags both from lobby and arrival flights are transferred to the central bag room, where are sorted for their next destination. The passenger bags are distributed from the central bag room to each gate by a “bag runner” – an employee who drives a truck (ground equipment) and loads/unloads bags from that truck. Your challenge is to schedule the final bag run(s) before departure at each gate. The gate layout is linear, and each gate is equally separated from its neighbors. It takes one minute to go to either of the neighboring gates (e.g. it takes one minute to go from gate 3 to gate 2 or gate 4) with a ground equipment, which can haul up to 4 bags cars at most. The central bag room can be treated as gate 0. Each bag car is destined to a gate and assumed to be capable of carrying all the bags for the flight, which will depart at that gate. The flights are scheduled to depart at 9:19 AM, 9:19 AM, 9:25 AM, 9:30 AM, 9:20 AM, 9:35 AM, and 9:17 AM at gates 1-7, respectively. It takes 3 minutes to load bags in the central bag room and 2 minutes to unload the bags at each gate. The maximum allowed delay for each gate is 10 minutes. The bag carts will be ready for pickup from the central bag room at 9:00 AM for the final bag run.
a) Create a linear optimization model to determine the best route that runner should follow that minimizes total delay. Please document your model with a text editor, code and solve this model with any programming language and free/commercial solver you are comfortable with.
b) Now imagine that you are provided an additional bag runner to operate the bag delivery. What changes you would make in the model you developed in (a)? Please report the total delay obtained with this modification.
c) Your optimization was proven to be very successful in the small airport and the leaders of your company would like you to implement it at one of the Hubs. However, curse of dimensionality due to sheer volume of flights, large number of gates and availability of multiple ground equipment renders the optimization mode not practical at the Hub. You are tasked with constructing a heuristic approach, which is not based on mathematical programming, yet provides a good solution in the Hub. Please clearly specify steps of your heuristic algorithm by providing a pseudo-code and explain what part(s) of your algorithm provide(s) evidence that it moves towards a good Solution.
d) Discuss (in words) pros and cons of your proposed heuristic approach as opposed to optimal solution from solution quality and runtime perspectives including worst case solution quality, if possible, by providing examples.