Skip to main content
Top

2016 | Book

Operations Research Proceedings 2014

Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), RWTH Aachen University, Germany, September 2-5, 2014

Editors: Marco Lübbecke, Arie Koster, Peter Letmathe, Reinhard Madlener, Britta Peis, Grit Walther

Publisher: Springer International Publishing

Book Series : Operations Research Proceedings

insite
SEARCH

About this book

This book contains a selection of refereed papers presented at the "International Conference on Operations Research (OR 2014)", which took place at RWTH Aachen University, Germany, September 2-5, 2014. More than 800 scientists and students from 47 countries attended OR 2014 and presented more than 500 papers in parallel topical streams, as well as special award sessions. The theme of the conference and its proceedings is "Business Analytics and Optimization".

Table of Contents

Frontmatter
Experimental Validation of an Enhanced System Synthesis Approach

Planning the layout and operation of a technical system is a common task for an engineer. Typically, the workflow is divided into consecutive stages: First, the engineer designs the layout of the system, with the help of his experience or of heuristic methods. Secondly, he finds a control strategy which is often optimized by simulation. This usually results in a good operating of an unquestioned system topology. In contrast, we apply Operations Research (OR) methods to find a cost-optimal solution for both stages simultaneously via mixed integer programming (MILP). Technical Operations Research (TOR) allows one to find a provable global optimal solution within the model formulation. However, the modeling error due to the abstraction of physical reality remains unknown. We address this ubiquitous problem of OR methods by comparing our computational results with measurements in a test rig. For a practical test case we compute a topology and control strategy via MILP and verify that the objectives are met up to a deviation of 8.7 %.

Lena C. Altherr, Thorsten Ederer, Ulf Lorenz, Peter F. Pelz, Philipp Pöttgen
Stochastic Dynamic Programming Solution of a Risk-Adjusted Disaster Preparedness and Relief Distribution Problem

This chapter proposes a multistage stochastic optimization framework that dynamically updates the purchasing and distribution decisions of emergency commodities in the aftermath of an earthquake. Furthermore, the models consider the risk of exceeding the budget levels at any stage through chance constraints, which are then converted to Conditional Value-at-Risk constraints. Compared to the previous papers, our framework provides the flexibility of adjusting the level of conservativeness to the users by changing risk related parameters. Under some conditions, the resulting linear programming problems are solved through the Stochastic Dual Dynamic Programming algorithm. The preliminary numerical results are encouraging.

Ebru Angün
Solution Approaches for the Double-Row Equidistant Facility Layout Problem

We consider the Double-Row Equidistant Facility Layout Problem and show that the number of spaces needed to preserve at least one optimal solution is much smaller compared to the general double-row layout problem. We exploit this fact to tailor exact integer linear programming (ILP) and semidefinite programming (SDP) approaches that outperform other recent methods for this problem. We report computational results on a variety of benchmark instances showing that the ILP is preferable for small and medium instances whereas the SDP yields better results on large instances with up to 60 departments.

Miguel F. Anjos, Anja Fischer, Philipp Hungerländer
Simulation of the System-Wide Impact of Power-to-Gas Energy Storages by Multi-stage Optimization

In this paper a simulation method for the European power and natural gas system based on an optimization is introduced. The mathematical formulation of the problem represents a minimization of total costs subject to the coverage of demand and reserve requirements as well as the adherence of technical constraints. Due to the complexity of the problem, especially due to binary decisions and non-linearities resulting from restrictions of thermal power as well as Power-to-Gas plants, a closed-loop formulation is not practicable. Thus, this paper presents a simulation method consisting of a multi-stage optimization with the use of Lagrangian Relaxation and decomposition techniques.

Christoph Baumann, Julia Schleibach, Albert Moser
An Approximation Result for Matchings in Partitioned Hypergraphs

We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $$2\sqrt{d}$$2d for partitioned hypergraphs with parts of size $$\le d$$≤d. Furthermore, we show that this bound cannot be improved to $$\mathscr {O}(d^{0.5-\varepsilon })$$O(d0.5-ε).

Isabel Beckenbach, Ralf Borndörfer
On Class Imbalance Correction for Classification Algorithms in Credit Scoring

Credit scoring is often modeled as a binary classification task where defaults rarely occur and the classes generally are highly unbalanced. Although many new algorithms have been proposed in the recent past to mitigate this specific problem, the aspect of class imbalance is still underrepresented in research despite its great relevance for many business applications. Within the “Machine Learning in R” (mlr) framework methods for imbalance correction are readily available and can be integrated into a systematic classifier optimization process. Different strategies are discussed, extended and compared.

Bernd Bischl, Tobias Kühn, Gero Szepannek
The Exact Solution of Multi-period Portfolio Choice Problem with Exponential Utility

In the current paper we derive the exact analytical solution of the multi-period portfolio choice problem for an exponential utility function. It is assumed that the asset returns depend on predictable variables and that the joint random process of the asset returns follows a vector autoregression. We prove that the optimal portfolio weights depend on the covariance matrices of the next two periods and the conditional mean vector of the next period. The case without predictable variables and the case of independent asset returns are partial cases of our solution.

Taras Bodnar, Nestor Parolya, Wolfgang Schmid
On the Discriminative Power of Tournament Solutions

Tournament solutions constitute an important class of social choice functions that only depend on the pairwise majority comparisons between alternatives. Recent analytical results have shown that several concepts with appealing axiomatic properties tend to not discriminate at all when the tournaments are chosen from the uniform distribution. This is in sharp contrast to empirical studies which have found that real-world preference profiles often exhibit Condorcet winners, i.e., alternatives that all tournament solutions select as the unique winner. In this work, we aim to fill the gap between these extremes by examining the distribution of the number of alternatives returned by common tournament solutions for empirical data as well as data generated according to stochastic preference models.

Felix Brandt, Hans Georg Seedig
An Actor-Oriented Approach to Evaluate Climate Policies with Regard to Resource Intensive Industries

Metal production is responsible for a large part of greenhouse gas (GHG) emissions in Germany. While some political stakeholders call for a more restrictive climate policy to force further reductions of GHG emissions, the exceptions made for the metal industry increased so far to guarantee its global competitiveness. The question rises how a more restrictive climate policy would affect industrial GHG emissions and the profitability. To estimate the impact of political instruments the actor-oriented approach presented focuses on the simulation of plant-specific investment decisions. First, a detailed database of the internal material and energy flows of all relevant iron, steel and aluminium producing plants together with the best available techniques (BAT) for GHG emission reduction is developed. In the subsequent simulation, the plants, modelled as actors, decide on the implementation of these techniques dependent on the political conditions which are varied in scenarios. The results show, that there are only minor GHG emission reduction potentials due to already implemented high efficiency standards. Nevertheless, more restrictive climate policies can lead to significant cost increases influencing global competitiveness.

Patrick Breun, Magnus Fröhling, Frank Schultmann
Upper Bounds for Heuristic Approaches to the Strip Packing Problem

We present an algorithm for the two-dimensional strip packing problem (SPP) that improves the packing of the FFDH heuristic, and we state theoretical results of this algorithm. We also present an implementation of the FFDH heuristic for the three-dimensional case which is used to construct the COMB-3D heuristic with absolute worst-case performance ratio of 5. We also show, that this heuristic has absolute worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP. Based on this heuristic, we derive a general upper bound for the optimal height which depends on the continuous and the maximum height lower bound. We prove that the combination of both lower bounds also has an absolute worst-case performance ratio of at most 5 for the standard three-dimensional SPP. We also show that the layer-relaxation has a worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP.

Torsten Buchwald, Guntram Scheithauer
An Approximative Lexicographic Min-Max Approach to the Discrete Facility Location Problem

We propose a new approximative approach to the discrete facility location problem that provides solutions close to the lexicographic minimax optimum. The lexicographic minimax optimum is concept that allows to find equitable location of facilities. Our main contribution is the approximation approach, which is based on the rules allowing: (i) to take into account the multiplicities assigned to different customers; (ii) to detect whether for a given distance active customers can reach higher, equal or smaller distance to the closest located facility; and (iii) to use methods customized for solving the p-median problem. Customized methods can handle larger problems than state-of-the-art general purpose integer programming solvers. We use the resulting algorithm to perform extensive study using the well-known benchmarks and benchmarks derived from the real-world road network data. We demonstrate that our algorithm allows to solve larger problems than existing algorithms and provides high-quality solutions. The algorithm found the optimal solution for all tested benchmarks, where we could compare the results with the exact algorithm.

