Developing schedules for air marshals that closely match a game theoretic solution
Geetla, Tejswaroop Reddy
MetadataShow full item record
The goal of this thesis is to develop schedules for a set of Air Marshals in a way that matches, as closely as possible, the solution obtained from a game theoretic formulation. Game theoretic formulations of the Air Marshal problem typically ignore routing and scheduling constraints and only focus on determining flight segments whose coverage will result in the most favorable scenario for the government and the least favorable scenario for the terrorists. Translating these flight coverages into actual air marshal schedules is not a simple task, since there are constraints on where air marshals are based, the number of hours they are available and the flights that they can take. Furthermore, it is important not to cover unnecessary flight segments as this deviates from the ideal game theoretic solution. The task then is to develop a schedule (series of flight segments) for each Air Marshal which is feasible (starts and ends at their home base and does not violate available hours and other restrictions) and in which we maximize the number of desired flight segments covered and minimize the number of undesired flights covered. Our approach to this problem is an improvement heuristic, which starts of with a feasible schedule for each Air Marshal and scores it based on a penalty for non-coverage of desired segments and a lower penalty for coverage of undesired segments. The next step is to improve the air marshal schedule using a genetic algorithm, so that the sum of these penalties is reduced, while maintaining feasibility of each air marshal's schedule. To minimize the time to find a feasible solution, the problem is modeled innovatively as a shortest path problem in a network, which has a polynomial time algorithm. To test our methodology we have developed a case study based on flight data from 6 airports situated in the Eastern Time Zone. Our computational results show that there is a marginally decreasing improvement in penalty with increase of total air marshal hours. Thus our results can be used to determine the appropriate level of air marshals to use for a specific game theoretical solution.