Path finding is an important component in solving a wide array of engineering problems, ranging from video games to real-life applications such as automated warehouse management and autonomous vehicles.
Path finding algorithms are designed to solve complex problems, and in order to do so, assumptions are necessary to simplify the problems.
While these assumptions are important, using them makes the obtained algorithms less applicable to a real-life scenario, and as such, verifying how lifting some of them would affect the obtained results is worth pursuing.

Two main assumptions were identified and subsequently lifted.
First, classic multi-agent path finding algorithms use a centralized approach, where solutions are computed before execution.
This results in a long computation period followed by execution. Lifting this assumption results in a decentralized approach where agents solve conflicts on the go, while approaching their target.
The second assumption made by state of the art algorithms is that agents participating in a multi-agent path finding problem share a common goal: minimizing a global cost function.
This is not always applicable, as in a real-life scenario participating agents can have selfish goals.
This assumptions has been lifted by allowing agents to negotiate their paths by trading with the other participants to create better solutions for themselves.

The Selfish Localized Pathfinding (SLP) algorithm has been designed to lift these assumptions. It describes a decentralized algorithm that allows participating agents to negotiate their paths, which makes a good candidate for an application closer to real-life.

The SLP algorithm has been tested in order to evaluate its performance, both in terms of its ability to solve a set of test cases, and in terms of the cost incurred by the participating agents.
SLP performed well in varied domains.
SLP solved significantly more cases than Conflict Based Search, a centralized state of the art path finding algorithm.
This comes at the expense of an increase in the path lengths obtained by the algorithm.
This downside is offset by the significant decrease in the time required to solve problems, which can be divided in small clusters due to the decentralized approach of the algorithm.
On the whole, SLP can provide a good alternative to Conflict Based Search.

When addressing combinatorial optimization problems, the focus is predominantly on their computational complexity, and it is often forgotten to look at the bigger picture. As a result, it is common to miss critical details which could play a major role in the overall process. One such detail is the presence of uncertainty in the real world. A naive approach might directly predict values for the uncertain parameters, without taking into account that the ultimate goal is to obtain sound decisions. Consequently, in many cases, the resulting solutions are suboptimal. This challenge is precisely the premise behind Decision-Focused Learning (DFL) framework, which is a core of this work. This study pioneers the application of the DFL framework to scheduling problems with uncertain processing times, utilizing contextual features to predict these uncertainties. By employing the promising Score Function Gradient Estimation method, the research tackles the issue of non-differentiable regret loss functions in DFL. Key contributions include the development of techniques to enhance the performance of the Score Function, an in-depth analysis of DFL's applicability to complex scheduling scenarios, and a detailed evaluation of its strengths and weaknesses. This work not only demonstrates the potential of DFL in this new context but also lays the groundwork for future research and improvements in handling uncertainty in combinatorial optimization.

This paper analyses manually realised solutions to the Train Unit Shunting Problem (TUSP) to find patterns in train type. The parking element is most important for the TUSP. Therefore, this research specifically investigates the presence of train type patterns in parking track and parking time. The difference in the patterns between main train type and train subtype is also analysed. The study uses statistical hypothesis testing to look for biases between individual train types and parking tracks. Kernel density estimation is used to analyse the differences in parking time between the types. The results show that there are strong patterns in type and parking track, but no clear difference in parking time. Considering subtype results in the differences being more specific. It is suspected that the strongly present track pattern is a strategy used by human planners.

Solutions for the Train Unit Shunting Problem are constantly being researched and improved to be- come more efficient and match the needs of train transport in the Netherlands. For this reason, we are exploring new ways to find patterns in the train data to identify where those solutions could be en- hanced. More specifically, we are trying to find patterns that make identifying different locations possible. We identify patterns in the capacity of the shunting yards and the types of trains used in various locations, which result in reasonable ac- curacy in classification. Some locations operate closer to their capacity, and some require longer paths to get inside the shunting yards. These find- ings could be helpful not only for the planning algo- rithms but also in identifying which locations might need expansion or restructuring and where more of the train fleet should be allocated.

Shunting yards are locations next to train stations that serve as parking places for trains when they are not in operation and often contain facilities for maintenance and cleaning for passenger trains. Planning of the tasks regarding shunting trains involves routing, assignment of tracks, and scheduling tasks. This is done manually and requires a lot of effort, making it inefficient. Identifying patterns specific in the arrival times of trains at shunting yards can help to predict future train arrivals and potential delays throughout the year more accurately. This enables the alignment of staff and equipment with train arrivals, minimizing idle time and optimizing cost efficiency.
This research focuses on extracting and analyzing the arrival times of trains at shunting yards using a dataset consisting of GPS data. It conducts two algorithms to cluster the given data for each train unit within and across days to identify the same train across different days. Distributions and heatmaps of the arrival times and delays are created based on the identified train series. They are analyzed to identify patterns in train arrival times and delays across different months.

