This thesis addresses a timetabling problem known as Strategic Passenger-Oriented Timetabling (SPOT). SPOT is a timetabling problem that involves assigning departure and arrival times to train services. Unlike classical timetabling, which typically emphasizes infrastructural feasibility, SPOT shifts the focus toward enhancing the passenger experience without infrastructural constraints. The timetables generated by SPOT provide information regarding important connections for passengers and can later be adjusted to accommodate infrastructural constraints. SPOT evaluates a timetable based on the perceived travel time consisting of drive, dwell and transfer times, along with additional penalties for inconveniences by transfers and initial waiting times of passengers.

An initial research focused on using a Mixed-Integer Linear Programming (MILP) approach to solve the SPOT problem. However, this MILP formulation has multiple problems. The MILP tends to perform slow for small problem instances and becomes significantly worse as the problem size increases. Additionally, the effectiveness of the timetables generated by the MILP are often unreliable, because there is a substantial gap between the perceived travel time of the best-found timetable and the best-found lower bound.

This thesis explores a heuristic approach to solving SPOT. Specifically, two heuristics are employed: Local Search and Simulated Annealing. Both operate by exploring a neighborhood of possible timetables around a current timetable to identify better alternatives. The absence of infrastructural constraints in SPOT simplifies the creation of these neighborhoods, as different train services do not influence each other. Additionally, multiple lower bounds are calculated for the perceived travel time, providing benchmarks to evaluate the quality of the solutions. Overall, these heuristics are effective in finding good timetables within a short period, with the lower bounds being reasonably close to the perceived travel time of the generated timetables.

The security of sensitive areas against adversarial threats is a critical concern, necessitating the development of effective patrol strategies. This thesis addresses the problem of optimal patrolling in adver- sarial scenarios through the formulation of an analytical method to calculate the interception probability of a possible attacker in a graph-based patrolling game. By leveraging Markovian strategies, the research provides a robust framework for efficiently calculating interception probabilities and proposes a methodology to optimize patrol routes.

Firstly, the structure and modeling framework that is used in this thesis is set out. Subsequently, a probabilistic, a recursive, and a matrix-product method are derived to calculate the interception probability. This constitutes the core of this thesis. Lastly, the discussion is extended by applying the matrix-product method to practical examples. Monte Carlo simulations are used to compare the performance of different patrol strategies under varying conditions. The results illustrate how the developed methods enable detailed performance analyses, showing that the effectiveness of patrol strategies can vary based on the distribution of attack strategies.

Key findings highlight the impact of graph structure and attack strategy distributions on interception probabilities, the scalability and practicality of the matrix product method to calculate the interception probability, and the significant computational efficiency gained by using this approach. The research also outlines several avenues for future work, including the exploration of heterogeneous environments, optimization improvements, and multi-agent scenarios. Overall, this thesis contributes to the field of patrolling games by offering enhanced methods to evaluate and optimize Markovian patrol strategies, providing both theoretical methodologies and practical implementations that can be used to improve security in adversarial settings.

In the study of phylogenetic trees and -networks, it is frequently desirable to have a measure
of the distance between them. A potentially useful definition of this distance is the length (in
steps) of the shortest path from one to the other, where this path consists of single rearrangement moves of certain types. While there have recently been developments in methods for finding the shortest path between ranked phylogenetic trees, we will instead be inspecting paths between ranked phylogenetic networks in this work. The primary difference between trees and networks here is in the presence of reticulations in the latter, which are moments where different "branches" come together. More specifically, we work out an algorithm that will provide a path between any two binary, level-1, phylogenetic networks with some restrictions, so as to lay the groundwork for work to find shortest paths within this space

In the study of evolutionary biology, there exists a method called the “cherry picking algorithm” that produces the instructions needed to create a network that shows how different species are related.
This report explores what happens when the algorithm starts with a wrong choice, or a “suboptimal cherry” for the first step of the algorithm, and how this affects the accuracy of the algorithm. Imagine you are trying to build a family tree for different species, but you start with a mistake. This research looks at how such initial mistakes can impact the accuracy of the entire family tree. We conducted this study
using simulations of the algorithm that deliberately make an initial mistake, and afterwards continue as the algorithm would normally. The study found that starting with a wrong step in the algorithm usually makes the performance of the algorithm worse. Specifically, it lead to an average optimal performance decrease of 34,8% for networks relating a smaller number of species, and 11.3% for networks relating a larger number of species. Interestingly, the larger the number of species we are attempting to relate in the network produced by our algorithm, the less severe the impact of the initial mistake.
We concluded that making an initial mistake negatively effects the average performance of the algorithm, and the extent of the effect varies with the number of species we are trying to relate in our network.

