Operations Research Proceedings 2023

Branch-and-price is a common approach to optimally solve time-extended multi-robot task allocation (MRTA) problems. However, so far no complex dependencies could be considered. Complex dependencies arise if multiple decompositions of tasks are available that can be allocated to different robots. We propose three different methods how to handle complex dependencies within branch-and-price (BnP) approaches for MRTA problems. The decomposition method is based on a decompose-then-allocate concept, while the decision variable method and the cluster method incorporate the complex dependencies explicitly into the overall optimization model. An evaluation is conducted to compare the proposed approaches.

Due to climate change, high-emission industries must transform their production processes toward low-carbon technologies. Therefore, steelmakers plan to replace currently operated production facilities long-term. However, production facilities can also be modified to achieve medium-term emission reductions. Against this background, we present a planning model to support decisions about closing or modifying production facilities within production networks for conventional primary steelmaking. The mixed-integer linear programming model aims to maximize the net present value of steelmaking. It incorporates time-dependent emission budgets that initiate the transformation process. Also, plant modifications to reduce specific greenhouse gas emissions are included. Using different climate scenarios, the dynamic transformation of a European steelmakers’ production network is examined in a case study. The results indicate that modifying production facilities is more favorable in the case of site-specific emission budgets compared to global budgets.

Intensive care units (ICUs) are specialized departments designed to provide comprehensive care and continuous monitoring to critically ill or injured patients. These units are equipped with high-tech medical equipment and staffed by specially trained healthcare professionals. Due to their high cost and limited capacity, ICUs often pose a bottleneck in the patient flow, making efficient use of ICU resources a critical concern for both hospitals and patients. Especially hospital departments with a high proportion of intensive care patients do sometimes express the wish to reserve ICU beds exclusively for their patients. This reservation policy can be a source of debate and controversy, as it can affect the overall performance of the ICU. To investigate the advantages and disadvantages of such a policy, this study first develops a discrete-event simulation model of the current patient flow in an ICU based on real-world data from a Bavarian maximum-care hospital. On this basis, the effects of bed reservation for certain departments will be analyzed in a scenario as well as the impact on the overall performance of the ICU to provide decision support in this regard. We show that reserving capacity for specific units results in benefits for them at the expense of performance losses for the whole system. In our sensitivity analysis, we are able to quantify these effects.

In this paper, we consider the single machine scheduling problem of minimizing the number of late jobs taking into account ready times, due dates, and uniform processing times. Assuming limited machine availability, position-dependent maintenance operations of uniform length must be performed on the machine no later than a given number of scheduled jobs. This type of maintenance can be found in any real-world setting where the number of jobs, rather than their length, is the main cause of deterioration, such as aircraft landing gear. We discuss the characteristics of this scheduling problem and formulate an algorithm to solve the above single machine problem in polynomial time.

The Traveling Purchaser Problem serves as a model for a multitude of transportation and procurement issues. In the basic model, a decision-maker buys products from different markets while balancing the prices of each market together with the tour costs from visiting them. One variant that has not been investigated yet describes the problem of additional tariffs payable when a truck enters a particular area to visit markets. This case describes the real-world situation as it is often found, e.g., near country borders. A subset of markets shares an extra fee as soon as one of them is visited. This paper explores this new variant with zone-based tariffs. The model is set up and then examined in detail to understand the particular characteristics of the problem compared to the basic variant. Furthermore, the structure of the solutions is examined to gain deeper insight into this design.

In case of disturbance, train dispatching takes place in a geographically limited area, the dispatching area. From a practical point of view, this is due to the workload of the dispatcher. In order to obtain a more holistic view of the train dispatching problem, this work presents an approach which extends a microscopic approach of dispatching by a macroscopic view of railway operations that take place outside the dispatching area. For this purpose, a cost function is developed, which is applied within a MIP as a subproblem of a column generation. For a selected dispatching area, numerical calculations show that the presented method satisfies the requirements for real-time train dispatching.

The Electric Vehicle Routing Problem (EVRP) requires finding the optimal route for electric vehicles to travel while considering factors such as battery capacity, charging infrastructure, and time constraints. This paper addresses the EVRP problem with forced driving breaks (EVRP-LB), as stated in the EU regulation No 561/2006. The traditional approach to incorporate these breaks is first to solve a model formulation that neglects them and then repair the obtained routes by fixing some breaks within the routes. In contrast, this paper incorporates the breaks directly in the optimization model as constraints. The aim is to understand whether it matters or not to incorporate these breaks over the traditional approach, and to identify which features differ in the so-obtained solutions. A MILP model is proposed to conduct experiments on a simplified real-world dataset. The numerical analysis demonstrates that the novel model leads to travel time reductions of up to 4.8%.

Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different nodes in the tree to tighten variable bounds. We show that this helps to speed up the solutions times by about 8 % on our testset.

We introduce Scylla, a primal heuristic for mixed-integer optimization problems. It exploits approximate solves of the Linear Programming relaxations through the matrix-free Primal-Dual Hybrid Gradient algorithm with specialized termination criteria, and derives integer-feasible solutions via fix-and-propagate procedures and feasibility-pump-like updates to the objective function. Computational experiments show that the method is particularly suited to instances with hard linear relaxations.

We consider mixed-integer programs with non-convex objectives that are modelled with indicator variables. Because this modelling typically requires the use of big-M values, such programs often have weak linear programming relaxations. The dual bound in a branch-and-bound tree therefore improves only slowly, which results in very long solution times. To strengthen the dual bound we partition the problem and then apply Lagrangean decomposition in order to obtain independent subproblems. We show for an application to support vector machines with ramp loss, that the dual bound can be improved compared to the bound obtained from a full mixed-integer programming formulation. Moreover, the subproblems can be efficiently solved in parallel.

Lot-sizing models are a vital part of the inventory management literature. Especially dynamic lot-sizing models are the basis of many industrial applications. Besides the basic single-item model, many extensions exist. Among them, remanufacturing models are important concerning aspects of quality and sustainability. They focus on the handling of product returns from customers and thus combine the processes of manufacturing and remanufacturing into a single model. Whereas many models are focusing on this aspect of external product returns, comparatively little attention has been paid to internal product returns. While quality management aims to optimise production towards zero defects, this is not always possible. Therefore, this paper contributes to the literature by introducing a basic model that assumes an imperfect production process and rework of the resulting defective items. We compare this model to the closely related models, namely the basic single-item model with perfect production and the remanufacturing model. In addition, a numeric study will compare the computation efforts for them and will also highlight hard cases of the rework model. It will be shown, that the model formulations are very similar but the computation times differ strongly for the three models. The rework model shows the largest runtimes and increases strongly with increasing lengths of the planning horizon. Also, there are specific cost parameter combinations that cause multiples of the average computation times.