We investigate the generalization performance of predictive models in model-based reinforcement learning when trained using maximum likelihood estimation (MLE) versus proper value equivalence (PVE) loss functions. While the more conventional MLE loss aims to fit models to predict state transitions and rewards as accurately as possible, value-equivalent methods (e.g. PVE) prioritize value-relevant features. We show that in a tabular setting, MLE-based models generalize better than their PVE counterparts when fit to a small number of training policies, whereas PVE-based models perform better as the number of policies increases. With increasing model rank, generalisation error tends to improve for MLE and PVE, and the two become closer in generalisation ability.

When not in service, trains are parked and serviced at shunting yards. The Train Unit Shunting Problem (TUSP), an NP-hard problem, encompasses the challenge of planning movements and tasks in shunting yards. A feasible shunting plan serves as a solution to the TUSP. Current automated planning tools utilized to assist human planners in this computationally heavy planning task are not able to distinguish inherent patterns in input train data, as opposed to humans. This paper aims to address this technological gap by examining whether valuable patterns could be extracted from shunting plan data, consisting of solutions to the TUSP. More specifically, it is mainly concerned with the automatic detection of whether a solution to the TUSP is a week or a weekend day. Therefore, the data is examined for the presence of several groups of patterns. Moreover, binary classification is performed on the data. The experiments conducted in this study suggest the presence of valuable patterns in the data, which could be leveraged to design specialized heuristics for automated planning models tailored to generate shunting plans for weekdays and weekends.

This research aims to find patterns in the live position data of trains within shunting yards. These patterns can be converted to heuristics and applied in algorithms developed by railway operators in the Netherlands to tackle the Train Unit Shunting Problem. The usage patterns were extracted from real-world location data of train units. Specifically, this research focuses on finding patterns in the paths taken in both temporal and spatial metrics. These investigations identified the busiest times in the shunting yards according to various metrics, such as the total number of trains and the number of serviced trains. These metrics are extracted from the type of train movement at a given moment, which was provided with the dataset. The accuracy of the provided train movement category has been analyzed and shown to be inaccurate for uses within shunting yards compared to a proposed approach. Finally, an algorithm for classifying train units that belong to the same train has been shown to have initial success.

Computational efficiency is essential for large-scale mathematical optimisation problems, such as the generation expansion planning problem, to be practically applicable. In linear programming solvers, crossover is frequently a bottleneck when solving optimisation problems. This study aims at determining why crossover is a bottleneck in solving the generation expansion planning problem and deriving a method which obtains an optimal solution faster. Symmetry was found to be disrupting crossover, causing its runtime to significantly increase. However, the preceding barrier method benefit from the symmetry handling of the solver. An alternative approach using problem-specific knowledge to reduce symmetry before serving the model to a solver was proposed. The key to the efficiency of this method is using the information of how symmetries are reduced when retrieving the solution to the original problem. The approach was applied to two types of symmetry we identified in the generation expansion planning problem, leading to a significant speed-up of the crossover phase and total runtime for the algorithm resolving a formulation symmetry, but a longer runtime for the method resolving a more practically available non-formulation symmetry. However, the latter was faster in a couple of cases and has many directions for future improvements. The results of this research, thus, demonstrate that domain knowledge of linear programming problems can be applied to reduce symmetry that state-of-the-art solvers cannot detect and to more efficiently obtain an optimal solution than traditional crossover.

When trains are not actively traveling on the main rail network, they to be parked and prepared for their next journey. This is a complex problem, involving several interconnected subproblems. Additionally, there is uncertainty in this environment which can render initial plans infeasible during their execution. To ensure trains are able to depart in time, having finished all their required service tasks, a schedule is created in advance.

The focus of this thesis is to address the challenges associated with generating robust initial shunting plans in an uncertain environment. This thesis focuses on a sequential problem formulation, modeled as a Markov Decision Process (MDP) and uses a policy optimized for this environment. The goal is to design a method capable of deriving robust initial shunting plans from the policy that are likely to remain feasible for a large number of possible plan executions.

The limitation addressed in this thesis, is that conventional policy-rollout techniques generate action sequences that overlook most alternative outcomes, thereby making the overall plan not feasible for a large number of plan realizations. To address this issue, the thesis proposes two distinct solution methods, aimed to consider every possible state that might be encountered, either directly or indirectly.

Through experimentation on realistically generated problem instances, the research concludes that both proposed methods significantly outperform the baseline approach, demonstrating the possibility of extracting robust initial shunting plans from a given policy that was not explicitly designed for this purpose.

