Operations Research Proceedings 2017

Planning efficient routes fast becomes ever more important, especially in the context of aircraft trajectories. As time-dependent wind conditions factor into the shortest path query, we use an artificial wind vector called Super-Optimal Wind as a means of creating a suitable potential function for the A* algorithm, thus speeding up the query. We assess the quality of Super-Optimal Wind both theoretically and computationally, and use Super-Optimal Wind in a real-world instance.

For many routing applications, decision making is conducted under incomplete information. The information is only revealed successively during the execution of the routing. In many cases, dispatchers adapt their decisions dynamically to new information. Nevertheless, to avoid myopic decisions, dispatchers have to anticipate future events in current decision making. In this paper, we propose the use of a Markov decision process (MDP) to model stochastic dynamic vehicle routing problems (SDVRPs). For the integration of stochasticity in dynamic decision making, we present novel methods of approximate dynamic programming (ADP). These methods are extensions and combinations of general ADP-methods and are tailored to match the characteristics of SDVRPs. A comparison with conventional state-of-the-art benchmark heuristics for a SDVRP with stochastic customer requests proves the ADP-methods to be highly advantageous.

In this paper the traveling salesman problem is used as an example to describe an allocation concept for cooperative scenarios where besides a common objective function also individual objectives of players are of importants. From a game theoretical view, such a problem corresponds to a cooperative game with non-transferable as well as transferable utilities. We define formally this cooperative game as well as an allocation concept motivated by the Shapley NTU value.

Completing possibly unforeseen tasks in a timely manner is vital for many real-world problems: For instance, in hospitals, emergency patients may come in and require to be treated, or self-driving cars need to avoid obstacles appearing on the street. Under the hard constraint of timely fulfilling these tasks, one still usually wishes to use resources conscientiously. We consider the above applications in the form of two fundamental mathematical problems. First, in online deadline scheduling, jobs arrive over time and need to scheduled on a machine until their deadline. Second, in convex-body chasing, an agent needs to immediately serve tasks located within convex regions and minimize the total travelled distance. In this paper we review the main results we obtained in the thesis of the same title: We present various novel online algorithms and techniques for analyzing them. Thereby we improve upon previously known bounds.

This is a summary of the dissertation of the author (Fontaine, Methodological Advances and New Formulations for Bilevel Network Design Problems, 2016) [12]. We propose a Benders decomposition algorithm to solve discrete-continuous bilevel problems to optimality. Using the underlying problem structure, the convergence is further improved by using the multi-cut version or pareto-optimal cuts. Numerical studies on existing problems from the literature (the Discrete Network Design Problem, the Decentralized Facility Selection Problem and the Hazmat Transport Network Design Problem) show run time improvements of more than 90% compared to the mixed-integer linear program.Moreover, the Discrete Network Design Problem is extended to a multi-period model for traffic network maintenance planning. We further introduce a population-based risk definition and extend the Hazmat Transport Network Design Problem to a multi-mode model to fairly distribute risk among the population.The numerical results show a better distribution of risk compared to classical models in the literature and a convex relation between risk equilibration and minimization.

We consider polytopes that arise in the cluster analysis of a finite set of data points. These polytopes encode all possible clusterings and their vertices correspond to clusterings that admit a power diagram, which is a polyhedral separation of the underlying space where each cluster has its own cell. We study the edges of these polytopes and show that they encode cyclical transfers of elements between clusters. We use this characterization to obtain a relation between power diagrams and the volume of the cones of outer normals of the respective clustering. This allows us to derive a new stability criterion for clusterings, which can be used to measure the dependability of the clustering for decision-making. Further, the results explain why many popular clustering algorithms work so well in practice.

We propose a new variant of Bin Packing Problem, where rectangular items of different types need to be placed on a two-dimensional surface. This new problem type is denoted as two-dimensional Bin Packing with side constraints. Each bin may consist of different two-dimensional sides, and items of different types may not overlap on different sides of the same bin. By different parameter settings, our model may be reduced to either a two- or three-dimensional Bin Packing Problem. We propose practical applications of this problem in production and logistics. We further introduce lower bounds, and heuristics for upper bounds. We can demonstrate for a variety of instance classes proposed in literature that the GAP between those bounds is rather low. Additionally, we introduce a Column-Generation based algorithm that is able to further improve the lower bounds and comes up with good solutions. For a total of 400 instances, extended from previous literature, the final relative gap was just 6.8%.

Unsupervised image segmentation and denoising are two fundamental tasks in image processing. Usually, graph based models such as multicut are used for segmentation and variational models are employed for denoising. Our approach addresses both problems at the same time. We propose a novel ILP formulation of the first derivative Potts model with the $$\ell _1$$ data term, where binary variables are introduced to deal with the $$\ell _0$$ norm of the regularization term. The ILP is then solved by a standard off-the-shelf MIP solver. Numerical experiments are compared with the multicut problem.

In a purchase decision process, consumers often tend to choose a branded product that arouses the most positive brand affect. Recent literature identified brand personality as a central driver for brand affect and showed that consumers prefer brands that are aligned with their own personality traits. Hence, harmonization of brand personality with personality traits of the target market segments may lead to affective brand loyalty. However, focusing on consumers’ personality traits for market segmentation is challenging, since personality traits are not directly observable. Linking personality traits to easily observable variables may simplify company’s communication efforts to create brand personality. We therefore explore whether a consumer’s preference for a specific sport may serve as a predictor of the consumer’s response to brand personality and found evidence that different sport clusters differ significantly with respect to certain personality traits.

Finding significant changes in multidimensional data is a crucial task for several use cases. With change mining on frequent itemsets, alterations in the statistics of personal injury road accidents can be detected. Since a lot of factors determine the situation of an accident, the statistical data consists of too many dimensions to detect changes in their frequencies manually. Hence, we propose an automated approach based on Frequent Itemset Mining using known algorithms, such as Apriori, to detect significant changes within the data. Firstly, the 1.8 million records of Great Britain’s road safety data openly published by the Department for Transport are prepared and adjusted to match the algorithms’ requirements. Secondly, the most frequent itemsets for each time interval are filed and compared to the itemsets of the previous period and are split into classes of changing, stable and semi-stable itemsets. To build our framework we concentrate on the support of frequent itemsets and the changes between the months of two consecutive years.