The production of oil and gas on the Norwegian continental shelf takes place at offshore installations owned and controlled by different operators, located in remote areas. Specialized platform supply vessels (PSVs) are used for servicing the installations with commodities needed for stable and continuous production. In current practice, each operator controls its own fleet of PSVs, and each installation is serviced from a dedicated supply base (among several) along the Norwegian coast where cargo demands are specified for each installation on particular days. In this work, we explore how costs and greenhouse gas emissions from the offshore logistics can be reduced by collaboration among operators through a sharing of their vessels and supply bases. We solve this by generating a priori a large set of feasible voyages that can be combined to form weekly routes for each vessel. Spot vessels can also be used to meet demands by performing the same voyages at a higher operational cost. A small numerical example based on real data is provided, illustrating a fuel saving that reduces emissions by more than 25% together with the possibility of also reducing the fleet size required to meet cargo demands.

The Covering Tour Problem (CTP) is considered as a generalization of the Traveling Salesman Problem in which not all nodes must be visited. The main concept of the CTP is that some nodes must be visited by the vehicles whereas some other nodes have to be covered. If a node is located within a predetermined covering distance of its next visited node, it is said to be covered. The interest in this subject has recently increased, both theoretically and practically. Multiple researchers have been interested in the CTP for real-life applications, such as humanitarian logistics, regional development, urban patrolling, and healthcare management. To the best of our knowledge, no work has considered reviewing the covering tour problem. For this reason, we will introduce in this work, the CTP and its different variants. The main objective is to examine the existent literature to highlight the studies that have already been done and to identify any gaps and promising areas for further studies.

The weighted set packing problem (WSPP) is a variant of the well-known set packing problem, assigning a weight to every considered subset of a given finite base set. Its solution is a maximum sum-weight, element-disjoint covering of the base set. Using its formulation as a binary linear program (BLP), every column of the constraint matrix describes one of the given subsets. Thus, column generation (CG) provides a good solution method, generating iteratively only promising subsets as candidates for the covering. We consider an extension of the WSPP, where forbidden pairs are taken into consideration, i.e., there can be pairs of subsets that cannot be chosen at the same time, and adapt CG to derive a new solution algorithm to solve the resulting BLP. At each iteration, the optimal solution obtained with CG is checked for potential conflicts and either they are resolved locally without changing the objective function value or a new linear constraint forbidding the conflicting pair of columns is added. Then the CG procedure starts again. The applicability of this approach is shown for a team orienteering problem involving two unmanned aerial vehicles that must maintain safety distances between them.

In this paper, a class of combinatorial optimization problems with uncertain objective function costs is considered. The unknown probability distribution for the uncertain cost vector is approximated by an empirical distribution based on an available sample of the cost realizations. The true probability distribution is assumed to lie in a Wasserstein ball centered in the empirical distribution. A solution minimizing the Conditional Value at Risk for a worst probability distribution in the Wasserstein ball is computed. A general method for computing this solution is proposed.

We propose a novel method for designing and optimizing truss-like structures using mathematical optimization. As additive manufacturing continues to advance, innovative structural design methods become increasingly relevant in practical applications. To this end, we present an approach that combines established truss optimization techniques in engineering with technical operations research methods. The model developed is capable of optimizing truss structures while accounting for the effects of moving structural elements under various loading scenarios. The primary objective is to quantify the advantages of dynamic structures over rigid ones in terms of efficiency and effectiveness as well as demonstrate that mathematical optimization is a compelling tool for advanced applications in structural engineering.

Integrating urban parcel transportation into a public passenger transport system is a promising concept to reduce traffic congestion and use resources more efficiently. However, the last decade saw several pilot projects failing due to the lack of long-term support and profitability. Integrated transport relies on a range of stakeholders, which differ in their incentives and want to profit from the system. Existing reviews show that financial viability is an important aspect for the long-term success of such projects. For example, partially financing the public transit system with the revenue gained from parcel transportation may contribute to the success of a shared transport system from the point of view of public transit providers. This work conceptualizes an agent-based simulation model to evaluate business schemes for an integrated passenger and freight urban transport system.

This paper outlines a Mixed-Integer Multi-Period Linear Programming approach to identify so-called no-regret energy transition pathways. The methodology presented is essentially a trilemma-solver that supports industry, network operators, and regional governments to decide upon efficient and effective investments to meet CO2 reduction targets. The decarbonization of an industrial cluster like the Port of Rotterdam (PoR) is presented as a case study to demonstrate the approach. Different scenarios are evaluated, such as ‘accelerated decarbonization’ of the Rotterdam industrial cluster. This scenario calculates the most cost-efficient way to accelerate the transition. In addition, the methodology identifies which levers are essential for decarbonization under different scenarios. One limitation of the approach is its implicit modeling of uncertainties, currently part of two separate PhD trajectories.

We consider a scheduling problem from an industrially relevant high-throughput laboratory, which we model as a quadratic unconstrained binary optimization problem (QUBO). We are particularly interested in the impact of the D-Wave quantum annealer when solving this QUBO. Due to the limited capabilities of the D-Wave quantum hardware, we propose a quantum-classical hybrid algorithm to obtain a solution. For our study, we replace the quantum annealer in the hybrid algorithm by simulated annealing and compare the results. We find that the quantum annealer is not clearly superior to the simulated annealer, but can improve a local search with suitable perturbations.

This study provides an assessment of machine learning applied to the field of univariate financial time series analysis. Drawing on widely accepted ARIMA models, competing machine learning approaches are compared and various training scenarios and network architectures are discussed to identify the optimal network approach for daily return series forecasts. As a result of this exercise, plain vanilla recurrent neural networks with one layer describe a sensible choice.

This paper deals with the recoverable robust shortest path problem under the interval uncertainty representation. The problem is known to be strongly NP-hard and not approximable in general digraphs. Polynomial-time algorithms for the problem under consideration in DAGs are proposed.

Concerns over the rising energy consumption and CO2 emissions of the expanding cloud market necessitate urgent sustainability improvements. However, there are no coherent studies on the costs and benefits of sustainability measures for cloud infrastructures. To investigate the value of renewable energy and excess heat utilization, we propose a mixed-integer programming model for cost-minimal cloud infrastructure network planning. We apply our model to a German case study and find significant potential for carbon footprint and cost reduction associated with excess heat utilization.