Over 700 trains in the Netherlands are used daily for passenger transportation. Train operations involve tasks like parking, recombination, cleaning, and maintenance, which take place in shunting yards. The train unit shunting problem (TUSP) is a complex planning problem made more difficult by uncertainties such as delays. Most existing approaches overlook these disturbances and the approaches that consider them incorporate heuristics to enhance the robustness of their solutions to disturbances. This thesis proposes an alternative approach: utilizing probabilistic programming to turn an existing planning algorithm and simulator into a generative model of the TUSP. The model introduces disturbances without the need to modify the planning algorithm or simulator. Through two types of inference, we infer a distribution of robust solutions for the TUSP. Empirical results demonstrate the effectiveness of our approach for inferring robust plans in small-scale scenarios.

The wake effect which is turbulence behind a wind turbine created when it extracts energy negatively impacts the power output of the downstream turbines. Active Wake Control can mitigate this effect, by rotating some turbines away from the wind. Previous research applied single agent reinforcement learning to apply Active Wake Control, show- ing good results for small-scale layouts, that don’t scale for larger, practical wind farms.
To that extent, this study focuses on the application of mean-field multi-agent reinforcement learning to Active Wake Control, under constant wind conditions. This algorithm limits the computations to a limited set of neighbouring turbines, reducing their complexities. To build the answer to this question I will also study:
1. how to model the rewards to solve the lazy- agent problem, leveraging the nature of the Active Wake Control
2. how the view of the agent changes the results
3. how does it compare to a single-agent reinforcement learning algorithm, TD3
The experiments were done using the Floris Wake Simulator, with each turbine sharing the same agent, placed in tunnel layouts at real-life distances (6-7 rotor diameters), under constant wind conditions.
Results show that with the proper configuration of rewards and view space within wind tunnels, the mean-field algorithm finds near optimal configurations for Active Wake Control, within a small number of episodes. This shows a promising start for the application of mean-field multi-agent algorithms for the Active Wake Control problem, and provides insight into how to model the rewards, which might be applicable for the whole class of algorithms.

The close proximity of wind turbines to one another in a wind farm can lead to inefficiency in terms of power production due to wake effects. One technique to mitigate the losses is to veer from their individual optimal direction. As such, the wakes can be steered away from downstream turbines in order to increase the overall power output. Multi-Agent Reinforcement Learning (MARL) models the interactions between wind turbines and determines an optimal control strategy through agents that learn the collective consequences of their actions. To
analyse the benefit of multi-agent cooperation and centralised critic evaluation, I investigated the effect of Counterfactual Multi-Agent Policy Gradients (COMA) on Active Wake Control. Ultimately, experiments on wind farms of three and sixteen turbines indicate that the algorithm performs moderately, yet worse than single-agent Reinforcement Learning. In addition, high computation costs hinder its application on real-life environments.

Wind energy, generated by windfarms, is playing an increasingly critical role in meeting current and future energy demands. windfarms, however, face a challenge due to the inherent flaw of wake-induced power losses when turbines are located in close proximity. Wakes, characterized by regions of turbulence and lower wind speed, are created as air passes through the rotors, reducing the efficiency of downstream turbines. Wake losses can be reduced by yawing upstream turbines to steer the wake away from downstream turbines. While there are power losses associated with turning turbines off-wind, the gains in the subsequent turbines can outweigh these losses. Yawing turbines to increase overall power output is known as Active Wake Control, and the literature shows that single-agent reinforcement learning algorithms can be used to learn such control policies. However, these approaches are limited to a small number of turbines and do not scale well to larger windfarms. Multi agent reinforcement learning algorithms do scale to larger windfarms and this paper investigates the application of the DGN algorithm for windfarm active wake control. DGN is a fully cooperative algorithm that utilizes a graph representation of agents to encourage collaboration among neighboring turbines. The use of DGN is particularly interesting because windfarms naturally have a topological structure, and depending on the modeling choices, graphs can capture a significant amount of information. This paper demonstrates that DGN can learn useful policies for wake control. Although it does not outperform the DQN single-agent algorithm on small windfarms, its advantage becomes apparent in larger windfarms, where its performance remains consistent while DQN’s performance deteriorates.

In wind farms wind turbines are often placed close to each other. Each turbine generates a turbulent wake field, this field negatively affects subsequent turbines. This can cost more than 12% efficiency. To decrease this loss we can steer the turbines away from the wind direction, this will decrease the individual turbine power output, but can increase the total power output of the farm. As the size of the farm increases the number of possible actions increase exponentially. Due to this a numerical solution is not feasible. A reinforcement learning technique has been proven useful in the past, but a standard single agent implementation is still very computationally expensive. We evaluate the effectiveness of MADDPG on the active wake control problem. MADDPG is a multi agent reinforcement learning algorithm. MADDPG will be compared to the numerical solver FLORIS and to the already implemented and proven TD3 (which is a variation on a single agent DDPG algorithm). We compare the eventual output power of the algorithms with MADDPG. From the results we can see that MADDPG does improve on the learning performance of TD3, but since MADDPG needs to manage more neural networks the overhead is larger. MADDPG reaches an optimum solution in less training steps, but these steps take significantly more time.

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.