Reconstructing a minimum reticulation network from phylogenetic trees is used in evolutionary studies. In this thesis, we focus on finding temporal networks using cherry-picking sequences for binary trees with all taxa. Finding such a minimum reticulation temporal network is NP-hard.

We introduce an algorithm to find a minimum reticulation network with a running time of O(2^n poly(n,t)). In addition, this study explores potential enhancements to the algorithm through the utilisation of branch and bound.

Additionally, we introduce a similar algorithm to determine the existence of a temporal phylogenetic network. This algorithm is improved upon by integrating a new concept called cherry growing. This leads to a notable speed-up in performance.

Furthermore, we examine the application of Graph Neural Networks (GNN) in heuristics to find a cherry-picking sequence which can be used to construct a network. This is done by classifying leaves into good, which leads to optimal solutions, and bad leaves. To assess this, two types of data were employed: one simulating evolutionary models and the other employing a fully random approach. The best-performing GNN model has a 97.4% accuracy for evolution-based data and a 79.1% accuracy for random-based data.

The GNN models are implemented as predictors in two classes of heuristics. The first generates a cherry-picking sequence by repeatedly picking leaves. The second class of heuristics is based on a tree search heuristic. This tree-search-based heuristic outperforms the cherry-picking-based heuristic. Furthermore, the GNN heuristics outperform their random variant, even for problems substantially larger than the GNN was trained on.

We also examine the use of GNN in predicting the existence of a phylogenetic temporal network given a set of trees. The best-performing GNN found for this problem has an accuracy of 80.3%.

Phylogenetic trees are commonly utilised in evolutionary biology. These trees represent the evolution of a set of species. In case of gene transfer however, a phylogenetic tree is insufficient. In such cases, tree-based phylogenetic networks are more suitable as they can depict reticulate evolution.
Nonetheless, tree-based phylogenetic networks have their limitations as they are unable to represent reticulate events occurring between different environments, families, or lineages of species. To address this, forest-based networks offer a solution.
A forest-based network is a collection of leaf-disjoint phylogenetic trees with arcs added between different trees in case of reticulate evolution.
In this thesis, an integer linear programme (ILP) is created to determine whether a binary phylogenetic network is forest-based. It is important to note that this thesis exclusively focuses on binary phylogenetic networks.
This ILP model is expected to be valuable in the development of new models and algorithms for both binary and non-binary phylogenetic networks, thereby enhancing the understanding of reticulate evolution. Additionally, the ILP may lead to time-related challenges when processing bigger phylogenetic networks.

Phylogenetic networks are a specific type of directed acyclic graph (DAG), used to depict evolutionary relationships among, for example, species or other groups of organisms. To solve computationally hard problems, treewidth has been used to parametrize algorithms in phylogenetics. In the hope of simplifying the algorithmic design process, Berry, Scornavacca and Weller recently proposed a new measure of tree-likeness that takes into account the directions of the arcs: scanwidth. They showed that the corresponding decision problem of this parameter - which can be seen as a variant of directed cutwidth, using a tree instead of a linear ordering - is NP-complete. This thesis aims to widen the structural knowledge of scanwidth and to find efficient ways of computing it on general DAGs, both by exact and heuristic algorithms.

With the help of reduction rules, we construct an explicit dynamic programming algorithm that computes scanwidth exactly, along with its corresponding tree extension, in O(k * n^k * m) time for rooted DAGs of scanwidth k. This slicewise polynomial algorithm proves that computing the scanwidth is in the complexity class XP. The algorithm also functions as an FPT algorithm for networks of level-l, with the complexity bounded by O(2^4l-1* l * n + n²). It performs well in practice, being able to compute the scanwidth of networks up to 30 reticulations and 100 leaves within 500 seconds.