In rural (or sparsely populated) areas public transport lines are often operated with low frequencies. These lines used on the first mile of a passenger travel chain often connect the starting point of a travel chain with the nearest hub served by high-frequency lines, where the passengers change the line. For delivering a high-quality, attractive timetable for their passengers, public transport operators try to enable short connection times. This is challenging especially when a line serves several hubs and different travel chains must be coordinated. We propose a new method for integrating a travel chain into a periodic timetable to minimize passenger connection times. We will illustrate the potential of our approach through a small case study of a bus line in Switzerland.

Developing operations research (OR) software that is used productively comes with degrees of freedom and restrictions. We will examine the tackled decisions, pros and cons of options, constraints imposed by company rules, and lessons learned by DB Schenker’s OR team as it developed and revised its tech stack.

An increasing number of service providers deliver products and services to our homes. Examples are health care, deliveries of goods like parcels, food or groceries as well as repairs or cleaning services. These types of services are subject to similar operational planning: clients need to be assigned to a service provider. For each of these service providers a route and a schedule need to be designed. Extended vehicle routing problems with time windows (VRPTW) display these planning problems. To the best of our knowledge, in literature, most articles tackle only one of the home services with the VRPTW, despite their similarities. We compare existing model extensions of different service types and develop a generic home delivered services routing and scheduling problem (HDSRSP) that covers three different service types. Preliminary tests on benchmark instances show that the model is capable of solving these problems. This lays the foundation for further research regarding general solution approaches for home delivered services.

The identification of parameters within dynamical systems using measurements is a well-understood but effortful endeavor. To simplify the required steps, we present TOPAS Model Fitting, a software that covers aspects such as measurement preprocessing, optimization-based parameter identification, and post-optimal system simulation in a user-friendly, graphical interface-based way. The tool provides established methods such as single and multiple shooting, full discretization, and gradient matching. In this paper, they are applied to an extensive set of test problems. As only their default configurations are used, the results demonstrate the tool’s ability to solve a wide range of problems. They reveal that multiple shooting and full discretization are to be preferred, while the necessity of deploying multiple methods also becomes evident.

In multi-period inventory management, decisions are made about procurement timing and quantities as well as on inventory control of goods. To strive for cost minimization, for B and C goods procurement companies apply inventory policies. A major assumption of most policies are constant purchase prices and stochastic demand. Today, however, products and services often experience price fluctuations. This raises two challenges: (1) The economic advantage of conventional inventory policies in presence of fluctuating purchase prices, and (2) the integration of value orientation into inventory policies. To address these questions, a simulation study is conducted with fluctuating purchase prices, including value-oriented aspects. The study focuses on developing inventory policies for goods with fluctuating prices and comparing their performance to conventional policies. The simulation evaluates the degree of demand and price fluctuation, demonstrating that value-oriented extensions improve performance and solution robustness as price fluctuation increases. These findings highlight the need for further research on efficient configuration of value-oriented inventory policies for economically procuring and storing goods during price fluctuations.

The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5% performance improvement for SCIP over the MIPLIB 2017 benchmark set.

Industrial decision-makers often base decisions on mathematical optimization models to achieve cost-efficient design solutions in energy transitions. However, since a model can only approximate reality, the optimal solution is not necessarily the best real-world energy system. Exploring near-optimal design spaces, e.g., by the Modeling All Alternatives (MAA) method, provides a more holistic view of decision alternatives beyond the cost-optimal solution. However, the MAA method misses out on discrete investment decisions. Incorporating such discrete investment decisions is crucial when modeling industrial energy systems. Our work extends the MAA method by integrating discrete design decisions. We optimize the design and operation of an industrial energy system transformation using a mixed-integer linear program. First, we explore the continuous, near-optimal design space by applying the MAA method. Thereafter, we sample all discrete design alternatives from the continuous, near-optimal design space. In a case study, we apply our method to identify all near-optimal design alternatives of an industrial energy system. We find 128 near-optimal design alternatives where costs are allowed to increase to a maximum of one percent offering decision-makers more flexibility in their investment decisions. Our work enables the analysis of discrete design alternatives for industrial energy transitions and supports the decision-making process for investments in energy infrastructure.

This paper presents the design of a system for generating realistic problem instances for loading and unloading RoRo (roll-on roll-off)-ships in seaports. The generator can be configured according to problem-specific layouts and input data like the cargo types, stowage plan, size of the terminal areas and vessel, and distribution of specific travel times. Each thus generated instance represents a scenario in which a RoRo-ship arrives at the harbor to be loaded/unloaded. The resulting instances are viable inputs to test planning approaches and we shortly discuss their applications in static and dynamic decision-making.

Lowering overhead costs and environmental impact in bike-sharing requires the efficient realization and optimization of a vehicle-based rebalancing strategy. The goal is to solve the total problem for a large city within one minute. For that, carefully chosen metaheuristics together with efficient numerical implementations have been developed. Initial solutions, stochastically produced by a Greedy method, are improved by an advanced Variable Neighborhood Search (VNS) algorithm together with a Large Neighborhood Search (LNS) metaheuristic. VNS is the efficient local search strategy, LNS better explores global solution space but is slower. For VNS, different neighborhood operators and operator change strategies are experimentally analyzed for real and large data sets of cities like Munich. Loading instructions obtained from exact maximum flow computations are derived for every set of intermediate candidate routes and are used as feasibility checks. Our two approaches (VNS+LNS and Parallel Variable Neighborhood Search (pVNS)) are benchmarked against (exact) Branch-and-Cut (B&C) methods and provide near-optimal solutions while vastly outperforming the exact method in terms of computational time, especially for large cities. Extensions to hybrid systems and a new windowing strategy modeling behavior of human experts are presented. They significantly improve real-world applicability and ease the work of bike-sharing systems (BS) operators.

We consider branch and price solution methodologies for optimal aircrew scheduling. Utilizing an optimization model termed master, these methodologies aim to assign a roster to each member of the group under consideration, so that the total system cost is minimized. The master problem is typically formulated as a set-partition optimization model. In order to expedite the identification of the attainable duty coverage, we propose its formulation as a set-cover optimization model instead, in which duty over-coverage is allowed while roster quality is ignored. The resulting set-cover solution is transformed into an equivalent set-partition one through the employment of a mixed integer optimization model which removes overcovered duties from the rosters, so as to optimize roster quality without affecting optimal coverage. We use tests on realistic problem instances for evaluating the proposed methodology.

Restricted normal cones are of interest, for instance, in the theory of local error bounds, where they have recently been used to characterize the existence of a constrained Lipschitzian error bound. In this paper, we establish relations between two concepts for restricted normals. The first of these concepts was introduced in the late 1990s by Studniarski, the second more than ten years later by Bauschke et al. Under assumptions, suitable for the use in the theory of error bounds, we explain that the two concepts are the same. Furthermore, we develop several formulas that simplify the computation of restricted normals.

