Operations Research Proceedings 2019

Cities and municipalities are critical for the success of the energy transition and hence often pursue their own sustainability goals. However, there is a lack of the required know-how to identify suitable combinations of measures to achieve these goals.The RE3ASON model allows automated analyses, e.g. to determine the energy demands as well as the renewable energy potentials in an arbitrary region. In the subsequent optimization of the respective energy system, various objectives can be pursued—e.g. minimization of discounted system expenditures and emission reduction targets. The implementation of the model employs various methods from the fields of geoinformatics, economics, machine learning and mixed-integer linear optimization.The model is applied to derive energy concepts within a small municipality. By using stakeholder preferences and multi-criteria decision analysis, it is shown that the transformation of the urban energy system to use local and sustainable energy can be the preferred alternative from the point of view of community representatives.

In the era of e-commerce and just-in-time production, an efficient supply of goods is more than ever a fundamental requirement for any supply chain. In this context, this paper summarizes the author’s dissertation about optimization in outbound logistics, which received the dissertation award of the German Operations Research Society (GOR) in the course of the OR conference 2019 in Dresden. The structure of the thesis is introduced, the investigated optimization problems are described, and the main findings are highlighted.

The article summarizes the findings of my Ph.D. thesis finished in 2018; see (Sirvent, Incorporating differential equations into mixed-integer programming for gas transport optimization. FAU University Press, Erlangen, 2018). For this report, we specifically focus on one of the three new global decomposition algorithms, which is used to solve stationary gas transport optimization problems with ordinary differential equations. Moreover, we refer to the promising numerical results for the Greek natural gas transport network.

In this paper we investigate the problem to schedule a proportionate flow shop of batching machines (PFB). We consider exact and approximate algorithms for tackling different variants of the problem. Our research is motivated by planning the production process for individualized medicine. Among other results we present the first polynomial time algorithm to schedule a PFB for any fixed number of machines. We also study the online case where each job is unknown until its release date. We show that a simple scheduling rule is two-competitive. For the special case of two machines we propose an algorithm that achieves the best possible competitive ratio, namely the golden section.

To counteract the constantly increasing CO2 emissions, especially in local public transport, more environmentally friendly electric buses are intended to gradually replace buses with combustion engines. However, their current short range makes charging infrastructure planning indispensable. For a cost-minimal allocation of electric vehicles to service trips, the consideration of vehicle scheduling is also crucial. This paper addresses the modeling and implementation of a simultaneous solution method for vehicle scheduling and charging infrastructure planning for electric buses. The Savings algorithm is used to construct an initial solution, while the Variable Neighborhood Search serves as an improvement heuristic. The focus is on a comparison between partial and complete charging processes of the vehicle battery within the solution method. An evaluation based on real test instances shows that the procedure implemented leads to large cost savings. Oftentimes, the consideration of partial charging processes is superior to the exclusive use of complete charging processes.

We propose a data-driven integrated production and maintenance planning model, where machine breakdowns are subject to uncertainty and major sequence-dependent setup times occur. We address the uncertainty of breakdowns by considering various covariates and the combinatorial problem of sequence-dependent setup times with an asymmetric Traveling Salesman Problem (TSP) approach. The combination of the TSP with machine learning optimizes the production planning, minimizing the non-value creating time in production and thus, overall costs. A data-driven approach integrates prediction and optimization for the maintenance timing, which learns the influence of covariates cost-optimal via a mixed integer linear programming model. We compare this approach with a sequential approach, where an algorithm predicts the moment of machine failure. An extensive numerical study presents performance guarantees, the value of data incorporated into decision models, the differences between predictive and prescriptive approaches and validates the applicability in practice with a runtime analysis. We show the model contributes to cost savings of on average 30% compared to approaches not incorporating covariates and 18% compared to sequential approaches. Additionally, we present regularization of our prescriptive approach, which selects the important features, yielding lower cost in 80% of the instances.

Tensor extrapolation attempts to integrate temporal link prediction and time series analysis using multi-linear algebra. It proceeds as follows. Multi-way data are arranged in the form of tensors, i.e., multi-dimensional arrays. Tensor decompositions are then used to retrieve periodic patterns in the data. Afterwards, these patterns serve as input for time series methods. However, previous approaches to tensor extrapolation are limited to special cases and typical applications of link prediction.The paper at hand connects state-of-the-art tensor decompositions with a general class of state-space time series models. In doing so, it offers a useful framework to summarize existing literature and provide various extensions to it. Moreover, it overcomes the boundaries of classical link prediction and examines the application requirements in traditional fields of time series analysis. A numerical experiment demonstrates the superiority of the proposed method over univariate extrapolation approaches in terms of forecast accuracy.

Stock cutting is an important optimisation problem which can be found in many industries. The aim of the problem is to minimize the cutting waste, while cutting standard-sized pieces from sheets or rolls of a given material. We consider an application of this problem arising from the packing industry, where the problem is extended from the standard one or two dimensional definition into the three dimensional problem. The purpose of this work is to help businesses determine the sizes of boxes to purchase so as to minimize the volume of empty space of their packages. Given the size of a real-world problem instances, we present an effective Adaptive Large Neighbourhood Search heuristic that is able to decrease the volume of empty space by an average of 22% compared to the previous approach used by the business.

Conventional strategies for microgrid control are based on low level controllers in the individual components. They do not reflect the nonlinear behavior of a coupled system, which can lead to instabilities of the whole system. Nonlinear model predictive control (NMPC) can overcome this problem but the standard methods are too slow to guarantee sufficiently fast feedback rates. We apply Multi-Level Iterations to reduce the computational expenses to make NMPC real-time feasible for the efficient feedback control of microgrids.

Multi-modal chromatography emerged as a powerful tool for the separation of proteins in the production of biopharmaceuticals. In order to maximally benefit from this technology it is necessary to set up an optimal process control strategy. To this end, we present a mechanistic model with a recent kinetic adsorption isotherm that takes process controls such as pH and buffer salt concentration into account. Maximizing the yield of a target component subject to purity requirements leads to a mixed-integer nonlinear optimal control problem constrained by a partial differential equation. Computational experiments indicate that a good separation in a two-component system can be achieved.

The switching times optimization problem for switched dynamical systems, with fixed initial state, is considered. A nonnegative cost term for changing dynamics is introduced to induce a sparse switching structure, that is, to reduce the number of switches. To deal with such problems, an inexact Newton-type arc search proximal method, based on a parametric local quadratic model of the cost function, is proposed. Numerical investigations and comparisons on a small-scale benchmark problem are presented and discussed.

First steps toward a novel deterministic algorithm for finding a minimum among all local minima of a nonconvex objective over a given domain are discussed. Nonsmooth convex relaxations of the objective and of its gradient are optimized in the context of a global branch and bound method. While preliminary numerical results look promising further effort is required to fully integrate the method into a robust and computationally efficient software solution.

In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.