On the heuristic side, an algorithm that repeatedly splits at a specific type of smallest cut is proposed. Enhanced with simulated annealing, this heuristic shows promising results, obtaining an average approximation ratio of 1.5 for large synthetic networks of 30 reticulations and 100 leaves. Applied to a real-world dataset of networks, the heuristic performs near-optimal. Although we prove that the scanwidth is always greater than or equal to the treewidth, experiments show that they are close to each other in practice. This further motivates the use of scanwidth over treewidth as a parameter in algorithms.

In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous complexity of inferring a network directly from DNA data.
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances.

TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree-width parameter instead of in the number of reticulations. However, due to the implicit formulations of two crucial steps in this algorithm, this running time cannot be achieved in practice without finding ways to generate the required structures explicitly. This paper provides two new sub-algorithms that can do that. To further improve the performance of the algorithm, I introduce a number of criteria and other methods that can be used to reduce the number of structures generated. Additionally, I describe a way to manipulate the nice tree-decompositions to create a more favorable order of bags for the dynamic programming. These sub-algorithms and improvements are used by two new algorithms TWITCH and PITCH, whose implementations are compared to a brute force algorithm and a new branching cherry-picking algorithm named BOTCH. The latter has an FPT running time that is exponential in the number of vertices that have only reticulations as children. The comparisons show that the implementations of the dynamic programming algorithms TWITCH and PITCH are slower in practice than the brute force algorithm, despite their numerous improvements. Of the four new implementations, BOTCH has the best test results and it is shown to be fast in practice.

The problem considered in this thesis is the box set optimization problem. In
this problem the goal is to find the optimal dimensions of a number of shipping
boxes which have to provide an optimal fit on a set of items. The application
considered is e-commerce, and hence the number of items is relatively large
compared to other applications found in literature.

The literature describes multiple problem formulations where a small num-
ber of optimal shipping boxes are selected from a large set containing candidate
boxes. However, since the instances considered in e-commerce application are
often too large to be solved in this way, we introduce a simulated annealing
heuristic solution method. In this way we are able to generate box sets con-
taining 10 to 20 boxes with centimeter accuracy for data sets containing up to
XX single item orders.

We pay special attention to an algorithm to very efficiently calculate the
objective value associated to the fit of a selection of candidate boxes on a set of
items. This is done by assigning items to shipping boxes using a pre-calculation
table. Because the heuristic can process a larger set of candidate boxes than
the exact solution method, ultimately results of the heuristic are better than
those found by the exact solution method.

Finally we generate multiple box sets based on the input data provided by
the industry partner bol.com, and compare the results. We conclude that on
almost all tested instances, the total amount of carton used can be reduced by
more than XX in combination with a total send volume reduction of over XX
in comparison with the box set that is currently used. Furthermore, we answer
additional questions. We find that minimizing the total amount of carton used,
instead of minimizing the total volume send, can lead to a result that is most
desirable in practice. We discover that pack-line specific, warehouse specific or
seasonal specific box sets provide none to only minor additional improvements.

In this paper we give a historical and theoretical background to minimal triangulation and its relation to minimal separators.
We introduce a new type of minimal separators, the minimal meta separator, which its size is a lower bound for the treewidth problem, its fill-in is a lower bound for the minimum fill-in problem and can be used for the aid of enumeration of minimal separators.
Furthermore, we introduce the idea of transformation which are controlled graph modifications that predictably modify the minimal separators of such graph. Namely, we introduce the transformations of inclusion minimal clique decomposition, saturate minimal separator, edge addition and minimal meta separator decomposition. These transformations can aid the architecting of algorithms for the enumeration of minimal separators.
Finally, we then apply such methods on the problem of enumeration of minimal almost-clique separators and demonstrate faster runtimes compared to the current state of the art.

Phylogenetic networks generalize evolutionary trees and are commonly used to represent evolutionary relationships between species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. In this thesis all quarnets, networks on four species, of a network are assumed to be known. We prove that each recoverable undirected or semi-directed binary level-2 phylogenetic network without redundant biconnected components is encoded by its set of quarnets, meaning that the network is uniquely determined by its quarnets. Furthermore, two decomposition theorems for undirected and semi-directed binary phylogenetic networks are presented. These decomposition theorems are proved for undirected binary phylogenetic networks for all levels and for semi-directed binary phylogenetic networks that are at most level-2.