This work introduces a new day-ahead market coupling mechanism as part of AMIRIS, an agent-based market model for renewable and integrated energy systems. The mechanism enables researchers to analyze cross-border electricity trading and its effects on electricity markets. Bids and asks from local traders are processed by a central “MarketCoupling” agent. This agent minimizes the total system cost of providing electricity by dispatching cross-border demands based on available transmission capacity. The proposed algorithm achieves cost-effective market coupling by prioritizing transfers between markets with the highest price differences. The implementation is demonstrated in a case study of four interconnected markets. The results indicate a reallocation of demand from the more expensive markets to the cheaper ones, leading to a minimization of total system costs. Computation times are roughly doubled compared to runs without market coupling, but still remain below 9 minutes per run for a comprehensive European scenario for a full year when executed on a standard laptop computer. Besides large-scale cross-border coupling, the algorithm could also be used for much smaller market zones (i.e. “nodal pricing”). It is available as part of the open-source model AMIRIS.

The dynamic vehicle routing problem with time windows (DVRPTW) is a generalization of the classical VRPTW to an online setting, where customer data arrives in batches and real-time routing solutions are required. In this paper, we adapt the Hybrid Genetic Search (HGS) algorithm, a successful heuristic for VRPTW, to the dynamic variant. We discuss the affected components of the HGS algorithm including giant-tour representation, cost computation, initial population, crossover, and local search. Our approach modifies these components for DVRPTW, attempting to balance solution quality and constraints on future customer arrivals. To this end, we devise methods for comparing different-sized solutions, normalizing costs, and accounting for future epochs. Though our methods do not require any prior training, computational results on data from the EURO meets NeurIPS Vehicle Routing Competition 2022 demonstrate significantly improved solution quality over the best-performing baseline algorithm.

We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve RSRP-PdM.

The nature of chemical processes imposes multiple challenges on production planning and scheduling. The Westenberger–Kallrath (WK) problem which was published in 2002 still serves as a benchmark for that industry. In the past, mathematical models and solution approaches made use of mixed-integer (linear) programming (MI(L)P) methods or metaheuristics. Nowadays, algorithmic advances in artificial intelligence (AI) provide new opportunities for integrated modeling and solution methods. In this research, we investigate the application of reinforcement learning (RL) and propose a novel approach to solve the WK problem. Specifically, we develop a material requirements planning (MRP) and batching heuristic to preprocess the problem data and create chains of production orders that can be scheduled independently. Next, we apply RL algorithms to train an agent to schedule the chains following the objective of minimizing the makespan of the complete schedule. We detect modeling and implementation challenges arising from first experiments.

Ventilation systems are used to ensure a good indoor climate even in increasingly airtight buildings. It is predicted that ventilation systems will be installed in 90% of all new buildings in Germany by 2035 in order to achieve the EU’s climate targets. To design energy-efficient ventilation systems, topology decisions have to be made about the number, size, location and interconnection of fans and volume flow controllers, and operation under different load scenarios has to be anticipated. This leads to enormous degrees of freedom and methods from discrete optimisation become helpful. The resulting optimisation problem is a 2-stage stochastic MINLP. Preliminary work has confirmed the enormous potential of the approach to reduce life-cycle costs by up to 23%. However, so far consideration of acoustic phenomena has been lacking. The noise from a ventilation system must not exceed certain sound pressure levels in rooms. To integrate the acoustics into the optimisation, this paper models sound propagation from the duct network to the rooms as a network flow problem. Then, airflow and acoustics are coupled in a multipole approach. To overcome the strong nonlinearities and to reduce the model size, the model’s structure is exploited. The addition of acoustics is an important step that takes mathematically supported designing of ventilation systems to a new level.

The configuration of heuristics strongly affects the resulting objective function values for given problem instances. Finding the most suitable algorithm components is essential for efficient production scheduling. This paper aims to automatically compare and combine different priority rules, machine allocation, and stage allocation strategies on hybrid flow shop instances with different sets of real-world constraints. To test and tune algorithm configurations and parameters for scheduling problems, an approach with combinatorial logic using the combinatory logic synthesizer is applied. To automatically test scheduling instances, the trace formats in the literature are first reviewed. A trace format is proposed to harmonize the data sets for a large number of beta constraints. In the second step, 32 constructive heuristic configurations are automatically constructed using componentization and recombination with four priority rules, four machine assignment strategies, and two-stage assignment strategies in a general framework of a constructive heuristic. Finally, three sets of test instances with different numbers of jobs by Wittrock (Operations Research 36:445–453, 1988), Naderi et al. (Computers & Operations Research 37:236–246, 2010) and Ruiz et al. (Computers & Operations Research 35: 1151–1175, 2008) are used to evaluate the resulting constructive heuristics.

Most land use problems, such as the choice of varieties of a given crop for a region, are solved by considering a single decision maker. In the case where there are several decision-makers, it is often assumed that a consensus has been reached among them so that they all act as one decision-maker. To compensate for this single decision-maker view, literature propose several multi-criteria methods for group decision making. However, most of them suffer from certain limitations. A first limitation may be the large number of parameters to be determined during the execution of the decision process, which may be inherent to the method used itself. The difficulty of aggregating the preferences of each stakeholder, who are now all considered to be decision-makers, in order to arrive at a decision that can be accepted by all of them, constitutes a second limitation. In this work, we contribute to remedy these two limitations by proposing an extension of the existing KEMIRA multi-criteria choice method, namely KEMIRA-group, for group decision making. We illustrate the effectiveness of our approach through a case study of the selection of the best cowpea varieties (crop) appropriate to a given region in West Africa (Burkina Faso).

It is a major open problem in the fields of operations research and linear optimization whether there is an efficient pivot rule for Dantzig’s simplex algorithm. We show that it is not possible to obtain the desired strongly polynomial running time with a pivot rule that is a combination of Bland’s pivot rule, Dantzig’s pivot rule, and the Largest Increase rule—three of the most classical simplex pivot rules. The proof is based on a close relation to the policy iteration algorithm for Markov decision processes. More precisely, we construct a family of Markov decision processes for which policy iteration performs the same exponential sequence of improving switches when applied with any of the three pivot rules. This behavior yields that the worst-case running time of the algorithm is exponential for every combination of the considered rules. Then, due to the connection between both algorithms, we obtain the same exponential lower bound result for the simplex method. Typically, the policy iteration algorithm applies multiple switches simultaneously, and our lower bounds for Dantzig’s rule and the Largest Increase rule, where we assume that policy iteration only performs single switches, seem novel. The individual lower bounds for the simplex algorithm were previously proven separately via deformed hypercube constructions.