Election campaign optimization problem (ECOP) can be described as finding the best way to allocate a political party’s resources among different election locations in order to maximize the seats or member of parliaments (MPs) won. For this purpose, first one has to determine the minimum amount of votes needed to pass the opponent to win extra seats. The analysis are carried out on one of the most popular election rules: D’Hondt rule and mathematical formulae are derived to exactly determine the required vote amounts. Next, a mixed integer linear program to capture the problem is proposed. Finally, the methodology is tested on the Turkish Parliamentary elections data and it is observed that with small amount of budget shifts among election regions significant gains can be obtained.

Long-term projections for commodity prices are a key challenge in science as well as in business environment. This paper proposes a new mathematical approach for future projections of prices for time horizons larger than 10 years using a Dynamic Bayesian Network (DBN). The DBN approach is verified at the crude oil price example.

The rising shares of volatile renewable energy supply in the European electricity markets lead to an increased relevance for short-term trading at the EPEX SPOT. In this paper, we propose a holistic modeling approach for a robust prediction of EPEX SPOT day-ahead prices for the bidding zone Germany, Austria and Luxembourg applying three-layer and deep neural networks. In the first step, we describe, why neural networks are well suited for econometric modeling tasks. In the modeling part, we distinguish an optimal set of meta-parameters and then gradually adjust the final model setup. Lastly, we further improve the performance accuracy by applying a quantile-based scaling process. Thus, we obtain accurate and robust predictions even for sharp price peaks in rare events.

The splitting preconditioner is very effective, in the final iterations, when applied together with the conjugate gradient method for solving the linear systems arising from interior point methods. This preconditioner relies on an LU factorization of unknown linearly independent subset of the linear problem constraint matrix columns. However, that preconditioner is expensive to compute since a nonsingular matrix must be built from such set of columns. In this work, a new splitting preconditioner is presented which eliminates the need to obtain a nonsingular matrix. The controlled Cholesky factorization is used to compute the preconditioner from normal equations matrix from a given set of not necessarily independent columns. Such an approach is practicable since the controlled Cholesky factorization may be computed by adding suitable diagonal perturbations. Numerical experiments show that the new approach improves previous performance results in some large-scale linear programming problems.

We consider bilevel problem in the following formulation. The follower problem is a convex quadratic problem which linearly depends on the leader variable. The leader problem is a quadratic problem. We are looking for an optimistic solution. Optimal value function of the follower problem is used to reformulate bilevel problem as a standard (one-level) optimization problem. By this way we obtain a nonconvex multiextremal problem with implicit nonconvex constraint generated by the optimal value function. We show how to construct an explicit piecewise quadratic function which is support to the optimal value function at a given point. Usage of the support functions allows us to approximate the implicit one-level problem by a number of explicit nonconvex quadratic problems. In our talk we describe an iterative procedure based on such approximation.

The standard model of information valuation as presented by Emery, Organization planning and control systems: theory and technology, Macmillan Pub Co., London, 1969, [1] and Laux, Grundfragen der Organisation: Delegation Anreiz und Kontrolle, Springer, Berlin, 1979, [2] is based on Bayesian statistics. This approach is limited to the processing of a crisp objective function as well as a crisp decision field. It is assumed that information is solely obtained in order to improve prior state probabilities. In this paper, we first present and discuss variations of the standard model, including considerations of potential negative information values. Second, we want to take vague information into account by implementing intuitionistic fuzzy logic.

This paper examines a problem of the Canadian Coast Guard. The mission of the Coast Guard (Atlantic) is to provide assistance to vessels or persons aboard that are in distress. This piece focuses on the search & rescue mission of the Coast Guard. The two most important criteria include the average time that it takes to reach a vessel in distress, and the number of vessel incidents that can be reached within a reasonable time limit. Given that demand throughout the year is not constant but peaks during the summer season (in excess of 50% of the distress calls occur in July and August), there is a potential for congestion and the resulting inability of the Coast Guard to answer distress calls within an acceptable amount of time. In order to avoid formulating the model as a probabilistic model with all its computational difficulties, we use backup coverage as a third important concern. We model the problem of locating different types of rescue vessels along the coastline of the Maritime Provinces as an integer programming problem with three objectives, each dealing with one of the major concerns. The problem is solved given the available vessels and on the basis of incidents reported in the past. The solution is compared to the arrangement that is presently used by the Coast Guard.

We match photogrammetric point clouds with 3D city models in order to texture their wall and roof polygons. Point clouds are generated by the Structure from Motion (SfM) algorithm from overlapping pictures and videos that in general do not have precise geo-referencing. Therefore, we have to align the clouds with the models’ coordinate systems. We do this by matching corners of buildings, detected from the 3D point cloud, with vertices of model buildings that are given in CityGML format. Due to incompleteness of our point clouds and the low number of models’ vertices, the standard registration algorithm “Iterative Closest Point” does not yield reliable results. Therefore, we propose a relaxation of a Mixed Integer Linear Program that first finds a set of correspondences between building model vertices and detected corners. Then, in a second step, we use a Linear Program to compute an optimal linear mapping based on these correspondences.

We consider the well-known uncapacitated p-hub median problem with multiple allocation (UMApHMP), and single allocation (USApHMP). These problems have received significant attention in the literature because while they are easy to state and understand, they are hard to solve. They also find practical applications in logistics and telecommunication network design. Due to the inherent complexity of these problems, we apply a modified Benders decomposition method to solve large instances of the UMApHMP and USApHMP. The Benders decomposition approach does, however, suffer from slow convergence mainly due to the high degeneracy of subproblems. To resolve this, we apply a novel method of accelerating Benders method. We improve the performance of the accelerated Benders method by more appropriately choosing parameters for generating cuts, and by solving subproblems more efficiently using minimum cost network flow algorithms. We implement our approach on well-known benchmark data sets in the literature and compare our computational results for our implementations of existing methods and commercial solvers. The computational results confirms that our approach is efficient and enables us to solve larger single- and multiple allocation hub median instances. We believe this paper is the first implementation of Benders method to solve USA$$p$$HMP and UMA$$p$$HMP.