Shunting yards are the locations where trains, which are not included in the train schedule at a certain time, are parked until they are required again. Managing the parking of the trains such that all trains can leave at the desired time is a complicated task, and results in the problem formally known as the Train Unit Shunting Problem (TUSP). This problem is an NP-hard problem, and current algorithms cannot always determine whether an instance is feasible. We analyze a simplified variant of the TUSP, leaving out details from the real-world scenario to study the theoretical conditions for basic scenarios to be feasible. To this extent, we identify essential elements of the TUSP and include these in a modification of the Pebble Motion problem. Based on this Pebble Motion variant, we establish new problems that can be studied to analyze the feasibility of the TUSP. For each of these problems, we examine the complexity and look into different solution approaches.

With the emergence of energy communities, where a number of prosumers (consumers with their own energy generation) invest in shared renewable generation capacity and battery storage, the issue of fair allocation of benefits and costs has become increasingly important. The Shapley value, a solution concept in cooperative game theory initially proposed by Nobel prize-winning economist Lloyd Shapley, has attracted increasing interest for redistribution in energy settings. However, due to its high time complexity, it is intractable beyond communities of a few dozen prosumers. This study proposes a new deterministic method for approximating the Shapley value in realistic community energy settings and compares its performance with existing methods. To provide a benchmark for the comparisons of these methods, we also design a novel method to compute the exact Shapley value for communities of up to several hundred agents by clustering consumers into a smaller number of demand profiles. Experimental analyses with large-scale case studies of a community of up to 200 household consumers in the UK show that the newly proposed method can achieve very close redistribution to the exact Shapley values but at a much lower (and practically feasible) computation cost. Furthermore, it performed similarly to the probabilistic, state-of-the-art approximation method while having smaller time complexity as well as other desirable characteristics for cost redistribution in energy communities.

District heating systems (DHSs) have the potential to play a big part in the energy transition. The efficient operation of DHSs is therefore also an important subject of study. The operation of DHSs where combined heat and power (CHP) plants are used are particularly interesting, because CHPs can operate with high efficiency.

In this work, the operational optimization of DHSs with CHP plants is considered. Determining the optimal heat and electricity production for CHPs for multiple time steps into the future is a complex problem. Because of the heat storage capabilities in the network many solutions are feasible, but determining which solutions are infeasible because of constraint violations in the DHS involves computing time delays that depend on complex network dynamics.

In this work, the possibility of using an input convex neural network (ICNN) to learn the network dynamics of a DHS is explored. ICNNs have limitations on their learning capabilities, but theoretically allow for easier optimization. Experiments on the learning capabilities of ICNNs reveal that caution should be used when they are used to learn non-convex constraints, as the accuracy of the ICNN highly depends on how non-convex the function is. Experiments on the feasible space of supply temperatures to a small district heating network (DHN) reveal that although the network does not provide the same flexibility as heat storage tanks, still some flexibility in the operation can be found. This is due to the fact that water with a higher supply temperature is consumed by consumers at a slower pace and this increases the time delay between production and consumption. Supply temperatures that follow can then be lowered if the increased time delay causes this water to arrive when the heat demands are lower.

In the experiments it was found that this flexibility in operation translates to non-convex areas in the feasible space. When this space would be learned by an ICNN, this space would be made convex. How much of the flexibility would be removed by doing this is yet unknown and could be researched in future work. Other future work can be done on safely learning non-convex constraints with an ICNN.

This papers examines an ant colony optimization approach for solving a specific variant of the Flexible Job Shop Problem faced by the Dutch chemistry company DSM. Jobs consisting of operations on a specific enzyme need to be scheduled as efficiently as possible on groups of available machines. The most interesting requirement upon the general FJSP are the sequence-dependent cleaning times a machine needs when it processes two different enzyme types consecutively. This can all be intuitively represented using a weighted disjunctive graph, which ACO uses as its input. The algorithm consists of a number of epochs for which multiple ants create a feasible schedule one operation at the time. Scheduling choices are made using pheromones and an heuristic visibility function based on earliest starting times. Pheromone amounts are updated using both a negative local updating rule and a positive global update for the best ant per epoch. Two hyperparameters, the initial pheromone amount τ₀ and the cutting exploration parameter q₀ are experimentally evaluated. Varying τ₀ does not consistently impact the solution quality nor runtime, while the higher the value of q₀, the better both measures. Performance evaluation of ACO is done using a provided MILP solver as baseline and the makespan as objective function for a range of different time limits. For the tested instances, ACO shows to significantly outperform MILP, finding good solutions exceptionally fast. Based on this, ACO is an efficient method to solve the production scheduling problem of DSM.