J.T. van Essen
Please Note
45 records found
1
Operating Room Scheduling
A Patient Prioritization Approach
The scheduling problem is addressed through Integer Linear Programming (ILP). A core optimization model is developed to minimize the total DALY loss resulting from surgical delays while respecting MWTs. Two extensions of this model are introduced: one explicitly incorporating patient waiting time with a penalty on exceeding MWTs, and another designed to minimize the maximum DALY loss across patients to promote fairness. These three distinct models, each representing a different prioritization strategy, are empirically tested and compared. Additionally, a sensitivity analysis is conducted on the parameter gamma, which penalizes excess waiting time beyond the MWT, to assess how varying emphasis on excess waiting time impacts prioritization outcomes and overall scheduling effectiveness.
The results highlight key trade-offs between system-level efficiency and individual patient fairness, offering actionable insights for improving surgical scheduling practices. The findings support the integration of objective health-outcome metrics alongside clinical judgment into operational decision-making, contributing to a more equitable and effective allocation of surgical resources.
Overall, this study contributes to the field of surgical scheduling by incorporating the objective measure of Disability-Adjusted Life Years (DALYs) into prioritization decisions and promoting ethically grounded, outcome-oriented scheduling policies. The development of three distinct optimization models—balancing medical urgency, fairness, operational constraints, and MWTs—scheds light on the complex trade-offs between minimizing total DALY loss, considering waiting times and subjective urgency, and ensuring equitable patient outcomes. ...
The scheduling problem is addressed through Integer Linear Programming (ILP). A core optimization model is developed to minimize the total DALY loss resulting from surgical delays while respecting MWTs. Two extensions of this model are introduced: one explicitly incorporating patient waiting time with a penalty on exceeding MWTs, and another designed to minimize the maximum DALY loss across patients to promote fairness. These three distinct models, each representing a different prioritization strategy, are empirically tested and compared. Additionally, a sensitivity analysis is conducted on the parameter gamma, which penalizes excess waiting time beyond the MWT, to assess how varying emphasis on excess waiting time impacts prioritization outcomes and overall scheduling effectiveness.
The results highlight key trade-offs between system-level efficiency and individual patient fairness, offering actionable insights for improving surgical scheduling practices. The findings support the integration of objective health-outcome metrics alongside clinical judgment into operational decision-making, contributing to a more equitable and effective allocation of surgical resources.
Overall, this study contributes to the field of surgical scheduling by incorporating the objective measure of Disability-Adjusted Life Years (DALYs) into prioritization decisions and promoting ethically grounded, outcome-oriented scheduling policies. The development of three distinct optimization models—balancing medical urgency, fairness, operational constraints, and MWTs—scheds light on the complex trade-offs between minimizing total DALY loss, considering waiting times and subjective urgency, and ensuring equitable patient outcomes.
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known. ...
This thesis focuses on two optimisation problems, the bucketised planning problem (BPP) and the travelling salesman problem, to investigate the performance of potential KPIs. Various potential KPI functions and employment methods are tested to determine the efficacy of potential KPIs and to study their behaviour.
The findings of this thesis indicate that adding a potential KPI to the objective function can significantly improve a basic local search algorithm. The performance of the method with potential KPI is highly dependent on the chosen potential KPI function. Moreover, defining such a function is challenging since some knowledge about the local and global optima is needed. While a random function can already improve the algorithm a lot, using a well-constructed function performs even better as potential KPI.
Furthermore, the performance of the method is dependent on how the chosen function is employed. The method should always end with the local search with the original objective function, but whether to start with or without potential KPI is dependent on the function. Nevertheless, starting without potential KPI seems to be slightly better due to the lower runtime and ability to be always better than the basic local search. The weight of the potential KPI in comparison with the original objective should be high and instance-dependent. Additionally, the initial solution also influences the found solution of the method, as a better initial solution, such as a greedy solution, leaves less room for improvement for the basic local search. Thus, the technique of a potential KPI can significantly improve the basic local search, but its effectiveness is dependent on the method of employment and constructed function. Moreover, a potential KPI can only be used when enough information about the optimisation problem is known.
Surgery Scheduling
Dealing with uncertainty in surgery duration
overtime directly impacts utilisation, as intuitively expected... ...
overtime directly impacts utilisation, as intuitively expected...
Location Optimization of Catching Systems for Plastic Waste Removal from Waterways
A Plastic Waste Flow Capturing Location Model
In this model, the plastic waste flow through a network of waterways is represented as a Markov chain, using environmental data as inputs to estimate the initial probabilities and transition probabilities of plastic waste in the network. The PW-FCLM extends an existing Markov Decision Process-based Flow Capturing Location Model by incorporating various types of catching systems, considering sensitive areas, and specifying orientations for the systems. The equivalence of the linearized version of the extended model is demonstrated, a proof of NP-hardness of the problem is given and a greedy heuristic is presented as an alternative solution method.
A sensitivity analysis on the different types of input parameters is performed, and the runtimes for different problem sizes and solution methods are tested for case studies of Delft and Groningen in the Netherlands. The model is most sensitive to changes in the distance between the nodes in the network and to the probability of getting stuck due to water vegetation. For budgets up to B=2 and problem sizes up to n=375 nodes, the exact optimal solution can be found efficiently without a commercial solver license. For larger problem sizes or a higher budget, the heuristic appears to be a more appropriate solution method.
For future research, it is recommended to further study the influence of the distance between the nodes on the optimal solution and to investigate the plastic flow representation in the Markov chain further. Exploring the model's application to larger areas, such as provinces or countries, would be beneficial. The real-life effectiveness of placing catching systems at the optimal locations suggested by the model, depends on the accuracy of the input parameters. In this thesis, the values of the input parameters are primarily based on estimations of experts. It would be beneficial for the user of the model to further validate the values of the input parameters through experiments. ...
In this model, the plastic waste flow through a network of waterways is represented as a Markov chain, using environmental data as inputs to estimate the initial probabilities and transition probabilities of plastic waste in the network. The PW-FCLM extends an existing Markov Decision Process-based Flow Capturing Location Model by incorporating various types of catching systems, considering sensitive areas, and specifying orientations for the systems. The equivalence of the linearized version of the extended model is demonstrated, a proof of NP-hardness of the problem is given and a greedy heuristic is presented as an alternative solution method.
A sensitivity analysis on the different types of input parameters is performed, and the runtimes for different problem sizes and solution methods are tested for case studies of Delft and Groningen in the Netherlands. The model is most sensitive to changes in the distance between the nodes in the network and to the probability of getting stuck due to water vegetation. For budgets up to B=2 and problem sizes up to n=375 nodes, the exact optimal solution can be found efficiently without a commercial solver license. For larger problem sizes or a higher budget, the heuristic appears to be a more appropriate solution method.
For future research, it is recommended to further study the influence of the distance between the nodes on the optimal solution and to investigate the plastic flow representation in the Markov chain further. Exploring the model's application to larger areas, such as provinces or countries, would be beneficial. The real-life effectiveness of placing catching systems at the optimal locations suggested by the model, depends on the accuracy of the input parameters. In this thesis, the values of the input parameters are primarily based on estimations of experts. It would be beneficial for the user of the model to further validate the values of the input parameters through experiments.
Scheduling surgical specialties
Leveling the bed occupancy through stochastic master surgery scheduling
To address the uncertainty of future patient characteristics, we consider the surgery durations and the downstream to the nursing wards in a probabilistic manner. For the latter, we follow the approach of Schneider et al. (2020). For the first aspect, we devised a column generation based approach in which, assuming that individual surgery durations follow a log-normal distribution, we employ the
Fenton-Wilkinson method to estimate the distribution of the total sum of individual surgery durations. When this distribution is known, it becomes feasible to identify pairs of specialties with corresponding surgery counts that can be scheduled within our overtime restriction. The resulting model that includes this incorporation is referred to as the Log-normal Column model.
For our research, we use historical data provided by the Sophia Children’s Hospital. The data included properties about the patients’ surgeries and bed assignments. Due to the presence of errors in the data, we conducted preprocessing before utilizing it as input in our modeling. Additionally, we conducted goodness of fit tests to assess whether adopting the log-normal distribution for surgery duration was genuinely superior to the normal distribution. Our analysis revealed that, for the majority of instances, the log-normal distribution outperformed the normal distribution. This was the case for individual surgeries, as well as the Fenton-Wilkinson approximation for the duration of multiple surgeries.
We compared the performance of our Log-normal Column model to two other models which assume normality for the surgery durations. One is, similar to the Log-normal Column model, created with the column generation based approach, while the other is the model described by Schneider et al. (2020). The two column generation based approach models performed significantly better than the model proposed by Schneider et al. (2020). Furthermore, we compared our Log-normal Column model to the real-life situation with the help of a simulation. ...
To address the uncertainty of future patient characteristics, we consider the surgery durations and the downstream to the nursing wards in a probabilistic manner. For the latter, we follow the approach of Schneider et al. (2020). For the first aspect, we devised a column generation based approach in which, assuming that individual surgery durations follow a log-normal distribution, we employ the
Fenton-Wilkinson method to estimate the distribution of the total sum of individual surgery durations. When this distribution is known, it becomes feasible to identify pairs of specialties with corresponding surgery counts that can be scheduled within our overtime restriction. The resulting model that includes this incorporation is referred to as the Log-normal Column model.
For our research, we use historical data provided by the Sophia Children’s Hospital. The data included properties about the patients’ surgeries and bed assignments. Due to the presence of errors in the data, we conducted preprocessing before utilizing it as input in our modeling. Additionally, we conducted goodness of fit tests to assess whether adopting the log-normal distribution for surgery duration was genuinely superior to the normal distribution. Our analysis revealed that, for the majority of instances, the log-normal distribution outperformed the normal distribution. This was the case for individual surgeries, as well as the Fenton-Wilkinson approximation for the duration of multiple surgeries.
We compared the performance of our Log-normal Column model to two other models which assume normality for the surgery durations. One is, similar to the Log-normal Column model, created with the column generation based approach, while the other is the model described by Schneider et al. (2020). The two column generation based approach models performed significantly better than the model proposed by Schneider et al. (2020). Furthermore, we compared our Log-normal Column model to the real-life situation with the help of a simulation.
Hence, we develop three heuristics for the BFLP: two greedy heuristics and one local search heuristic. These heuristics are adapted from heuristics used for the standard Capacitated Facility Location Problem (CFLP).
The idea behind the first greedy heuristic is to close one facility at a time, starting with all facilities being open, until we have as many facilities open as the budget constraint of the BFLP dictates. At each step, the best facility to close is closed. Apart from adapting this heuristic to accommodate the slightly different constraints of the BFLP, we also make some further adjustments in order to reduce the running time.
The second heuristic that we adapt is a heuristic that instead of closing facilities one at a time, opens facilities one by one, until we reach the budget of open facilities that the BFLP allows. These simple heuristics perform very well in practice on both small and large instances of the BFLP.
Lastly, we discuss a local search heuristic, which attempts to improve a solution to the BFLP by opening one facility and closing another facility at each iteration. The local search only improves marginally upon the results of the greedy algorithms.
For use within the heuristics for the BFLP, we require fast heuristics to solve a subproblem of the BFLP, the problem of assigning users to facilities where the set of open facilities is fixed. Hence, we develop three heuristics for this subproblem and also adapt a previously developed heuristic to be optimised for its use within the BFLP heuristics.
Our heuristics achieve results that are similar or better than what a MIP solver achieves and find a good solution in significantly less time. Especially when the MIP solver struggles, due to the size or limited capacity of the BFLP instance, our heuristics are able to outperform the MIP solver. ...
Hence, we develop three heuristics for the BFLP: two greedy heuristics and one local search heuristic. These heuristics are adapted from heuristics used for the standard Capacitated Facility Location Problem (CFLP).
The idea behind the first greedy heuristic is to close one facility at a time, starting with all facilities being open, until we have as many facilities open as the budget constraint of the BFLP dictates. At each step, the best facility to close is closed. Apart from adapting this heuristic to accommodate the slightly different constraints of the BFLP, we also make some further adjustments in order to reduce the running time.
The second heuristic that we adapt is a heuristic that instead of closing facilities one at a time, opens facilities one by one, until we reach the budget of open facilities that the BFLP allows. These simple heuristics perform very well in practice on both small and large instances of the BFLP.
Lastly, we discuss a local search heuristic, which attempts to improve a solution to the BFLP by opening one facility and closing another facility at each iteration. The local search only improves marginally upon the results of the greedy algorithms.
For use within the heuristics for the BFLP, we require fast heuristics to solve a subproblem of the BFLP, the problem of assigning users to facilities where the set of open facilities is fixed. Hence, we develop three heuristics for this subproblem and also adapt a previously developed heuristic to be optimised for its use within the BFLP heuristics.
Our heuristics achieve results that are similar or better than what a MIP solver achieves and find a good solution in significantly less time. Especially when the MIP solver struggles, due to the size or limited capacity of the BFLP instance, our heuristics are able to outperform the MIP solver.
Surgery scheduling
Dealing with overtime
To capture the probabilistic nature of surgery durations, we investigate suitable probability distributions. Existing literature suggests that surgery durations follow a lognormal distribution. However, since the sum of lognormally distributed random variables lacks a closed form solution, we initially assume a normal distribution for analytical convenience. Subsequently, we approximate the lognormal distribution using the Fenton-Wilkinson method to account for its realistic behavior. To incorporate the
lognormalistic behavior and solve the ILP models efficiently, we employ a column based approach. This approach enables us to handle the complexities introduced by the lognormal distribution. Our study utilizes data provided by a hospital in the Netherlands, including information on surgeries, specialties, groups, and the master surgery schedule (MSS). Given the consideration of both normal and lognormal distributions for surgery durations, we assess the goodness of fit using appropriate statistical
tests.
Our results reveal that using averages or expected values yields the highest OR utilizations. However, there is a discussion regarding the validity of this method, as it does not explicitly incorporate the probabilistic overtime constraints. Nevertheless, we observe that all methods include cases which
surpass the predetermined overtime threshold, suggesting that utilizing averages or expected values can be a valid alternative. However, utilizing averages or expected values gives rise to high percentage
of cases surpassing our overtime threshold. So, we suggest to use a method which explicitly uses the probabilistic nature of the surgery durations.
During the examination of our methods, we had to take a minimum number of mandatory scheduled surgeries for each group into account. This means that another dataset, with different mandatory numbers, might lead to different results. Additionally, we noticed that our overtime definition might not be the most optimal, as we still have cases that surpass our overtime threshold. In future research, it would be valuable to include financial and staff factors, which can further enhance the scheduling process.
Overall, this study contributes to the field of surgery scheduling by addressing the probability of overtime and presenting insights into the trade-offs between OR utilization and the inclusion of probabilistic
constraints. Further research can build upon these findings to refine the scheduling approaches and incorporate additional factors for a more comprehensive solution. ...
To capture the probabilistic nature of surgery durations, we investigate suitable probability distributions. Existing literature suggests that surgery durations follow a lognormal distribution. However, since the sum of lognormally distributed random variables lacks a closed form solution, we initially assume a normal distribution for analytical convenience. Subsequently, we approximate the lognormal distribution using the Fenton-Wilkinson method to account for its realistic behavior. To incorporate the
lognormalistic behavior and solve the ILP models efficiently, we employ a column based approach. This approach enables us to handle the complexities introduced by the lognormal distribution. Our study utilizes data provided by a hospital in the Netherlands, including information on surgeries, specialties, groups, and the master surgery schedule (MSS). Given the consideration of both normal and lognormal distributions for surgery durations, we assess the goodness of fit using appropriate statistical
tests.
Our results reveal that using averages or expected values yields the highest OR utilizations. However, there is a discussion regarding the validity of this method, as it does not explicitly incorporate the probabilistic overtime constraints. Nevertheless, we observe that all methods include cases which
surpass the predetermined overtime threshold, suggesting that utilizing averages or expected values can be a valid alternative. However, utilizing averages or expected values gives rise to high percentage
of cases surpassing our overtime threshold. So, we suggest to use a method which explicitly uses the probabilistic nature of the surgery durations.
During the examination of our methods, we had to take a minimum number of mandatory scheduled surgeries for each group into account. This means that another dataset, with different mandatory numbers, might lead to different results. Additionally, we noticed that our overtime definition might not be the most optimal, as we still have cases that surpass our overtime threshold. In future research, it would be valuable to include financial and staff factors, which can further enhance the scheduling process.
Overall, this study contributes to the field of surgery scheduling by addressing the probability of overtime and presenting insights into the trade-offs between OR utilization and the inclusion of probabilistic
constraints. Further research can build upon these findings to refine the scheduling approaches and incorporate additional factors for a more comprehensive solution.
Applying machine learning in route optimization
Predicting construction algorithm performance for the vehicle routing problem using neural networks
Optimising OR planning
Sequencing surgery groups while levelling bed occupancy
In a hospital, different departments work together to treat the patient as good and efficient as possible. If a patient needs a surgery, not only an OR is needed, but also a bed at a ward which matches the patient's needs. The goal of this thesis is to use the different resources of the hospital as efficiently as possible. This is done by not only optimising the utilisation of the OR, but at the same time levelling the bed occupancy of the different wards. The levelling of the bed occupancy is done by minimising the maximum number of used beds at each ward. Because, if we minimise the maximum, we force that the patients are spread out more evenly over the day.
For each specialty, the patients are divided into patient groups based on historical data using a constrained $k$-means clustering algorithm. For each patient group, information is gathered about the length of stay (LoS) and the surgery duration of patients in this patient group. Next to that, the number of patients in a patient group indicates how often a patient group needs to be scheduled at least.
The probability distribution of the surgery duration is taken into account when deciding at which day, at what time, and in which OR a surgery is planned. A patient group can only be scheduled during OR shifts assigned to the corresponding specialty. At the same time, the levelling of the bed occupancy is taken into account.
After some constraints are linearised, this model can be formulated as a mixed integer linear program (MILP). However, the model has a large number of variables. Therefore, column generation is used to split the model into smaller subproblems per specialty. Some of the pricing subproblems take a lot of time to optimise. For that reason, we set some time limits both on the runtime of the pricing subproblems and the runtime of the entire algorithm. Column generation does not guarantee an optimal solution of our MILP. However, the objective value of our MILP improves over time, when new columns are added to the set of available columns. This indicates that column generation can be used to optimise our model.
In this thesis, several versions of the model are presented. For example, the schedule is different if the bed occupancy is calculated every hour or of every fifteen minutes. Next to that, the model can either be more focussed on maximising the OR utilisation or on levelling the bed occupancy. ...
In a hospital, different departments work together to treat the patient as good and efficient as possible. If a patient needs a surgery, not only an OR is needed, but also a bed at a ward which matches the patient's needs. The goal of this thesis is to use the different resources of the hospital as efficiently as possible. This is done by not only optimising the utilisation of the OR, but at the same time levelling the bed occupancy of the different wards. The levelling of the bed occupancy is done by minimising the maximum number of used beds at each ward. Because, if we minimise the maximum, we force that the patients are spread out more evenly over the day.
For each specialty, the patients are divided into patient groups based on historical data using a constrained $k$-means clustering algorithm. For each patient group, information is gathered about the length of stay (LoS) and the surgery duration of patients in this patient group. Next to that, the number of patients in a patient group indicates how often a patient group needs to be scheduled at least.
The probability distribution of the surgery duration is taken into account when deciding at which day, at what time, and in which OR a surgery is planned. A patient group can only be scheduled during OR shifts assigned to the corresponding specialty. At the same time, the levelling of the bed occupancy is taken into account.
After some constraints are linearised, this model can be formulated as a mixed integer linear program (MILP). However, the model has a large number of variables. Therefore, column generation is used to split the model into smaller subproblems per specialty. Some of the pricing subproblems take a lot of time to optimise. For that reason, we set some time limits both on the runtime of the pricing subproblems and the runtime of the entire algorithm. Column generation does not guarantee an optimal solution of our MILP. However, the objective value of our MILP improves over time, when new columns are added to the set of available columns. This indicates that column generation can be used to optimise our model.
In this thesis, several versions of the model are presented. For example, the schedule is different if the bed occupancy is calculated every hour or of every fifteen minutes. Next to that, the model can either be more focussed on maximising the OR utilisation or on levelling the bed occupancy.
Electrical energy storage scheduling
Short-term scheduling for the intraday market using stochastic programming
This thesis focuses on short-term EES scheduling, comparing pumped hydropower storage (PHS), compressed air energy storage (CAES), and battery energy storage systems (BESS). This thesis aims to optimize EES scheduling, which includes charging and discharging actions, in the intraday electricity market, considering market price uncertainties. Storage decisions are optimized for one day (24 hours) from the perspective of the storage owner, and its objective is to maximize its profit through market operations. The research introduces a two-stage stochastic programming approach with a rolling horizon method (SORH) to adapt to changing conditions of the intraday market throughout the day.
The results of SORH, its deterministic counterpart (DORH), and simple deterministic optimization (DO) are compared by implementing a case study organized in four typical days based on trading data from the German electricity market. SORH consistently outperforms DORH and DO and is a suitable optimization strategy. SORH reaches on average 72 percentage of the theoretical optimum, where all prices are known in advance. Moreover, SORH offers opportunities for speculative trading using the storage as an option rather than only physically operating the storage. For a practical application of the model, future research could explore methods to match the current day with representative typical days to construct relevant price scenarios. ...
This thesis focuses on short-term EES scheduling, comparing pumped hydropower storage (PHS), compressed air energy storage (CAES), and battery energy storage systems (BESS). This thesis aims to optimize EES scheduling, which includes charging and discharging actions, in the intraday electricity market, considering market price uncertainties. Storage decisions are optimized for one day (24 hours) from the perspective of the storage owner, and its objective is to maximize its profit through market operations. The research introduces a two-stage stochastic programming approach with a rolling horizon method (SORH) to adapt to changing conditions of the intraday market throughout the day.
The results of SORH, its deterministic counterpart (DORH), and simple deterministic optimization (DO) are compared by implementing a case study organized in four typical days based on trading data from the German electricity market. SORH consistently outperforms DORH and DO and is a suitable optimization strategy. SORH reaches on average 72 percentage of the theoretical optimum, where all prices are known in advance. Moreover, SORH offers opportunities for speculative trading using the storage as an option rather than only physically operating the storage. For a practical application of the model, future research could explore methods to match the current day with representative typical days to construct relevant price scenarios.
Implementing station-based bike-sharing in strategic transport models
Creating an approach to combine tour-based mode-choice and modelling multimodality