We present a feasible direction approach to general linear programming, which can be embedded in the simplex method although it works with non-edge feasible directions. The feasible direction used is the steepest in the space of all variables, or an approximation thereof. Given a basic feasible solution, the problem of finding a (near-)steepest feasible direction is stated as a strictly convex quadratic program in the space of the non-basic variables and with only non-negativity restrictions. The direction found is converted into an auxiliary non-basic column, known as an external column. Our feasible direction approach allows several computational strategies. First, one may choose how frequently external columns are created. Secondly, one may choose how accurately the direction-finding quadratic problem is solved. Thirdly, near-steepest directions can be obtained from low-dimensional restrictions of the direction-finding quadratic program or by the use of approximate algorithms for this program.

The efficient numerical treatment of convex quadratic mixed-integer optimization poses a challenging problem. Therefore, we introduce a method based on the duality principle for convex problems to derive suitable lower bounds that can used to select the next node to be solved within the branch-and-bound tree. Numerical results indicate that the new bounds allow the tree search to be evaluated quite efficiently compared to benchmark solvers.

A biobjective extension of the maximum flow network interdiction problem is considered: Two maximum flows from source to sink are to be computed independently from each other while an interdictor aims to reduce the value of both maximum flows simultaneously by interdicting arcs. We show that this problem is intractable and propose two procedures to solve this problem on specific graph classes.

In this paper we present an approach to assess energy and emission reduction measures in container terminals. A modified PROMETHEE V approach is used to select suitable portfolios of these measures based on the decision makers preferences and further inter-dependencies.

The selection of projects for realization or co-financing is a complex process, often strategic in nature, which involves confronting trade-offs between multiple, frequently conflicting, factors. In this process the expectations of various stakeholders should be taken into account, while simultaneously ensuring the achievement of numerous objectives. This work presents and compares the application of two approaches—multi-criteria decision aiding (MCDA) methods for mixed evaluations (deterministic and stochastic ones, thus with stochastic dominance (SD) rules), e.g. BIPOLAR MIX, and multi-actor multi-criteria analysis (MAMCA)—to help decision-makers (DMs) in the project selection process. The problem is illustrated by ranking environmental infrastructure projects.

The energy consumption of large-scale data centers or server clusters is expected to grow significantly in the next couple of years contributing to up to 13% of the worldwide energy demand in 2030. As the involved processing units require a disproportional amount of energy when they are idle, underutilized or overloaded, balancing the supply of and the demand for computing resources is a key issue to obtain energy-efficient server consolidations. Whereas traditional concepts mostly consider deterministic predictions of the future workloads or only aim at finding approximate solutions, here we propose an exact bin packing based approach to tackle the problem of assigning jobs with (not necessarily independent) stochastic characteristics to a minimal amount of servers subject to further practical constraints. Finally, this new approach is tested against real-world instances obtained from a Google data center.

Degree programs with a largely fixed timetable require centralized planning of student groups (sections). Typically, group sizes for exercises and practicals are small, and different groups are taught at the same time. To avoid late or weekend sessions, exercises and practicals of the same or of different subjects can be scheduled concurrently, and the duration of lessons can vary. By means of an integer linear program, an optimal group division is carried out. To this end, groups have to be assigned to time slots and students have to be divided into groups such that they do not have conflicting appointments. The optimization goal is to create homogeneous group sizes.

Set covering problems are well-studied and have many applications. Sometimes the duality gap is significant and the problem is computationally challenging. We dissect the duality gap with the purpose of better understanding its relationship to problem characteristics, such as problem shape and density. The means for doing this is a set of global optimality conditions for discrete optimization problems. These decompose the duality gap into two terms: near-optimality in a Lagrangian relaxation and near-complementarity in the relaxed constraints. We analyse these terms for numerous instances of large size, including some real-life instances. We conclude that when the duality gap is large, typically the near-complementarity term is large and the near-optimality term is small. The large violation of complementarity is due to extensive over-coverage. Our observations should have implications for the design of solution methods, and especially for the design of core problems.

Many design/layout processes of warehouses, depots or parking lots are subject to reachability constraints, i.e., each individual storage/parking space must be directly reachable without moving any other item/car. Since every storage/parking space must be adjacent to a corridor/street one can alternatively consider this type of layout problem as a network design problem of the corridors/streets.More specifically, we consider the problem of placing quadratic parking spaces on a rectangular shaped parking lot such that each of it is connected to the exit by a street. We investigate the optimal design of parking lot as a combinatorial puzzle, which has—as it turns out—many relations to classical combinatorial optimization problems.

We present and share the experience of modeling a real-life optimization problem. This exercise in modeling is a text book example of how a naive, straightforward mixed-integer modeling approach leads to a highly intractable model, while a deeper problem analysis leads to a non-standard, much stronger model. Our development process went from a weak model with burdensome run times, via meta-heuristics and column generation, to end up with a strong model which solves the problem within seconds. The problem in question deals with the challenges of planning the order-driven continuous casting production at the Swedish steel producer SSAB. We study the cast planning problem, where the objective is to minimize production waste which unavoidably occurs as orders of different steel grades are cast in sequence. This application can be categorised as a rich bin packing problem.

With the expansion of mobile devices and new trends in mobile communication technologies, there is an increasing demand for diversified services. Thus, it becomes crucial for a service provider to optimize resource allocation decisions to satisfy the service requirements. In this paper, we propose a stochastic programming model to determine server placement and service deployment decisions given a budget restriction when certain service parameters are random. Our computational tests show that the Sample Average Approximation method can effectively find good solutions for different network topologies.

We consider a variant of the job shop scheduling problem, which considers different operational states of the machines (such as off, ramp up, setup, processing, standby and ramp down) and time-dependent energy prices and aims at minimizing the energy consumption of the machines. We propose an integer programming formulation that uses binary variables to explicitly describe the non-operational periods of the machines and present a branch-and-price approach for its solution. Our computational experiments show that this approach outperforms the natural time-indexed formulation.

In this work we analyze the multiple Traveling Salesperson Problem (mTSP) on regular grids. While the general mTSP is known to be NP-hard, the special structure of regular grids can be exploited to explicitly determine optimal solutions in linear time.Our research is motivated by several real-world applications, for example delivering goods with swarms of unmanned aerial vehicles (UAV) or search and rescue operations. In order to obtain regular grid structures, we divide large search areas in several equal-sized squares, where we choose the square size as large as the sensor range of a UAV.First, we use an Integer Linear Program (ILP) to formally describe our considered mTSP variant on regular grids that aims to minimize the total tour length of all salespersons, which corresponds to minimizing the average search time for a missing person.With the help of combinatorial counting arguments and the establishment of explicit construction schemes, we are able to determine optimal mTSP solutions for specific grid sizes with two salespersons, where the depot is located in one of the four corners.

In this work, we introduce and analyze an extension of the Linear Ordering Problem ( LOP) . The LOP aims to find a simultaneous permutation of rows and columns of a given weight matrix such that the sum of the weights in the upper triangle is maximized. We propose the weighted Linear Ordering Problem ( wLOP) that additionally considers individual node weights.First, we argue that in several applications of the LOP the optimal ordering obtained by the wLOP is a worthwhile alternative to the optimal solution of the LOP. Additionally, we show that the wLOP constitutes a generalization of the well-known Single Row Facility Layout Problem.We introduce an Integer Linear Programming formulation as well as a Variable Neighborhood Search for solving the wLOP. Finally, we provide a benchmark library and examine the efficiency of our exact and heuristic approaches on the proposed instances in a computational study.

