Many practical optimisation problems can be formulated as a traffic assignment problem, i.e. optimally route a multi-commodity flow through a network. In order to do this, a network is defined that...Show moreMany practical optimisation problems can be formulated as a traffic assignment problem, i.e. optimally route a multi-commodity flow through a network. In order to do this, a network is defined that can capture congestion and a notion of optimal flow. The shortest path problem is derived as a sub-problem of the traffic assignment problem, discussing several algorithms that can solve it. In addition, several speed-up techniques for the shortest path problem are described that can be applied to static networks. In conclusion, an algorithm is discussed that solves the traffic assignment problem by iteratively solving a shortest path problem.Show less
The High School Scheduling Problem is the operational research problem of finding an optimal timetable for students and teachers in a secondary school. It is a minimisation problem, in which we...Show moreThe High School Scheduling Problem is the operational research problem of finding an optimal timetable for students and teachers in a secondary school. It is a minimisation problem, in which we need to satisfy as many wishes as possible while guaranteeing all demands are satisfied. The High School Scheduling Problem has been studied for over half a century, owing to the importance of schools having a good schedule and the difficulty of finding a schedule that adequately satisfies the different constraints. This thesis studies two new approaches to optimising solutions of a problem instance. Both of these approaches are based on transformations of the problem’s search space. First, locally optimal solutions are improved by changing the penalty associated with soft constraints in specific ways. Secondly, the schedule’s penalty function itself is improved, aimed at shifting focus from improving the schedule as a whole to making sure individual schedules become acceptable.Show less
The Game of Cops and Robbers is played by two players on a graph, the one player controlling a set of cops and the other controlling a robber. The goal of the cops is to capture the robber in a...Show moreThe Game of Cops and Robbers is played by two players on a graph, the one player controlling a set of cops and the other controlling a robber. The goal of the cops is to capture the robber in a finite number of moves, whereas the robber wants to evade the cops indefinitely. The central question we ask is: how many cops are needed on a given graph for them to be able to win the game? This amount is called the cop number of a graph. In this thesis, we give an extensive overview of results that give an upper bound on the cop number for graphs of a given type, like unit disk graphs and string graphs, as well as some examples of these graphs having a high cop number. In this overview, we will see that the results all greatly depend on the statement or proof method of one of two theorems published by Aigner and Fromme [1]. In addition to a survey of the existing work, we explore whether the two main theorems can be used to further sharpen these results. Leading to mostly negative answers, we conjecture that a different approach is necessary in order to book further progress.Show less