Ľuboš Buzna, Michal Koháni, Jaroslav Janáček
Effects of Profit Taxes in Matrix Games

It is consensus in different fields of practical relevance that the introduction of taxes will—in one way or the other—affect the playing behavior of actors. However, it is not clear what the effects might really look like. Here, a game theoretic model is considered that concentrates on effects of relative or constant taxes on transferred monetary volume. For matrix games it is asked: How do taxes change the behavior of players and the expected transacted volume? Analyzing this basic research model clearly shows: One has to be careful in considering taxes as a powerful instrument to confine aggressive playing behavior. Taxes might encourage increased expected transfers.

Marlis Bärthel
Extension and Application of a General Pickup and Delivery Model for Evaluating the Impact of Bundling Goods in an Urban Environment

In this work we present results from a research project dealing with the bundling of goods, which was applied to the region of Zurich. The main goal was to develop a model for quantifying the impact of bundling goods on total costs. We focussed on the case of two distributors here and investigated two scenarios, namely no and full cooperation. The scenarios were based on transportation requests from customers and known origin-destination transport flows between postcodes. The costs include salaries, fleet degeneration and amortisation, respectively, and CO$$_2$$2 emissions. To allow for computing the total costs, a pickup and delivery model from literature was implemented and extended. It could be shown that even for a simple kind of cooperation, savings of around 7 % in total costs are possible.

Stephan Bütikofer, Albert Steiner
Optimizing Time Slot Allocation in Single Operator Home Delivery Problems

Motivated by applications in last-mile home delivery, we tackle the problem of optimizing service time to customers by service providers in an online-realtime scenario. We focus on the particular case where a single operator performs all deliveries. We formalize the problem with combinatorial optimization models. We propose diverse time slot assignment policies and level of service measures. We perform a computational study to evaluate the impact of each policy on the quality of a solution, and to assess the overall effectiveness on the time slot assignment process.

Marco Casazza, Alberto Ceselli, Lucas Létocart
Robust Scheduling with Logic-Based Benders Decomposition

We study project scheduling at a large IT services delivery center in which there are unpredictable delays. We apply robust optimization to minimize tardiness while informing the customer of a reasonable worst-case completion time, based on empirically determined uncertainty sets. We introduce a new solution method based on logic-based Benders decomposition. We show that when the uncertainty set is polyhedral, the decomposition simplifies substantially, leading to a model of tractable size. Preliminary computational experience indicates that this approach is superior to a mixed integer programming model solved by state-of-the-art software.

Elvin Coban, Aliza Heching, J. N. Hooker, Alan Scheller-Wolf
Optimal Adaptation Process of Emergency Medical Services Systems in a Changing Environment

Quality of emergency medical services (EMS) depends on the EMS infrastructure which is subject to exogenous conditions, like the considered demand area. Demographic changes, increased traffic volume, and structural modifications in the urban infrastructure lead to permanent changes in the demand area. To provide high EMS quality in a strategic perspective, an adaptive planning system to consider these future environmental changes is necessary. An anticipatory adaptation process based on the existing EMS infrastructure and anticipating future developments has to be determined. Assessment criteria of an adaptation process include (1) EMS quality, (2) periodic operating costs, and (3) system adaptation costs. A linear multi-criteria program is developed to support EMS decision makers to dynamically improve an existing EMS infrastructure with respect to multiple requirements during a strategic time horizon.

Dirk Degel
Strategic Network Planning of Recycling of Photovoltaic Modules

Due to high subsidies, the installed capacity of photovoltaic (PV) in Germany steeply increased in the last years. Considering an expected lifetime of 20–25 years the related amount of PV waste will increase during the next decades. Thus, PV modules have been integrated into the WEEE directive in 2012. In order to fulfil the WEEE recycling and recovery quotas, it will be sufficient to recover the raw materials with the highest mass, i.e. glass and aluminium. However, with new technologies under development, it will be possible to recover also other rare strategic materials with limited availability in Germany, like silver, copper or indium. Against this background, the aim is to develop a strategic planning approach to analyse the early installation of appropriate collection and recycling infrastructures with the focus on resource criticalities. In order to do so, a multi-period MILP is developed regarding capacity, technology and location decisions for collection and recycling facilities of PV modules. Decisions are evaluated with regard to economic aspects. Additionally, information on resource criticalities derived from criticality indicators are integrated. A case study illustrates the approach and its results.

Eva Johanna Degel, Grit Walther
Designing a Feedback Control System via Mixed-Integer Programming

Pure analytical or experimental methods can only find a control strategy for technical systems with a fixed setup. In former contributions we presented an approach that simultaneously finds the optimal topology and the optimal open-loop control of a system via Mixed Integer Linear Programming (MILP). In order to extend this approach by a closed-loop control we present a Mixed Integer Program for a time discretized tank level control. This model is the basis for an extension by combinatorial decisions and thus for the variation of the network topology. Furthermore, one is able to appraise feasible solutions using the global optimality gap.

Lena C. Altherr, Thorsten Ederer, Ulf Lorenz, Peter F. Pelz, Philipp Pöttgen
Fair Cyclic Roster Planning—A Case Study for a Large European Airport

Airport ground staff scheduling has been long known as one of the most challenging and successful application of operations research. In this presentation, we will concentrate on one type of rostering known as cyclic roster. Numerous aspects required in practice have to be taken into account, amongst others crew qualification, work locations and the travel time between each location, government regulations and labor agreements, etc. INFORM’s branch-and-price solution approach covers all of these aspects and is in use on many airports world-wide. Cyclic Rosters cover several fairness aspects by construction. In this case study we will discuss why one of our customers wanted to add additional fairness criteria to the roster. We show which new fairness requirements are needed. We present a fast local search post-processing step that transforms a cost optimal shift plan into a fair cyclic shift plan with the same costs. The transformed plans are highly accepted and are in operational use.

Torsten Fahle, Wolfgang Vermöhlen
Why Does a Railway Infrastructure Company Need an Optimized Train Path Assignment for Industrialized Timetabling?

Today’s timetabling process of German rail freight transport is a handicraft make-to-order process. Train paths are only planned when operators apply for specific train services including specific train characteristics such as train weight, train length, accelerating and braking power, etc. What seems customer-friendly, has indeed many disadvantages: frequent mismatch of demand and supply, long customer response times and general lack of service level differentiation for the train operators; inefficient use of network capacity and timetabling resources for the rail infrastructure manager. Modern and industrialized supply chain concepts do not feature pure make-to-order processes but often prefer a mix of maketo-stock/make-to-order processes, namely assemble-to-order processes. The paper shows how an assemble-to-order process can eliminate the aforementioned disadvantages of today’s make-to-order process in rail freight timetabling. It then focuses on the assembly phase of the new process and gives a basic introduction to the underlying optimization model. Some test scenarios illustrate the performance of the optimization model.

Matthias Feil, Daniel Pöhle
A Polyhedral Study of the Quadratic Traveling Salesman Problem

In this paper we summarize some of the results of the author’s Ph.D.-thesis. We consider an extension of the traveling salesman problem (TSP). Instead of each path of two nodes, an arc, the costs depend on each three nodes that are traversed in succession. As such a path of three nodes, a 2-arc, is present in a tour if the two corresponding arcs are contained in that tour, we speak of a quadratic traveling salesman problem (QTSP). This problem is motivated by an application in biology, special cases are the TSP with reload costs as well as the angular-metric TSP. Linearizing the quadratic objective function, we derive a linear integer programming formulation and present a polyhedral study of the associated polytope. This includes the dimension as well as three groups of facet-defining inequalities. Some are related to the Boolean quadric polytope and some forbid conflicting configurations. Furthermore, we describe approaches to strengthen valid inequalities of TSP in order to get stronger inequalities for QTSP.

Anja Fischer
New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem

We investigate a heuristic for the two-dimensional rectangular strip packing problem that constructs a feasible two-dimensional packing by placing one-dimensional cutting patterns obtained by solving the horizontal one-dimensional bar relaxation. To represent a solution of the strip packing problem, a solution of a horizontal bar relaxation has to satisfy, among others, the vertical contiguous condition. To strengthen the one-dimensional horizontal bar relaxation with respect to that vertical contiguity new inequalities are formulated. Some computational results are also reported.

Isabel Friedow, Guntram Scheithauer
Representing Production Scheduling with Constraint Answer Set Programming