The Hamiltonian cycle problem (HCP) consists of finding a cycle of length N in an N-vertices graph. In this investigation, a graph G is considered with an associated set of matrices, in which each cell in the matrix corresponds to the weight of an arc. Thus, a multi-objective variant of the HCP is addressed and a Pareto set of solutions that minimizes the weights of the arcs for each objective is computed. To solve the HCP problem, the Branch-and-Fix algorithm is employed, a specific branching algorithm that uses the embedding of the problem in a particular stochastic process. To address the multi-objective HCP, the Branch-and-Fix algorithm is extended by computing different Hamiltonian cycles and fathoming the branches of the tree at earlier stages. The introduced anytime algorithm can produce a valid solution at any time of the execution, improving the quality of the Pareto Set as time increases.

In Brazil, reverse auctions are the main mechanism for contracting generation and transmission assets. However, mismatches between their start-up dates have depleted supply on approximately 17,000 GWh. So, we propose a new Combinatorial Reverse Auction format, that jointly auctions’ transmission and generation assets. The conceptual proposal was divided into two phases: descending clock rounds and sealed bid round. Activity rules as eligibility points and preference revealed were implemented to restrict the packages allowed for bidding in each round. The Winner Determination Problem was modeled as an Integer Linear Program adjusted to the Brazilian electric market. Computational experiments will be developed based on real data.

We consider the capacity and operations planning of a European energy supply system with a high share of renewable energy. Our model includes the energy sectors electricity, heat, and transportation and it considers numerous types of consumers and power generation, storage, and transformation technologies, which participate in these energy sectors. Given time series for the regional demands in each sector and the potential renewable production, the goal is to simultaneously optimize the strategic dimensioning and the hourly operation of all components in the system such that the overall costs are minimized.In this paper, we propose a Lagrangian solution approach that decomposes the model into many independent unit-commitment-type problems by relaxing several coupling constrains. This allows us to compute high quality lower bounds quickly and, in combination with some problem tailored heuristics, globally valid solutions with less computational effort.

Electricity is now traded in various ways in the market. Planning is necessary to buy or sell electricity in the market, because the fluctuations in the market price may incur significant costs. Regardless of the irregularities in power generation due to plant failures or inspections, or inconsistent weather conditions, the electricity demand of the market must be delivered. Therefore, it is necessary to have an operational plan that takes into account the uncertainty of the market price. Such uncertainty problems are usually solved by using the expected value minimization model. However, this model is risk-neutral, and does not consider fluctuations in the costs of different constituents. Accordingly, we propose a conditional value at risk minimization model that avoids the risk of fluctuating costs. In this study, we formulate a stochastic programming model for the operational plan (considering uncertainty), for factories. Further, we show the effectiveness of the proposed model by comparing it with the expected value minimization model.

In this contribution the planning and optimization of a mixed electric and diesel bus fleet for a municipal transportation company is presented. The goal and objective is to maximize the driven electric mileage without expanding the total number of buses in the fleet. Boundary conditions are driving schedules and timetable planning must be hold. Moreover, buses are to be charged exclusively in the depot. No opportunity charging outside the depot is allowed due to costs of additional installations. Based on an existing timetable, cycles are identified which can be driven with a parametrizable battery capacity. Furthermore, climatic conditions and weight of batteries, which are incorporated into the specific energy requirement per kilometer, are modeled.

Large scale energy storage installations have seen a rise in recent years, especially in combination with renewable power plants. Their increasing integration is contingent on successful market participation. So far, a common objective in energy resource scheduling is the maximization of profit from market participation, which requires high storage utilization and, consequently, leads to their degradation. This contribution presents a multi-objective mixed-integer program for operational planning of solar-storage plants that maximizes profit and minimizes the number of charge cycles. In a case study, solar-storage plants are studied in a short-term market environment. Pareto optimal solutions are determined using the epsilon constraint method. Analysis of the pareto-front shows that even minor sacrifices in profit allow to significantly reduce the number of charge cycles and therefore increase the lifetime of the battery.

Management of energy systems is one of the biggest challenges of our time. The daily demand for energy increases constantly for many reasons. Moreover, the wide use of renewable energies, aimed at limiting polluting emissions, can create instability in the networks and uncertainty in energy production. In this context, Operational Research is a crucial tool that allows optimizing strategic, tactical, and operational decisions to be taken. We focus on a strategic problem in smart grids, the phasor measurement units placement. The aim is to make the grid observable, i.e., to install devices that can communicate the status of the grid. Being able to observe it allows the grid manager to improve efficiency. We introduce and compare several mathematical optimization formulations proposed in the literature.

The imminent end-of-funding for an enormous number of wind energy turbines in Germany until 2025 is confronting affected operators with the challenge of deciding whether to further extend the lifetime of old turbines or to repower and replace it with new and more efficient ones. By means of a real options approach, we combine two methods to address the question if extending the operational life of a turbine is economically viable, and if so, for how long until it is replaced by a new turbine. It may even be the case that repowering before leaving the renewable energy funding regime is more viable. The first method, which is the net present repowering value, determines whether replacing a turbine before the end of its useful life is financially worthwhile. The second method, which follows a real options approach, determines the optimal time to invest in the irreversible investment (i.e., replacing the turbine) under uncertainty. The combination allows for continuously evaluating the two options of lifetime extension and repowering in order to choose the most profitable end-of-funding strategy and timing. We finally demonstrate the relevance of our approach by applying it to an onshore wind farm in a case study.