The k simple shortest paths problem (kSSP) on a simple weighted digraph is a classic combinatorial problem. Although Yen’s algorithm no longer possesses the best known time complexity, it remains an important benchmark for kSSP algorithms. Roditty and Zwick developed a kSSP algorithm that solves the problem by solving 2k instances of 2SSP. However, the authors do not specify how to solve this subroutine efficiently. We close this gap by providing a new biobjective search algorithm for 2SSP. The algorithm by Roditty and Zwick in conjunction with our new algorithm matches the running time bound of Yen’s algorithm and is fast in practice. Moreover, we discuss the framework of the asymptotically fastest kSSP algorithm due to Gotthilf and Lewenstein and use it in connection with a recent breakthrough result on the all pairs shortest paths problem by Orlin and Végh to show the existence of an O(kmn) algorithm for kSSP for integer costs. This improved time complexity bound is the best known for this relevant special case. In our computational experiments on road and grid graphs we assess the new algorithm’s practical efficiency. It turns out to be significantly faster than Yen’s algorithm on these graphs.

Due to an enormous growth in resource usage and environmental pollution, returning the end-of-use product to the use cycle has received wide attention. A closed-loop supply chain can reduce virgin resource usage and environmental impact and achieve economic benefit by returning waste and end-of-use products to the use cycle. This study examines significant practices such as recycling and reducing, considering material type and material recyclability. Especially, the impact of raw material types and their recyclability on recycling amount, resource usage, and environmental pollution are investigated. Effectively, a MILP multi-objective model is formulated with total cost as an economic benefit and material management as an environmental benefit. Finally, the correctness of the proposed model is verified by a case study of the beverage industry in Mexico City using the augment epsilon constraints method. We analyze the proposed model in three aspects, including material types, recycling rate, collection mechanism, and return rate. The findings demonstrate that the manufacturing supply chain could tend to enhance the recycling amount when the recycling cost decreases and the recycling rate increases. Additionally, improving the collection mechanism could increase reverse value to achieve economic and environmental benefits. The research also extends the understanding of closed-loop supply chains by defining the important reverse flow practices and collection mechanisms for manufacturing enterprises.

We consider a capacitated job shop problem with order acceptance. This research is motivated by the management of a research and development project pipeline for a company in the agricultural industry whose success depends on regularly releasing new and innovative products. The setting requires the consideration of multiple problem characteristics not commonly considered in scheduling research. Each job has a given release and due date and requires the execution of an individual sequence of operations on different machines (job shop). There is a set of machines of fixed capacity, each of which can process multiple operations simultaneously. Given that typically only a small percentage of jobs yield a commercially viable product, the number of potential jobs to schedule is in the order of several thousands. Due to limited capacity, not all jobs can be started. Instead, the objective is to maximize the throughput. Namely, to start as many jobs as possible. We present a Mixed Integer Programming (MIP) formulation of this problem and study how resource capacity and the option to delay jobs can impact research and development throughput. We show that the MIP formulation can prove optimality even for very large instances with less restrictive capacity constraints, while instances with a tight capacity are more challenging to solve.

Due to the coexistence of different gases in underground storage, this work explores the interface stability’s impact on energy storage, specifically during the injection and withdrawal of gases such as hydrogen and natural gas. A new approach of combing simulation and time series analysis is used to accurately predict instability modes in energy systems. Our simulation is based on the 2D Euler equations, solved using a second-order finite volume method with a staggered grid. The solution is validated by comparing them to experimental data and analytical solutions, accurately predicting the instability’s behavior. We use time series analysis and state-of-the-art regime-switching methods to identify critical features of the interface dynamics, providing crucial insights into system optimization and design.

It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate-scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling.

The pressure on the air traffic sector to reduce the amount of emitted CO $$_2$$ 2 emissions is continuously increasing. Green hydrogen offers an alternative aircraft fuel that is CO $$_2$$ 2 neutral. However, the production is very energy-intensive, which could lead to different prices at different production sites due to geological differences regarding possibilities to generate renewable energy. On the other hand, the amount of available hydrogen at airports might differ because of the divergent potential for building necessary infrastructure. Furthermore, the number of available hydrogen-powered aircraft will at least in the beginning not be enough to serve all of the European air traffic demand. Hence, there is a need to plan which routes would be operable on a hydrogen basis. For this purpose, we set up a MILP deciding how to use the available hydrogen and hydrogen-powered aircraft best for the European aviation sector. This MILP consists of two parts, one handling the flow of passenger demand through the network via a multicommodity flow problem and one handling the hydrogen refueling, where it is possible that aircraft can be refueled for more than one flight-leg. The solution is a network showing which routes within Europe could be operated by hydrogen-powered aircraft and which ones conventionally.

Energy systems are complex networks consisting of various interconnected components. Accurate energy demand and supply forecasts are crucial for efficient system operation and decision-making. However, high-dimensional data, complex network structures, and dynamic changes and disruptions in energy networks pose significant challenges for forecasting models. To address this, we propose a hybrid approach for resilient forecasting of network time series (H-NTS) in the energy domain. Our approach combines mathematical optimization methods with state-of-the-art machine learning techniques to achieve accurate and robust forecasts for high-dimensional energy network time series. We incorporate an optimization framework to account for uncertainties and disruptive changes in the energy system. The effectiveness of the proposed approach is demonstrated through a case study of forecasting energy demand and supply in a complex, large-scale natural gas transmission network. The results show that the hybrid approach outperforms alternative prediction models in terms of accuracy and resilience to structural changes and disruptions, providing stable, multi-step ahead forecasts for different short to mid-term forecasting horizons.

Electric vehicles (EVs) are an essential lever for decarbonizing the transportation sector. However, many drivers remain reluctant to purchase an EV as they do not trust the public charging infrastructure, due to charging station congestion risks and unreliable charging station availability. This thesis contributes novel models and solution methods, that aim to reliably help EV drivers find a free public charging station in the presence of uncertainties. From a short-term user perspective, the objective is to provide reliable in-car guidance instructions that explicitly account for charging station availability uncertainty. In a single-agent setting, an algorithmic framework composed of a rollout and a labeling algorithm can save up to 44% of a driver’s search time. In a multi-agent setting, efficient driver coordination strategies through information-sharing and charging requests centralization can decrease the multi-agent search cost by up to 38%, compared to uncoordinated greedy searches. From a long-term perspective, the objective is to avoid public charging station utilization conflicts of drivers that get guidance instructions through self-interested navigation platforms. A mechanism design approach allows gearing the behavior of such platforms towards an outcome that benefits all EV drivers, by decreasing the total cost by up to 52% in an offline setting and by up to 42% in an online setting.

