Scheduling of Ticket Inspectors in Deutsche Bahn Inter-City Express Trains
We study the underdeveloped Inspector Scheduling Problem. The Deutsche Bahn want to maximise the number of passenger tickets inspected given already set train schedules with their limited resources, the passenger ticket inspectors. We formulate this problem as a network flow and implement this as a Mixed Integer program. We account for lack of data by estimating Origin-Destination Matrices and discuss the complexity of the problem. We obtain empirical results of run time of the algorithm as a function of number of inspectors and conjecture that this problem is NP-hard. We also propose heuristic methods to solve this problem.