Answer Set Programming and Constraint Programming constitute declarative programming approaches with different strengths which have already been shown to be highly effective for many hard combinatorial problems. In this article we discuss two hybrid Constraint Answer Set Programming approaches with regard to their suitability for encoding production scheduling problems. Our exemplifications are done on the basis of a production scheduling problem of Infineon Technologies Austria AG.

Gerhard Friedrich, Melanie Frühstück, Vera Mersheeva, Anna Ryabokon, Maria Sander, Andreas Starzacher, Erich Teppan
Day-Ahead Versus Intraday Valuation of Flexibility for Photovoltaic and Wind Power Systems

This paper takes the perspective of a photovoltaic (PV) or wind power plant operator who wants to optimally allocate demand-side flexibility to maximize realizable production value. We compare two allocation alternatives: (1) use of flexible loads to maximize relative day-ahead market value by shifting the portfolio balance in view of day-ahead prices; (2) use of flexible loads in intraday operations to minimize the costs incurred when balancing forecast errors. We argue that the second alternative yields a greater average value than the first in continuous-trade intraday markets. The argument is backed by a market data analysis for Germany in 2013.

Ernesto Garnier, Reinhard Madlener
A Real Options Model for the Disinvestment in Conventional Power Plants

The liberalization of the energy market and the promotion of renewables lead to difficulties in the profitable operation even of many modern conventional power plants. Although such state-of-the-art plants are highly energy-efficient, they are often underutilized or even mothballed. Decisions about further operation or shut-down of these conventional power plants are in most cases characterized as being irreversible, implying uncertainty about future rewards, and being flexible in timing. A useful approach for evaluating (dis-)investment projects with uncertainties is the real options approach (ROA) [2, 14]. This valuation technique is based on option pricing methods used in finance that have been developed by Black, Scholes, and Merton [1, 11]. In the last two decades, real options models have been widely applied to analyze investment decisions under dynamic market conditions. In recent years, however, also the analysis of disinvestment decisions considering market uncertainties has gained in importance (e.g. in studies on the agricultural and dairy sector). Moreover, ignoring disinvestment options in decision-making processes can lead to incorrect valuations of investment strategies at the firm level. In this paper, we develop a real options model for the disinvestment in conventional power plants, with the aim of determining the optimal timing for the shut-down of unprofitable power plants.

Barbara Glensk, Christiane Rosen, Reinhard Madlener
Political Districting for Elections to the German Bundestag: An Optimization-Based Multi-stage Heuristic Respecting Administrative Boundaries

According to the legal requirements for Elections to the German Bundestag the problem of partitioning Germany into electoral districts can be formulated as a multi-criteria graph partition problem. To solve this regularly current problem, an optimization-based heuristic is introduced and successfully applied to German population data.

Sebastian Goderbauer
Duality for Multiobjective Semidefinite Optimization Problems

In this note we introduce a new multiobjective dual problem for a given multiobjective optimization problem consisting in the vector minimization with respect to the corresponding positive semidefinite cone of a matrix function subject to both geometric and semidefinite inequality constraints.

Sorin-Mihai Grad
Algorithms for Controlling Palletizers

Palletizers are widely used in delivery industry. We consider a large palletizer where each stacker crane grabs a bin from one of k conveyors and position it onto a pallet located at one of p stack-up places. All bins have the same size. Each pallet is destined for one customer. A completely stacked pallet will be removed automatically and a new empty pallet is placed at the palletizer. The FIFO Stack-Up problem is to decide whether the bins can be palletized by using at most p stack-up places. We introduce a digraph and a linear programming model for the problem. Since the FIFO Stack-Up problem is computational intractable and is defined on inputs of various informations, we study the parameterized complexity. Based on our models we give xp-algorithms and fpt-algorithms for various parameters, and approximation results for the problem.

Frank Gurski, Jochen Rethmann, Egon Wanke
Capital Budgeting Problems: A Parameterized Point of View

A fundamental financial problem is budgeting. A firm is given a set of financial instruments $$X=\{x_1,\ldots ,x_n\}$$X={x1,…,xn} over a number of time periods T. Every instrument $$x_i$$xi has a return of $$r_i$$ri and for time period $$t=1,\ldots ,T$$t=1,…,T a price of $$p_{t,i}$$pt,i. Further for every time period t there is budget $$b_t$$bt. The task is to choose a portfolio $$X'$$X′ from X such that for every time period $$t=1,\ldots ,T$$t=1,…,T the prices of the portfolio do not exceed the budget $$b_t$$bt and the return of the portfolio is maximized. We study the fixed-parameter tractability of the problem. For a lot of small parameter values we obtain efficient solutions for the capital budgeting problem. We also consider the connection to pseudo-polynomial algorithms.

Frank Gurski, Jochen Rethmann, Eda Yilmaz
How to Increase Robustness of Capable-to-Promise
A Numerical Analysis of Preventive Measures

Reliable delivery date promises offer supply chains a chance to differentiate from competitors. Order planning therefore not only aims at short-term profit maximization, but also at robustness. For planning purposes different preventive measures are proposed to enhance robustness if order- and resource-related uncertainty is present. With regard to profit and robustness this paper analyzes the interaction of preventive measures applied in capable-to-promise approaches.

Ralf Gössinger, Sonja Kalkowski
An Iterated Local Search for a Re-entrant Flow Shop Scheduling Problem

This paper discusses a re-entrant permutation flow shop scheduling problem with missing operations. The two considered objective functions are makespan and total flow time. Re-entrant flows are characterized by a multiple processing of jobs on more than one machine. We propose a heuristic for solving the problem. Since there have been promising approaches in literature on other scheduling problems, we chose the iterated local search (ILS). This meta-heuristic framework combines the advantages of local search algorithm and still tries to avoid being stuck in local optima by a so called shaking step. The initial solution for the ILS is obtained by a dispatching rule. Various rules have been tested, e.g., total job processing time and total processing time of job levels. A hill climbing algorithm has been implemented as the integrated local search method of the ILS. The ILS is compared to a MIP formulation from literature. The results show, that the ILS can deliver better results.

Richard Hinze, Dirk Sackmann
Selecting Delivery Patterns for Grocery Chains

On a tactical level retailers face the problem of determining on which weekdays stores should be delivered, and of setting a frame for short-term vehicle routing. We therefore propose a binary program that considers the decision-relevant costs and capacities at the distribution center, in transportation and instore. To resolve the trade-off between the different cost components aligned to the delivery pattern decision, we propose a sequential solution approach. A numerical example illustrates first results.

Andreas Holzapfel, Michael Sternbeck, Alexander Hübner
Towards a Customer-Oriented Queuing in Service Incident Management

The provision of services hinges considerably on the contribution of the provider and the customer and—if present—on their involved networks. In this paper we focus on incident management—a service domain that is highly relevant for all kinds of industries and is described from a provider internal perspective in the ITIL documentation.

Peter Hottum, Melanie Reuter-Oppermann
A Lagrangian Relaxation Algorithm for Modularity Maximization Problem

Modularity proposed by Newman and Girvan is one of the most common measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. We formulate the modularity maximization problem as a set partitioning problem, and propose an algorithm based on the Lagrangian relaxation. To alleviate the computational burden, we use the column generation technique.

Kotohumi Inaba, Yoichi Izunaga, Yoshitsugu Yamamoto
Row and Column Generation Algorithm for Maximization of Minimum Margin for Ranking Problems

We consider the ranking problem of learning a ranking function from the data set of objects each of which is endowed with an attribute vector and a ranking label chosen from the ordered set of labels. We propose two different formulations: primal problem, primal problem with dual representation of normal vector, and then propose to apply the kernel technique to the latter formulation. We also propose algorithms based on the row and column generation in order to mitigate the computational burden due to the large number of objects.

Yoichi Izunaga, Keisuke Sato, Keiji Tatsumi, Yoshitsugu Yamamoto
Dual Sourcing Inventory Model with Uncertain Supply and Advance Capacity Information

We model a periodic review, single stage dual sourcing inventory system with non-stationary stochastic demand, where replenishment can occur either through a regular stochastic capacitated supply channel with immediate delivery and/or an alternative uncapacitated supply channel with a longer fixed lead time. We focus on describing a situation in which upfront information on capacity availability of an unreliable supply channel is available, denoted as advance capacity information (ACI), to the customer. We derive the optimal dynamic programming formulation and we show some of the properties of the optimal policy by carrying out a numerical analysis. Additionally, our numerical results on the benefits of dual sourcing and the value of sharing ACI reveal several managerial insights.