In the effort to reduce their CO2 footprint to fight global warming, airports might electrify the vehicles operating on the airport’s apron, e.g., passenger buses. It is conceivable to use dynamic inductive (wireless) charging to transfer energy to the vehicles and charge their batteries while they are moving on the apron. To this end, a system of underground inductive transmitter units (coils) has to be placed at strategically chosen segments of the apron road network. This leads to the question of how to allocate those inductive transmitter units, i.e., the coils, within the apron road network such that the required investment in the charging technology is minimized, while for a large set of conceivable vehicle service requests the required energy can be picked up on the way of handling this call. We report about an ongoing effort to solve this challenging problem via branch-and-price approaches, partially using the SCIP framework.

The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.

The energy supply chain is critical for meeting the increasing global energy demand. However, disruptions in the energy supply chain can have dramatic effects on various stakeholders, including manufacturers, consumers, and the environment. This study proposes a game-theoretic model integrating renewable and fossil fuel power plants to increase supply chain resilience. The manufacturer benefits from a renewable power plant as the main supplier and a fossil fuel power plant as backup. Two sourcing strategies are considered dependent based on disruption probability: (1) single sourcing from renewable power plant, and (2) dual sourcing from both renewable and fossil fuel power plants. Given the uncertain environment of the energy supply chain, a game theoretic approach provides the appropriate framework to analyze the strategic interactions between different players in a complex system, such as the interactions between the renewable and fossil fuel power plants and the manufacturer in this study. Based on the two sourcing options, we analyzed the strategic scope for different levels of collaboration between power plants, capturing interactions, ordering decisions, and pricing strategies. This study contributes to the literature, particularly in the areas of resilience and sustainability of the energy supply chain. By proposing a novel energy supply chain model that integrates renewable and fossil fuel power plants, considering different sourcing strategies and collaboration scenarios, and analyzing the decision-making process from a game-theoretic perspective, this study offers insights into how to overcome energy supply risk by supply chain design and collaboration.

The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.

We study a functional autoregressive model for high-frequency time series. We approach the estimation of the proposed model using a Mixed Integer Optimisation method. The proposed model captures serial dependence in the functional time series by including high-dimensional curves. We illustrate our methodology on large-scale natural gas network data. Our model provides more accurate day-ahead hourly out-of-sample forecast of the gas in and out-flows compared to alternative prediction models.

The importance and relevance of sustainability and climate neutrality is related to the transformation of energy, mobility and industry sectors. Decision-oriented, quantitative predictive or prescriptive methods (e.g., linear programming, multi-criteria decision support) are required to evaluate and design these complex systems. These are provided particularly by operations research. The relevance and need for these methods in the context of sustainable development is evidenced by many research projects, as well as the application of the operation research methods in the different industry sectors. That are also central topics in many study programs. The goal of the project “Operations Research (OR) for Sustainability: Energy, Mobility, Industry” founded by OERContent.nrw is to develop, implement and disseminate a digital, model- and application-oriented teaching/learning offer in the subject area of “Operations Research for Sustainable Development” using open source software. This project opens also new possibilities for students to learn how the real business problems can be solved with methods from finance and operations research applied to the energy domain. In the case study presented, the students are offered to learn the basics of mean-variance portfolio theory, the economics of selected power plants, and how to apply the theory to optimize power plant portfolios. In the context of real assets, the main challenge is to define the rate of return as a portfolio selection criterion and to simulate it in the modeling. The analysis is conducted in moodle learning platform by using the object-oriented programming language Python, which creates some specific challenges that are discussed in the case study as well.

This study examines the implications of considering additive manufacturing (AM) machines in scheduling approaches and evaluates the relationship to well-known scheduling problems on batch processing machines. To this end, we first analyze AM technologies and derive ways to model the processing time of production jobs. We examine the impact of integrating AM-specific processing time models into scheduling problems. For this purpose, we present a mixed-integer programming model aiming to minimize makespan on unrelated parallel AM machines. Based on our findings, we integrate different variants to calculate processing times for this model and demonstrate the different influences on the scheduling tasks. To evaluate the performance of the model variants and their impacts on resulting schedules, we explore various instance settings. The results of our study highlight the benefits of explicitly incorporating AM features in model formulations to substantially improve makespan in AM production facilities.

One of the most urgent challenges in Reinforcement Learning research is the lack of reproducibility. Therefore, to further the understanding of the training behavior of Reinforcement Learning agents, we analyze the training of agents playing the established baseline environment Taxi. In particular, we contrast results based on different forms of exploration. In addition, we can demonstrate that in this context penalization without termination is to be the preferred punishment for incorrect actions.

Hydrogen-based propulsion concepts for aircraft are considered a promising technology towards the decarbonization of aviation. While the development of respective aircraft models is in progress, questions regarding the supply network of green hydrogen are arising. We present a formulation of the hydrogen supply chain network (HSCN) design problem that focuses on the aviation sector. The mixed-integer linear programming model minimizes the total cost of hydrogen supply by deciding on locations, capacities, transportation modes and flows. The respective supply chain starts with the generation of renewable electricity used in the electrolysis of water. The gas hydrogen obtained from this process is liquefied before being used to refuel the aircraft. Moreover, various transportation and storage processes for gas and liquid hydrogen are involved between the electrolyzers and the airports. Our model formulation considers the spatially dispersed availability of renewable electricity, the techno-economic characteristics of hydrogen storage, liquefaction and transportation (e.g., economies of scale), as well as the specific requirements of hydrogen handling (e.g., losses). The application is illustrated for Germany in 2050, considering the hydrogen pipeline backbone projection. Optimal network design and results are presented.

We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.

Due to its speed and reliability, the air cargo industry is essential in supply chain logistics and is constantly growing. A cargo airline’s aircraft must always be available to the company’s network to be profitable. A lack of spare parts can cause aircraft to be grounded whenever an aircraft part fails, which makes spare parts management vital for the airline’s success. To contribute to this essential task, we present a mixed integer program to optimally distribute spare parts at the outstations of a German air transport company. The objective function is a cost-based minimization of aircraft on ground situations where aircraft cannot deploy as planned and the schedule disrupts. The model is based on six-monthly flight schedules and previous spare part demand information. We compare the results with the company’s spare part consumption in the second quarter of 2022. In addition, we include scenario analysis for outstation and home base parameters and limitations of the spare parts purchase quantity. We show that the generated solutions support logistic planners and can be used to reveal problems such as lack of spare parts and insufficient storage space.

Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible jobs-to-servers assignment having minimum overall power-on time. Although BTMP can be classified as a variant of temporal bin packing, it actually represents an independent branch of research since, for instance, the related solution sets are generally different. Typically, such computations (and generalizations of it) are very important in data center workload management to keep operational costs low. Hence, finding efficient solution techniques for BTMP is a relevant topic in discrete optimization, both from a theoretical and a practical point of view. In this work, we first give an overview of heuristic approaches for the problem under consideration. As a main contribution, a new best-cost based heuristic is presented as well as theoretically analyzed, and it is empirically shown to improve the quality of feasible solutions obtained for a set of challenging benchmark instances.