Russia’s transition to a market economy was accompanied by several monetary regime changes of the Bank of Russia (BoR) and even different policy goals. In this context we should mention the transformation of the exchange rate regime from managed floating to free floating (since November 2014) and several changes of the monetary regimes (exchange rate targeting, monetary targeting, and inflation targeting). As a measurement of changes in Russian monetary policy in 2008–2018 we develop a Monetary policy index (MPI). We focus on key monetary policy instruments: interest rates (key rate, liquidity standing facilities and standing deposit facilities rates), amount of REPO operations, BoR foreign exchange operations and required reserve ratio on credit institutions` liabilities. Our investigation provides a practical contribution to the discussion of Russian monetary regimes by creating a new MPI adopted to the conditions in Russia and enlarges the discussion of appropriate monetary policy regimes in transition and emerging countries.

In this contribution, we deal with an emergency service system design, in which the average disutility is minimized. Optimization of the average user disutility is related to the large weighted p-median problem. The necessity to solve large instances of the problem has led to the development of many heuristic and approximate approaches. Due to complexity of the integer programming problems, the exact methods are often abandoned for their unpredictable computational time in the case, when a large instance of a location problem has to be solved. For practical use, various kinds of metaheuristics and heuristics are used to obtain a good solution. We focus on usage of uniform deployment of p-median solutions in heuristic tools for emergency service system design. We make use of the fact that the uniformly deployed set of solutions represents a partial mapping of the “terrain” and enables to determine areas of great interest. We study here the synergy of the uniformly deployed set and heuristics based on neighborhood search, where the solution neighborhood is set of all p-median solutions, Hamming distance of which from the current solution is 2.

The uniform deployment has emerged from the need to inspect the enormously large set of feasible solutions of an optimization problem and due to inability of the exact methods to terminate the computation in an acceptable time. The objective function values of the solutions of the uniformly deployed set enable to determine areas of great interest. The uniformly deployed set can also represent population with maximal diversity for evolutionary metaheuristics. The paper deals with a notion of uniformity based on minimal Hamming distance between each pair of solutions. The set of selected solutions is considered to be uniformly deployed if the minimal Hamming distance across the set of all pairs of selected solutions is greater than or equal to a given threshold and if there is no possibility to add any other solution to the set. The paper contains a way of suggesting an initial uniformly deployed set of solutions and an iterative approach to the set enlargement.

In the Equal Maximum Flow Problem (EMFP), we aim for a maximum flow where we require the same flow value on all arcs in some given subsets of the arc set. We study the related Almost Equal Maximum Flow Problems (AEMFP) where the flow values on arcs of one homologous arc set differ at most by the valuation of a so called homologous function Δ. We prove that the integer AEMFP is in general N P $$\mathcal {N}\mathcal {P}$$ -complete, and that even finding a fractional maximum flow in the case of convex homologous functions is also N P $$\mathcal {N}\mathcal {P}$$ -complete. This is in contrast to the EMFP, which is polynomial time solvable in the fractional case. We also provide inapproximability results for the integral AEMFP. For the integer AEMFP we state a polynomial algorithm for the constant deviation and concave case for a fixed number of homologous sets.

The Steiner path problem is a restriction of the well known Steiner tree problem such that the required terminal vertices lie on a path of minimum cost. While a Steiner tree always exists within connected graphs, it is not always possible to find a Steiner path. Despite this, one can ask for the Steiner path cover, i.e. a set of vertex disjoint simple paths which contains all terminal vertices and possibly some of the non-terminal vertices. We show how a Steiner path cover of minimum cardinality for the disjoint union and join composition of two graphs can be computed in linear time from the corresponding values of the involved graphs. The cost of an optimal Steiner path cover is the minimum number of Steiner vertices in a Steiner path cover of minimum cardinality. We compute recursively in linear time the cost within a Steiner path cover for the disjoint union and join composition of two graphs by the costs of the involved graphs. This leads us to a linear time computation of an optimal Steiner path, if it exists, for special co-graphs.

The subset sum problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two extensions of this problem: The subset sum problem with digraph constraint (SSG) and subset sum problem with weak digraph constraint (SSGW). In both problems there is given a digraph with sizes assigned to the vertices. Within SSG we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if at least one of its predecessors is part of the solution. Within SSGW we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if all its predecessors are part of the solution. SSG and SSGW have been introduced by Gourvès et al. who studied their complexity for directed acyclic graphs and oriented trees. We show that both problems are NP-hard even on oriented co-graphs and minimal series-parallel digraphs. Further, we provide pseudo-polynomial solutions for SSG and SSGW with digraph constraints given by directed co-graphs and series-parallel digraphs.

A rapid response to emergencies is particularly important. When an emergency call arrives at a site that is currently busy, the call is forwarded to a different site. Thus, the busy fraction of each site depends not only on the assigned area but also on the interactions with other sites. Typically, the frequency of emergency calls differs throughout the city area. The assumption made by existing standard models for ambulance location of an average server busy fraction may over- or underestimate the actual coverage. Thus, we introduce a new mixed-integer linear programming formulation with an upper bound for the busy fraction of each site to explicitly model site interdependencies. We apply our mathematical model to a realistic case of a local EMS provider and evaluate the optimal results provided by the model using a discrete event simulation. The performance of the emergency network is improved compared to existing standard ambulance location models.

Health Care Delivery is the process in charge of providing a certain health service addressing different questions (equity, rising cost, ...) in such a way to find a balance between service quality for patients and efficiency for health care providers. The intrinsic uncertainty and the dynamic nature of the processes in health care delivery are among the most challenging issues to deal with. This paper illustrates how online optimization could be a suitable methodology to address such challenges.

In this article, a generalized model in the context of logistics optimization for renewable energy from biomass is presented and analyzed. It leads us to the conclusion that demand-driven location planning approaches have to be expanded by a supply-driven one.

This article describes a dispatching approach for Automated Guided Vehicles with a capacity of greater than one load (referred as Multiple Load Automated Guided Vehicles). The approach is based on modelling the dispatching task as a Dial-a-Ride Problem. An Adaptive Large Neighborhood Search heuristic was employed to find solutions for small vehicle fleets online. To investigate the performance of this heuristic the generated solutions are compared to results of an exact solution method and well established rule-based dispatching policies. The comparison is based on test instances of a use case in semiconductor industry.

Several alternatives to home delivery have recently appeared to give customers greater choice on where to securely pickup goods. Among them, the click-and-collect option has risen through the development of locker points for unattended goods pickup. Hence, transportation requests consist of picking up goods from a specific location and dropping them to one of the selected delivery locations. Also, transfer points allow the exchange of goods between heterogeneous vehicles. In this regard, we propose a novel three-index mixed-integer programming formulation of this problem. Experiments are performed on various instances to estimate the benefits of taking into account several transfer points and alternative delivery points instead of the traditional home delivery.

There is a strong political focus on moving cargo transportation from trucks to ships to reduce environmental emissions and road congestion. We study how the introduction of a future generation of autonomous ships can be utilized in maritime transportation systems to become more cost-efficient, and as such contribute in the shift from land to sea. Specifically, we consider a case study for a Norwegian shipping company and solve a combined liner shipping network design and fleet size and mix problem to analyze the economic impact of introducing autonomous ships. The computational study carried out on a problem with 13 ports shows that a cost reduction up to 13% could be obtained compared to a similar network with conventional ships.

The problem solving competition organized by the Railway Application Section of the Institute of Operations Research and Management Sciences (INFORMS) in 2017 was to predict the values of load exerted by wheels on the track, when a currently empty rail car would be loaded in the next trip. The organizers provided Wheel Impact Load Detector (WILD) data i.e. value of peak force along with other input variables such as train number, car number, axle side, wheel age, loaded or empty status etc.In this work, the original prediction problem is converted into a classification problem on the basis of peak force values in order to detect defects in railroad wheels. Peak force values greater than or equal to threshold value (≥ 90 Kilo Pound Force (kips)) define one class, while its values less than threshold value (< 90 kips) define its complement. Given data set is highly imbalanced as about 99.23% of the peak force values fall below threshold values and the remaining 0.76% peak force values fall into its complement. The statistical methodologies that have been attempted to come up with a classification rule include (1) Zero-Inflated Binomial (ZIB) regression model, (2) ZIB regression with L 1 norm regularization model, and (3) ZIB regression with L 2 norm regularization model. Out of these three methods, ZIB regression with L 2 norm model yielded satisfactory results with False Positive Rate reduced to 13.06% and False Negative Rate to 07.75% with accuracy of 87%.

The Courier, Express and Parcel industry is facing great challenges due to constantly growing parcel volumes combined with increasing customer expectations. A concept to overcome these challenges bases on delivery robots. These robots have a unit capacity and are capable of transporting small goods autonomously on sidewalks. One field of application is the last mile of parcel delivery, where a small fleet of robots could deliver time-critical parcels over small distances. Compared to traditional trucking personnel costs can be saved and due to their autonomy, the robots can operate all day long. In this study, we model the arising optimization problem of scheduling robots and customers. Moreover, we compare two different assignment approaches between robots and micro-depots and evaluate the concept based on test instances.

This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018.

In this paper a class of robust two-stage combinatorial optimization problems with uncertain costs is discussed. It is assumed that the uncertainty is modeled by using a convex uncertainty set, for example of polyhedral or ellipsoidal shape. Several methods to compute exact and approximate solutions are introduced. Experimental results for robust two-stage version of the weighted set cover problem are presented.

The paper deals with a version of the capacitated single-item lot sizing problem with backordering under uncertainty. The interval representation of uncertain cumulative demands is considered. Two its variants: the discrete budgeted uncertainty and the continuous budgeted uncertainty, are examined. In order to choose a robust production plan, for the problem under consideration, that hedges against the uncertainty the well-known minmax criterion is adopted. Polynomial and pseudopolynomial methods for finding a robust production plan, respectively, under the discrete and continuous budgeted uncertainty are proposed.

Quantified integer (linear) programs (QIP) are integer linear programs with variables being either existentially or universally quantified. They can be interpreted as two-person zero-sum games between an existential and a universal player on the one side, or multistage optimization problems under uncertainty on the other side. Solutions are so called winning strategies for the existential player that specify how to react on moves—certain fixations of universally quantified variables—of the universal player to certainly win the game. In this setting the existential player must ensure the fulfillment of a system of linear constraints, while the universal variables can range within given intervals, trying to make the fulfillment impossible. Recently, this approach was extended by adding a linear constraint system the universal player must obey. Consequently, existential and universal variable assignments in early decision stages now can restrain possible universal variable assignments later on and vice versa resulting in a multistage optimization problem with decision-dependent uncertainty. We present an attenuated variant, which instead of an NP-complete decision problem allows a polynomial-time decision on the legality of a move. Its usability is motivated by several examples.

A failure of an aircraft component during flight operations could lead to the grounding of an aircraft (AOG) until fault rectification is completed. This often results to high costs due to flight cancellations and delay propagation. With the technology of the digital twin, which is a virtual copy of a real aircraft, predictions of the technical reliability of aircraft components and thus the availability of the aircraft itself have recently become available. In the context of the combinatorial problem of aircraft resource planning, we examine how the predicted dispatch reliability of an aircraft could be used to achieve robustness of the schedule against AOG. We gain robustness only by flight scheduling, aircraft assignment and optimization of aircraft utilization, thus we avoid the use of expensive reserve ground times. We extend an integrated tail assignment and aircraft routing problem by “dispatch reliability” as a result from a digital twin. We disturb the flight schedule with random AOG cases, determine costs related to delay and flight cancellations, and improve robustness by taking into account the AOG-related costs in the objective function.

To maximize the travel distances of battery electric vehicles such as cars or buses for a given amount of stored energy, their powertrains are optimized energetically. One key part within optimization models for electric powertrains is the efficiency map of the electric motor. The underlying function is usually highly nonlinear and nonconvex and leads to major challenges within a global optimization process. To enable faster solution times, one possibility is the usage of piecewise linearization techniques to approximate the nonlinear efficiency map with linear constraints. Therefore, we evaluate the influence of different piecewise linearization modeling techniques on the overall solution process and compare the solution time and accuracy for methods with and without explicitly used binary variables.

Additive Manufacturing (AM) has become more relevant to industry in recent years and enables fabrication of complex lightweight lattice structures. Nevertheless, material extrusion processes require internal and/or external support structures for the printing process. These support structures generate costs due to additional material, printing time and energy.

For many industrial applications, the heating and cooling of fluids is an essential aspect. Systems used for this purpose can be summarized under the general term ‘thermofluid systems’. As an application, we investigate industrial process cooling systems that are used, among other things, for mold cooling in injection molding. The systems considered in this work consist of interconnected individual air-cooled chillers and injection molds which act as ideal heat sources. In practice, some parts of the system are typically fixed while some components and their connections are optional and thus allow a certain degree of freedom for the design. Therefore, our goal is to find a favorable system design and operation regarding a set of a-priori known load scenarios. In this context, a favorable system is one which is able to satisfy the demand in all load scenarios and has comparatively low total costs. Hence, an optimization problem arises which can be modeled using mixed integer non-linear programming. The non-linearity is induced both by the component behavior as well as by the general physical system behavior. As a proof of concept and to complete our work, we then conduct a small case study which illustrates the potential of our approach.

Successful optimization requires an appropriate model of the system under consideration. When selecting a suitable level of detail, one has to consider solution quality as well as the computational and implementation effort. In this paper, we present a MINLP for a pumping system for the drinking water supply of high-rise buildings. We investigate the influence of the granularity of the underlying physical models on the solution quality. Therefore, we model the system with a varying level of detail regarding the friction losses, and conduct an experimental validation of our model on a modular test rig. Furthermore, we investigate the computational effort and show that it can be reduced by the integration of domain-specific knowledge.

A new type of product portfolio design task where the products are identified with geometrical objects representing the efficiency of a product, is introduced. The sizes and shapes of these objects are determined by multiple constraints whose activity cannot be easily predicted. Hence, a discretization of the parameter spaces could obfuscate some advantageous portfolio configurations. Therefore, the classical optimal product portfolio problem is not suitable for this task. As a new mathematical formulation, the continuous set covering problem is presented which transfers into a semi-infinite optimization problem (SIP). A solution approach combining adaptive discretization of the infinite index set with regularization of the non-smooth constraint function is suggested. Numerical examples based on questions from pump industry show that the approach is capable to work with real-world applications.

The design of water networks consists of selecting pipe connections and pumps to ensure a given water demand to minimize investment and operating costs. Of particular importance is the modeling of variable speed pumps, which are usually represented by degree two and three polynomials approximating the characteristic diagrams. In total, this yields complex mixed-integer (non-convex) nonlinear programs.This work investigates a reformulation of these characteristic diagrams, eliminating rotating speed variables and determining power usage in terms of volume flow and pressure increase. We characterize when this formulation is convex in the pressure variables. This structural observation is applied to design the water network of a high-rise building in which the piping is tree-shaped. For these problems, the volume flow can only attain finitely many values. We branch on these flow values, eliminating the non-convexities of the characteristic diagrams. Then we apply perspective cuts to strengthen the formulation. Numerical results demonstrate the advantage of the proposed approach.

The chemical industry is one of the most important industrial sectors in Germany in terms of manufacturing revenue. While thermodynamic boundary conditions often restrict the scope for reducing the energy consumption of core processes, secondary processes such as cooling offer scope for energy optimisation. In this contribution, we therefore model and optimise an existing cooling system. The technical boundary conditions of the model are provided by the operators, the German chemical company BASF SE. In order to systematically evaluate different degrees of freedom in topology and operation, we formulate and solve a Mixed-Integer Nonlinear Program (MINLP), and compare our optimisation results with the existing system.

Optimal (model-based) experimental design (OED) aims to determine the interactions between input and output quantities connected by an, often complicated, mathematical model as precisely as possible from a minimum number of experiments. While statistical design techniques can often be proven to be optimal for linear models, this is no longer the case for nonlinear models. In process engineering applications, where the models are characterized by physico-chemical laws, nonlinear models often lead to nonconvex experimental design problems, thus making the computation of optimal experimental designs arduous. On the other hand, the optimal selection of experiments from a finite set of experiments can be formulated as a convex optimization problem for the most important design criteria and, thus, solved to global optimality. Since the latter represents an approximation of common experimental design problems, we propose a two-phase strategy that first solves the convex selection problem, and then uses this optimal selection to initialize the original problem. Finally, we illustrate and evaluate this generic approach and compare it with two statistical approaches on an OED problem from chemical process engineering.

Water distribution systems are an essential supply infrastructure for cities. Given that climatic and demographic influences will pose further challenges for these infrastructures in the future, the resilience of water supply systems, i.e. their ability to withstand and recover from disruptions, has recently become a subject of research. To assess the resilience of a WDS, different graph-theoretical approaches exist. Next to general metrics characterizing the network topology, also hydraulic and technical restrictions have to be taken into account. In this work, the resilience of an exemplary water distribution network of a major German city is assessed, and a Mixed-Integer Program is presented which allows to assess the impact of capacity adaptations on its resilience.

In this paper, we develop and evaluate a shift system for a fully-continuous production division that allows incorporating standby duties to cope with production-related fluctuations in personnel demand. We start by analyzing the relationships between fundamental parameters of shift models, including working hours, weekend load and flexibility and introduce approaches to balance out these parameters. Based on these considerations we develop a binary feasibility problem to find a suitable shift plan that is parametrized in the number of standby shifts.

Lot-sizing problems are of high relevance for many manufacturing companies, as they have a major impact on setup and inventory costs as well as various organizational implications. We discuss a practical capacitated lot-sizing problem, which arises in injection molding processes for plastic blanks at a large automotive manufacturer in Germany. 25 different product types have to be manufactured on 7 distinct machines, whereas each product type may be assigned to at least two of these machines. An additional challenge is that the following production processes use different shift models. Hence, the stages have to be decoupled by a buffer store, which has a limited capacity due to individual storage containers for each product type. For a successful application of the presented planning approach several real-world requirements have to be integrated, such as linked lot sizes, rejects as well as a given number of workers and a limited buffer capacity. A mixed integer programming model is proposed and tested for several instances from practice using CPLEX. It is proven of being able to find very good solutions within in few minutes and can serve as helpful decision support. In addition to a considerable reduction of costs, the previously mostly manual planning process can be simplified significantly.

For some time now, customers are more interested in sustainable manufacturing and are requesting products to be delivered in the shortest possible time. To deal with these new customer requirements, companies can follow the Distributed Manufacturing (DM) paradigm and try to move their production sites close to their customer. Therefore, the aim of this paper is to connect the idea of DM with the integrated planning of production and distribution operations mathematically in a MIP model. To this end, the model simultaneously decides the position of the plants, the production capacity in each period as well as the production and distribution scheduling.

In static-deterministic flow shop scheduling, solution algorithms are often tested by problem instances with uniformly distributed processing times. However, there are scheduling problems where a certain structure, variability or distribution of processing times appear. While the influence of these aspects on common objectives, like makespan and total completion time, has been discussed intensively, the efficiency-oriented objectives core idle time and core waiting time have not been taken into account so far. Therefore, a first computational study using complete enumeration is provided to analyze the influence of different structures of processing times on core idle time and core waiting time. The results show that in some cases an increased variability of processing times can lead to easier solvable problems.

Due to unexpected events (e.g. bad weather conditions), soccer league schedules cannot always be played as announced before the start of the season. This paper aims to mitigate the impact of uncertainty on the quality of soccer league schedules. Breaks and cancellations are selected as two quality measures. Three proactive policies are proposed to deal with postponed matches. These policies determine where to insert so-called catch-up rounds as buffers in the schedule, to which postponed matches can be rescheduled.

Hybrid flow shop (HFS) systems represent the typical flow shop production system with parallel machines on at least one stage of operation. This paper considers unrelated machines and anticipatory sequence-dependent setup times where job families can be formed based on similar setup characteristics. This results in the opportunity to save setups if two jobs of the same family are scheduled consecutively. Three constructive heuristic approaches, aiming at minimization of makespan, total completion time and the total number of setup procedures, are implemented based on the algorithm of Nawaz, Enscore and Ham (NEH).

A resource transition constraint models sequence dependent setup costs between activities on the same resource. In this work, we propose a heuristic for the multi-project scheduling problem with resource transition constraints, which relies on constraint programming and local search methods. The objective is to minimize the project delay, earliness and throughput time, while at the same time reducing setup costs. In computational results, we demonstrate the effectiveness of an implementation based on the presented concepts using instances from practice.

It is generally accepted that global warming is caused by greenhouse gas emissions. Consequently, ecological aspects, such as emissions, should also be integrated into operative planning. The amount of pollutants emitted strongly depends on the energy mix and thus on the respective time period the energy is used. In this contribution we analyse the influence of fluctuating carbon dioxide emissions on emission minimization in flow shop scheduling. Therefore, we propose a new multi-objective MIP formulation which considers makespan and time-depending carbon dioxide emissions as objectives. Epsilon constraint method is used to solve the problem in a computational study, where we show that emissions can reduced by up to 10% if loads are shifted at times of lower CO2 emissions.

We describe a planning and scheduling problem arising from a pharmaceutical application. In a complex production process, individualized drugs are produced in a flow-shop like process with multiple dedicated batching machines at each process stage. Furthermore, due to errors jobs might recirculate to earlier stages and get re-processed. Motivated by the practical application, we investigate techniques for improving the performance of the process. First, we study some simple scheduling heuristics and evaluate their performance using simulations. Second, we show how the scheduling results can also be improved significantly by slightly increasing the number of machines at some crucial points.

Increased awareness of resource scarcity and man-made pollution has driven consumers and manufacturers to reflect ways how to deal with end-of-life products and exploit their remaining value. The options of repair, remanufacturing or recycling each require at least partial disassembly of the structure with the variety of feasible process plans and large number of emerging parts and sub-assemblies generally making for a challenging optimization problem. Its complexity is further accentuated by considering divergent process flows which result from multiple parts or sub-assemblies that are released in the course of disassembly. In a previous study, it was shown that exact solution using an and/or graph based mixed integer linear program (MILP) was only practical for smaller problem instances. Consequently, a meta-heuristic approach is now taken to enable solution of large size problems. This study presents a genetic algorithm (GA) along with a problem specific representation to address both the scheduling and process planning aspect while allowing for parallel execution of certain disassembly tasks. Performance analysis with artificial test data shows that the proposed GA is capable of producing good quality solutions in reasonable time and bridging the gap regarding application to large scale problems as compared to the existing MILP formulation.

Natural disasters are extreme, sudden events caused by environmental factors that injure people and damage assets. In order to reduce the disaster’s impact, many workforces like professional emergency forces and volunteers work simultaneously. An integrated, central coordination of available resources can therefore reduce overall damage. For this purpose, we introduce a mixed-integer linear program for project management, particularly scheduling, in disaster response. Many specific characteristics such as partially renewable resources, flexible resource profiles, and variable activity durations with possible interruptions are taken into account. First small-scale instances are solved with GAMS using CPLEX 12.9.

Current literature on price bundling focuses on the situation with limited capacity. This paper extends this research by considering multiple discrete customer segments each with individual size and buying behavior represented by distributed willingness to pay and max-surplus rule. We develop a stochastic non-linear programming model that can be solved by standard NLP optimization software. Aiming to examine the model behavior, we conduct a full-factorial numerical study and analyze the impact of capacity limitations and number of customer segments on optimal solutions.

The long-distance traffic division of Deutsche Bahn (DB) uses a revenue management system to sell train-tickets to more than 140 million passengers per year. One essential component of a successful Railway Revenue Management system is an accurate forecast of future demand. To benefit from a tighter integration, DB decided in 2017 to develop its own forecast environment PAUL (Prognose AUsLastung) to replace the legacy third-party forecasting system. This paper presents the conceptual and technical setup of PAUL. Furthermore, experiences of the first year using PAUL as a production forecast environment are presented: It turned out that PAUL has a higher forecasting quality than the predecessor system and that the insourcing led to a constructive collaboration of PAUL system experts and revenue managers, which is beneficial for identifying opportunities for improvement.

This study presents a model in which heterogenous, risk-averse agents can use either (legal) tax optimisation or (illegal) tax evasion to reduce their tax burden and thus increase their utility. In addition to introducing individual variables like risk aversion or income, we allow agents to observe the behaviour of their neighbours. Depending on the behaviour of their peer group’s members, the agents’ utilities may increase or decrease, respectively. Simulation results show that taxpayers favour illegal evasion over legal optimisation in most cases. We find that interactions between taxpayers and their social networks have a deep impact on aggregate behaviour. Parameter changes such as increasing audit rates affect the results, often being intensified by social interactions. The effect of such changes varies depending on whether or not a fraction of agents is considered inherently honest.

In order to optimally prepare for competitions athletes gather as much data about their training units as possible. For cyclists, interesting figures are, e.g., the distance covered, the average and the maximum of speed, cadence, heart rate, and power output as well as the cumulative elevation gain. However, measuring devices do not always work reliably for all these factors. While factors like distance, speed, and cadence can be metered trustworthily with the help of magnets, which are attached directly to the bicycles, the metering of other factors still has room for improvement regarding accuracy and trustworthiness.In this paper we consider the cumulative elevation gain, the measurement of which is done by either GPS or barometric pressure nowadays. Therefore, it is dependent of steady connections to satellites (measurement by GPS) or steady changes in the barometric pressure. For the barometric pressure, however, it can happen that it varies merely due to weather changes or the time of the day. It is not surprising that for the same routes different measuring devices deliver quite different quantities for the elevation gain—not only depending on whether they measure by GPS or by barometric pressure. In the following we present ideas on how to support measuring devices to deliver more reliable quantities for the elevation gain by using statistics and mathematical methods.

Causal Loop Diagrams (CLDs) are a flexible and valuable tool for diagramming the feedback structure of systems. In strategic decision-making and management, we use CLDs to structure and explore complex decision-making situations, to foster learning, as a basis for simulation models, and to communicate simulation results. However, the crucial dissemination of CLDs and the possible learnings beyond the project-team is challenging.To overcome this problem, we developed a Domain-Specific Language that allows modeling experts with little programming experience to generate visual representations of CLDs that (1) replace the most complicated CLD elements with a step-by-step explanation and (2) strive to lower the barriers to learning while addressing a broader target audience.

Passenger routing in railway systems has traditionally relied on fixed timetables, working under the assumption that actual performance always matches the planned schedules. The complex variable interplay found in railway networks, however, make it practically impossible for trains to systematically hold the designed timetables as delays are a common occurrence in these systems. A more sensible approach to passenger routing involves assessing the probability distributions that characterize the system and consider them in the routing recommendation. This paper describes one such approach using a simulation model working under both deterministic and stochastic conditions and describes the weak points of a deterministic routing strategy in a complex system.

Due to increasing passenger and flight numbers, airports need to plan and schedule carefully to avoid wasting their resources, but also congestion and missed flights. In this paper, we present a deep learning framework for predicting the number of passengers arriving at an airport within a 15-min interval. To this end, a first neural network predicts the number of passengers on a given flight. These results are then being used with a second neural network to predict the number of passengers in each interval.

Important current trends influencing the development of modeling environments include expectations on interconnection between optimization and analytics tools, easy and secure deployment in a web-based, distributed setting and not least, the continuously increasing average and peak sizes of data instances and complexity of problems to be solved. After a short discussion of the history of modeling languages and the contributions made by FICO Xpress Mosel to this evolution, we point to a number of implementation variants for the classical travelling salesman problem (TSP) using different MIP-based solution algorithms as an example of employing Mosel in the context of parallel or distributed computing, for interacting with a MIP solver, and for the graphical visualisation of results. We then highlight some newly introduced features and improvements to the Mosel language that are of particular interest for the development of large-scale optimization applications.

We analyze the window fill rate in an inventory system with constant lead times under a periodic review policy. The window fill rate is the probability that a random customer gets serviced within a predefined time window. It is an extension of the traditional fill rate that takes into account that customers generally tolerate a certain waiting time. We analyze the impact of the reorder-cycle on the window fill rate and present an inventory model that finds the optimal spares allocation and the optimal reorder cycle with the objective of minimizing the total costs. Furthermore, we present a numerical example and find that the number of spares increase almost linearly when the reorder-cycle time increases. Finally, we show how managers can find the optimal spares allocation and the optimal reorder-cycle time and show how they can estimate the cost of changing the required window fill rate and the reorder-cycle time.

Buying raw materials at low cost is important for the economic success of manufacturing companies. In this extended abstract, we summarize some of the cost-driving constraints and cost-saving opportunities available to a global manufacturer when purchasing raw materials. We outline how to model the procurement problem as a mixed-integer linear program, and describe the use of Sankey diagrams to compare alternative order volume plans.

We examine a retail distribution network design problem that considers the strategic decision of determining the number of distribution centers (DC) as well as their type (i.e., central, regional, local), and anticipates the tactical decision of allocating products to different types of DC. The resulting distribution structure is typical for grocery retailers that choose to operate several types of DC storing a distinct set of products each. We propose a novel model considering the decision-relevant costs along the retail supply chain and present a case study of a major European retailer.

Over the past years, closed-loop supply chains (CLSC) gained a considerable attention in both academia and industry due to environmental regulations and concerns about sustainability. Although various problems in CLSC’s are addressed by researchers, not much attention is given to the effects of closing the loop in supply chains. In this study, we propose a set of linear programming models for both forward and closed-loop supply chains to see the economic and environmental effects of closing the loop. In addition to the case where there is no emission regulation, we also study the carbon cap policy and compare the forward and closed-loop supply chains under this policy. Computational results bring two important insights to us. First, we see that there are instances in which closing the loop may bring significant cost and emission reductions. Second, we observe that it may be possible to work under lower carbon caps by closing the loop in supply chains.

In railway timetabling one objective is that the timetable is robust against minor delays. One way to compute the robustness of a timetable is to simulate it with some predefined delays that occur and are propagated within the simulation. These simulations typically are complex and do not provide any information on the derivative of an objective function such as the punctuality. Therefore, we propose black-box optimization techniques that adjust a given timetable so that the expected punctuality is maximized while other objectives such as the number of operating trains or the travel times are fixed. As an example method for simulation, we propose a simple Markov chain model directly derived from real-world data. Since every run in any simulation framework is computationally expensive, we focus on optimization techniques that find good solutions with only few evaluations of the objective function. We study different black-box optimization techniques, some including expert knowledge and some are self-learning, and provide convergence results.

In this paper we address a variant of the freight train routing problem to estimate the residual capacity in railway networks with regular passenger services. By ensemble averaging over a random temporal distribution of usable slots in the network, bounds on the number of additional freight trains on predefined relations are established. For the solution, a two-step capacitated routing approach based on a time-expanded network is used. The approach is applied in a case study to freight relations in the railway network of North Rhine Westphalia.

The key to a successful ridesharing service is an efficient allocation and routing of vehicles and customers. In this paper, relevant aspects from practice, like customer waiting times, are integrated into a mathematical programming model for the operational optimization of a dynamic ridesharing system, improving existing models from the literature. Moreover, a new heuristic solution method for the optimization of a dynamic ridepooling system is developed and compared with the exact solution derived by a MIP solver based on the above-mentioned model.In a case study consisting of 30 customers who request different rides and can be transported by a fleet of 10 vehicles in the area of Hamburg, both approaches are tested. The results show that the heuristic solution method is superior to the exact solution method, especially with respect to the required solution time.

The accurate prediction of train delays can help to limit the negative effects of delays for passengers and railway operators. The aim of this paper is to develop an approach for training a supervised machine learning model that can be used as an online train delay prediction tool. We show how historical train delay data can be transformed and used to build a multivariate prediction model which is trained using real data from Deutsche Bahn. The results show that the neural network approach can achieve promising results.

The problem of creating a rolling stock schedule is complex and difficult. In Japan, research to develop an optimal schedule using mathematical models has not progressed sufficiently due to the large number of train services. We aim to create an optimal schedule for a railway line where “mutual direct operation” is being conducted. Previous studies proposed a mathematical model as an integer-programming problem to obtain an optimal roster for a single company. In this paper, we extend the formulation to create a schedule for multiple companies to apply to mutual direct operation. The difference from previous studies is, in addition to minimizing the total distance of empty runs, to making the total running distances by company vehicles on each other’s lines as close to equal as possible.

The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.

Preserving the efficiency of an airport during winter operations and corresponding conditions requires proper configuration of the snow removal fleet and its smart operation by using optimal routing schemes to clean the airport’s airside. In this paper, we present a two-stage approach for optimizing typical winter operations at large airports. In the first stage, we estimate the minimum fleet size to undertake maintenance operations in due time based on a vehicle capacity model. We consider various vehicle parameters, dedicated airport maps with allocated service areas and potential service level agreements between airport operator and airlines acting as customers. In the second stage, the optimal routing of the vehicles is determined under the objective of minimizing the cleaning time of pre-defined areas. We apply a specially adapted variant of Vehicle Routing Problem with problem-specific constraints such as vehicle synchronization for joint snow removal, restrictions resulting from the wind direction and, furthermore the preference of runways over taxiways. With the help of the developed methodology it is possible to verify potential investments into fleet resources, which might seem to be necessary to meet increasing service level requirements. The methodology is being demonstrated for Leipzig-Halle Airport (LEJ).

Predicting the target time of an aircraft turnaround is of major importance for the tactical control of airport and airline network operations. Nevertheless, this turnaround time is subject to many random influences, such as passenger behavior while boarding, resource availability, and short-noticed maintenance activities. This paper proposes a mathematical optimization model for the aircraft turnaround problem while considering various uncertainties along the process. The proposed method is acting on a microscopic, thus detailed operational level. Dealing with uncertainties is implemented by two approaches. First, an analytical procedure based on convolution, which has not been considered in the literature so far but provides fast computational results, is proposed to estimate the turnaround finalization, called Estimated Off-Block Time (EOBT). The convolution algorithm considers all process-related stochastic influences and calculates the probability that a turnaround can be completed within the pre-set target time TOBT. At busy airports, such assessments are needed in order to comply with installed slot allocation mechanisms. Since aircraft turnaround operations reflect a scheduling problem, a chance-constrained MIP programming model is applied as a second approach. This procedure assumes stochastic process durations to determine the best alternative of variable process executions, so that the TOBT can be met. The procedure is applied to an Airbus A320 turnaround.

This paper presents a strategic depot planning approach for a railway crew scheduling problem integrated in a column generation framework. Since the integration strongly weakens the relaxation of the master problem we consider different variants for strengthening the formulation. In addition, the problem can be sufficiently simplified by using a standard day at the strategic level. Based on a case study for an exemplary real-life instance, we can show that a proper pre-selection of depots reduces the number of needed depots significantly with the same personnel costs.

In the project smartrail 4.0 Swiss Federal Railways (SBB) aims for a higher degree in automatization of the railway value chain (e.g. line planning, timetabling and vehicle scheduling, etc.). In the context of an applied research project together with SBB, we have developed an extension of the Periodic Event Scheduling Problem (PESP) model. On one hand the extension is based on using a finer resolution of the track infrastructure, the so-called mesoscopic topology. The mesoscopic topology allows creating timetables with train lines assigned to track paths. On the other hand, we use a known, flexible PESP formulation (FPESP), i.e. we calculate time intervals instead of time points for the arrival resp. departures times at operating points. Both extensions (mesoscopic topology and flexibility) should enhance feasibility of the timetables on the microscopic infrastructure. We will call our model therefore track-choice, flexible PESP model (TCFPESP).

Runway system configurations constitute a bottleneck at major international airports. Capacity management is used to determine the maximal throughput of an airport, which is limited by several infrastructural and operational factors. Within this paper we describe how to model complex capacity restrictions on airport runway systems. The model is solved by a Column Generation approach where the subproblem is represented as a Shortest Path Problem. Additionally, a lower bound based on Lagrangian Relaxation and a Primal Rounding Heuristic are applied in our approach.

In this paper, we address the electric bus scheduling problem (EBSP) and its solution. We propose an algorithm for input data reduction which reduces the number of service trips by merging two service trips into one. Also, a method of choosing possible candidates for merging and two different criteria to choose the best candidate are described. Proposed algorithm was tested on real data from the city of Žilina provided by the public transport system operator DPMŽ. After the reduction of the inputs, an exact optimization was performed on the reduced problem to compare the solutions with the original problem.

We consider the problem of constructing crew duties for a large, real instance of operations for commuter train services in Mumbai, India. Optimized allotment of crew duties and enforcement of work rules ensures adequate safety and welfare of rail workers. Currently, within Indian railways, decisions related to crew allotment are made manually. The main objective is to use as few crew members as possible to execute upon the timetable. This improves the efficiency of the system by increasing the average working hours of work per duty. We also have several other secondary objectives. The presence of a large number of operational constraints makes the problem difficult to solve. Computational experiments are performed over the current train timetables and the results of our algorithm compare very favorably with the crew duty schedules in use. For the Western Railways train timetable of 2017–18, the crew duty sets required to perform the timetable was 382. The proposed algorithm achieves crew allotment with 368 sets, promising significant savings of manpower and money.