Marko Jakšič
Integrated Line Planning and Passenger Routing: Connectivity and Transfers

The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. In this paper we show that analysing the connectivity aspect of a line plan gives a new idea how to integrate a transfer handling.

Marika Karbstein
Robust Discrete Optimization Problems with the WOWA Criterion

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing all possible vectors of the costs which may occur. In order to choose a solution the Weighted Ordered Weighted Averaging aggregation operator (WOWA) is used. The WOWA operator allows decision makers to take both their attitude towards the risk and subjective probabilities for scenarios into account. The complexity of the problem is described and an approximation algorithm with some guaranteed worst case ratio is constructed.

Adam Kasperski, Paweł Zieliński
Robust Single Machine Scheduling Problem with Weighted Number of Late Jobs Criterion

This paper deals with a single machine scheduling problem with the weighted number of late jobs criterion, where some job parameters, such as: processing times, due dates, and weights, may be uncertain. This uncertainty is modeled by specifying a scenario set containing all vectors of the job parameters, called scenarios, which may occur. The min-max criterion is adopted to compute a solution under uncertainty. In this paper some of the recent negative complexity and approximability results for the problem are extended and strengthened. Moreover, some positive approximation results for the problem in which the maximum criterion is replaced with the OWA operator are presented.

Adam Kasperski, Paweł Zieliński
Price of Anarchy in the Link Destruction (Adversary) Model

In this model of network formation, players anticipate the destruction of one link, which is chosen according to a known probability distribution. Their cost is the cost for building links plus the expected number of other players to which connection will be lost as a result of the link destruction. We consider different equilibrium concepts (Nash equilibrium, pairwise Nash equilibrium, pairwise stability) and two different ways in which the probability distribution depends on the network.

Lasse Kliemann
Decision Support System for Week Program Planning

This contribution aims to give an overview of the research issue on weekly program filling in the automotive industry and presents an approach to improve this process by using a logistic assistance system. This system supports a dispatcher at choosing customer orders for a production week and takes into account the large amount of restrictions. Finally, results of the heuristic used are presented.

Benjamin Korth, Christian Schwede
On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies

We consider a problem of multi-product lot-sizing and scheduling where each product can be produced by a family of alternative multi-machine technologies. Multi-machine technologies require one or more machine at the same time. A sequence dependent setup time is needed between different technologies. The criterion is to minimize the makespan. Preemptive and non-preemptive versions of the problem are studied. We formulate mixed integer linear programming models based on a continuous time representation for both versions of the problem. Using these models, the polynomially solvable cases of the problem are found. It is proved that the problem without setup times is strongly NP-hard if there is only one product, and each technology occupies at most three machines. Besides that, problem cannot be approximated within a practically relevant factor of the optimum in polynomial time, if P $$\ne $$≠ NP.

Anton V. Eremeev, Julia V. Kovalenko
Condition-Based Maintenance Policies for Modular Monotic Multi-state Systems

In this work, we consider a modular monotonic multi-state system, i.e., a system with several components evolving in different states, where the maintenance of a component cannot impair the performance of the system. A structure function provides the system performance depending on the states of its components. Furthermore, we suppose that for each component, the deterioration over time can be described by a deterministic or stochastic process with known properties. The amount of money to be spent on the components’ maintenance is limited by a given budget. A loss in the system performance results in opportunity costs. We try to find a component-specific maintenance policy which minimizes the opportunity cost over a finite planning horizon.

Michael Krause
An Optimization Model and a Decision Support System to Optimize Car Sharing Stations with Electric Vehicles

An increasing environmental awareness, rising energy cost, progressing urbanization, and shortage of space cause to rethink individual mobility behavior and personal car ownership in cities. Car sharing is a sustainable mobility concept that allows individuals to satisfy their mobility needs without owning a car and addresses modern mobility. Car sharing is particularly suitable to cover medium-range distances and can be linked to the public transport of major cities (intermodal mobility). Within this context, the integration of electric vehicles represents an opportunity to further protect the environment and potentially save energy cost. In order to create an efficient car sharing transportation network, the location of stations, the number of vehicles and the availability of electric fast charging infrastructure are critical success factors. We provide a decision support system (DSS) to plan and optimize car sharing stations for electric vehicles. An optimization model and the DSS OptCarShare 1.1 enable to optimize stations and visualize results. Parameters, such as the annual lease payment for charging infrastructure, the expected travel time of consumers, the charging time of electric vehicles dependent on available charging infrastructure, affect the decision variables such as the number of car sharing stations, vehicles and fast chargers. On the basis of evaluations and benchmarks for the cities of Hannover and Zürich, we establish generalizations for the parameters of the model. The results show a high impact of fast chargers (half an hour to fill 80 % of the battery) on the current model and the optimal solution.

Kathrin S. Kühne, Tim A. Rickenberg, Michael H. Breitner
Optimising Energy Procurement for Small and Medium-Sized Enterprises

Increasing energy prices present a challenging task for small and medium-sized enterprises (SMEs). Since the availability of energy plays a crucial role in running the day-to-day business, this paper focuses on energy procurement of SMEs. Due to limited financial and human resources, SMEs find it difficult to implement measures to reduce energy costs. It is shown that a sustainable reduction of energy purchase prices can be achieved by choosing an appropriate procurement strategy. We develop a quantitative optimisation model that takes into account specific needs of SMEs. The aim of the model is to minimise energy purchase costs while assuring that demand is fulfilled at all times. Uncertainty regarding future energy prices and consumption is modelled by considering different scenarios for the evolution of uncertain parameters. A minimax regret approach is used to determine a robust selection of purchase contracts. For strategic decision support, a robust optimisation model is particularly well-suited to choose a risk-averse procurement strategy. In an exemplary case study, different procurement strategies are compared. Computational results show that a structured energy procurement concept has a high potential to significantly reduce energy costs if SMEs are willing to take over volume and price risk.

Nadine Kumbartzky, Brigitte Werners
Approximation Schemes for Robust Makespan Scheduling Problems

Makespan Parallel Machine and Flow Shop Scheduling belong to the core of the polynomial optimization problems. Both problems are well studied and they are known to be NP-hard, thus no optimal polynomial time algorithm exists under certain theoretical assumptions. In this paper we present a Polynomial Time Approximation Scheme for the generalized Min-Max version of the problems and the Competitive Ratio Approximation Scheme for the online counterpart of considered problems. All the presented algorithms work in linear time in the input size.

Adam Kurpisz
The Price of Fairness for a Small Number of Indivisible Items

We consider the price of fairness for the allocation of indivisible goods. For envy-freeness as fairness criterion it is known from the literature that the price of fairness can increase linearly in terms of the number of agents. For the constructive lower bound a quadratic number of items was used. In practice this might be inadequately large. So we introduce the price of fairness in terms of both the number of agents and items, i.e., key parameters which generally may be considered as common and available knowledge. It turns out that the price of fairness increases sublinearly if the number of items is not too much larger than the number of agents. For the special case of conformity of both counts, exact asymptotics are determined. Additionally, an efficient integer programming formulation is given.

Sascha Kurz
Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty

This article provides an overview of the author’s dissertation (Kutschka, Ph.D. thesis, RWTH Aachen University, 2013 [10]). In the thesis, we consider mathematical optimization under data uncertainty using MIP techniques and following the robust optimization approach. We investigate four robustness concepts, their parametrization, application, and evaluation. The concepts are $$\varGamma $$Γ-robustness, its generalization multi-band robustness, the novel more general submodular robustness, and the two-stage recoverable robustness. We investigate the corresponding robust generalizations of the knapsack problem (KP) presenting IP formulations, detailed polyhedral studies including new classes of valid inequalities, and algorithms. In particular, for the submodular KP, we establish a connection to polymatroids and for the recoverable robust KP, we develop a nontrivial compact reformulation and carry out detailed computational experiments. Further, we consider the $$\varGamma $$Γ-robust and multi-band brobust generalizations of the network design problem (NDP) presenting MIP formulations, new detailed polyhedral insights with new classes of valid inequalities, and algorithms. For example, we derive alternative formulations for these robust NDPs by generalizing metric inequalities. Furthermore, we present representative computational results for the $$\varGamma $$Γ-robust NDP using real-life measured uncertain data from telecommunication networks based on our work with the German ROBUKOM project.

Manuel Kutschka
An Insight to Aviation: Rostering Ground Personnel in Practice