Phylogenetic networks are used to represent evolutionary histories of a set of taxa. In this thesis, we look at a certain network class, called orchard networks.
In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves time-labelling of the vertices.
Then, an algorithm is given to see if a given network is orchard. The next section, explores a non-recursive labelling of a given network. There is not an explicit algorithm for the labelling. An algorithm for the labelling is given.
The last chapter is about non-orchard networks. It contains multiple actions that can be performed on the non-orchard networks in order to transform the non-orchard networks into orchard networks.

Describing phylogenetic trees or networks with a polynomial is a tool to distinguish between them. In this thesis, a new polynomial for describing rooted binary internally labeled phylogenetic networks and trees is introduced based on the research of P. Liu and J. Pons et al. Two different cases are considered, one where the reticulation nodes have distinct labels λ_i and one where the reticulation nodes have the same label λ. There are a few conjectures stated about the uniqueness of the polynomial and the relation of the polynomial with the primary subtrees and their monomial. Also the folding and unfolding of a network is described. Furthermore, an algorithm is provided with which a tree can be made out of different monomials. With use of the lemma that states when a tree can be folded to a network, it can be determined if the tree can be folded to a network.

In the current economy, there is an increasing focus on sustainability. Green transport solutions, like rail freight, are becoming more and more popular. We will look into the shunting operations at Kijfhoek shunting yard. This yard functions as the central hub for DB Cargo Nederland and connects the Port of Rotterdam with the hinterland. About 2000 cars are sorted at this yard each week. At the yard, there are 43 parallel classification tracks.
Shunting problems come in many shapes and sizes but are generally hard to solve. To that end, we will use both exact algorithms and heuristics to solve the shunting problem at Kijfhoek within reasonable time. In practice, it is not known at the beginning of the planning horizon which cars will arrive. To that end, we will create general solutions which will be updated over time when new information becomes available. We test how well the solutions perform and/or can be reoptimized with the latest information using a simulator.
We find that our solution approaches can generate solutions for instances with 28 classification tracks of similar quality as solutions found for the same instances with 43 classification tracks with complete information at the beginning of the planning horizon. Furthermore, with incomplete information, we find good solutions with 32 classification tracks.

When processing a trace DNA sample at the Netherlands Forensic Institute, an STR electropherogram can be created. An analyst uses this electropherogram and analysis software to read out peaks signifying DNA. After analysis, the DNA profile is used in the interpretation process, which can include the comparison to a reference DNA profile of a person of interest. The software that is currently being used for profile analysis is threshold-based and the process includes the intervention of trained analysts. To further automate (allelic) peak identification in STR electropherograms, as well as to increase efficiency and uniformity, neural networks were studied and applied. Previous work by Duncan Taylor and David Powers provided a proof of concept using a simple fully connected neural net. After reviewing literature, the U-net was selected to be used in this thesis. Training U-net on electropherograms proved successful and achieved a 95% accuracy on the per-pixel labels. However, translating the per-pixel output to alleles was more difficult than expected, so an upper bound on the score was calculated. The upper bound got close to an analyst’s performance and demonstrated the potential of this method.

Interval graphs play an important role in graph theory and have intensively been studied for over sixty years due to their wide range of applications and because most NP-hard problems on general graphs become solvable in linear time on interval graphs. However, the class of interval graphs is restricted and does not even contain a cycle of length 4. To overcome this drawback, we study some generalisations of interval graphs where instead of considering one interval on one real line for each vertex we consider d intervals on d different real lines and take the union of each lines (d-track graphs) or t intervals on the same real line (t-interval graphs). Nevertheless, most problems now become NP-hard as shown for Vertex Cover, Clique Cover, Biclique Cover or even APX-hard in the case of Feedback Vertex Set. This is even the case if we add some restrictions on the length of the intervals. We also give a bound on the unit track number of any interval graph (number of tracks needed so that all the intervals have the same length). Furthermore, we study the relationship between the classes of d-track graphs and t-interval graphs with the length of the intervals restricted or not. Finally, we also consider taking the intersection of d tracks (boxicity d graphs) and show that is it not more or less restrictive than taking the union of d tracks.

