Skip to main content
main-content
Top

About this book

This book gathers a selection of peer-reviewed papers presented at the International Conference on Operations Research (OR 2018), which was held at the Free University of Brussels, Belgium on September 12 - 14, 2018, and was jointly organized by the German Operations Research Society (GOR) and the Belgian Operational Research Society (ORBEL). 575 scientists, practitioners and students from mathematics, computer science, business/economics and related fields attended the conference and presented more than 400 papers in parallel topic streams, as well as special award sessions.
The respective papers discuss classical mathematical optimization, statistics and simulation techniques. These are complemented by computer science methods, and by tools for processing data, designing and implementing information systems. The book also examines recent advances in information technology, which allow big data volumes to be processed and enable real-time predictive and prescriptive business analytics to drive decisions and actions. Lastly, it includes problems modeled and treated while taking into account uncertainty, risk management, behavioral issues, etc.

Table of Contents

Frontmatter

Awards

Frontmatter

On a Polynomially Solvable Subclass of the Clique Problem with Applications in Energy-Efficient Timetabling

The clique problem under multiple-choice constraints is an N P $${\mathcal {N}\mathcal {P}}$$ -hard variant of the general clique problem, which incorporates a structure commonly found in real-world applications like underground, railway or runway scheduling. It is relevant whenever there is a set of decisions with discrete options for each decision and possible conflicts between options. In this article, we identify a polynomial-time solvable subclass and determine its complete convex hull using graph-theoretic arguments related to perfect graphs. Since the convex hull can have exponentially many facets, we present criteria on how to more efficiently find the stable sets required to describe the convex hull as well as a polynomial-time separation algorithm. Finally, the theoretical results were successfully applied to energy-efficient underground and railway scheduling.

Patrick Gemander

An Adaptive Large Neighborhood Search for Routing and Scheduling Carsharing Service Requests

One possibility of coordinating service requests that arise for vehicles of a carsharing fleet is to optimize routes of shuttles that drop off and pick up service agents. This scenario is modeled as a variant of Vehicle Routing Problem (VRP), including aspects of the VRP with Time Windows, the Team Orienteering Problem and the Pick-Up and Delivery Problem. A metaheuristic, an Adaptive Large Neighborhood Search is adapted, tested by applying real-world data and evaluated regarding performance and run time. The results show that, despite high run times to improve the initial solution several times, a feasible solution is obtained quickly. Some very practicable routes are obtained when including the minimization of the latest arrival time in the hierarchical objective function. Then, all shuttles are occupied evenly and results reach a high number of served requests. The algorithm can support fleet managers to handle a complex problem within their daily business.

Magdalena P. Lippenberger

Integration of Drones in Last-Mile Delivery: The Vehicle Routing Problem with Drones

Recently, there has been a surge of interest, from both practitioners and academic researchers, that concerns the utilization of drones for civil applications. In this work, we are interested in studying the Vehicle Routing Problem with Drones (VRPD). In the VRPD, a fleet of vehicles, each of them equipped with a set of drones, is tasked with serving a given set of customers with minimal makespan. A drone may be launched from and recovered by its assigned vehicle and might move at a different velocity. However, compared to vehicles, drones possess a limited flight endurance and carrying capacity. The VRPD can be formulated as a Mixed Integer Linear Program (MILP) and, consequently, be solved by any standard MILP solver; however, only small-sized instances can be solved within a reasonable amount of time. Hence, for solving large-scale VRPD instances, we propose an algorithm based on Variable Neighborhood Search (VNS). We carried out extensive computational experiments and through our numerical results, we illustrate that drones might be beneficial with regards to a significantly reduced makespan.

Daniel Schermer

Robust Evacuation Planning for Urban Areas

This article summarizes the findings of my Ph.D. thesis finished in 2017, which focuses on the mass evacuation of urban areas. The main task of evacuation planning is the guidance of the evacuees through the street network to reduce casualty risks and increase the performance of the evacuation process. Usually the capacities of the street network are assumed as in daily-traffic. However, such rare and unique situations induce disaster-related or traffic-related factors which affect the capacities of the street network negatively. The contribution of this work lies in designing a deterministic optimization model that is more robust against these capacity uncertainties. Therefore, we adopt an idea that has already been successfully applied to robust network design: The robustness of the street network is enhanced by a better utilization of the available network capacities and by reducing interdependencies in the network. Thus, evacuation performance (e.g., the total evacuation time) is not our only objective and we are willing to sacrifice some of it to enhance the robustness in the face of unpredictable capacity disruptions. A new innovative bi-objective evacuation model and individual solution methods are presented. These methods and the new robust concept are evaluated in an extensive computational study.

Marc Maiwald

Contributions to Branch-and-Price-and-Cut Algorithms for Routing Problems

This article deals with new exact branch-and-price-and-cut algorithms for the solution of routing problems. Specialized methods for the pickup-and-delivery problem (PDP), the truck-and-trailer routing problem (TTRP), the periodic vehicle routing problem (PVRP) and a service network design and hub location problem (SNDHLP) are presented. We develop a new technique for the acceleration of bidirectional labeling algorithms by a dynamic choice of the merge point. Moreover, for variants of the PDP, the bidirectional labeling can be effectively applied for the first time. In the TTRP, we model the extension to a 2 days planning horizon and the consideration of a quantity-dependent transfer time. The PVRP is treated with full flexible schedule structures for the first time. For these two last-mentioned problems, special techniques to tackle the symmetry are presented. The SNDHLP constitutes a new real-world problem in the application area of combined transport and is also solved with a problem-specific branch-and-price-and-cut algorithm.

Ann-Kathrin Rothenbächer

Logistics Networks with Intermediate Stops: Designing Innovative and Green Solutions

Today’s logistics networks are facing a multitude of conflicting challenges and targets as fleet operators are striving to realize efficient, flexible, and sustainable networks at once. In this context, logistics networks with intermediate stops provide promising solutions to achieve these goals, as they allow for new delivery concepts and the deployment of new technologies. This article summarizes the findings of the correspondent doctoral thesis that presents a generic algorithmic framework for the strategic design and the operation of such networks. Besides, it derives deep managerial insights for one specific application case, the use of electric vehicles in mid-haul logistics.

Maximilian Schiffer

Exploiting Structure in Non-convex Quadratic Optimization

The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties. This paper summarizes the dissertation of the author for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quad ratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch-and-bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.

Jonas Schweiger

Business Analytics, Artificial Intelligence and Forecasting

Frontmatter

Military Manpower Planning Using a Career Path Approach Applied to the Belgian Defense