Numerous dynamic, interdependent processes exist at an airport. These processes are highly affected by uncertain events as changing flight schedules, delays, or weather conditions. Naturally a flexible workforce management is needed to support such operation. Airlines, airports, and ground handlers provide the necessary workforce to meet this demand. But legal requirements, union agreements and company policies define the flexibility of workforce planning and utilization in practice. Nevertheless a valid (monthly) roster matching the supply with demand under all these requirements has to be prepared usually several weeks before the day of operation. In this paper we discuss the optimization challenges to create monthly rosters for ground personnel at an airport. We give examples of typical constraints, point out characteristics of different work areas at an airport, and how this affects the rostering. Further we present how rostering is solved by our branch-and-price solution methodology in practice. Using this approach, we report on our real world experience with optimized rostering in airport ground handling.

Manuel Kutschka, Jörg Herbers
Consensus Information and Consensus Rating
A Note on Methodological Problems of Rating Aggregation

Quantifying credit risk with default probabilities is a standard technique for financial institutes, investors or rating agencies. To get a higher precision of default probabilities, one idea is the aggregation of different available ratings (i.e. default probabilities) to a so called ‘consensus rating’. But does the concept of ‘consensus rating’ really make sense? What is a ‘real’ consensus rating? This paper tries to clarify under which conditions a consensus rating exists. Therefore, the term of ‘consensus information’ is used. This leads to a concept that deals with the precision of aggregated rating characteristics. Within this framework the problem of misinformation resp. contradictory information is addressed. It is shown that consensus information is not necessarily more informative than individual information. Furthermore, the aggregation aspects are discussed from a statistical perspective.

Christoph Lehmann, Daniel Tillich
Integration of Prospect Theory into the Outranking Approach PROMETHEE

Outranking methods as a specific application of Multi-Criteria Decision Analysis (MCDA) are applied to structure complex decision problems as well as to elicitate the decision makers preferences. Therefore, a consideration of behavioral effects within outranking-methods seems to be meaningful. Several behavioral effects and biases have been identified in previous studies, however, only few approaches exist to consider such behavioral issues within the application of MCDA-methods explicitly. The prospect theory developed by Kahneman and Tversky (1979) represents one of the most prominent theories from behavioural decision theory. Their findings concerning the decision behaviour of humans, e.g. loss aversion or reference dependency, are broadly supported and confirmed through a variety of empirical research. Hence, the aim of the presented paper is to integrate these elements from prospect theory within the outranking approach PROMETHEE. For that purpose, an additional discrete reference alternative is incorporated. A case study concerning the sustainable usage of biomass for energy conversion illustrates the new developed method.

Nils Lerche, Jutta Geldermann
Multistage Optimization with the Help of Quantified Linear Programming

Quantified linear integer programs (QIPs) are linear integer programs (IPs) 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 of feasible QIPs 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 order to solve the QIP optimization problem, where the task is to find an especially attractive winning strategy, we examine the problem’s hybrid nature and combine linear programming techniques with solution techniques from game-tree search.

T. Ederer, U. Lorenz, T. Opfer, J. Wolf
Analysis of Ambulance Location Models Using Discrete Event Simulation

The quality of a rescue service system is typically evaluated ex post by the proportion of emergencies reached within a predefined response time threshold. Optimization models in literature consider different variants of demand area coverage or busy fractions and reliability levels as a proxy for Emergency Medical Service quality. But no comparisons of the mentioned models with respect to their real-world performance are found in literature. In this paper, the influence of these different model formulations on real-world outcome measures is analyzed by means of a detailed discrete event simulation study.

Pascal Lutter, Dirk Degel, Lara Wiesche, Brigitte Werners
Tight Upper Bounds on the Cardinality Constrained Mean-Variance Portfolio Optimization Problem Using Truncated Eigendecomposition

The mean-variance problem introduced by Markowitz in 1952 is a fundamental model in portfolio optimization up to date. When cardinality and bound constraints are included, the problem becomes NP-hard and the existing optimizing solution methods for this problem take a large amount of time. We introduce a core problem based method for obtaining upper bounds to the mean-variance portfolio optimization problem with cardinality and bound constraints. The method involves performing eigendecomposition on the covariance matrix and then using only few of the eigenvalues and eigenvectors to obtain an approximation of the original problem. A solution to this approximate problem has a relatively low cardinality and it is used to construct a core problem. When solved, the core problem provides an upper bound. We test the method on large-scale instances of up to 1000 assets. The obtained upper bounds are of high quality and the time required to obtain them is much less than what state-of-the-art mixed integer softwares use, which makes the approach practically useful.

Fred Mayambala, Elina Rönnberg, Torbjörn Larsson
Scheduling Identical Parallel Machines with a Fixed Number of Delivery Dates

We consider the scheduling problem of a manufacturer that has to process a set of jobs on identical parallel machines where jobs can only be delivered at a given number of delivery dates and the total tardiness is to be minimized. In order to avoid tardiness, jobs have to be both, processed and delivered before or at their due dates. Such settings are frequently found in industry, for example when a manufacturer relies on a logistics provider that picks up completed jobs twice a day. The scheduling problem with fixed delivery dates where the delivery dates are considered as an exogenously given parameter for the manufacturer’ scheduling decisions can be solved by various optimal and heuristic solution procedures. Here, we consider a variant of this problem where only the number of deliveries is fixed and the delivery dates can be set arbitrarily. For example, a manufacturer may be entitled to assign the logistics provider two pick-up times per day and decide on the exact times of these pick-ups. Then, the machine schedule and the delivery dates can be determined simultaneously which may significantly improve adherence to due dates. Our findings can provide valuable input when it comes to evaluating and selecting distribution strategies that offer a different extent of flexibility regarding the delivery dates.

Arne Mensendiek, Jatinder N. D. Gupta
Kinetic Models for Assembly Lines in Automotive Industries

We discuss a newMichailidis, Lena model for automotiveHerty, Michael production basedZiegler, Marcus on kinetic partial differential equations. Some theoretical analysis as well as numerical results are presented.

Lena Michailidis, Michael Herty, Marcus Ziegler
Optimization of Vehicle Routes with Delivery and Pickup for a Rental Business: A Case Study

Optimization of vehicleMorito, Susumu routes with deliveryInoue, Tatsuki and pickupNakahara, Ryo for aHirota, Takuya rental industry is considered. The company delivers to or pickups from customers rented products. Several types of products exist, and customers rent the specified number of products of the specific type. Time windows exist for delivery and pickup. There exist two sizes of vehicles, and their trips start from and end at depot and vehicles can make several trips during a day. Delivery must precede pickup on any trip of a vehicle. Capacity of vehicles depends on product type and also on how products are loaded on vehicles. Depending on demand quantity, split deliveries/pickups may be necessary. The company wants to minimize the total transportation cost. Based on the fact that the total number of distinct trips is rather small due to limited capacity of the vehicles, our solution strategy first enumerates all possible trips. Routes (i.e., collection of trips) are obtained by assigning trips to vehicles so that the total cost is minimized subject to constraints on demand, an upper limit on the number of trips per vehicle, and time compatibility of trips assigned to each vehicle. Since there exist many time compatibility constraints, the problem is first solved without them, we then check the compatibility and if necessary add compatibility constraints, and the problem is solved again until all routes become time compatible. Computational performance of the proposed solution approach is evaluated.

Susumu Morito, Tatsuki Inoue, Ryo Nakahara, Takuya Hirota
An Ant Colony System Adaptation to Deal with Accessibility Issues After a Disaster

One of the mainMuñoz, Héctor problems relief teamsJiménez-Martín, Antonio face after a naturalMateos, Alfonso or man-made disaster is how to plan rural road repair work to take maximum advantage of the limited available financial and human resources. In this paper we account for the accessibility issue, that is, to maximize the number of survivors that reach the nearest regional center in a minimum time by planning which rural roads should be repaired given the available financial and human resources. This is a combinatorial problem and we propose a first approach to solve it using an ant colony system adaptation. The proposed algorithm is illustrated by means of an example, and its performance is compared with the combination of two metaheuristics, GRASP and VNS.

Héctor Muñoz, Antonio Jiménez-Martín, Alfonso Mateos
Modelling and Solving a Train Path Assignment Model

We introduceNachtigall, Karl a binary linear modelOpitz, Jens for solving the train path assignment problem. For each train request a train path has to be constructed from a set of predefined path parts within a time-space network. For each possible path we use a binary decision variable to indicate, whether the path is used by the train request. Track and halting capacity constraints are taken into account. We discuss different objective functions, like maximizing revenue or maximizing total train path quality. The problem is solved by using column generation within a branch and price approach. This paper gives some modeling and implementation details and presents computational results from real world instances.