Mixed integer linear programming (MILP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MILP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MILP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.

We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct.

“Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex” This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.

Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.

The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact for one checkpoint, for solving the mCOP. Our computational experiments show that there is no clear winner between the two methods. While the ILP approach is hardly influenced by increasing the number of checkpoints or the length of the departments, the performance of our DP algorithm deteriorates in both cases.

The 1D skiving stock problem (SSP) is a combinatorial optimization problem being of high relevance whenever an efficient utilization of given resources is intended. In the classical formulation, (small) items shall be used to build as many large objects (specified by some required length) as possible. Due to the NP-hardness of the SSP, the performance of the LP relaxation (measured by the additive gap of the related optimal values) and/or heuristics are of scientific interest. In this paper, theoretical properties of the best fit decreasing heuristic (for the SSP) are investigated and shown to provide a new and improved upper bound for the gap of the so-called divisible case.

Let a (generalized) chessboard in two or three dimensions be given. A closed knight’s tour is defined as a Hamiltonian cycle over all cells of the chessboard where all moves are knight’s moves, i. e. have length $$\sqrt{5}$$. It is well-characterized for which chessboard sizes it is not possible to construct a closed knight’s tour. On such chessboards a closed almost knight’s tour is defined as a Hamiltonian cycle of minimal length if only moves of length at least $$\sqrt{5}$$ are allowed. The problem of determining closed (almost) knight’s tours on 2D and 3D chessboards is equivalent to the so called traveling salesman problem with forbidden neighborhoods on regular 2D and 3D grids if the radius of the forbidden neighborhood is two and hence the minimal feasible distance of two consecutive vertices in the tour equals the length of a knight’s move. In this paper we present explicit construction schemes for closed almost knight’s tours by extending ideas used for the construction of knight’s tours.

The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.

In the literature, packing and partitioning orbitopes were discussed to handle symmetries that act on variable matrices in certain binary programs. In this paper, we extend this concept by restrictions on the number of 1-entries in each column. We develop extended formulations of the resulting polytopes and present numerical results that show their effect on the LP relaxation of a graph partitioning problem.

The (usual) k-server problem was introduced by Manasse, McGeoch and Sleator in 1988. Meanwhile it is the most studied problem in the area of competitive online problems. In [4] (Information Processing Letters, 114(5):239–246, 2014) we have created a generalized k-server problem with parallel requests. This research was initiated by an operations research problem which consists of optimal conversions of machines or moulds. In the present paper we give a first summary of “competitive” algorithms for solving the “k-server problems with parallel requests” or the generalized paging problem.

We study the traveling salesperson problem with forbidden neighborhoods (TSPFN) on regular three-dimensional (3D) grids. The TSPFN asks for a shortest tour over all grid points such that successive points along a tour have at least some given distance. We present optimal solutions and explicit construction schemes for the Euclidean TSP and the TSPFN, where edges of length one are forbidden, on regular 3D grids.

In the field of disaster logistics one often faces tasks which can be modeled as a TSP with additional ordering constraints. In this paper we therefore want to consider four different variants of the TSP. In detail we consider the Clustered TSP, the Ordered Clustered TSP, the Precedence Constraint TSP and the Target Visitation Problem. For each of these four problems we discuss IP models and examine the connections between them. We also present a branch-and-cut algorithm which can solve these problems to optimality.

Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.

In average, more than 1,275 wind turbines were installed annually since 1997 in Germany and more than 27,000 wind turbines are in operation today. The technical and economic life time of wind turbines is around 20 to 25 years. Consequently, dismantling of aging wind turbines will increase significantly in upcoming years due to repowering or decommissioning of wind farms and lead to millions of costs for operators. An option to supersede the costly and time-consuming dismantling of wind turbines entirely on-site is to establish a dismantling network in which partly dismantled wind turbines are transported to specialized dismantling sites for further handling. This network requires an optimization model to determine optimal locations and an appropriate distribution of disassembly steps to dismantling sites. The challenge is to consider the networks dependency on the trade-off between transportation and dismantling costs which, in turn, depends on the selection of dismantling depths and sites. Building on the Koopmans-Beckmann problem, we present a mathematical optimization model to address the described location planning and allocation problem. To permit a proof-of-concept, we apply our model to a case-study of an exemplary wind farm in Northern Germany. Our results show that the model can assist dismantling companies to arrange efficient dismantling networks for wind turbines and to benefit from emerging economic advantages.

In the last decades, several different research questions arose in the area of water distribution systems. To evaluate the new models, techniques and solution methods, there is need of a large range of test models. In most research work the evaluation is performed on simple generated networks with no realistic size and properties. In this work, we present a generator for water network models, which can be used for the evaluation of new models and solution methods. The generator can create network models with arbitrary size and realistic properties.

Due to various challenges such as climatic changes or implementation of renewable energy generation, improvements in regulating energy grids are required. Demand-Side-Management (DSM) contributes to this progress by managing, shifting and controlling loads. However, many DSM algorithms make assumptions regarding load characteristics which do not consider real world conditions. Prior studies find a total of five constraints but so far no investigation shows the effects of these constraints on DSM algorithms. Hence, this research analyses the effects of several constraints of DSM algorithms by conducting a simulation. As a result, we can conclude that the constraints have an effect on the results. For example, the savings dropped about 7% when considering multiple constraints. The handling and the outcomes depend on several factors and might vary. As a logical conclusion, we postulate that these constraints should be considered in DSM algorithms.

The German Energiewende is a substantial project posing many challenges. One is the maintainance of grid quality and stability that can be met by demand side management. Our research interest within the innovation cluster ER-WIN® is to estimate the economic potential of demand side management from the perspective of a producing company. Therefore, we modelled the production scheme of a case example, namely a sand processing facility, as a Mixed-Integer-Program. This paper presents how we integrated continuous and discontinuous processes while preserving a satisfactory computing time.

The aftermath of the financial crisis has threatened the stability of several financial institutions over the past years. Most heavily hit were banks with a notable exposure to ship finance, who saw the collateral value of many loans being diminished. Industry observers trace back the rare occurrence of actual defaults of ship loans to the use of the Long-Term-Asset Value (LTAV), a valuation method explicitly designed for ship investments. As the LTAV is based on a discounted cash-flow approach, it accounts for investment risks in the discount rate. Consequently, the LTAV bundles the time value of money and risk in a single value, which begs the question if this method oversimplifies the incorporation of risk in the evaluation of ship investments. In the context of infrastructure investments, the Decoupled Net Present Value (DNPV) has recently been proposed as an alternative method that addresses the problem of using risk-adjusted discount rates. It separates the time value of money from risks by quantifying risk factors individually and treating them as costs to the investment. We provide a proof-of-concept regarding the applicability of the DNPV in the context of ship investments. To this end, we develop a DNPV valuation model and instantiate a prototype in Python. We then perform a simulation study that evaluates a ship investment using both the LTAV and the DNPV. The results of our study confirm the applicability of the DNPV to ship investments and point to both its advantages and limitations compared to the LTAV.

The index tracking problem asks for a portfolio of a restricted number of assets from a stock market index, such that the portfolio resembles the index as closely as possible. The tracking error to be minimized is a quadratic function of the difference between the portfolio and the index weights. The index tracking problem is strongly NP-hard. In this work, we develop construction and simprovement methods that are one order of magnitude faster than recently suggested methods. Computational experiments confirm the favorable running times, but also show that the faster methods produce portfolios with larger tracking errors.

Many real-life situations, e.g., budget allocation within universities or negotiations between insurance companies over compensation for damages, etc., highlight the relevance of distribution problems. In many corresponding situations, it is not only positive outcomes that need to be divided but also negative or combinations of positive and negative ones. Previous research typically focuses on distribution problems that emerge either in a gain or in a loss domain or on a comparison between the two domains. In this experimental study, we focused on the behavior of players in two modified versions of an ultimatum game that implemented asymmetric strategic advantages for the players, i.e., the game allowed for both, positive and negative overall payoffs for both players. We found that (1) the bargaining behavior of the proposers was in line with previous research findings, i.e., most proposers offered between 40 and 50% of the pie to the responder, and (2) the responders, in contrast to literature on gains or losses, oriented their behavior towards breaking-even. Their desire to break-even seemed to act as a stronger motive than their preference to secure an equal split.

We introduce a graph theoretic approach in order to solve a large number of knapsack instances in polynomial time. For this purpose we apply threshold graphs, which have the useful property, that their independent sets correspond to feasible solutions in respective knapsack instances. We present a method to count and enumerate all maximal independent sets in a threshold graph in polynomial time and expanding this method for k-threshold graphs. This allows us to solve special knapsack instances as well as special multidimensional knapsack instances for a fixed number of dimensions in polynomial time. Furthermore, our results improve existing solutions for the maximum independent set problem on k-threshold graphs.

In this paper we focus on r-neighbor bootstrap percolation on finite graphs, which is a process on a graph evolving in discrete rounds where, initially, a set $$A_0$$ of vertices gets infected. Now, subsequently, an uninfected vertex becomes infected if it is adjacent to at least r infected vertices. Call $$A_f$$ the set of vertices that are infected after the process stops. More formally, we let $${A_t:=A_{t-1}\cup \{v\in V: |N(v)\cap A_{t-1}|\ge r\}}$$, where N(v) is the neighborhood of some vertex v. Then $$A_f=\bigcup _{t>0} A_t$$. We are mainly interested in the size of the final set $$A_f$$. We present a theorem which bounds the size of the final infected set for degenerate graphs in terms of $$\vert A_0\vert ,d$$ and r. To be more precise, for a d-degenerate graph, if $$r\ge d+1$$, the size of $$A_f$$ is bounded from above by $$(1+\tfrac{d}{r-d})|A_0|$$.

We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm, see Cambini et al, Mathematical Programming, 78, 195–217, 1997, [6]. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that most operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.

We use exact mathematical modeling and optimization to evaluate various operational modes of a cooperative truck network for full-truckload transportation.

A mathematical model is used to schedule and route full truckload shipments in a cooperative network as relays. We describe a matching of transports in the network, which eleminates empty runs. To maximize the matched number of transports handled in the network, each transport is associated with a multiple number of possible routes, under certain conditions. These re-designed dispatching processes enhance the total costs of transports for members in the cooperation.

Inner-city sports events such as skate nights, company races or bicycle races often take place on circular courses. Regular streets are blocked for normal traffic and only released for the active participants of the event. Often, the participants start and end at the same point. We present an algorithm to find running tracks of prespecified length in a general road network. This constitutes a simplification tool in the decision making process of finding adequate running tracks as the algorithm returns a number of possibilities from which organizers are able to choose the track that meets most requirements desired by the organizer. The returned solutions can further be used as input to additional (mulicriteria) optimization problems as, for example, finding tracks that do not exceed a given limit on the altitude difference or that avoid street turns that are to sharp.

In this article we consider the following problem arising in the context of scenario generation to evaluate the transport capacity of gas networks: In the Uncapacitated Maximum Minimum Cost Flow Problem (UMMCF) we are given a flow network where each arc has an associated nonnegative length and infinite capacity. Additionally, for each source and each sink a lower and an upper bound on its supply and demand are known, respectively. The goal is to find values for the supplies and demands respecting these bounds, such that the optimal value of the induced Minimum Cost Flow Problem is maximized, i.e., to determine a scenario with maximum transportmoment. In this article we propose two linear bilevel optimization models for UMMCF, introduce a greedy-style heuristic, and report on our first computational experiment.

Air transportation networks are known to be scale-free and easily modeled using a multiplex structure. Each airline’s network tends to develop independent of the other carriers, based on economic and political factors, influenced by the interaction between them. Creating synthetic models for air transportation networks provides a tool towards creating larger size similar networks, based on the existing structure and development of the network used as the model. We enhance the Barabási-Albert-based BinBall model (Basu, Sundaram, Dippel in IEEE/ACM 25–28, 2015, [9]), by (1) decoupling the scaling factors related to the global and local degree of a new attached node, and (2) a fitted distribution of the edge count per layer. We validate it using the European Air Transportation Network (Cardillo, Gmez-Gardees, Zanin, Romance et al, in Scientific Reports, 2013, [7]), showing that our model outperforms BinBall with respect to the diversity of individual layer structure.

We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths’ demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.

In Kidney exchange programs patients with chronic kidney disease and a willing but incompatible donor are joined in a pool and preliminary compatibility between patient in one pair and donors in other pairs is evaluated. Based on this information a set of transplants is planned. After a transplants plan is set, additional compatibility tests are performed for each pair selected for transplant. These tests can elicit extra incompatibilities and lead to cancellation of planned transplants. In this paper we propose to conduct some crossmatch tests before a transplantation plan is set and address the issue of how many additional transplants can be performed for a given number of tests. Three different policies are proposed to decide which pairs should be selected for crossmatch. They differ in the rules used to update the current plan, whenever a new incompatibility is found. Comparison of results, in terms of transplants performed with and without a priori crossmatch shows that more flexible policies allow for substantial improvement on the actual number of transplants for a small number of tests.

High dose-rate brachytherapy is a method of radiation cancer treatment, where the radiation source is placed inside the body. The recommended way to evaluate dose plans is based on dosimetric indices which are aggregate measures of the received dose. Insufficient spatial distribution of the dose may however result in hot spots, which are contiguous volumes in the tumour that receive a dose that is much too high. We use mathematical optimization to adjust a dose plan that is acceptable with respect to dosimetric indices to also take spatial distribution of the dose into account. This results in large-scale nonlinear mixed-binary models that are solved using nonlinear approximations. We show that there are substantial degrees of freedom in the dose planning even though the levels of dosimetric indices are maintained, and that it is possible to improve a dose plan with respect to its spatial properties.

In our work we focus on Robotic Mobile Fulfillment Systems in e-commerce distribution centers. These systems were designed to increase pick rates by employing mobile robots bringing movable storage units (so-called pods) to pick and replenishment stations as needed, and back to the storage area afterwards. One advantage of this approach is that repositioning of inventory can be done continuously, even during pick and replenishment operations. This is primarily accomplished by bringing a pod to a storage location different than the one it was fetched from, a process we call passive pod repositioning. Additionally, this can be done by explicitly bringing a pod from one storage location to another, a process we call active pod repositioning. In this work we introduce first mechanisms for the latter technique and conduct a simulation-based experiment to give first insights of their effect.

We study an integrated production–inventory system that manufactures new items of a certain product and receives some of the used items back. These can be either remanufactured on the same production line or disposed of. Used items awaiting remanufacturing need to be held in stock. New and as-good-as-new items are kept in stock, from which the product demand is satisfied. Controlling such a system involves decisions with regard to disposal of used items, succession of manufacturing and remanufacturing operations, and the choice of respective lot sizes. Recent works have referred to settings assuming variation in quality of returned items and a limited number of remanufacturing cycles that an item can undergo. We seek to determine optimal lot sizing for such a system and derive sufficient conditions for an optimal policy to forego remanufacturing.

In this paper, we present a matheuristic solution technique to solve a real world problem related to the distribution and inventory management of beer from breweries to restaurants and bars. Consistency in delivery times is an important requirement for this application. Other problem characteristics are the possibility of split deliveries and the existence of time windows. Hence, the problem aims to minimize costs related to routing, consistency, inventory holding stock-out. We develop an adaptive large neighborhood search method and we propose different destroy and repair operators. The method is tested using a benchmark data set and compared to optimal solutions on small test instances.

Current order picking technologies are characterized by different degrees of automation. Irrespective of the automation level, order picking remains a labor-intensive process. Hence, the decisions on the deployment of installed technologies and on labor utilization are interdependent. We develop two planning approaches for an integrative decision support. In comparison to the simultaneous approach the sequential one induces coordination deficits, but less computational effort. In order to inquire into the behavior of both approaches, we conduct a numerical study using sampled data of a pharmaceutical wholesaler.

The vehicle in finding a set of routes, problem with backhauls and time windows contains two disjoint sets of customers: those that receive goods from the depot, who are called linehauls, and those that send goods to the depot, named backhauls. To each customer is associated an interval of time (time window), during which each one should be served. For solving this problem we created a deterministic iterated local search algorithm, which was tested using a large set of benchmark problems taken from the literature. These computational tests have proven that this algorithm competes with best known algorithms in terms of the quality of the solutions and computing time.

A robust design of a service system has to be resistant to randomly appearing failures in the network. To achieve the resistance, a finite set of scenarios is generated to cover the most detrimental combinations of failures. The system is designed to minimize the maximal impact of individual scenarios. Since each scenario corresponds to particular objective function, searching for the robust service system design consists in minimizing the maximum of particular objective functions. This problem is hard to be solved. We focus here on handling big size of the original model by employing new approach based on convex combination of scenarios.

Theoretical study of real-life leasing scenarios was initiated in 2005 with a simple leasing model defined as follows. Demands arrive with time and need to be served by leased resources. Different types of leases are available, each with a fixed duration and price, respecting economy of scale (longer leases cost less per unit time). An algorithm is to lease resources at minimum possible costs in order to serve each arriving demand, without knowing future demands. In this paper, we generalize this model and introduce the Lease-or-Decline and Lease-or-Delay leasing models. In the Lease-or-Decline model, not all demands need to be served, i.e., the algorithm may decline a demand as long as a penalty associated with it is paid. In the Lease-or-Delay model, each demand has a deadline and can be served any day before its deadline as long as a penalty is paid for each delayed day. The goal is to minimize the total cost of purchased leases and penalties paid. For each of these models we give a deterministic online primal-dual algorithm, evaluated using the standard competitive analysis in which an online algorithm is compared to the optimal offline algorithm which knows the entire sequence of demands in advance and is optimal.

This paper deals with a class of scheduling problems with uncertain job processing times and due dates. The uncertainty is specified in the form of discrete scenario set. A probability distribution in the scenario set is known. Thus the cost of a given schedule is then a discrete random variable with known probability distribution. In order to compute a solution the popular risk criteria, such as the value at risk and the conditional value at risk, are applied. These criteria allow us to establish a link between the very conservative maximum criterion, typically used in robust optimization, and the expectation, commonly used in the stochastic approach. Using them we can take a degree of risk aversion of decision maker into account. In this paper, basic single machine scheduling problems with the risk criteria for choosing a solution are considered. Various positive complexity results are provided for them.

The traditional approach of flight trajectory planning for commercial airplanes aligns the routes to a finite air travel network (ATN) graph. A new alternative is the free-flight trajectory planning, where routes can use the entire 4D space (3D+time) for more fuel-efficient trajectories that minimize the travel costs. In this work, we focus on the vertical optimization part of such trajectories for a fixed horizontal trajectory, computed or manually derived beforehand. The idea is to assign to each of the trajectory’s segments an optimal altitude and speed for the cruise phase of the flight. We formulate this problem as a nonlinear programming (NLP) problem. As for the input of the model, information about the airplane’s fuel consumption is provided for discrete levels of speed and weight values. Thus a continuous formulation of this input data is required, to meet the NLP requirements. We implement different interpolation and approximation techniques for this. Using AMPL as modeling language, along with nonlinear commercial solvers such as SNOPT, CONOPT, KNITRO, and MINOS, we present numerical results on test instances for real-world instance data and compare the resulting trajectories in terms of the fuel consumption and the computation times.

The combination of optimization tools of any kind and additive manufacturing should be able to improve lightweight construction. In this article we discuss a mixed-integer linear program to describe the static load distribution in a two-dimensional space as a first starting point. The results indicate there is an opportunity to use optimization for the initial design within a defined assembly space. A design example illustrates first results.

Pre-runtime scheduling of the kind of Integrated Modular Avionic (IMA) system addressed in this paper can be considered as multiprocessor scheduling with additional constraints on precedence relations between tasks and the concurrent scheduling of a communication network with discrete time slots for sending messages. This paper extends an existing constraint generation procedure for such IMA-systems to facilitate co-allocation of messages in the time slots. To send a communication message involves the execution of a set of tasks. Co-allocation of messages means that tasks of the same type that originate from these messages are merged and their total execution requirements are shortened. The reduction of the execution requirements induces capacity savings that can have a positive impact on the feasibility of the problem.

Afghanistan is geo-strategically in an important transit zone in South and Central Asia, but currently lacks of modern infrastructure. We present the construction of optimal transit routes in Afghanistan through mathematical optimization. Basically there are three different optimization goals (a) the shortest route w.r.t. the distance, (b) the cheapest route w.r.t. the construction cost, and (c) the most convenient route w.r.t. the elevation change. It is possible to combine two objectives by considering the Pareto front. For the design and modeling of the routes, a computer program named “Contra ” (Computing an Optimal Network of Transit Routes through mathematical Algorithms) was developed. As a demonstrator example, we compute Pareto-optimal routes between two Afghan cities.

The energy-efficiency of technical systems can be improved by a systematic design approach. Technical Operations Research (TOR) employs methods known from Operations Research to find a global optimal layout and operation strategy of technical systems. We show the practical usage of this approach by the systematic design of a decentralized water supply system for skyscrapers. All possible network options and operation strategies are modeled by a Mixed-Integer Nonlinear Program. We present the optimal system found by our approach and highlight the energy savings compared to a conventional system design.

We derive an optimization problem for a mission planning problem of a firefighting department challenged by a wildfire. Here the fire is modeled using partial differential equations (PDEs), and the response from the firefighters is modeled as a dynamic network flow. The firefighters influence the spread of the wildfire, and vice versa, the fire restricts the movement options of the firefighters. These mutual interactions have to be incorporated into the model. The presented approach to formulate this problem mathematically is to replace the infinite dimensional constraints imposed by the PDE by a finite dimensional system. These systems however tend to be very large even for a moderate resolution of the approximation. This causes a direct approach using a finite difference method to be outperformed by a new method, in which the PDE is solved in a pre-optimization step. We demonstrate the superiority of this approach in a computational study, where both methods are compared for various approximation resolutions.

We consider the multiple traveling salesmen problem with moving targets (MTSPMT), which is a generalization of the classical traveling salesman problem (TSP). Here the nodes (objects, targets) are not static, they are moving over time on trajectories. Moreover, each target has a visibility time window and it can be reached by a salesman only within that time window. The objective function is to minimize the total traveled distances of all salesmen. We recall the time-discrete model formulation from Stieber et al. [9]. This model is applicable to arbitrarily shaped trajectories. Thus, we generated non-linear trajectories based on polynomials, trigonometric functions and their combinations. Computational experiments are carried out with up to 16 trajectories and the results are compared to the ones obtained with linear trajectories.

Highly competitive markets paired with tremendous production volumes demand particularly cost efficient products. The usage of common parts and modules across product families can potentially reduce production costs. Yet, increasing commonality typically results in overdesign of individual products. Multi domain virtual prototyping enables designers to evaluate costs and technical feasibility of different single product designs at reasonable computational effort in early design phases. However, savings by platform commonality are hard to quantify and require detailed knowledge of e.g. the production process and the supply chain. Therefore, we present and evaluate a multi-objective metamodel-based optimization algorithm which enables designers to explore the trade-off between high commonality and cost optimal design of single products.

A multistatic sonar system consists of one or more sources that are able to emit underwater sound, and receivers that listen to the direct sound as well as its reflected sound waves. From the differences in the arrival times of these sounds, it is possible to determine the location of surrounding objects. The propagation of underwater sound is a complex issue that involves several factors, such as the density and pressure of the water, the salinity and temperature level, as well as the pulse length and volume and the reflection properties of the surface. These effects can be approximated by nonlinear equations. Furthermore, natural obstacles in the water, such as the coastline, need to be taken into consideration. Given a certain area of the ocean that should be endowed with a sonar system for surveillance, we consider the task of determining how many sources and receivers need to be deployed, and where they should be located. We give an integer nonlinear formulation for this problem, and several ways to derive an integer linear formulation from it. These formulations are numerically compared using a test bed from coastlines around the world and a state-of-the-art MIP solver (CPLEX).

The UN sets the goal to ensure access to water and sanitation for all people by 2030. To address this goal, we present a multidisciplinary approach for designing water supply networks for slums in large cities by applying mathematical optimization. The problem is modeled as a mixed-integer linear problem (MILP) aiming to find a network describing the optimal supply infrastructure. To illustrate the approach, we apply it on a small slum cluster in Dhaka, Bangladesh.

Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.

Many firms are selling different types of products. Typically sales applications are characterized by competitive settings, limited demand information, and substitution effects. The demand probabilities of a firm’s products are affected by its own product prices as well as competitors’ product prices. Due to the complexity of such markets, effective pricing strategies are hard to derive. In this paper, we analyze stochastic dynamic multi-product pricing models under competition for the sale of durable goods. In a first step, a data-driven approach is used to quantify substitution effects and to estimate sales probabilities in competitive markets. In a second step, we use a dynamic model to compute effective heuristic feedback pricing strategies, which are even applicable if the number of competitors’ offers is large and their pricing strategies are unknown.

We consider the problem of estimating possible stability levels of automotive manufacturing facilities, which are currently operating under differing production premises. The problem is motivated by the necessity of car producers to transform their existing plants to a stabilized production in order to deal with the increasing complexity of the production process. Thus, the achievable range of stability has to be estimated and potential fields of action have to be identified. In order to verify the proposed method, a real world data case study was conducted. As a result, various stability characteristics were discovered. This simulation study reveals process related stability losses in front of the final assembly and measures the impact of external influence factors on the achievable sequence. The transparency and fields of action provided by this simulation study reduce the uncertainties in the planning activities and contribute to the successful transformation process.

Maintenance activities of machines in the manufacturing industry are essential to keep machine availability as high as possible. A breakdown of a single machine can lead to a complete production stop. Maintenance is traditionally performed by predefined maintenance specifications of the machine manufacturers. With the help of condition- based maintenance, maintenance intervals can be optimized due to detailed knowledge through sensor data. This results in an adapted maintenance schedule where machines are only maintained when necessary. Apart from time savings, this also reduces costs. An decision support system with optimization model for maintenance planning is developed considering the right balance between the probabilities of failure of the machines and the potential breakdown costs. The current conditions of the machines are used to forecast the necessary maintenance activities for several periods. The decision support system helps maintenance planners to choose their decision-making horizon flexibly.

Process industries are facing strong global competition in recent years. In order to stay competitive, it is important to quickly react to new market developments and to serve specialized product demands. To meet these requirements, flexible production capacity is required. Recently, the use of modular plants has received much attention as an answer to these new challenges. Modular plants consist of standardized process modules, which allow for quick assembly, disassembly and relocation of production plants. Using modular production concepts, the flexibility of the production network is greatly increased (Seifert et al., Chemical Engineering and Technology 37(2):332–342, 2014, [6]). The technical feasibility of modular plant concepts has been proven by several projects, like the EU funded “$$F^3$$-Factory” project and the “CoPIRIDE” project (European Commission: Final report for flexible, fast and future production processes, 2014, [3]). Modular plants offer an increased manufacturing flexibility in type, volume and location of production capacities.

Many practical projects incorporate random rework, which leads to a stochastic project network structure. Until now, however, there have been only few works in the literature that have looked into this particular aspect of project planning and scheduling. In this paper, we consider a resource-constrained project scheduling problem (RCPSP) with exponentially distributed activity durations and two types of random rework. A mathematical model is proposed based on a continuous-time Markov decision process (CTMDP) with the objective to minimize the expected project makespan, which is further converted into an equivalent DTMDP with removing the self-transitions. In order to cope with the curse of dimensionality that comes into play upon solving large-scale instances, we examine a decomposition and parallel method that limits the memory usage. In addition, we also analyze the effect of random rework on the expected project makespan and the optimal rework strategy. Finally, a computational experiment is set up to validate the effectiveness of the proposed model and procedures.

Multiprocessor scheduling is a well studied NP-hard optimisation problem that occurs in variety of forms. The focus of this paper is explicit modelling of multiple task intervals. This work extends a constraint generation procedure previously developed for an avionics scheduling context. We here address a relaxation of the original problem and this relaxation can be considered as multiprocessor scheduling with precedence relations and multiple intervals. The explicit modelling of multiple intervals strengthens the formulation used in the constraint generation procedure and we illustrate the computational effects on an industrial relevant avionics scheduling problem.

Satalia is working with a multinational company that needs to have a team of 10 people spend 4 months every year manually assigning 1,000 staff to perform 10,000 jobs on 2,000 projects. This is a massive undertaking, in part because of the scale of the problem and in part because the problem is multi-objective with 57 hard and soft business rules. The task can be formulated as a large-scale scheduling problem. We demonstrate that our optimisation methods can unlock substantial savings in company work-hours while also improving quality as measured across a range of objectives. In this paper, we will outline the heuristic and exact approaches utilised, describe some of the many challenges of such a real-world problem, and show how we overcame them.

The consideration of blocking constraints refers to the absence of buffers in a production system. A job-shop scheduling problem with a total tardiness objective is NP-hard even without blocking constraints and mathematical programming results indicate the necessity of heuristics. The neighborhood is one of its main components. In contrast to classical job-shop scheduling, a permutation of operations does not necessarily define a feasible schedule. A neighbor is determined by an adjacent pairwise interchange (API) of two operations on a machine and the resulting permutation of operations is modified to regain feasibility while maintaining the given API. The neighborhood is implemented in a simulated annealing and tested on train-scheduling-inspired problems as well as benchmark instances. The heuristic method obtains optimal and near-optimal solutions for small instances and outperforms a given MIP formulation for some of the larger ones.

We consider a scheduling problem with a learning effect, where independent jobs are scheduled on two parallel identical machines. Jobs are preemptable but only a restricted preemption of a single job is allowed. The optimality criterion of a schedule is the maximum completion time. A few properties of the problem are presented and an exact algorithm solving this problem is proposed.

Agent-based models are currently in wide use in innovation and technology diffusion research, as they are able to capture the inherent complexity arising from adoption processes and they allow the consideration of various influences of the underlying social systems. While they are sometimes criticized as “toy models”, agent-based models often do not reach their full potential if they lack an empirical foundation. Therefore, we present an agent-based simulation that addresses consumers’ adoption behavior of electric and plug-in hybrid electric vehicles in Germany using various empirical data sources for parametrization and validation. In particular, we conducted a focus group and a choice-based conjoint study. Additionally, our model is to our knowledge the first that takes into account explicitly and comprehensively the supply of home charging options.

The hybrid agent-based modeling (HABM) framework is intended to specify integrated models based on agent-based modeling and simulation, discrete event simulation, and system dynamics. HABM not only supports the specification of agents exhibiting discrete and continuous behavior but also considers flexible structures. The latter is an important aspect for many agent-based models. HABM has been successfully used in strategic workforce planning. However, it can also be applied to other OR fields such as supply chain management or even for the specification of certain kinds of agent-based metaheuristics.

This paper describes the development process of a System Dynamics model for the air transport system (MATS). The focus of this paper is placed on the methodological steps required to model the air transport system, from the organization and management of a multidisciplinary team to the statistical data analysis required to reliably parameterize the System Dynamics model. The MATS model represents a step forward regarding the inclusion of multiple interrelated aspects from this industry, and their potential integration on a global scale.

This paper studies the dynamic Nash equilibrium problem with shared constraint (NEPSC), a set of optimal control problems with coupled cost functionals and control sets. This problem is reformulated into a variational inequality (VI) posed in an Hilbert space, and a VI-based Galerkin method is proposed for solving its equilibrium solution.

We present a concept that provides an efficient description of differential-algebraic equations (DAEs) describing flow networks which provides the DAE function $$f$$ and their Jacobians in an automatized way such that the sparsity pattern of the Jacobians is determined before their evaluation and previously determined values of $$f$$ can be exploited. The user only has to provide the network topology and local function descriptions for each network element. The approach uses automatic differentiation (AD) and is adapted to switching element functions via the abs-normal-form (ANF).

Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.

Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.

Nonlinear optimization problems that arise in real-world applications usually depend on parameter data. Parametric sensitivity analysis is concerned with the effects on the optimal solution caused by changes of these. The calculated sensitivities are of high interest because they improve the understanding of the optimal solution and allow the formulation of real-time capable update algorithms. We present WORHP Zen, a sensitivity analysis module for the nonlinear programming solver WORHP that is capable of the following: (i) Efficient calculation of parametric sensitivities using an existing factorization; (ii) efficient sparse storage of these derivatives, and (iii) real-time updates to calculate an approximated solution of a perturbed optimization problem. An example application of WORHP Zen in the context of parameter identification is presented.

We present an algorithm to minimize the investment in stock in a n-level inventory distribution network using a (R,Q)-order policy with stochastic demands and wait times. Our research is motivated by the inventory planning for a worldwide spare parts supply chain of a big automotive company. The algorithm is fast enough to be used in real world applications. It is, to our knowledge, the first one to determine reorder points for inventory distribution systems using complex wait time approximations.

Food supply chain (FSC) refers to the processes from production to delivery of food products from farmers to customers and is different from other kinds of supply chains because of the perishable nature of food. Among the current FSCs, the agricultural fruit supply chain has been paid the least attention. The fact that the quality of fruits deteriorates along supply chain processes and the lack of planning in different stages of FSC results in food loss, which has an impact on food security, insufficiency, and profitability. Therefore, reducing food loss will bring substantial benefits not only to FSC companies but also to society regarding food provision. The purpose of this paper is to present a mixed-integer linear programming (MILP) model for apple supply chain to manage inventory flows in different types of storage rooms for apples from different harvesting periods, while satisfying the demand. The model also reports the optimal type of each storage room. Food loss decision variables are defined to quantify the amount of apple losses in each type of storage room based on the time gap between the harvest and delivery. The objective function of the model is total cost minimization, including penalty costs for apple losses. The model is applied in a real industrial case study in Australia to show its applicability and is solved by Gurobi optimization solver 7.0.

The logistics of perishable goods differs significantly from non-perishable items due to various uncertainties related to seasonable fluctuating supply and demand. Operational research models represent powerful tools to handle such growing complexity and uncertainties. This work focuses on the integration of product quality and aims to minimize food losses during storage and transport. A generic keeping quality model, which models quality losses based on storage temperatures and durations, is implemented in a discrete event simulation. To test the model, the strawberry supply chain of Lower Austria is investigated. The impacts of integrated shelf life information in stock rotation schemes and tailored delivery strategies are discussed. Results indicate that stock rotation schemes, which integrate product qualities, and tailored delivery strategies substantially reduce food losses.

Exchangeable-item repair systems are inventory systems in which customers receive operable items in exchange of the failed items they brought. The failed items are not discarded, but instead, they are repaired on site. We consider such a system in which failed items arrival follows a Compound Poisson process and in which the item removal and installation times may be positive. For this system, we develop exact formulas for the window fill rate, that is, the probability that customers receive service within a specific time window. This service measure is appropriate in situations that customers tolerate a certain delay and therefore the system does not incur reputations costs if it completes service within this time window.

Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.

The police aim for using electric vehicles within the criminal investigation service. However, the challenges related to the use of electric vehicles result in a limited availability of these vehicles. Until now, decision support for fleet operation with electric vehicles at the police is missing. This contribution introduces an extension of the Electric Vehicle Scheduling Problem for the police.

Electrification of public transport is one important pillar of sustainable urban planning. However, the infrastructure is still costly and a cost-efficient solution crucial. Costs and effectiveness depend mainly on the number and location of charging stations as well as on the batteries’ capacities. Here, also the ageing, i.e. the loss in capacity must be taken into account. Thus, we introduce the Charging Stations Location Problem with Battery Ageing (CSLP-BA). We present a mixed integer model with multiple periods, enhanced by a battery ageing function to solve the problem. To evaluate the model, we give an overview of our results obtained from real world data of the bus network of Mannheim and contrast them with the present configuration used in Mannheim.

We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We are aware of only one collection of instances, the so-called PESPlib. In the present paper, we aim at providing good solutions for the smallest and the largest of its instances (R1L1 and R4L4). We run a standard MIP solver (CPLEX) on a very elementary problem formulation. To come up with MIP sizes that fit better for standard MIP solvers, we propose to simplify the instances first, by invoking some basic preprocessing, parts of which having a heuristic character. Doing so, we improve the previously best-known objective value for R1L1 from 37,338,904 down to 33,711,523, and for R4L4 from 47,283,768 down to 43,234,156, i.e. by 9.7% and 8.6%, respectively.

We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers.

Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.

In this paper traffic management strategies for disruption-caused inaccessibility of one track on double-track railway lines are analyzed. Building on previous results for polling systems with $$k_i$$-limited service discipline and non-zero switchover times heuristic rules for optimally switching the orientation of the remaining track are investigated. QoS-standards enforcing delay constraints for both orientations as well as asymmetric traffic load, e.g. resulting from differing block length in both directions, are accounted for. For a system without train priorities analytical approximations as well as simulation results for the optimal switching parameter are compared. The analysis is extended to priority systems in a simulation approach. The performance of the heuristic is tested in a case study by comparing it to the optimal solution obtained by solving the train scheduling problem for the bidirectional line segment.

With the increasing interest in creating Smart Cities, traffic speed prediction has attracted more attention in contemporary transportation research. Neural networks have been utilized in many studies to address this problem; yet, they have mainly focused on the short-term prediction while longer forecast horizons are needed for more reliable mobility and route planning. In this work we tackle the medium-term prediction as well as the short-term. We employ feedforward neural networks that combine time series forecasting techniques where the predicted speed values are fed into the network. We train our networks and select the hyper-parameters to minimize the mean absolute error. To test the performance of our method, we consider two multi-segment routes in Istanbul. The speed data are collected from floating cars for every minute over a 5-month horizon. Our computational results showed that accurate predictions can be achieved in medium-term horizon.

As the demand for home delivery continues to grow, so too does the need for organisations to implement more efficient delivery operations. For our clients, the constraints imposed on home delivery are numerous — and it is a challenge that causes many organisations to struggle. Our clients have any number of vehicles, each with limited capacity. Vehicles are limited to certain routes, and routes are often limited by traffic, accidents or road closures. Add driver shifts, multiple destinations and the rising desire for nominated time-window delivery (slots) and you get a scheduling problem no human operator can solve with any degree of accuracy. Our data-driven, operations research approach has, and will continue to improve the efficiency of home delivery; reducing costs for our clients, and vastly improving the customer experience.

The goal of this presentation is to show how schedule adjustments based on plan-actual-comparisons improve on time performance, to point out limitations for the practical implementation and discuss further enhancements using metaheuristic algorithms for network optimization. The effect of the schedule adjustment is calculated using the movement data for the long-distance railway network for Deutsche Bahn for a full year (2014). The extent of the plan changes is determined by the cost of operation and the (opportunity) cost for delays.