In order to accomplish the missions of the organization, military manpower planning aims to provide the required workforce with the adequate competences and ranks. The military organization specificity is the hierarchical structure which restricts personnel movements and recruitments. Military manpower planning involves two logics: statutory logic and competence logic. We combine both logics into one integrated model, which allows the simultaneous optimization of the two logics. We model the military manpower using a career path approach where each soldier is assigned to one of the possible career paths. The model was applied to the Belgian military manpower. The model helps the human resources managers study the impact of different policies on the statutory and the competence levels. Furthermore, the model contributes to planning the future policies regarding job transfers and annual recruitment.

Oussama Mazari Abdessameud, Filip Van Utterbeeck, Marie-Anne Guerry

Profit-Oriented Feature Selection in Credit Scoring Applications

In credit scoring, feature selection aims at removing irrelevant data to improve the performance of the scorecard and its interpretability. Standard feature selection techniques are based on statistical criteria such as correlation. Recent studies suggest that using profit-based indicators for model evaluation may improve the quality of scoring models for businesses. We extend the use of profit measures to feature selection and develop a wrapper-based framework that uses the Expected Maximum Profit measure (EMP) as a fitness function. Experiments on multiple credit scoring data sets provide evidence that EMP-maximizing feature selection helps to develop scorecards that yield a higher expected profit compared to conventional feature selection strategies.

Nikita Kozodoi, Stefan Lessmann, Bart Baesens, Konstantinos Papakonstantinou

A Maturity Model for the Classification of RealWorld Applications of Data Analytics in the Manufacturing Environment

As digitalization continuously gets established in manufacturing, increasing amounts of data are being generated. This change opens up various possibilities to utilize these data to improve production processes by supporting decision-making. Data analytics advances the acquisition of knowledge from data and, thus, improves decision-making in manufacturing and related processes such as maintenance. Identifying the current maturity of data analytics in the manufacturing environment reveals potential and builds the basis for future developments. This paper presents a theory-driven maturity model for the classification of data analytics use cases in the context of data analytics in manufacturing. Furthermore, the model aims to offer a subcategorization of the vast and complex topic of data analytics for manufacturing purposes. The model is applied to an example of Smart Services at TRUMPF GmbH + Co. KG. This case highlights the major potential of predictive data analytics and first ideas towards prescriptive data analytics are presented.

Thomas Pschybilla, Daniel Baumann, Wolf Wenger, Dirk Wagner, Stephan Manz, Thomas Bauernhansl

Decision Theory and Multiple Criteria Decision Making

Frontmatter

Fair Resource Allocation by Gini Index Minimization

In many resource allocation problems there is a need to minimize inequity to respect some fairness rules while looking for the overall efficiency. The Gini index representing the relative mean absolute difference of outcomes is the classical measure of inequity in outcome distribution. It was empirically found in real-life applications that the Gini index minimization while equalizing the outcomes it may simultaneously support their maximization (allocation efficiency). However, it depends on the feasible set structure and there is no guarantee to achieve good equitable and efficient allocation scheme. We show that with appropriate outcome shift the Gini index minimization is consistent both with inequity minimization and with outcomes maximization thus guaranteeing equitable allocation schemes. The interval of appropriate target values depends on the problem structure (feasible set). Although it can be found or adjusted during the optimization process without necessity of a special feasible set analysis.

Wlodzimierz Ogryczak, Grzegorz Zalewski

Discrete and Integer Optimization

Frontmatter