Karl Nachtigall, Jens Opitz
A New Approach to Freight Consolidation for a Real-World Pickup-and-Delivery Problem

During courierNowak, Curt and express providers’ operationalHahne, Felix scheduling, vehicles areAmbrosi, Klaus assigned to customer orders. This task is complex, combinatorially comprehensive, and contains aspects that defy modeling within reasonable effort, e.g. due to a lack of structured data. Hence, a fully automated solution cannot be achieved. In practice, human dispatchers often use dialog-oriented decision support systems (DSS). These systems generate recommendations from which the human dispatchers select the most profitable one, while additionally taking into account domain-specific knowledge. Solutions that consolidate the freight of multiple customer orders onto a single vehicle are usually particularly favorable. Generally, consolidating leads to a higher degree of vehicle capacity utilization, which in turn increases cost effectiveness and lowers the resulting environmental damage. We present a new recursive heuristic for this scenario based on the well-known savings algorithm. A central parameter of the algorithm limits the number of interdependent single tours. Through the appropriate setting of this parameter, one can control the results’ complexity and ensure their transparency and acceptance by human dispatchers. Using real-world data benchmarks, we prove the effectiveness of our algorithm empirically.

Curt Nowak, Felix Hahne, Klaus Ambrosi
High Multiplicity Scheduling with Switching Costs for Few Products

We studyGabay, MichaëlseveralGrigoriev, AlexandervariantsKreuzen, Vincent J.C. of the singleOosterwijk, Tim machine capacitated lot sizing problem with sequence-dependent setup costs and product-dependent inventory costs. Here we are given one machine and $$n \ge 1$$n≥1 types of products that need to be scheduled. Each product is associated with a constant demand rate $$d_i$$di, production rate $$p_i$$pi and inventory costs per unit $$h_i$$hi. When the machine switches from producing product i to product j, setup costs $$s_{i,j}$$si,j are incurred. The goal is to minimize the total costs subject to the condition that all demands are satisfied and no backlogs are allowed. In this work, we show that by considering the high multiplicity setting and switching costs, even trivial cases of the corresponding “normal” counterparts become non-trivial in terms of size and complexity. We present solutions for one and two products.

Michaël Gabay, Alexander Grigoriev, Vincent J. C. Kreuzen, Tim Oosterwijk
Sampling-Based Objective Function Evaluation Techniques for the Orienteering Problem with Stochastic Travel and Service Times

StochasticPapapanagiotou, VassilisCombinatorialMontemanni, Roberto Optimization ProblemsGambardella, Luca Maria are of great interest because they can model some quantities more accurately than their deterministic counterparts. However, the element of stochasticity introduces intricacies that make the objective function either difficult to evaluate or very time-consuming. In this paper, we propose and compare different sampling-based techniques for approximating the objective function for the Orienteering Problem with Stochastic Travel and Service Times.

Vassilis Papapanagiotou, Roberto Montemanni, Luca Maria Gambardella
Optimized Pattern Design for Photovoltaic Power Stations

The task of planning photovoltaic (PV) powerBischoff, MartinplantsKlug, Alena is veryKüfer, Karl-HeinzchallengingPlociennik, Kai. The decisionSchüle, Ingmar makers have to consider the local weather conditions, the land area’s topography, the physical behavior of the technical components and many more complex aspects. We present an approach for optimizing one variant of the way routing problem for PV plants. We formulate the problem as an Integer Program (IP) which can be solved by standard solvers. In addition, we reformulate the IP as a maximum independent set problem on interval graphs. This graph-theoretic problem can be solved in polynomial time. Using the latter approach, we are able to generate a variety of solutions with different angles for the ways with little effort of time.

Martin Bischoff, Alena Klug, Karl-Heinz Küfer, Kai Plociennik, Ingmar Schüle
What Are New Insights Using Optimized Train Path Assignment for the Development of Railway Infrastructure?

The train pathPöhle, Daniel assignment optimizationFeil, Matthias algorithm generates an optimal solution for freight train service applications by connecting available slots between several construction nodes without conflicts. This method is not only used for a real timetable e.g. for the following year but also for timetable-based development of railway infrastructure in long-term scenarios. However, for infrastructure development the actual slot connections are not the main concern in this planning step. The railway infrastructure company rather wants to detect bottlenecks in the infrastructure and needs to get evidence for necessary developments of its railway network. By presenting results of a real world German railway network’s test case, this paper shows which bottlenecks can be derived from an optimized slot assignment and which measures (in timetable and infrastructure) could eliminate the detected bottlenecks. Necessary key figures for discovering bottlenecks will be introduced, too. It is shown that shadow prices of the developed column generation method are a good indicator for the identification of bottlenecks. For the first time with the comparison of different scenarios one can deliver a clear monetary benefit for the removal of a single bottleneck, e.g. the revenue advantage of an additional track for dwelling of freight trains. Hence, using the developed optimization algorithm for train path assignment leads to new useful insights for a railway infrastructure company to develop its railway network.

Daniel Pöhle, Matthias Feil
The Cycle Embedding Problem

Given two hypergraphs, representingBorndörfer, Ralf a fineKarbstein, Marika and a coarseMehrgardt, Julika “layer”, and a cycleReuther, MarkuscoverSchlechte, Thomas of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer programming formulation for the CEP that provides a complete description of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.

Ralf Borndörfer, Marika Karbstein, Julika Mehrgardt, Markus Reuther, Thomas Schlechte
Dispatch of a Wind Farm with a Battery Storage

The combinationRied, Sabrina of a windReuter-Oppermann, MelaniefarmJochem, Patrick with a batteryFichtner, Wolf storage allows to schedule the system in a more balanced way, alleviating natural wind power fluctuations. We present a mathematical model that optimizes the contribution margin (CM) of a system that consists of a wind farm and a lithium-ion battery storage from an operator’s perspective. We consider the system to take part in the electricity stock exchange. We discuss adaptions of the model when additional participation at the minute reserve market is possible. We construct a test instance for the model for Germany and compare the optimal solutions to two reference cases. We evaluate if the gain of an integrated wind battery system compensates the investment and operating costs for the storage and we derive target prices for the battery system.

Sabrina Ried, Melanie Reuter-Oppermann, Patrick Jochem, Wolf Fichtner
Exact Algorithms for the Vehicle Routing Problem with Soft Time Windows

This paper studiesGambardella, Luca Maria a variantSalani, Matteo of the VehicleBattarra, Maria Routing Problem with Soft Time Windows (VRPSTW) inspired by real world distribution problems. Soft time windows constraints are very common in the distribution industry, but quantifying the trade-off between routing cost and customer inconvenience is a hard task for practitioners. In our model, practitioners impose a minimum routing cost saving (to be achieved with respect to the hard time windows solutions) and ask for the minimization of the customer inconvenience only. We propose two exact algorithms. The first algorithm is based on standard branch-and-cut-and-price. The second algorithm uses concepts of bi-objective optimization and is based on the bisection method.

Matteo Salani, Maria Battarra, Luca Maria Gambardella
Impact of Heat Storage Capacity on CHP Unit Commitment Under Power Price Uncertainties

Combined heatSchacht, Matthias and power (CHP) plants generateWerners, Brigitte heat and power simultaneously leading to a higher efficiency than an isolated production. CHP unit commitment requires a complex operation planning, since power is consumed in the moment of generation. The integration of a heat storage allows a partially power price oriented plant operation, where power is generated especially in times of high market prices. Consequently, an efficient plant operation depends on the accuracy of the anticipated power prices and the flexibility due to storage capacity. This contribution analyzes the effects of short-term uncertainties in power prices on the CHP unit commitment for different heat storage capacities. A simulation study is run to evaluate the financial impact of an inaccurate power price anticipation. Results show that the storage capacity affects the sensitivity of the solution due to stochastic influences. The isolated consideration of long-term uncertainties might result in a suboptimal choice of heat storage capacity. It is recommended, to explicitly consider short-term uncertainties when supporting strategic planning of heat storage capacities.

Matthias Schacht, Brigitte Werners
Optimizing Information Security Investments with Limited Budget