Prior to the FIFA World Cup Qatar 2022 $$^\textrm{TM}$$ TM , we conducted a survey regarding the use of different modes of transportation. This empirical research was performed to calibrate a passenger demand model to estimate the number of passengers at metro stations, considering a no-show rate and providing a basis for admission control. Decision theory and machine learning techniques were used to identify the key factors that influence transport choices. Interaction terms and binary variables from a decision tree created by the CART algorithm were included to capture non-linear effects. Maximum likelihood with a lasso penalty term was applied to estimate the high-dimensional utility function of the multinomial logit model, resulting in a sparse utility function. Our results illustrate that the use of a data-driven method can provide remarkably accurate predictions for transport mode choice analysis. This can be achieved without time-consuming and subjective preprocessing. Most importantly, no additional expert knowledge is required.

In recent years, European gas transport has been affected by major disruptive events like political issues such as, most recently, the Russian war on Ukraine. To incorporate the impacts of such events into decision-making during the energy transition, more complex models for gas network analysis are required. However, the limited availability of consistent data presents a significant obstacle in this endeavor. We use a mathematical-modeling-based scenario generator to deal with this obstacle. The scenario generator consists of capacitated network flow models representing the gas network at different aggregation levels. In this study, we present the coarse-to-fine approach utilized in this scenario generator.

Currently, some food products are produced in specific regions that must be distributed to other regions to fulfill the demand on time, highlighting the role of international trading, such as import and export. The distribution planning of these products introduced the global food supply chain (GFSC) problem that involves complex economic and agricultural constraints. In this paper, an integrated Linear Programming (LP) model is developed for the combined rice and wheat supply chain. The model aims to optimize the flow of rice and wheat within the trading partners for these products globally. The constraints are also imposed on production, exports, imports, storage, budget, and flow capacity. Depending on the current import trend, assumptions are made about the purchasing ability of the countries with a focus on imports, including their Gross Domestic Product (GDP). Thus, the paper also analyses the proposed GFSC from an economic point of view. A real-world case study is conducted to show the model’s applicability in most countries worldwide. The data were collected from different publicly available sources and prepared as input to the model. The developed LP model was solved using the CPLEX solver of GAMS software. The results are analyzed and compared to the current distribution scenario. The analyses uncover interesting insights into the global supply chain of rice and wheat and the potential of the countries in economic growth or decline.

Classification yards are important nodes in railroad networks, especially in the single wagonload transport system. The yard operations are complex due to a high number of involved resources and restrictive dependencies. Inbound train delays can cause railcar transitions to occur later than originally envisaged. Decisions on job sequencing and resource allocation have a major impact on reactionary outbound delays and thus on the quality of service in the network. Due to permanent updates of arrival times and resource availabilities, a constant rescheduling of operations is necessary. In some cases, it is useful to deviate from the standard treatment by replacing certain processes, parallelize activities or assigning additional personnel to reduce resulting delays of outbound trains. The paper addresses these options and their integration into a comprehensive scheduling approach. Therefore, a mixed integer program (MIP) considering train processing alternatives is presented together. It includes all necessary types of resources, i.e. personnel and locomotives together with their interdependencies and time constraints. The objective function minimizes the overall outbound delay. Afterwards, some practical scenarios adapted from the classification yard in Munich operated by DB Cargo AG are calculated with CPLEX. The results of the optimization approach are presented and evaluated regarding to the effects of the alternative train treatments. Finally, conclusions are derived for operating the model in real-time-environments of classification yards.

We consider a bi-objective covering problem which is a close relative to the set covering problem. It is encountered in an application concerning cost-efficient camera surveillance of a bio-fuel depot. The two objectives are to simultaneously minimize the cost of the solution and to maximize its coverage, measured as the number of fulfilled covering constraints. These objectives are clearly in conflict, and for large scale instances it is very challenging and practically unfeasible to calculate the Pareto frontier. We propose a matheuristic approach to the problem. It aims at finding a near Pareto frontier in practically feasible computation times, and works by gradually constructing this frontier from zero coverage to full coverage. We apply the matheuristic to real-life instances and analyse its performance with respect to frontier quality metrics.

We consider solving linear optimization (LO) problems with uncertain objective coefficients. For such problems, we often employ robust optimization (RO) approaches by introducing an uncertainty set for the unknown coefficients. Typical RO approaches require observations or prior knowledge of the unknown coefficient to define an appropriate uncertainty set. However, such information may not always be available in practice. In this study, we propose a novel uncertainty set for robust linear optimization (RLO) problems without prior knowledge of the unknown coefficients. Instead, we assume to have data of known constraint parameters and corresponding optimal solutions. Specifically, we derive an explicit form of the uncertainty set as a polytope by applying techniques of inverse optimization (IO). We prove that the RLO problem with the proposed uncertainty set can be equivalently reformulated as an LO problem. Numerical experiments show that the RO approach with the proposed uncertainty set outperforms classical IO in terms of performance stability.

Branch and bound algorithms have to cope with several additional difficulties in the multi-objective case. Not only the bounding procedure is considerably weaker, but also the handling of upper and lower bound sets requires much more computational effort since both sets can be of exponential size. Thus, the order in which the subproblems are considered is of particular importance. Thereby, it is crucial not only to find efficient solutions as soon as possible but also to find a set of (efficient) solutions whose images are well distributed along the non-dominated frontier. In this paper we evaluate the performance of multi-objective branch and bound algorithms depending on branching and queuing of subproblems. We use, e.g., the hypervolume indicator as a measure for the gap between lower and upper bound set to implement a multi-objective best-first strategy. We test our approaches on multi-objective knapsack and generalized assignment problems.

Insertion heuristics are approximation algorithms that are widely used in practice to solve the traveling salesperson problem (TSP) which is arguably among the most prominent problems in combinatorial optimization. In this paper, we analyze well-known variants of insertion heuristics restricted to instances with edge weights in $$\{1,2\}$$ { 1 , 2 } , deriving the exact approximation ratio of 7/4 for multiple variants. These ratios yield the first tight bounds known for arbitrary insertion heuristic and the farthest insertion heuristic for any class on which TSP is NP-complete.