Phylogenetic networks are used to describe evolutionary histories and are a generalisation of evolutionary trees. They can contain so called reticulations, representing reticulate evolution, such as hybridization, lateral gene transfer and recombination. Methods are being developed to construct certain rooted phylogenetic networks from their subnetworks. A constructed network is encoded by their subnetworks if it is uniquely determined by that set. It has been shown that phylogenetic trees are encoded by their set of triplets, which are rooted trees on three species. However, triplets do not encode phylogenetic networks. Huber and Moulton introduced trinets, rooted networks on three species, which do encode level-1 phylogenetic networks, which are networks containing at most one reticulation in each biconnected component. Van Iersel and Moulton proved that level-2 phylogenetic networks are encoded by their set of trinets and Nipius proved that level-3 phylogenetic networks are encoded by their set of quarnets, which are rooted networks on four species. In this thesis we prove that for all k>1, level-k networks without symmetry in their biconnected components are encoded by their set of (k+1)-nets, which are rooted networks on k+1 leaves. This result provides some evidence for the conjecture that all level-k phylogenetic networks are encoded by their set of (k+1)-nets. Thereafter, we generalise encoding results for level-2 and level-3 networks, where the underlying structure, called generator, and its sides play an important role. A generator is a directed acyclic biconnected multigraph, containing only vertices with indegree 2 and outdegree at most 1, indegree 1 and outdegree 2, and indegree 0 and outdegree 2. The sides of a generator are the arcs and outdegree-0 vertices of a generator. We have not been able to prove that level-k networks with symmetry in the generators of their biconnected components are in general encoded by k+1-nets. For the networks with symmetry, we prove encoding results for networks with leaves on at most p sides of the underlying generators of their biconnected components. We further prove that level-4 networks are encoded by 6-nets. Although Nipius gave a counterexample showing that not all (level-3) phylogenetic networks are encoded by their set of trinets, it is useful to know which networks are encoded by their set of trinets or k-nets. In this thesis, we provide an algorithm which can serve as tool for proving that certain level-k networks are encoded by their set of k-nets. Our presented algorithm is a first step to generalise encoding results to level-k networks with k>3 by using trinets. Furthermore, we are a step closer to proving the conjecture that all level-k networks are encoded by (k+1)-nets, including networks with symmetry in the generators of their biconnected components.

In this report, the bounded Maximum Parsimony distance will be considered when
applying three different reduction rules. The distance is a measure on how dissimilar two trees are and is calculated based on the number of mutations that occur when looking at heritable traits. The first rule considered, is the chain reduction. For this rule, it is proven that the bounded MP distance is preserved after applying this rule. This is done by adapting the proof from Steven Kelk et al. [10]. For the second rule considered, the generalized subtree reduction, it is also proven that the bounded MP distance is preserved after applying this reduction. Again, this is done by adapting the proof in the paper by Steven Kelk et al. [10]. Then, at last, we looked at a new reduction rule for the TBR distance, introduced by Steven Kelk and Simone Linz [12], the (2,1,2)-reduction. In this report, it is shown with help of a counterexample that this rule does not necessarily reduce the distance with one like it is the case for the TBR distance. However, it can be concluded that the distance is either preserved or reduced with one.

For NP-hard optimisation problems no polynomial-time algorithms exist for finding a solution. Therefore, heuristic methods are often used, especially when approximate solutions can be satisfactory. One such method is quantum annealing, a method where some initial Hamiltonian is slowly perturbed to anneal towards a problem Hamiltonian. The annealing schedule should follow the adiabatic theorem of quantum mechanics and should therefore be slow to yield the most accurate results. Finding a schedule that is both fast and still accurate has been referred to as a 'black art' and is usually just guessed. In this thesis reinforcement learning (RL) is explored to see if it can help with finding the optimal quantum annealing (QA) schedules. The Hamiltonians used are of
the form of a transverse field Ising model. These are well studied Hamiltonians that can map to many NP-complete problems [1]. Finding a good balance between going both fast and being precise proved to be difficult and needs further research. Therefore this thesis mainly dealt with training an RL agent to find the most accurate QA schedule. The results show that the agent learns to find the most accurate (slowest) annealing schedule after 300,000 learning steps for a problem Hamiltonian with a single coupling constant J and no reward shaping. Annealing in an environment with a spin glass problem Hamiltonian proved to be difficult and has not shown good results in this thesis This needs further investigation. Nonetheless, the result on the single coupling constant Hamiltonian shows the potential of an RL agent for learning in a quantum annealing environment with very sparse rewards. This paves the way for further research into an RL agent that can find a schedule that is both fast and accurate on a wide range of problem Hamiltonians.