The importance ofSchilling, Andreas information security is constantlyWerners, Brigitte increasing with technology becoming more pervasive every day. As a result, the necessity and demand for practical methods to evaluate and improve information security is particularly high. The aim of this paper is to apply mathematical optimization techniques tool improve information security. According to the identified problem structure, a combinatorial optimization model is established. The objective of the presented approach is to maximize system security by choosing the best combination of security controls limited by available budget. In addition, by performing a What-If analysis and systematic budget variations, the decision maker can get improved insights and thus determine an ideal budget proposition yielding the highest benefit among all possible control configurations. An exemplary case study demonstrates how this approach can be used as a tool within the risk management process of an organization.

Andreas Schilling, Brigitte Werners
Cut-First Branch-and-Price Second for the Capacitated Arc-Routing Problem

The basic multiple-vehicleSchlebusch, Claudiaarc-routingIrnich, Stefan problem is called capacitated arc-routing problem (CARP) and was introduced by Golden and Wong (Networks 11:305–315, 1981 [9]). This paper presents a full-fledged branch-and-price (bap) algorithm for the CARP. In the first phase, the one-index formulation of the CARP is solved in order to produce strong cuts and an excellent lower bound. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. Furthermore, different pricing problem relaxations are analyzed and the construction of new labeling algorithms for their solution is presented. The cut-first branch-and-price second algorithm provides a powerful approach to solve knowingly hard instances of the CARP to proven optimality.

Claudia Schlebusch, Stefan Irnich
Solving a Rich Position-Based Model for Dairy Products

By consideringSchneeberger, Karl the lot-sizingSchilde, MichaelproblemDoerner, Karl F. and the detailed sequencing and scheduling problem simultaneously in a very realistic model formulation we aim to improve the overall performance of the entire production process for a dairy producing company. For this purpose we extended the Position-Based Model introduced by Lütke et al. (Int. J. Prod. Res. 43, 5071–5100, 2005 [5]). Based on a set of real-world production data, we used our model to determine exact solutions to very small problem settings. As even for small instances the time required for obtaining exact solutions is too long in general, we developed a fix&optimize inspired construction heuristic to obtain a feasible solution for several products. The results of our approach show that the solutions obtained are competitive compared to the optimal solution with less time consumption.

Karl Schneeberger, Michael Schilde, Karl F. Doerner
A European Investment and Dispatch Model for Determining Cost Minimal Power Systems with High Shares of Renewable Energy

In this paperPape, Carsten a multistage combined investment and dispatch modelSandau, Fabian for long-termScholz, Angela unit commitment problems of large-scale hydrothermal power systems is presented. It is based on a combination of a continuous and mixed integer programming algorithm as well as Lagrangian relaxation. First, the required capacities of power generation and storage units are determined by a continuous linear program (LP). Second, in an optional stage the unit commitment problem for all investigated market areas, i.e. those of Europe, is solved by a mixed integer linear program (MILP). At last, a MILP solves the same problem with a higher level of detail for a focused subarea.

Angela Scholz, Fabian Sandau, Carsten Pape
Pre-selection Strategies for Dynamic Collaborative Transportation Planning Problems

To improve the competitivenessSchopka, Kristian, small and mid-sizedKopfer, Herbert carriers may ally in coalitions for request exchange. One main barrier is the “carrier-fear” of losing autonomy. A decentralized pre-selection that allows carriers to preserve own transportation requests for the private fleet may limit the information shared within the coalition and increase the autonomy. Several heuristic pre-selection strategies are presented. A computational study analyzes which of those are most qualified.

Kristian Schopka, Herbert Kopfer
Optimal Operation of a CHP Plant for the Energy Balancing Market

For energy companiesSchulz, Katrin with a combined heat and power (CHP) plant and a heat storageHechenrieder, Bastian device, the provisionWerners, Brigitte of balancing power provides additional revenue potential. Balancing power is needed to ensure a stable frequency if current generation differs from demand. In Germany, the responsible transmission system operator procures the needed type of reserve energy through an auction. To participate in the balancing market for minute reserve, energy companies have to submit a bid for a certain time frame of the following day that comprises a price and the amount of electricity at which power generation can be increased or decreased considering the expected load. Therefore, capacity allocation for the balancing market has to be considered simultaneously with the uncertain next day’s unit commitment of the CHP plant and the heat storage device. To support energy companies planning their bids, an optimization model is developed to determine the optimal bidding amount based on a forecasted market clearing price.

Katrin Schulz, Bastian Hechenrieder, Brigitte Werners
Gas Network Extension Planning for Multiple Demand Scenarios

Today’s gas marketsSchweiger, Jonas demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition. We solve MINLP single-scenario sub-problems and obtain valid bounds even without solving them to optimality. Heuristics prove capable of improving the initial solutions substantially. Results of computational experiments are presented.

Jonas Schweiger
Impacts of Electricity Consumers’ Unit Commitment on Low Voltage Networks

Todays electricitySchäuble, JohannesconsumerJochem, Patrick tend to becomeFichtner, Wolf small businesses as they invest in their own decentralized electricity generation and stationary electricity storage as well as in information technology (IT) to connect and organize these new devices. Furthermore, the installed IT allows them at least technically to establish local markets. The variety of consumers and their characteristics implies numerous ways of how they optimize their individual unit commitment. This paper aims to analyze the impact of the individual consumers decisions on a future electricity demand and feed-in on low voltage network level. Therefore, in a first step the different unit commitment problems of the different small businesses have been modeled using linear programming (LP). In a second step these consumers are modeled as learning agents of a multi-agent system (MAS). The MAS comprises a local electricity market in which participants negotiate supply relationships. Finally, using scenarios with different input parameters the resulting impact is studied in detail. Amongst others, the simulations’ results show major changes in electricity demand and feed-in for scenarios with high market penetration of storages.

Johannes Schäuble, Patrick Jochem, Wolf Fichtner
Congestion Games with Multi-Dimensional Demands

Weighted congestionSchütz, Andreas games are an important and extensively studied class of strategic games, in which the players compete for subsets of shared resources in order to minimize their private costs. In my Master’s thesis (Congestion games with multi-dimensional demands. Master’s thesis, Institut für Mathematik, Technische Universität Berlin, 2013, [17]), we introduced congestion games with multi-dimensional demands as a generalization of weighted congestion games. For a constant $$k \in \mathbb {N}$$k∈N, in a congestion game with k-dimensional demands, each player is associated with a k-dimensional demand vector, and resource costs are k-dimensional functions of the aggregated demand vectors of the players using the resource. Such a cost structure is natural when the cost of a resource depends not only on one, but on several properties of the players’ demands, e.g., total weight, total volume, and total number of items. We obtained a complete characterization of the existence of pure Nash equilibria in terms of the resource cost functions for all $$k \in \mathbb {N}$$k∈N. Specifically, we identified all sets of k-dimensional cost functions that guarantee the existence of a pure Nash equilibrium for every congestion game with k-dimensional demands. In this note we review the main results contained in the thesis.

Andreas Schütz
Unit Commitment by Column Generation

The unit commitmentShiina, Takayuki problem is to determineYurugi, Takahiro the schedule of power generating units and the generating levelMorito, Susumu of each unit. The decisionsImaizumi, Jun involve which units to commit at each time period and at what level to generate power to meet the electricity demand. We consider the heuristic column generation algorithm to solve this problem. Previous methods used the approach in which each column corresponds to the start–stop schedule and output level. Since power output is a continuous quantity, it takes time to generate the required columns efficiently. In our proposed approach, the problem to be solved is not a simple set partitioning problem, because the columns generated contain only a schedule specified by 0–1 value. It is shown that the proposed heuristic approach is effective to solve the problem.

Takayuki Shiina, Takahiro Yurugi, Susumu Morito, Jun Imaizumi
Parallel Algorithm Portfolio with Market Trading-Based Time Allocation

We proposeAlba, Enrique a parallel portfolio of metaheuristic algorithms thatParsopoulos, Konstantinos E.adoptsSouravlias, Dimitris a market trading-based time allocation mechanism. This mechanism dynamically allocates the total available execution time of the portfolio by favoring better-performing algorithms. The proposed approach is assessed on a significant Operations Research problem, namely the single-item lot sizing problem with returns and remanufacturing. Experimental evidence suggests that our approach is highly competitive with standard metaheuristics and specialized state-of-the-art algorithms.

Dimitris Souravlias, Konstantinos E. Parsopoulos, Enrique Alba
Global Solution of Bilevel Programming Problems