A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes

Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially (at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set.We propose a revised variant of an old algorithm by Bieri and Nef (Linear Algebra Appl 52:69–97, 1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.

Lovis Anderson, Benjamin Hiller

A Heuristic for the Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids

We examine an extension of the Traveling Salesperson Problem (TSP), the so called TSP with Forbidden Neighborhoods (TSPFN). The TSPFN is asking for a shortest Hamiltonian cycle of a given graph, where vertices traversed successively have a distance larger than a given radius. This problem is motivated by an application in mechanical engineering, more precisely in laser beam melting.This paper discusses a heuristic for solving the TSPFN when there don’t exist closed-form solutions and exact approaches fail. The underlying concept is based on Warnsdorff’s Rule but allows arbitrary step sizes and produces a Hamiltonian cycle instead of a Hamiltonian path. We implemented the heuristic and conducted a computational study for various neighborhoods. In particular the heuristic is able to find high quality TSPFN tours on 2D and 3D grids, i.e., it produces optimum and near-optimum solutions and shows a very good scalability also for large instances.

Philipp Armbrust, Philipp Hungerländer, Anna Jellen

A Mixed Integer Linear Program for Optimizing the Utilization of Locomotives with Maintenance Constraints

In this paper we investigate the Locomotive Scheduling Problem, i.e., the optimization of locomotive utilization with prior known transports that must be performed. Railway timetables are typically planned a year in advance and then revised, updated and fixed for shorter time periods, e.g., for a week, during the year. Our aim is to assign locomotives to the trains such that the locomotive utilization is maximized considering maintenances. We model this optimization problem on a sparse weighted directed multigraph that defines the input variables for our proposed Mixed Integer Linear Program (MILP). We consider two different objective functions: We minimize over the number of deadhead kilometers, i.e., kilometers from a locomotive driven without pulling a train, and over the number of locomotives used. Finally, we conduct a computational study to compare the performance of our MILP with the different proposed objective functions and show how the MILP can be used within a rolling horizon approach.

Sarah Frisch, Philipp Hungerländer, Anna Jellen, Dominic Weinberger

Proportional Apportionment for Connected Coalitions

We generalize extensively studied apportionment methods to apply them to the political districting problem. For the generalization, we prove NP-hardness and develop a mixed-integer linear program.

Sebastian Goderbauer, Leonie Ermert

Beautification of City Models Based on Mixed Integer Linear Programming

3D City Models often are generated from sparse airborne laser scanning point clouds. Data-driven algorithms fit plane segments with the points and combine segments to watertight roof models. But low resolution laser scanning data lead to noisy boundary structures that have to be straightened. We propose a mixed integer linear program that rectifies directions of boundary edges according to the cadastral footprint and favors orthogonality. We apply this procedure to all connected components of the planar graph that represents polygonal boundaries of roof facets. The proposed method is suitable for the generation of large scale city models.

Steffen Goebbels, Regina Pohle-Fröhlich

Sweep Algorithms for the Capacitated Vehicle Routing Problem with Structured Time Windows

The capacitated Vehicle Routing Problem with structured Time Windows (cVRPsTW) is concerned with finding optimal tours for vehicles with given capacity constraints to deliver goods to customers within assigned time windows. In our problem variant these time windows have a special structure, namely they are non-overlapping and each time window holds several customers. This is a reasonable assumption for Attended Home Delivery services. Sweep algorithms are known as simple, yet effective heuristics for the classical capacitated Vehicle Routing Problem. We propose variants of the sweep algorithm that are not only able to deal with time windows, but also exploit the additional structure of the time windows in a cVRPsTW. Afterwards we suggest local improvement heuristics to decrease our objective function even further. A carefully constructed benchmark set that resembles real-world data is used to prove the efficacy of our algorithms in a computational study.

Christoph Hertrich, Philipp Hungerländer, Christian Truden

An Improved Arcflow Model for the Skiving Stock Problem

Because of the sharp development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a viable tool for solving cutting and packing problems in recent years. Constituting a natural (but independent) counterpart of the well-known cutting stock problem, the one-dimensional skiving stock problem (SSP) asks for the maximal number of large objects (specified by some threshold length) that can be obtained by recomposing a given inventory of smaller items. In this paper, we introduce a new arcflow formulation for the SSP applying the idea of reflected arcs. In particular, this new model is shown to possess significantly fewer variables as well as a better numerical performance compared to the standard arcflow formulation.

John Martinovic, Maxence Delorme, Manuel Iori, Guntram Scheithauer

Simulation-Based Location Optimization of Ambulance Stations

For the location analysis of ambulance stations, we outline a static and a dynamic method using isochrones and discrete event simulation. Both techniques base on a realistic driving time estimation for ambulances on a detailed road network. We used these analyses for a real world study in Southwest Germany.

Johanna Schneider, Michael Schröder

Assigning Students to Schools for an Internship

Every student in North Rhine-Westphalia, Germany, studying to become a teacher, has to complete a semester of practical training at a school. In order to assign students to schools and thereby satisfy the requests of the students, without exceeding capacity limitations at the schools, a discrete, assignment-like optimization problem is formulated and solved to optimality. Since students study two major subjects, a school has to provide capacities in both of them to be a candidate for a feasible assignment. An additional requirement comes from the fact that students have to attend seminar courses in the respective subjects during their internship. The overall optimization problem is a generalized assignment problem, which has an alternative interpretation as a fixed-charge multicommodity flow problem.

Michael Stiglmayr, Simon Görtz, Kathrin Klamroth

Energy and Environment

Frontmatter

Electricity Price-Oriented Scheduling Within Production Planning Stage

The fact that energy prices on spot markets are volatile opens up economic potentials for industrial companies, as they consider them in production planning processes. In practice, this means that energy costs can be saved by shifting jobs to time intervals of low energy prices. This contribution addresses the effects of electricity price-oriented scheduling for planning periods of one week. We study a flow shop scheduling environment with up to three machines and energy-intensive jobs. The problem requires the information of electricity prices before they will be emerged on the market. Therefore, we analyze the suitability of electricity price forecasts in scheduling models. Moreover, we compare the potentials of electricity price-oriented scheduling to makespan minimization.

Jan Busse, Julia Rieck

Two-Stage Unit Commitment Modeling for Virtual Power Plants

The development of an increasingly decentralized, renewable power supply requires adequate planning approaches. Compared to unit commitment planning in regulated markets with a dominant share of dispatchable power generation, power systems with large shares of intermittent renewable power sources such as wind or photovoltaics are subject to uncertain supply as well as uncertain load forecasts and prices.Virtual Power Plants have been developed to aggregate intermittent renewables with so-called flexibility options, which include dispatchable power plants, storage systems and flexible power consumers. Dispatchable power plants, such as biogas plants, include all that can actively be committed to supply power in a time interval. Storage systems, such as pumped-storage hydroelectricity, can store power in times of low prices and resell it when prices rise. Flexible power consumers, such as operators of electric vehicles, can attempt to use these time windows to load the batteries, lowering their power purchasing costs.In the current German power market, power can be traded either in auctions on the day before physical delivery or in continuous intraday trading on the day itself. To determine optimal schedules for flexibility options in the context of day-ahead or intraday markets, a two-stage unit commitment model is presented to deal with the uncertainty of market prices resulting from the interplay of power generation in wind turbines and photovoltaic cells one the one hand with power demand on the other.

Lars-Peter Lauven

Globally Optimal Short-Term Unit Commitment and Dispatch for Combined Heat and Power Generation Units Connected to District Heating Grids

With the raising share of renewable power generation, economic operation of combined heat and power plants (CHPs) is becoming more challenging. CHPs need to become more flexible to react to volatile renewable infeed and volatile energy prices. Such more flexible operation can be achieved by considering the heat storage capabilities of the connected district heating grid. But finding a good optimization model for heating grid dynamics is hard, as the underlying problem is a mixed integer nonlinear program (MINLP) with bilinear terms and time delays. There has not been much attention on global optimization of this problem yet. In this paper we present a new approach to find a global optimum for this MINLP using multiparametric disaggregation for bilinear terms and proposing “multiparametric delay modeling” for the modeling of time delays. It can be used to benchmark existing and future non-global optimization schemes.

Lennart Merkert, Sören Hohmann

An Exact Method for Cost-Minimal Deployment of a Rail Crane Using Demand Response

We present a mixed-integer linear program (MILP) for demand response for an electric rail crane system in a container terminal. The overall goal is to determine the cost-reduction potential of demand response programs for rail cranes by comparing energy costs of an optimal demand management and energy costs without demand management for small problems. We use the MILP to determine the most cost-efficient demand schedule with the constraints guarantee an in-time execution of container jobs in the planing horizon.

Erik Pohl, Lars-Peter Lauven, Jutta Geldermann

Entity-Oriented Multi-Level Energy System Optimization Modeling

Market actors along the energy value chain might assess challenges and opportunities from different actor perspectives and various interest criteria since every single consumer and operator has a differing technology-mediated relationship. Existing energy system optimization models, however, ignore the roles different actors play and the resulting impact they have. This research paper develops an entity-oriented multi-level optimization framework called Integrated Resource Planning and Optimization (IRPopt). The objective function exhibits a novel formal interface between the supply and demand side which merges technical and commercial aspects. This is achieved by explicit modeling of municipal market actors on one layer and state-of-the-art technology processes on another layer as well as resource flow interrelations and service agreements mechanism among and between the different layers.

Fabian Scheller, Thomas Bruckner

Finance

Frontmatter

The Impact of Monetary Policy on Investment Bank Profitability in Unequal Economies

Central banks implement negative interest rate policies (NIRP) to incentivize economic subjects to spend and invest money for long term economic growth. Although nominal negative interest rates can not be effectively explained by economic theory, when inflation is included there are currently real negative interest rates in almost all industrial nations. We investigate the impact of these varying rates on bank profitability after the financial crisis starting in 2007. With industrial clustering, it is possible to observe heterogeneous performances of stock prices in the countries concerned.

Bernard M. Gilroy, Alexander Golderbein, Christian Peitz, Nico Stoeckmann

A Mathematical Programming Approach for the Optimal Collateral Allocation Problem

The minimization of regulatory capital requirements has significant impact on the activities of the financial institutions, since it is usually associated with an increase in liquidity which is considered of critical importance for their sustainability and growth. The main tool towards such an aim is the effective allocation of collaterals to the associated set of loans. A methodology regarding this problem, based on the well-known transportation problem, is provided in this paper. Our approach has been implemented and applied to both real data from a systemic bank and synthetic data. From the results obtained it is evident that the proposed formulation leads to less regulatory capital requirements compared to other existing methodologies also implemented for the purposes of the current work.

Konstantinos Papalamprou, Efthymios P. Pournaras, Styliani Tychalaki

Enhancing Strategic Bidding Optimization for Renewable Energy Auctions: A Risk-Adequate Marginal Cost Model

The shift toward auction mechanisms for renewable energies has introduced competitive price discovery of financial support levels for new projects. The starting point of finding an optimal bidding strategy in these auctions must always be a reliable determination of the marginal cost, which is the minimum sales price per unit of electricity required to permit an economically viable project realization at an acceptable level of risk. We focus on enhancing strategic bidding by introducing a holistic financial modeling approach for a risk-adequate quantification of the marginal cost, which serves as the basis for strategic bidding optimization models. In order to permit a proof-of-concept and in-depth understanding of our model enhancement, we conduct a simulation study of an onshore wind farm in Germany. The results of our study show that our modeling approach enables quantifying bid prices that are both cost-competitive and sustainable in terms of a likely project realization.

Chris Stetter, Jan-Hendrik Piel, André Koukal, Michael H. Breitner

An Optimization Model for Multi-Asset Batch Auctions with Uniform Clearing Prices

Conventional asset exchange mechanisms are based on pairwise order books and continuous order matching. Contrasting this, we introduce an alternative exchange and price-finding mechanism that simultaneously considers multiple assets in a discrete-time setting. We present a MIP formulation for this mechanism together with some computational results.

Tom Walther

Graphs and Networks

Frontmatter

A Network Flow Formulation of the Location-Scheduling Problem for Electric Vehicle Charge Stations with Incomplete Information

When solving the location-scheduling problems related to the design of a private charging infrastructure for a fleet of electric vehicles, we may encounter a gap between the number of unfeasible vehicles obtained from optimization and the simulation results. The gap is caused by the fact that users of the charging infrastructure make decisions based on less information than is assumed to be available in the optimization algorithms. In our contribution, we show how to model these problems by using the flows in networks. We propose an algorithm that will operate despite the lack of information utilised by the users of the charging infrastructure.

Peter Czimmermann, Ľuboš Buzna

Minimum Dominating Set and Maximum Independent Set for Evaluation of EU Funding Polices in Collaboration Networks

Stimulating innovation and growth within the European Union is crucial and can be achieved by fostering R&D partnerships with EU Foreign Policies. Research collaboration networks induced by these policies received strong attention from policymakers. In this paper, we show that some structures from graph theory (such as Minimum Dominating Set) can be used to determine which members are most involved in these collaborative networks. Although these networks are large in size, it is possible to determine optimal MDS. In particular, we show that some vertices are present in any optimal solution. We call them persistent vertices. They provide a better understanding of the impact of EUFP on collaborations induced between companies or research organizations.

Valentin Bouquet, Kymble Christophe, François Delbot, Gaétan Le Chat, Jean-François Pradat-Peyre

PHOEG Helps to Obtain Extremal Graphsch:32

We present PHOEG, an ecosystem of tools designed to help researchers in Extremal Graph Theory.It uses a big relational database of undirected graphs and works with the convex hull of the graphs as points in the invariants space in order to exactly obtain the extremal graphs and optimal bounds on the invariants for some fixed parameters. The results obtained on the restricted finite class of graphs can later be used to infer conjectures. This database also allows us to make queries on those graphs. Once the conjecture defined, PHOEG goes one step further by helping in the process of designing a proof guided by successive applications of transformations from any graph to an extremal graph. To this aim, we use a second database based on a graph data model.

Gauvain Devillez, Pierre Hauweele, Hadrien Mélot

The Knapsack Problem with Conflict Graphs and Forcing Graphs of Bounded Clique-Width

The 0-1-knapsack problem is a well-known NP-hard problem in combinatorial optimization. We consider the extensions to the knapsack problem with conflict graph (KCG) and the knapsack problem with forcing graph (KFG). Within this paper we provide pseudo-polynomial solutions for KCG and KFG with co-graphs as conflict and forcing graphs and extend these solutions to conflict and forcing graphs of bounded clique-width. Our solutions are based on dynamic programming using the tree-structure representing the conflict graph and the forcing graph. Further we conclude fully polynomial time approximation schemes (FPTAS) for KCG on conflict graphs of bounded clique-width and KFG on forcing graphs of bounded clique-width. This generalizes the known results for conflict and forcing graphs of bounded tree-width of Pferschy and Schauer.

Frank Gurski, Carolin Rehs

Logistics and Freight Transportation

Frontmatter

Heterogeneity of Items in an Integrated Item-Sharing and Crowdshipping Setting

We consider the operational planning of a platform that integrates two concepts of the sharing economy, namely item-sharing and crowdshipping. In item-sharing, members of a community can temporarily rent items from one another (peer-to-peer). Crowdshipping is an innovative means of transportation where private drivers execute delivery jobs along their intended trips. It has been shown by Behrend and Meisel (Transp Res B Methodol 111:227–243, 2018) that this integration leads to a number of assignment problems, whose optimal solution allows to increase a platform’s profit and the level of service provided to item-sharing consumers. However, this result has only been evaluated for scenarios with homogeneous items so far. Since item-sharing platforms usually serve as a market place for a wide range of products we investigate here how this finding is effected when heterogeneous items are considered. Our results show that integrating crowdshipping with item-sharing becomes even more relevant in a setting with heterogeneous items.

Moritz Behrend, Frank Meisel

Metamodel-Based Optimization of the Article-to-Device Assignment and Manpower Allocation Problem in Order Picking Warehouses

Efficient order picking requires a coordinated way of combining and utilizing three kinds of heterogeneous resources: articles, devices, and operators. Usually, the assortment of articles is subject to permanent adaptations. Hence, the interdependent decisions of assigning articles to devices and allocating manpower among devices need to be adjusted and the problem has to be solved frequently for similar instances. We propose a combination of exact and heuristic solution approaches. For an immediate reaction to each assortment change, a heuristic approach applying metamodel-based optimization is used. The data required for estimating the metamodel is provided by an exact approach which is utilized from time to time to reset the system to an optimal state. Based on sampled data of a pharmaceutical wholesaler, we compare exact and heuristic approach with regard to quality and time of solving in-sample and out-of-sample instances.

Ralf Gössinger, Grigory Pishchulov, Imre Dobos

Fleet Sizing and Empty Freight Car Allocation

Empty freight car allocation problems and fleet sizing problems are highly important topics in the field of railway cargo optimization. Fleet sizing is mainly used in order to find the minimal number of freight cars (with fixed costs) needed to operate the transportation network successfully (e.g. satisfying customer demands). After a consignment is transported to its destination, the unloaded freight cars must be reallocated. This reallocation process is linked to costs depending on the traveled distance.In this paper we propose a network flow problem on a time-space network, formulated as integer linear program (ILP), for determining the optimal trade-off between the number of freight cars and the costs of empty vehicle allocation. The ILP is tested on a distribution network that is related to a specific part of Rail Cargo Austria’s railway network. Different modifications in the network (changes in cost structure, travel time and demand) are examined and compared to the basic scenario.

Philipp Hungerländer, Sebastian Steininger

An Iterated Tabu Search for the Vehicle Routing Problem with Multiple Compartments and Last-in-First-Out Unloading

We study a variant of the vehicle routing problem with multiple compartments in which compartment sizes are flexibly adjustable in discrete steps. Additionally, a last-in-first-out unloading policy has to be considered since rearranging of cargo on the load bed is prohibited. This problem occurs as a special case at a German food retailer that has to supply a large number of hypermarkets on a daily basis. Transported products are divided into several categories based on the transport temperature. Due to these different temperatures, it is expedient to use trucks with multiple compartments. Moreover, the retailer engages various forwarders for transportation. Forwarders are paid according to previously negotiated tariffs based on the different product categories. This leads to a cost function that differs a lot from the common distance minimization. We propose an iterated tabu search with two different perturbation mechanisms to solve this challenging vehicle routing problem. Various computational experiments with real data from the retailer are performed to assess the performance of our algorithm. Comparisons with results obtained by employing a mixed integer program and solving this with a commercial solver show that the iterated tabu search consistently produces high quality solutions.

Felix Tamke

Metaheuristics

Frontmatter

An Adaptive Large Neighborhood Search Heuristic for Jointly Solving Storage Location Assignment and Picker Routing Problem

We focus on the order picking operation carried out in one of the major warehouses of a retailer to satisfy the orders placed by the stores of the same retailer. We investigate the simultaneous solution of the storage assignment problem and picker routing problem referred to as JSAPRP that involves both assigning items to storage locations and deciding on the routes of the pickers for item collection. The performance measure of interest is the minimization of the total traveling distance of the pickers. We develop a mathematical model which can only solve small instances of the JSAPRP. Therefore, we also devise a heuristic method based on adaptive large neighborhood search. Computational results obtained on numerous experiments reveal that the quality of the solutions produced by this heuristic is quite good.

Necati Aras, Berk Görgülü

Predicting the Vibroacoustic Quality of Steering Gears

In the daily operations of ThyssenKrupp Presta AG, ball nut assemblies (BNA) undergo a vibroacoustical quality test and are binary classified based on their order spectra. In this work we formulate a multiple change point problem and derive optimized quality intervals and thresholds for the order spectra that minimize the number of incorrectly classified BNA. We pursue a multiobjective goal: the first objective function maximizes the Cohen Kappa metric, while the second objective function reduces the number of employed order intervals. The proposed approach is based on a genetic algorithm and incorporates prior information on the correlation structure of BNA and steering gear vibroacoustics, gained via canonical correlation analysis. The computational experiments show a reduction of both the number of employed order intervals and the costs arising from falsely classified BNA parts with respect to the current production setting, ensuring thus a high practical relevance of our suggested approach.

Paul Alexandru Bucur, Klaus Frick, Philipp Hungerländer

Optimization Under Uncertainty

Frontmatter

Dynamic Policy Selection for a Stochastic-Dynamic Knapsack Problem

In this work, we solve a stochastic-dynamic optimization problem by means of combining candidate policies. The combination is realized by a dynamic policy selection. We draw on a stochastic-dynamic knapsack problem to evaluate the dynamic policy selection. Our computational studies point out that the benefit compared to the individual usage of candidate policies is significant.

Jeannette Anna Lena Hermanns, Jan Brinkmann, Dirk Christian Mattfeld

OR in Engineering

Frontmatter

Trajectory Optimization for Wire-Arc Additive Manufacturing

We consider a technical operations research problem that arises in the wire-arc additive manufacturing process. In order to manufacture a three dimensional object, it is build layer-wise from bottom to top, where in each layer a metal wire is melted using high temperatures at a welding torch. Deadheading is allowed for the welding torch, if the shape in a certain layer cannot be drawn continuously. A thorough planning of the path is important for process time and part quality. The most critical restrictions are due to the enormous heat input to the workpiece. We describe the optimization problem of how to partition a given traverse into continuous segments that are manufactured without intersection, and deadheading between the segments, such that deadheading is minimized in order to finish the process as fast as possible. As a further constraint of the optimization, the accumulated heat is tracked and the local amount of heat should be below a given threshold. We give a formulation of this problem as a mixed-integer program and demonstrate the applicability of standard mixed-integer solvers for their solution on a test-bed of components.

Armin Fügenschuh, Markus Bambach, Johannes Buhl

A Time-Flow Approach for Scheduling and Routing of Fly-in Safari Airplanes

A touristic company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of aircrafts in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in combination with a so called time-free relaxation in order to solve this problem with a solver for MILP. We give an alternative MILP formulation of the problem, that still allows for similar relaxation techniques to be used. This formulation, however, also allows for the construction of graphs which can be interpreted as intermediate graphs between the time-free and the (totally) time-expanded graph and therefore yield stronger relaxations. With knowledge obtained from the solutions of these relaxations the number of vertices that have to be expanded in order to guarantee feasibility is reduced significantly. On the benchmark set this lead to a decrease of the average computation time and a significant reduction of the remaining optimality gaps.

Fabian Gnegel, Armin Fügenschuh

Designing a Water Supply Network for Slums in Rio de Janeiro Using Mixed-Integer Programming

UN Sustainability Development Goal No. 6 aims at ensuring access to water and sanitation for all people by 2030. We address this goal in a multidisciplinary approach by applying mathematical optimisation methods to design optimal water supply systems for underserved areas, such as living environments of the urban poor, which are not integral part of the formal city. Hereby, we use remote sensing data to spatially localise the underserved areas operationalised by typical morphologic indicators for slum areas. With it, slum sizes and locations are spatial information available as input data for the decision problem. This problem is modelled as a MIP and chooses between different approaches combining supply by motorised vehicles with installed pipe systems while minimising overall costs. The solution of this MIP, the design of a low-cost water supply network, is presented and analysed for a slum cluster in Rio de Janeiro.

Marvin Meck, Lea Rausch, John Friesen, Michael Wurm, Hannes Taubenböck, Lena Altherr, Peter F. Pelz

Optimizing Pressure Screen Systems in Paper Recycling: Optimal System Layout, Component Selection and Operation

Around 60% of the paper worldwide is made from recovered paper. Especially adhesive contaminants, so called stickies, reduce paper quality. To remove stickies but at the same time keep as many valuable fibers as possible, multi-stage screening systems with several interconnected pressure screens are used. When planning such systems, suitable screens have to be selected and their interconnection as well as operational parameters have to be defined considering multiple conflicting objectives. In this contribution, we present a Mixed-Integer Nonlinear Program to optimize system layout, component selection and operation to find a suitable trade-off between output quality and yield.

Tim M. Müller, Lena C. Altherr, Marja Ahola, Samuel Schabel, Peter F. Pelz

Computation of Stable Honeycomb Structures for Additive Manufacturing

In certain additive manufacturing processes of industrial interest, the task arises to build up structures layer-wise in a purely vertical manner. The question arises how to construct such a structure in a convenient way so that it is structurally as stable as possible.In this paper, we consider the automatic construction of a honeycomb structure, given the boundary of a shape of interest. In doing this we employ Lloyd’s algorithm in two different realisations. For computing the incorporated Voronoi tessellation we consider the use of a Delaunay triangulation or the Eikonal equation. As a main point of our paper, we give a comparison of these two methods. We show that one can make use of the arising graph of the honeycomb structure as input for a specific routing scheme that enhances printability when the printing material stays soft for some time during the printing process.

Martin Bähr, Georg Radow, Michael Breuß, Armin Fügenschuh

Design and Optimization for Additive Manufacturing of Cellular Structures Using Linear Optimization

The rapid development of Additive Manufacturing (AM) enables a high geometrical freedom for the production of lightweight cellular structures. Through the newly gained possibilities in individualization and complexity in the areas of design and construction, optimization and generation of the initial design becomes even more important. We discuss a mixed-integer linear program (MIP) to generate a three-dimensional construction of cellular structures for a static case of loading. Additionally, based on the optimized structures, an automated construction in a CAD system allowing a numerically simulation of nonlinear material behaviour is presented. The model is planned as a support tool for engineers.

Christian Reintjes, Michael Hartisch, Ulf Lorenz

Machine Learning and Metaheuristics for Black-Box Optimization of Product Families: A Case-Study Investigating Solution Quality vs. Computational Overhead

In product development, numerous design decisions have to be made. Multi-domain virtual prototyping provides a variety of tools to assess technical feasibility of design options, however often requires substantial computational effort for just a single evaluation. A special challenge is therefore the optimal design of product families, which consist of a group of products derived from a common platform. Finding an optimal platform configuration (stating what is shared and what is individually designed for each product) and an optimal design of all products simultaneously leads to a mixed-integer nonlinear black-box optimization model. We present an optimization approach based on metamodels and a metaheuristic. To increase computational efficiency and solution quality, we compare different types of Gaussian process regression metamodels adapted from the domain of machine learning, and combine them with a genetic algorithm. We illustrate our approach on the example of a product family of electrical drives, and investigate the trade-off between solution quality and computational overhead.

David Stenger, Lena C. Altherr, Dirk Abel

Modeling Thermofluid Systems: An Approach Customized for Optimization

Many technical applications involve the heating and cooling of fluids. In technical terms, the corresponding systems are called thermofluid systems. These systems can be regarded as fluid systems with superimposed heat transfer. However, since both parts mutually depend on each other, they have to be considered simultaneously. As an extension of previous research on fluid systems, we present a mathematical model for the algorithmic system design of thermofluid systems. This includes modeling the physical properties and system components related to heat transfer. Besides that, another issue arises if heat transfer is considered. While it can be reasonable for fluid systems to be assumed as quasi-stationary systems, this does not hold for most thermofluid systems. Although some can be regarded as quasi-stationary, most of them show dynamic behavior. A major reason for this is that when dealing with heat, storage tanks become important. Thus, an appropriate time representation is required. For this purpose, we introduce a continuous-time approach.

Jonas B. Weber, Ulf Lorenz

Pricing and Revenue Management

Frontmatter

Data-Driven Stochastic Dynamic Pricing and Ordering

In many markets, firms use data-driven dynamic pricing and ordering strategies to increase their profits. To successfully manage both inventory levels as well as offer prices is a highly challenging task as (i) demand is typically uncertain and (ii) optimized pricing and ordering decisions are mutually dependent. In this paper, we analyze stochastic dynamic joint pricing and ordering models for the sale of durable goods. In a first step, a data-driven approach is used to estimate demand intensities and to quantify sales probabilities. In a second step, we use a dynamic programming model to compute optimized feedback pricing and ordering strategies. We are able to study the impact of ordering costs, inventory holding costs, and a delay in delivery. Further, we discuss potential extensions of the model proposed.

Rainer Schlosser

Production and Operations Management

Frontmatter

Tactical Planning of Modular Production Networks in the Chemical Industry: A Case Study in Specialty Polymers

Faced with new challenges, the chemical industry strives for more diversified product portfolios. Product life cycles are becoming shorter and lead to an increased uncertainty in product demands with regard to volume, location and type. To efficiently cope with highly individual demands, modular production concepts are considered. Modular plants can be installed in standard transportation containers and may operate at decentralized facilities in direct proximity to customers or suppliers. New modular plants can be added and existing plants can be relocated in the short-term to adapt to changing demand conditions. For an efficient utilization of the increased flexibility provided by modular plants, tactical planning must incorporate the new flexibility options. In this paper, using real data provided by a large chemical company, the economic benefits of modular production concepts in the specialty polymers market are assessed.

Tristan Becker, Bastian Bruns, Stefan Lier, Brigitte Werners

Validating Measurement Data in Manufacturing Processes

Statistical process control (SPC) is an industry-standard methodology for monitoring and controlling quality during manufacturing processes. In this method, one measures quality data of small samples in preset time intervals or after a specific amount of produced items. Based on this data and some mathematical statistics, one can extrapolate to the entirety and, if necessary, adjust process parameters to ensure perfect quality products. However, this method is conditioned on the fact that the measured data is correct and neither the measuring device nor the inspector manipulated the incoming data. We study the problem of detecting manipulations in measurement data of manufacturing processes, which we refer to as validation of measurement data. To this end, we combine Decision Stump Forests with a novel variation of the Smith-Waterman algorithm to detect characteristics from a predefined list of typical manipulations and test this for feasibility on real data from manufacturers in Germany.

David Brück, Sven Oliver Krumke

Modeling the Egg Packing Station Planning Problem

This paper presents the planning problem encountered by egg packing station managers. In an egg packing station, pallets containing unsorted eggs arrive daily from chicken farms and need to be packed into order-specific boxes on packing lanes. The grader automatically identifies damaged eggs and grades the remaining eggs in several weight classes. The number of packing lanes is station specific but can reach up to 32. The orders are destined for retailers and they specify the number of required eggs and a set of allowed grades. The challenge is to assign these orders to the packing lanes such that the incoming supply (distribution of grades) is completely covered by active orders on the packing lanes. This paper positions the egg packing problem in the optimization literature and proposes a model that efficiently covers this planning problem. Furthermore, we point out several future research directions such as additional practical work floor constraints and algorithmic challenges.

Reginald Dewil, Johan Philips, Jan Jaap Kempenaar, Dirk Cattrysse

A Multi-site Facility Layout and Product-to-Site Assignment Problem

This contribution deals with a multi-site facility layout and product-to-site assignment problem of a job shop production system to tackle the problem of finding the product program at every production site that minimizes the overall costs induced by internal transports and provision of production units. Because not every production unit is needed to produce a specific product, the decision field of facility layout planning is extended by two questions: (1) Which products are to be produced at which site, and (2) for which production unit redundancies across different sites are necessary? This contribution provides an extended optimization model (based on the quad ratic assignment problem) that combines layout planning of multiple sites with the product-to-site assignment to a multi-site facility layout problem (MSFLP). It is followed by a numerical study to examine the influence of homogeneity on product program and transport costs, which is extended by the variation of the provision costs for the respective production units to find the trade-off between internal transportation costs and costs for redundancies.

Bernd Hillebrand

A Scatter Search Approach for the Facility Layout Problem with Aisle Design

This paper proposes a scatter search based approach for solving the unequal area facility layout problem with aisle areas. This novel approach simultaneously arranges facilities within a planar site, locates material handling points, and determines the aisle design by minimizing the total travel distance along the travel paths. The effectiveness of the presented approach is shown in a computational study using well-known test instances. The results indicate a significant advantage of taking aisle areas into account within the arrangement problem.

Armin Klausnitzer

Project Management and Scheduling

Frontmatter

Real-World Staff Rostering via Branch-and-Price in a Declarative Framework

An important problem in staff scheduling is roster generation. The task is to find an assignment of shifts to employees, such that qualification restrictions and demands are met as well as possible. This assignment problem is in particular challenging due to business rules concerning working time, day on/off patterns, rest times, or employee preferences. The present paper outlines INFORM’s staff rostering optimizer that is used to solve large-scale real-world rostering instances, and evaluates the performance of the optimizer on nurse rostering data. Moreover, we describe how we integrate the optimizer into our system and adapt it to the needs of our customers using a declarative programming framework.

Marco Bender, Sebastian Berckey, Michael Elberfeld, Jörg Herbers

Scheduling in a Data Gathering Network to Minimize Maximum Lateness

In this work, we study scheduling in a data gathering network comprising a set of workers and a single base station. The workers produce datasets that have to be sent to the base station for further processing. Each dataset can be released at a different moment, and is assigned a due date by which it should be processed. Our goal is to schedule dataset transfers and the base station computations so as to minimize the maximum dataset lateness. We prove that the analyzed problem is strongly NP-hard, and present several polynomially solvable special cases. An exact branch-and-bound algorithm and three greedy heuristics are proposed. The performance of the algorithms is tested in computational experiments.

Joanna Berlińska

Heuristics for Solving the Job Sequencing and Tool Switching Problem with Non-identical Parallel Machines

The job sequencing and tool switching problem (SSP) is an NP-hard combinatorial optimization problem in the context of flexible manufacturing machines. Tool switches denote the interchange of tools between the global tool storage and the local tool magazine of a machine since the tool magazine capacity of the machine is limited and cannot hold all tools necessary for processing all jobs. The presented work considers the SSP with non-identical parallel machines (SSP-NPM) for the different objectives minimizing the number of tool switches, minimizing makespan and minimizing total flowtime. A simple and fast heuristic approach for the SSP-NPM is presented that, step-by-step, assigns jobs to machines and, in the process, determines the loading of the tools. The performance of the heuristics is analyzed with respect to computation time and solution quality for different objectives.

Dorothea Calmels, Chandrasekharan Rajendran, Hans Ziegler

Solution Algorithm for Time/Cost Trade-off Stochastic Project Scheduling Problem

In project management, the duration of the job is determined by the man-hour and resources inputted to the job. The duration can be shortened by increasing the amount of additional resources input. The cost increases according to the input of the resource. This problem is referred to as the Time/Cost Trade-off Problem (TCTP). In this study, the relation between time and cost is represented by an inverse proportional curve. We present a solution to the Stochastic Discrete TCTP-Curve (SDTCTP-C) in which the duration of the job is defined as a random variable.

Takumi Kitamura, Takayuki Shiina

Complexity and Approximation Results for Setup-Minimal Batch Scheduling with Deadlines on a Single Processor

We address the problem of sequencing n jobs that are partitioned into F families on a single processor. A setup operation is needed at the beginning of the schedule and whenever a job of one family is succeeded by a job of another family. These setup operations are assumed to not require time but are associated with a fixed setup cost which is identical for all setup operations. Jobs must be completed no later than by a given deadline. The objective is to schedule all jobs such that the total setup cost is minimized. This objective is identical to minimizing the number of setup operations. We provide a sketch of the proof of the problem’s strong NP-hardness as well as some properties of optimal solutions and an O ( n log n + n F ) $$O(n \log n + nF)$$ algorithm that approximates the cost of an optimal schedule by a factor of F. For details, we refer to our full paper.

Dominik Kress, Maksim Barketau, Erwin Pesch, David Müller

Exact and Heuristic Solution Approaches for a Flexible Job Shop Scheduling Problem Incorporating Machine Operator Restrictions

This paper addresses a flexible job shop scheduling problem with sequence-dependent setup times that incorporates heterogeneous machine operator qualifications. The objective is to minimize the makespan. We present a mixed-integer program and sketch exact and heuristic solution approaches that are based on a decomposition of the problem into a vehicle routing problem and a machine operator assignment problem. The solution methods are analyzed in computational tests. For details, we refer to our full paper.

David Müller, Dominik Kress, Jenny Nossack

Simulation and Statistical Modelling

Frontmatter

OR Control Towers: A Concept for Optimizing the Performance of Complex Adaptive Operating Systems

The optimization of complex adaptive operating systems is certainly a challenge. Such a system exhibits emergent behavior through learning and adaption of the entities it is composed of. We propose the OR control tower concept to address the optimization problems going along with these systems. We introduce a dedicated entity, the OR control tower, which not only has full overview of the system but is also able to force the system’s behavior into an optimal direction. Besides an observation component, the OR control tower has implemented an, e.g. simulation based, optimization algorithm. The tower influences the system by a control stimulus or a system reconfiguration when the performance is not adequate anymore. Our concept could make complex adaptive operating systems more stable and even resilient.

Joachim Block, Stefan Pickl

Fighting Fair? Evaluating Negative Campaigning with an Agent-Based Simulation

These days, the anonymity of the internet may encourage negative campaigning—spreading information in order to discredit competitors—as a means of gaining an advantage when contending for market dominance. To investigate the effects of negative campaigning as a measure to prevent some competing products or services from achieving a winner-take-all situation, we expand an agent-based simulation of a vampire economy developed to study the emergence of dominant designs. It turns out that the applied negative campaigning indeed works as intended, though other products or services, if technologically superior, profit as well. In our simulation experiments, the prospects of reaching a winner-take-all situation oneself therefore are still better if sticking to traditional marketing, which is, moreover, less risky in terms of an unwanted backlash against a company or individual spreading negative campaigning.

Michelle D. Haurand, Christian Stummer

A Variational Inequality Approach to Optimal Control Problems with Joint Constraints

We reformulate the optimal control problem (OCP) with joint state-control constraint into a variational inequality (VI), we use this reformulation to establish the solvability of the OCP, and propose a regularized Galerkin method, convergence properties are presented.

Zhengyu Wang, Stefan Pickl

Software Applications and Modelling Systems

Frontmatter

Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms

State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.

Gregor Hendel, Matthias Miltenberger, Jakob Witzig

Traffic, Mobility and Passenger Transportation

Frontmatter

Integrated Optimisation for Descent Trajectory Operations and Airport Runway Assignment

Continuous descent approach (CDA) aims at reducing fuel consumption and noise compared to other conventional descents. Instead of approaching an airport in a stair-step fashion, CDA allows for a smooth descent to landing. The descent profile depends on initial and final positions of aircraft, which depend on the followed route during the flight and the assigned landing runway, which in turn depends on airport congestion and/or availability. This work develops an optimization model for the management of approach and landing operations in airports, deciding on runway assignment and approach trajectory. The proposed scheme leads to a mixed integer non-linear model which is difficult to be solved. A Benders decomposition is proposed for that purpose. On the one hand, the master model deals with runway assignment, making use of a set of binary variables. On the other hand, the sub-model deals with the trajectory calculation problem, minimizing fuel consumption and complying with noise constraints.

Adrian Barea, Raul de Celis, Luis Cadarso

Real-Time Planning for Smart Charging of Electric Vehicle Fleets

Numbers of electric vehicles (EVs) are increasing, but undersized connection lines and a lack of charging stations limit how many can be charged concurrently. When this limitation is combined with peaking power demands there is a clear need for smart charging. We present a two-step approach for smart charging that considers phase-wise power assignment. First, a mixed integer linear programming model is used for day-ahead planning. Resulting charging schedules are then used as input for a proposed schedule guided heuristic for real-time planning. Experimental results from simulations show improved fair share among EVs and reduced energy costs.

Oliver Frendo, Nadine Gaertner

A Data-Driven Optimization Approach to Improve Railway Punctuality

In this paper, we present a data-driven optimization approach to improve railway punctuality. The approach can be integrated as an add-on to the existing railway planning process. We present the mathematical formulation of the optimization problem and use a simple illustrative example to demonstrate its effectiveness.

Florian Hauck, Natalia Kliewer

A Solution Approach for Railway Crew Scheduling with Attendance Rates for Multiple Networks

This paper deals with railway crew scheduling with attendance rates for multiple networks, a problem arising at a German railway operator. We discuss the particularities of the multi-network crew scheduling problem and present a set covering formulation with network-specific constraints. We present and compare two solution approaches: a hybrid column generation approach with genetic algorithm and a novel two-phase optimization method based on the algorithm above and a partitioning-and-re-combining strategy. Computational experiments with a real 1-day case of 12 networks show that the two-phase optimization method performs best in both computational time and best solution found. Moreover, collective crew scheduling over multiple networks reduces personnel cost by 2%.

Julia Heil

User-Based Redistribution in Free-Floating Bike Sharing Systems

We investigate the problem of user-based redistribution for free-floating bike sharing systems (BSS). We present a stochastic model of the bike dynamics and we show that the spatial distribution of bikes is correlated. This is specific to free-floating systems and it results in a substantially reduced service level.Offering incentives to users may stimulate them to change their behavior and usage pattern. We analyze drop-off incentives, derive an incentive methodology and study its potential. We show that by implementing a smart incentive system, the number of bikes for establishing a specific service level can be reduced significantly, even if only a minority of users participates. Under realistic behavioral assumptions, 30–50% reduction of bikes is achievable, which converts into substantial costs savings for the operator.Our research was carried out in the context of the development of the new e-bike sharing system “smide” in Zurich, launched in 2017. The incentive approach has been implemented and tested in a field test.

Christoph Heitz, Roman Etschmann, Raoul Stoeckle, Thomas Bachmann, Matthias Templ

Data Analytics for Trajectory Selection and Preference-Model Extrapolation in the European Airspace

Representing airspace users’ preferences in Air Traffic Flow Management (ATFM) mathematical models is becoming of high relevance. ATFM models aim to reduce congestion (en-route and at both departure and destination airports) and maximize the Air Traffic Management (ATM) system efficiency by determining the best trajectory for each aircraft. In this framework, the a-priori selection of possible alternative trajectories for each flight plays a crucial role. In this work, we analyze initial trajectories queried from Eurocontrol DDR2 data source. Clustering trajectories yields groups that are homogeneous with respect to known (geometry of the trajectory, speed) and partially known or unknown factors (en-route charges, fuel consumption, weather, etc.). Associations between grouped trajectories and potential choice-determinants are successively explored and evaluated, and the predictive value of the determinants is finally validated. For a given origin-destination pair, this ultimately leads to determining a set of flight trajectories and information on related airspace users’ preferences.

Carlo Lancia, Luigi De Giovanni, Guglielmo Lulli

Periodic Timetabling with ‘Track Choice’-PESP Based on Given Line Concepts and Mesoscopic Infrastructure

We present a track-choice and vehicle scheduling extension of the commonly known method for the generation of periodic event schedules ‘PESP’. The extension makes use of the mesoscopic track infrastructure representation widely used by public transport planners and operators. Taking into consideration the technical and operational constraints given by rolling stock, station and track topology data on the one hand, and the commercial requirements defined by a given line concept on the other, the method presented generates periodic timetables including train-track assignments. Due to the utilization of infrastructure based track capacities, we are also able to assess the feasibility of the line concept given. Additionally, the method allows for handling temporary resource restrictions (e.g. caused by construction sites or operational disturbances) up to a certain degree.

Raimond Wüst, Stephan Bütikofer, Severin Ess, Claudio Gomez, Albert Steiner, Marco Laumanns, Jacint Szabo

Efficiency of Semi-autonomous Platooning Vehicles in High-Capacity Bus Services

We analyze the efficiency of semi-autonomous platooning vehicles as an alternative to conventional vehicles in bus and BRT (bus rapid transit) systems. For each service type, optimal bus size, service headway and platoon length are obtained by minimizing total generalized cost, which includes passengers’ and the service provider’s costs. Results show that as the demand level increases, semi-autonomous vehicles can be introduced to enable a better service in both traditional bus and BRT systems. The benefits of semi-autonomous buses become more significant as the capacity upper bound decreases.

Wei Zhang, Erik Jenelius, Hugo Badia
Additional information

Premium Partner

    Image Credits