Particle Swarm Optimization (PSO) is widely acknowledged as one of the most effective swarm intelligence approaches in the field of metaheuristics. This paper introduces an adaptive variant of PSO that leverages fitness landscape information, specifically computing the ruggedness factor. The proposed method aims to identify the optimal PSO strategy by adopting an adaptive rule to update PSO parameters based on the ruggedness factor. The effectiveness of this approach is demonstrated through its evaluation on the feature selection problem, showcasing promising outcomes.

This work summarizes the results of my Ph.D. thesis on ordinal costs in combinatorial optimization. Ordinal costs model the quality of objects whenever numerical values are not appropriate or available. As an example the safety of a street for a cyclist can be ranked in ordered categories, like, e.g., safe (bike lane), medium safe (slow traffic) and unsafe (main road). Other examples for ordinal costs relate to quality, sustainability and rankings of, e.g., olympic medals. We consider ordinal costs for general combinatorial optimization problems and analyze the interrelation between ordinal optimization and multi-objective optimization. Moreover, in the thesis for the specific case of matroid optimization problems very efficient solution algorithms are suggested. In this paper the ideas of the solution methods and the main theoretical results are summarized.

The continued development of evaluation functions for use in chess and shogi engines resulted in the development of Efficiently Updatable Neural Networks in 2018 by Yu Nasu. These utilise the full potential of modern processors foregoing the need for specialised hardware and thus decreasing cost and energy consumption. There are three central optimisations, leveraging the sparsity and redundancy in the encoding, lowering the bit width and pivoting all calculations to integers, and lastly using advanced vectorisation with single instruction multiple data registers. These optimisations are evaluated for their contribution to Efficiently Updatable Neural Networks and how they could impact efficiency and speed in different environments. Finally, the optimisations are implemented in Python and C++ to test their real-world benefits.

The concept of demand-responsive transport is seen as a promising solution for the necessary changes in the mobility sector in the context of sustainable urban transport. In this work, a model for the Dial-a-Ride problem with public transport integration is presented. The model aims to minimise the sum of waiting times for all passengers, focusing on suburban stations with realistic route data. The model is optimally solvable for small instances, but a heuristic approach based on simulated annealing is proposed for larger instances. The research results suggest that the model is well suited to address the problem discussed and the heuristic approach provides reliable results in a reasonable computational time and is therefore suitable for practical applications.

Chebyshev center-based column generation, CCG, is a gently stabilized variant of classical column generation, CG, that relies on dual information provided by central interior points to identify new improving columns [3]. From a dual perspective, the basic algorithm corresponds to the well-known Chebyshev center cutting plane method, which draws on weak dual bounds and converges still rather slow in practice [1, 3]. We present deep Chebyshev center-based column generation, DCCG, a sophistication operating on stronger bounds and employing deeper cuts. Besides giving first numerical evidence of its superiority over both classical and state-of-the-art Chebyshev center-based column generation, we provide interesting analytical insights that lay the foundation for further improvements in the realm of column generation and beyond.

There is a long tradition of assigning students to courses taking into account various objective functions, e.g., maximizing lecturer and student preferences and/or balanced workload within departments, as well as constraints, e.g., such as capacity, minimum workload, and/or degree progress. Theoretical approaches here often provide efficient algorithms that can be useful in academic decision making. In this paper, we discuss the main findings on seminar assignment problems at the FernUniversität in Hagen, Germany, considering lower bounds related to ratios. The incorporation of such bounds is important when, for example, chairs try to meet preference quotas with respect to certain categories of students. However, the inclusion of such bounds undermines the total unimodularity of the multicriteria seminar assignment problem. In this paper, we show that the property of total unimodularity can be preserved without affecting the structure of the generic problem. We then use this structure to quickly find an optimal solution. Our findings are complemented by preliminary numerical results.

In mass casualty incidents, following natural or man-made disasters or incidents, often a high number of victims must be cared for by only a limited number of first responders. As time is crucial in order to increase survival probabilities for the victims, technology advances like drones equipped with cameras and sensors could help detect and triage victims. Then, first responders arriving at the scene could immediately start treatment. In this work, we propose an agent-based simulation model and analyse the expected potential of using drones in addition to first responders. The results show that the use of drones can be especially beneficial for severely injured patients.

To assess the quality of mobility systems, inconveniences associated with using different modes of transport can be quantified by incorporating travel time equivalents into the actual travel time. This combined value is referred to as travel resistance. Examples of these inconveniences include changing between trains, waiting times, walking distances to stations, and searching for parking spaces when using motorized private transport. This contribution adapts widely recognized shortest path algorithms, such as the Dijkstra or the A* search algorithm to determine the path with the least travel resistance for various modes of transportation.

In the early 2000s, AIS (Automatic Information System) became mandatory for almost all seagoing vessels, which must broadcast the ship’s tracking and navigational information for collision avoidance and maritime safety. Maritime surveillance agencies can use AIS data for the classification of vessels, e.g., for the detection of spoofing behavior in fishery scenarios. This contribution looks at detecting Fishery type behavior by Random Forests based on aggregated AIS messages. It addresses the question of how much classification performance, measured by accuracy and Cohen’s kappa, depends on the geographical features in training datasets of AIS data rather than on general fishery vessels’ properties. For this purpose, Random Forests are trained on aggregated real-life AIS data for fishery detection in different maritime areas and are then group-cross-validated against each other.

The most critical problem of viability theory is determining the initial states of a dynamical system for which at least one solution remains in the same set. This problem is analogous to many real situations, particularly management problems modelled as high-dimensional dynamic systems. However, the high dimensionality hampers the practical utility of the theory. The existing literature reports difficulties with models of more than four dimensions. Therefore, we investigate the current algorithms and study a calculation formula for high-dimensional linear and convex problems. We found a formula for viable sets in case of backward invariance of the environment set. Finally, since many dynamical systems are neither convex nor linear, extending our work to such systems is the immediate challenge.

Shared mobility systems like car sharing and bike sharing allow for individual urban mobility without the need to own a vehicle. Despite the rapid growth of these systems in recent years, providers still often fail to operate them profitably, mainly because of low fleet utilization which stems from dynamic imbalances between supply and demand. In this context, the author’s dissertation “Demand Management in Shared Mobility Systems” [7] proposes an alternative to the traditional supply-sided approach to counter these imbalances. That is, instead of actively relocating vehicles, the developed demand management approaches comprise pricing and availability control at both the tactical and operational decision making levels. This article summarizes parts of the author’s cumulative dissertation, focusing on contributions that have resulted in journal publications to date. In the course of the OR conference 2023 in Hamburg, the author was awarded with the dissertation award of the German Operations Research Society (GOR).