We discuss the global solution of Bilevel Programming ProblemsSteffensen, Sonja using their reformulations as Mathematical Programs with Complementarity Constraints and/or Mixed Integer Nonlinear Programs. We show that under suitable assumptions the Bilevel Program can be reformulated and globally solved via MINLP refomulation. We also briefly discuss some simplifications and suitable additional constraints.

Sonja Steffensen
Robustness to Time Discretization Errors in Water Network Optimization

Water networkTaheri, Nicole optimization problemsWirth, Fabian R.requireEck, Bradley J.modelingMevissen, Martin the progression of flowShorten, Robert N. and pressure over time. The time discretization step for the resulting differential algebraic equation must be chosen carefully; a large time step can result in a solution that bears little relevance to the physical system, and small time steps impact a problem’s tractability. We show that a large time step can result in meaningless results and we construct an upper bound on the error in the tank pressures when using a forward Euler scheme. We provide an optimization formulation that is robust to this discretization error; robustness to model uncertainty is novel in water network optimization.

Nicole Taheri, Fabian R. Wirth, Bradley J. Eck, Martin Mevissen, Robert N. Shorten
Forecasting Intermittent Demand with Generalized State-Space Model

We proposeTakahashi, Kei a methodFujita, Marina for forecasting intermittent demand with generalized state-spaceMaruyama, KishikomodelAizono, Toshiko using timeAra, Koji series data. Specifically, we employ mixture of zero and Poisson distributions. To show the superiority of our method to the Croston, Log Croston and DECOMP models, we conducted a comparison analysis using actual data for a grocery store. The results of this analysis show the superiority of our method to the other models in highly intermittent demand cases.

Kei Takahashi, Marina Fujita, Kishiko Maruyama, Toshiko Aizono, Koji Ara
Optimal Renewal and Electrification Strategy for Commercial Car Fleets in Germany

In this paperTejada, Ricardo we modelMadlener, Reinhard the uncertainty inherent in oil, electricity, and battery prices, in order to find the optimal renewal strategy for transport fleets in Germany from a car fleet operator’s perspective. We present a comprehensive statistical model of total operating costs for the usage of light duty vehicles in the transport industry. The model takes into consideration current and future power train technologies, such as internal combustion and electric engines. The framework allows for the calculation of sensitivities of the relevant explanatory variables (fuel price, interest rate, inflation rate, economic lifetime, subsidy/tax policies, and economic development). We also calculate and evaluate relevant diffusion scenarios for commercially used e-vehicles.

Ricardo Tejada, Reinhard Madlener
A Time-Indexed Generalized Vehicle Routing Model for Military Aircraft Mission Planning

We introduceVan den Bergh, Jorne a time-indexedQuttineh, Nils-Hassan mixed integer linear programming model for a militaryLarsson, Torbjörn aircraft missionBeliën, Jeroen planning problem, where a fleet of cooperating aircraft should attack a number of ground targets so that the expected effect is maximized. The model is a rich vehicle routing problem and the direct application of a general solver is only practical for scenarios of very moderate sizes. Therefore, a Dantzig–Wolfe decomposition and column generation approach is considered. A column here represents a specific sequence of tasks for one aircraft, and to generate columns, a longest path problem with side constraints is solved. We compare the column generation approach with the time-indexed model with respect to upper bounding quality and conclude that the Dantzig–Wolfe decomposition yields a much stronger formulation of the problem.

Jorne Van den Bergh, Nils-Hassan Quttineh, Torbjörn Larsson, Jeroen Beliën
Adapting Exact and Heuristic Procedures in Solving an NP-Hard Sequencing Problem

The paper on handWiehl, Andreas focuses on the development of computerized solutions for a particular class within the area of shunting yard optimization. Our aim is to determine a humping sequence to shunt freight cars from inbound trains to outbound trains. The objective is to minimize the total weighted tardiness. We present a simple mixed integer problem formulation, two heuristic approaches and an implementation in CPLEX for the study. In addition, we compare the CPU and objective value of the proposed algorithms with the results of CPLEX optimizer in a computational study.

Andreas Wiehl
Strategic Deterrence of Terrorist Attacks

Protection againstWiens, Marcus terrorist threats hasMeng, Sascha become an integralSchultmann, Frank part of organisational and national security strategies. But research on adversarial risks is still dominated by approaches which focus too much on historical frequencies and which do not sufficiently account for the terrorists motives and the strategic component of the interaction. In this paper we model the classical risk analysis approach using a specific variant of adaptive play and compare it with a direct implementation approach. We find that the latter allows for a more purposeful use of security measures as defenders avoid to get caught in a “hare-tortoise-trap”. We specify the conditions under which the direct implementation outperforms adaptive play in the sense that it lowers the cost of defence at a given rate of deterrence. We analyse the robustness of our results and discuss the implications and requirements for practical application.

Marcus Wiens, Sascha Meng, Frank Schultmann
Optimal Airline Networks, Flight Volumes, and the Number of Crafts for New Low-Cost Carrier in Japan

Recently, numerousYabe, Ryosuke low-cost carriers (LCCs) have beenHonma, Yudai established and have become popular as a new style of airline service. In Japan, Peach Aviation began business as an LCC in 2012. However, while it is true that some airline companies are suffering from a slump in business, Peach Aviation has succeeded because it set up a hub airport at Kansai International Airport and runs many cash-cow routes. To establish a new LCC, consideration of airline networks is most important for success. Therefore, in this study, we propose a mathematical model to optimize the airline network, flight volume, and number of aircrafts for maximizing a new LCC’s profit supposing a hub-spoke style network, and solve the model as a mathematical programming problem. First, we investigate the case of a single-hub network, and subsequently consider a two-hub network. It was determined that, when both Narita and Kansai International Airports are chosen as hub airports, a new LCC’s profit is maximized.

Ryosuke Yabe, Yudai Honma
Variable Speed in Vertical Flight Planning

Vertical flight planningYuan, Zhi concerns assigningFügenschuh, Armin cruise speedKaier, Anton and altitude toSchlobach, Swen segments that compose a trajectory, such that the fuel consumption is minimized and the time constraints are satisfied. The fuel consumption over each segment is usually given as a black-box function depending on aircraft speed, weight, and altitude. Without time consideration, it is known that it is fuel-optimal to fly at a constant speed. If an aircraft is under time pressure to speed up, the industrial standard of cost index cannot handle it explicitly, while research literature suggest using a constant speed. In this work, we formulate the vertical flight planning with variable cruise speed into a mixed integer linear programming (MILP) model, and experimentally investigate the fuel saving potential over a constant speed.

Zhi Yuan, Armin Fügenschuh, Anton Kaier, Swen Schlobach
A Fast Greedy Algorithm for the Relocation Problem

In this paper, we presentZakaria, Rabih three relocationMoalic, Laurent policies forDib, Mohammad the relocation problemCaminada, Alexandre in one carsharing system. We implement these policies in a greedy algorithm to evaluate their performance. Compared with CPLEX, greedy algorithm proved that it is able to solve the most difficult system configurations in at most one second while providing good quality solutions. On the other side, greedy algorithm results show that relocation policies that do not rely on historical data, will not be very efficient in reducing rejected user demands, on the contrary they can contribute in increasing their number while increasing the total number of relocation operations.

Rabih Zakaria, Laurent Moalic, Mohammad Dib, Alexandre Caminada
Multicriteria Group Choice via Majority Preference Relation Based on Cone Individual Preference Relations

A multicriteria group choiceZakharov, Alexey problem that is considered in the article includes: a set of feasible decisions; a vector criterion reflecting general goals of a group of Decision Makers (DMs); asymmetric binary relations of DMs, which reflect individual preferences. Individual preferences are given by “quanta” of information, which indicate a compromise between two components of vector criterion. A majority preference relation is also considered. It is proved that such majority relation is a cone one, and the cone, generally speaking, is not convex. The property of convex is equivalent to transitivity of the corresponding relation. The goal of the research is to construct a convex part of a majority preference relation cone, which gives a transitive part of this relation. The case of group of three DMs and three components of criteria is considered. It is shown how to specify a convex part of a majority preference relation cone, and construct a set of nondominated vectors.

Alexey Zakharov
Backmatter
Metadata
Title
Operations Research Proceedings 2014
Editors
Marco Lübbecke
Arie Koster
Peter Letmathe
Reinhard Madlener
Britta Peis
Grit Walther
Copyright Year
2016
Electronic ISBN
978-3-319-28697-6
Print ISBN
978-3-319-28695-2
DOI
https://doi.org/10.1007/978-3-319-28697-6