Operations Research Proceedings 2016

This article summarizes the findings of my Ph.D. thesis finished in 2015, whose topic are algorithmic approaches for the solution of network design problems. I focus on the results of a joint project with Deutsche Bahn AG on developing an optimal expansion strategy for the German railway network until 2030 to meet future demands. I have modelled this task as a multi-period network design problem and have derived an efficient decomposition approach to solve it. In a case study on real-world data on the German railway network, I demonstrate both the efficiency of by method as well as the high quality of the solutions it computes.

This work summarizes insights related to bidirectional traffic on a stretch containing bottleneck segments. On a bottleneck segment, concurrent traveling of vehicles in opposite direction is restricted. The considerations are motivated by the ship traffic at the Kiel Canal which connects the North and Baltic Seas and is operated bidirectionally. Since ships register their travel requests only on short notice, we investigate the Canal’s ship traffic additionally in the online setting.

The presented research addresses the integrated segmentation of supply and demand with service differentiation by means of service-level menus. To this end, it establishes a joint perspective on the market side—that is, prices and service levels—and the operations side—that is, the inventory management policy and the corresponding parameters. This joint perspective comprises analyzing when the introduction of a service-level menu increases profits over those of a single undifferentiated offering and how to design optimal service-level menus. Surprisingly, in many cases service differentiation does not increase profits significantly. One way to interpret this finding is that differentiating customers based on service levels alone is a weak differentiation lever only, that is, the price differences between offerings with differing service levels need to be small in order to prevent customers from switching to offerings with lower prices and service levels. Therefore, successful price differentiation requires service differentiations being supported by presence of additional conditions or measures (e.g., pricing restrictions or further differentiation levers). Indeed, it is possible to show that service differentiation can significantly increase profits if the company experiences pricing restrictions.

In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.

Induced by the rise of online retailing new storage strategies have evolved, designed to meet the demands of e-commerce warehousing. Although many of these new approaches have established over the last few years, literature on basic planning problems in these environments can be found only rarely. This paper points out the special needs of e-commerce warehousing and details the scattered storage strategy (also known as mixed-shelves storage) where unit loads are unbundled and single items are stored at multiple positions within the warehouse. This way, an item of an ordered product is always close by and the unproductive walking time of pickers is reduced. Based on the paper of Weidinger and Boysen (Scattered storage: how to distribute stock keeping units all around a mixed-shelves warehouse. Working Paper Friedrich-Schiller-University Jena, 2015) [8], the scattered storage assignment problem is presented and the processes in a scattered storage warehouse are described.

This research work is concerned with integrated location-inventory optimization in spare parts networks. A semi-Markov decision process (SMDP) is developed, formulated as linear program (LP) and finally, embedded into a set-covering problem framework. The resulting model is a mixed integer linear program (MILP) which integrates (1) strategic facility choice, (2) tactical base-stock level setting and (3) operational sourcing decisions. Due to the integration of these decision stages, physical and virtual inventory pooling opportunities can be evaluated at the same time. Experimental results emphasize the value of the integrated model compared to the sequential ‘location first, inventory and sourcing second’ approach. The cost savings are particularly high in networks with low fixed facility location cost, high shipment cost and high demand rates as virtual inventory sharing opportunities increase in these cases.

Motivated by optimal orchestration of virtual machines in mobile cloud computing environments to support mobile users, we face the problem of retrieving user trajectories in urban areas, when only aggregate information on user connections and trajectory length distribution is given. We model such a problem as that of finding a suitable set of paths-over-time on a time-dependent graph, proposing extended mathematical programming formulations and column generation algorithms. We experiment on both real-world and synthetic datasets. Our approach proves to be accurate enough to faithfully estimate mobility on the synthetic datasets, and efficient enough to tackle real world instances.

Electric vehicles (EVs) can play a central role in today’s efforts to reduce CO$$_2$$ emission and slow down the climate change. Two of the most important reasons against purchase or use of an EV are its short range and long charging times. In the project “E-WALD—Elektromobilität Bayerischer Wald”, we develop mathematical models to predict the range of EVs by estimating the electrical power consumption (EPC) along possible routes. Based on the EPC forecasts the range is calculated and visualized by a range polygon on a navigation map. The models are based on data that are constantly collected by cars within a commercial car fleet. The dataset is modelled with three methods: a linear model, an additive model and a fully nonparametric model. To fit the linear model, ordinary least squares (OLS) regression as well as linear median regression are applied. The other models are fitted by modern machine learning algorithms: the additive model is fitted by boosting algorithm and the fully nonparametric model is fitted by support vector regression (SVR). The models are compared by mean absolute error (MAE). Our research findings show that data preparation is more influential than the chosen model.

The estimation of consumer preferences with choice-based conjoint (CBC) models is well-established. In this context, the use of Hierarchical Bayesian (HB) models, which estimate consumers’ individual preferences is nowadays state-of-the-art. However, the knowledge of consumer preferences on a less disaggregated level, like segment-level, is key for demand predictions of non-customized products. Clustering individual HB data to achieve segment-level preferences is known as inappropriate, since 2-step segmentation approaches generally underlie 1-step approaches, e.g., Latent Class models. But, may the inclusion of different concomitant variables into the clustering process of individual CBC data relax that disadvantage? To answer this question, we used an empirical data set and compared the forecasting accuracy of 1- and 2-step approaches. While demographic variables showed small effects, psychographic variables turned out to heavily improve forecasting accuracy. In particular, 2-step approaches, that consider psychographic variables within the clustering process, showed a forecasting accuracy comparable to the one of 1-step approaches.

Models for workforce planning and scheduling have been studied in operations research for decades. Driven by the Industrial Internet of Things new data sources have become available that have not yet been used to improve field service management. This paper proposes a research agenda towards leveraging this potential in the context of industrial maintenance. By combining predictive analytics (e.g. forecasting demand) with prescriptive analytics (e.g. determining optimal maintenance schedules) companies can decrease uncertainties in their maintenance planning, increase the availability of machines, decrease overall maintenance costs, and ultimately develop new business models.

This work proposes an approach to the optimal placement of a weather radar network based on solutions to a multi-objective optimization problem. Given a finite number of weather radars, a network is produced by taking into account the maximization of network coverage area and the minimization of network general cost. Several constraints on the solutions are considered such as terrain blockage, radar beam elevation and distance from power grid and roads. By transforming the search space into a gridded system, a reduction in the number of possible combinations of radar networks is achieved making the problem manageable in size. The multiobjective optimization problem is solved by four different evolutionary algorithms and the obtained results are analysed using different performance metrics. The proposed approach can serve as an analysis tool for a decision support system by providing meteorologists a set of Pareto-optimal solutions to assist in the selection of future prime sites for the installation of weather radars.

The integration of decision-making procedures typically assigned to different hierarchical levels in a production system (strategic, tactical, and operational) requires the use of complex multi-scale mathematical models and high computational efforts, in addition to the need of an extensive management of data and knowledge within the production system. The aim of this study is to propose a comprehensive solution for this integration problem through the use of Conceptual Constraints. The presented methodology is based on a model in a domain ontology and the use of generalized concepts to develop tailor-made decision making models, created according to the introduced data. Different decision making formulations are reviewed and, accordingly, comprehensive Conceptual Constraints for the different concepts (like material balances) can be determined. This work shows how these Conceptual Constraints can be used when the quality of information is changed, enabling multi-scale implementations.

We apply methods of tropical optimization to handle problems of rating alternatives on the basis of the log-Chebyshev approximation of pairwise comparison matrices. We derive a direct solution in a closed form, and investigate the obtained solution when it is not unique. Provided the approximation problem yields a set of score vectors, rather than a unique (up to a constant factor) one, we find those vectors in the set, which least and most differentiate between the alternatives with the highest and lowest scores, and thus can be representative of the entire solution.

The university course timetabling problem deals with the task of scheduling lectures of a set of university courses into a given number of rooms and time periods, taking into account various hard and soft constraints. The goal of the International Timetabling Competitions ITC2002 and ITC2007 was to establish models for comparison that cover the most frequently found use cases. Our model, motivated by a project with University College London (UCL), builds on the standard model from track 3 of ITC2007. Compared to the standard model from the literature, we cover several new constraints and extra features. For example, we expand the ITC2007 framework to generate a timetable for several weeks of the term instead of only one and introduce the corresponding timetable regularity metric, which measures the consistency of time and room assignments for a course throughout the term. We suggest an Integer Linear Programming approach for solving this expanded timetabling problem and introduce a corresponding new benchmark library. Finally we conduct computational experiments and discuss the results obtained with respect to solution quality and practical suitability for UCL.

We present a new approach to create instances with high absolute worst-case performance ratio of common lower bounds for the two-dimensional rectangular Strip Packing Problem. The idea of this new approach is to optimize the width and the height of all items regarding the absolute worst case performance ratio of the lower bound. Therefore, we model the pattern related to the lower bound as a solution of an ILP problem and merge this model with the Padberg-type model of the two-dimensional Strip Packing Problem. The merged model maximizes the absolute worst-case performance ratio of the lower bound. We introduce this new model for the horizontal bar relaxation and the horizontal contiguous bar relaxation.

Based on the Woodbury matrix identity, we present a heuristic and a test-problem generation method for decomposing an invertible input matrix into a low-rank component and a component having a sparse inverse.

We consider the FIFO Stack-Up problem which arises in delivery industry, where bins have to be stacked-up from conveyor belts onto pallets. Given are k sequences $$q_1, \ldots , q_k$$ of labeled bins and a positive integer p. The goal is to stack-up the bins by iteratively removing the first bin of one of the k sequences and put it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. In this paper we consider on-line algorithms for instances where we only know the next c bins of every sequence instead of the complete sequences. We implemented our algorithms and could show that for realistic, but randomly generated instances our best approach leads only 12% more stack-up places than an optimal off-line solution. On the other hand we could show worst-case examples which show an arbitrary large competitive factor when comparing our on-line solutions with optimal off-line solutions.

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 that can hold several customers and have a special structure (in our case equidistant and non-overlapping). In this work, we consider an on-line variant of the cVRPsTW that arises in the online shopping service of an international supermarket chain: customers choose a delivery time window for their order online, and the fleet’s tours are updated accordingly in real time. This leads to two challenges. First, the new customers need to be inserted at a suitable place in one of the existing tours. Second, the new customers have to be inserted in real time due to very high request rates. This is why we apply a computationally cheap, two-step approach consisting of an insertion step and an improvement step. In this context, we present a Mixed-Integer Linear Program (MILP) and a heuristic that employs the MILP. In an experimental evaluation, we demonstrate the efficiency of our approaches on a variety of benchmark sets.

We consider a spectrum aggregation based spectrum allocation problem (SAP) for coexisting wireless systems: find the maximum number of secondary users whose bandwidth requirements can be satisfied by aggregating (parts of) given spectrum holes. In the classical form, this optimization problem turns out to share a common structure with the one-dimensional skiving stock problem (SSP), where as many (large) items as possible have to be constructed simultaneously by combining (smaller) items of a given supply. However, in practice, the spectrum aggregation is usually restricted by hardware limitations, such as filter technologies, and the capability of controlling interference. These additional constraints separate the considered problem from an ordinary SSP, and represent a new challenge in the field of discrete optimization. This article provides a general introduction to the relations between the SSP and the SAP. Moreover, we will discuss, how practically meaningful extensions of the classical SAP can be tackled from a mathematical point of view. As a main contribution, we exploit some important problem-specific properties to derive tailored solution techniques.

In this study, we consider a scheduling extension for the two-stage cutting stock problem with the integration of order due dates. The two-stage cutting stock problem arises when technical restrictions inhibit demanded items to be cut from stock rolls directly, and hence require the cutting process to be done in two subsequent stages. The mathematical model proposed for the due date extension aims to determine a cutting plan which not only minimizes the number of stock rolls used but also reduces tardiness and earliness costs incurred. Preliminary results have shown that the modeling approach used is capable of overcoming difficulties caused by the dependencies between stages.

In electricity systems unit commitment problems (UCP) target at a proper scheduling and coordinating of thermal plants, renewable energies, and storages. The need for fast solution methods has been growing in line with recent changes in the electricity system’s environment and complexity, in particular with the increasing share of volatile renewable feed-ins. In order to meet this need even for large-scale systems a decomposition methodology for the UCP is suggested within this paper. Our two-stage decomposition first performs an isolated dispatching of thermal plants using a greedy algorithm, rule-based algorithms and local search based steps, followed by a re-optimization stage in order to incorporate energy storages into the final solution. The comparison of the iterative two-stage heuristic with commonly used approaches based on mixed integer linear programming shows outstanding results in terms of solution time and solution quality. Besides typically used test instances, the heuristic is applied to comprehensive case studies of the German electricity market, where (near-) optimal solutions can be derived for a yearly planning horizon with hourly time steps with computational effort of a few minutes using a standard PC.

Germany’s energy system transformation process “Energiewende” implies, on the one hand, the promotion of renewable energy sources and, on the other hand, difficulties in the profitable operation of many modern conventional power plants due to increasing shares of renewable electricity and decreasing electricity wholesale prices. Nevertheless, the prioritized conventional power generation technologies are still needed in times of low wind and solar power generation in order to maintain the security of electricity supply. Regarding these aspects and the specific situation in the federal state of North Rhine-Westphalia, the problem of further operation of lignite-fired power plants is of particular importance. In the study undertaken we tackled the following research questions: Should lignite-fired power plants be operated without any changes until the end of their lifetime? Can already existing lignite-fired power plants be operated more flexibly? If so, which flexibility options should be taken into consideration? What is the optimal investment time for these flexibility options? Are investments in other power generation technologies more suitable for ensuring system stability than investing in the retrofitting of existing lignite-fired power plants is? To answer these questions, we propose an optimization model that is based on real options analysis (ROA) and, more precisely, on the option of choosing. In the proposed model, the economic as well as technical aspects of the power plant operation are taken into consideration for the profitability calculations. Moreover, the results show the importance of the subsidies for lignite-fired power plants and their further operation.

In the paper at hand we evaluate how a basic whitelist-approach with keywords performs on automatically assigning micro blog data (tweets) to customer need categories in the field of e-mobility. We are able to identify certain characteristics that determine the classification success like unambiguousness and uniqueness of the whitelist words.

The expansion of gas-fired power plants has led to increasing interactions between the natural gas and electricity market. In order to effectively manage risk of volatile energy prices, operators of gas-fired power plants need to take natural gas procurement and power plant resource planning simultaneously into account. An industrial company is considered that owns a gas-fired combined heat and power (CHP) plant. To ensure a stable heat and power supply, the amount of gas needed to operate the CHP plant must be available at any time. Natural gas can be procured by signing supply contracts or by engaging in the natural gas spot market. A two-stage stochastic MILP model is proposed that optimises the gas supply portfolio and the CHP plant operation according to revenue potential in the electricity spot market. Uncertainty of gas and electricity spot prices is addressed by means of stochastic processes. Price risk is explicitly taken into account by the Conditional Value-at-Risk (CVaR). A convex combination of expected total costs and CVaR allows for representing different risk preferences of the decision maker. The efficient performance of the presented approach is illustrated in a case study using the example of German energy markets. The results reveal the significant influence of different risk preferences on the optimal gas supply portfolio composition.

The Unit Commitment Problem (UCP) aims at finding the optimal commitment for a set of thermal power plants in a Power System (PS) according to some criterion. Our work stems from a collaboration with RSE S.p.A., a major industrial research centre for PSs in Italy. In this context the UCP is formulated as a large-scale MILP spanning countries over a year with hourly resolution to simulate the ideal behaviour of the system in different scenarios. Our goal is to refine existing heuristic solutions to increase simulation reliability. In our previous studies we devised a Column Generation algorithm (CG) which, however, shows numerical instability due to degeneracy in the master problem. Here we evaluate the application of Benders Decomposition (BD), which yields better conditioned subproblems. We also employ Magnanti-Wong cuts and a “two-phases scheme”, which first quickly computes valid cuts by applying BD to the continuous relaxation of the problem and then restores integrality. Experimental results on weekly instances for the Italian system show the objective function to be flat. Even if such a feature worsens convergence, the algorithm is able to reach almost optimal solutions in few iterations.

Co-firing of biomass in coal-fired power plants is considered one of the most economic ways of carbon dioxide abatement. We investigate the deployment and relocation of several semi-mobile processing facilities in order to supply a large coal-fired power plant with high-quality renewable energy carriers. Semi-mobile facilities are characterized by a containerized design and can be relocated in case of changes in supply and demand. The energy carriers which are produced by different types of semi-mobile technologies are bulky goods with high density and properties comparable to those of coal and fuel oil. Thus, intermodal transportation is required to achieve transportation costs which are competitive with the delivered cost of fossil fuels at the plant’s gate. The optimization of the investigated supply chain therefore requires simultaneous planning of semi-mobile facility deployment and intermodal transportation. To this end, we present a mixed-integer linear problem which optimizes the number of semi-mobile facilities, their respective relocation over time and the intermodal transportation of produced energy carriers to the power plant. In the presented case, train transportation is characterized by a low geographical coverage of the railway network and restrictions representing minimum shipping volumes per railway line. The model minimizes the objective function of total supply chain costs including electricity generation, transportation, the operation and relocation of the semi-mobile plants and the necessary forestry operations associated with the deployed facilities. The model is implemented in GAMS and solved using the CPLEX solver. We discuss a numerical example based on data from the forestry and energy sector in Chile.

Renewable energy investments are typically evaluated using traditional discounted cash flow (DCF) methods, such as the net present value (NPV) or the internal rate of return (IRR). These methods utilize the discount rate as an aggregate proxy for risk and the time value of money, which leads to an inadequate modeling of risk. An alternative to these methods represents the decoupled net present value (DNPV). Instead of accounting for risk in the discount rate, the DNPV utilizes so-called synthetic insurance premiums. These allow for the individual and disaggregate pricing of risk and can enhance the quality of investment decisions by facilitating a more detailed and comprehensive representation of the underlying risk structure. To reliably estimate and forecast synthetic insurance premiums requires the availability of appropriate data and expertise in interpreting this data. Thus, the practicality of the results calculated based on the DNPV depends on the quality of the inputs and the expertise of the analyst. After reviewing the main theory of the DNPV, we apply the method to a wind energy investment case to demonstrate its applicability and prospects. To illustrate the calculation of the synthetic insurance premiums, selected risk factors are modeled with probability distributions via Monte Carlo simulation (MCS). Our results show that the DNPV’s seamless integration of risk assessment with investment evaluation is a promising combination and warrants further research.

A coalition of freight carriers is considered which has to decide how to allocate a pool of transport requests among its members. The literature is aware of a number of solution approaches which usually assume truthful behavior of the freight carriers. However, the used negotiation protocols are mostly not proven to enforce truthful behavior. This paper gives some insights into the impact of non-truthful behavior via computational experiments. We solve the collaborative problem via a genetic algorithm (GA) which is operated by an auctioneer. The GA’s individuals are allocations of requests to carriers. To calculate the fitness of an individual, the carriers bid on the allocations. Bidding below a carrier’s true valuation could ceteris paribus increase its profits. However, understated valuations can influence the search process negatively, in particular when a favoured allocation is dismissed wrongly. It is shown via computational experiments that for six tested instances, bidding non-truthfully is individually, but not collectively, rational and results in a kind of prisoner’s dilemma.

The equilibrium selection in games with multiple equilibria, such as coordination games, depends on one player’s beliefs about the other player’s behavior; as such, the outcome of the game depends on the players’ expectations of one another’s behavior. This study assessed the extent to which players’ higher order beliefs influence the strategic choices they make during $$2\times 2$$ coordination games. Using a quadratic scoring rule, the players’ higher order beliefs about the choices their opponent would make were directly elicited in a laboratory experiment. The players’ higher order beliefs were analyzed to ascertain the extent to which players’ depth of thinking influenced their strategic decisions. In addition, this study focused on the question of whether the players update their beliefs to build higher order beliefs. The findings of the study revealed that the average participant operated on four steps of strategic depth. Higher order beliefs follow different patterns. In most cases, these contrast Bayesian updating.

We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to a formulation in Borndörfer et al. (Networks, 65, 312–328, [1]) using flows to describe the users’ strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.

Gearboxes are mechanical transmission systems that provide speed and torque conversions from a rotating power source. Being a central element of the drive train, they are relevant for the efficiency and durability of motor vehicles. In this work, we present a new approach for gearbox design: Modeling the design problem as a mixed-integer nonlinear program (MINLP) allows us to create gearbox designs from scratch for arbitrary requirements and—given enough time—to compute provably globally optimal designs for a given objective. We show how different degrees of freedom influence the runtime and present an exemplary solution.

Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) “unimodal demand” case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed.

The Particle-Image Velocimetry (PIV) is a standard optical contactless measurement technique to determine the velocity field of a fluid flow for example around an obstacle such as an airplane wing. Tiny density neutral and light-reflecting particles are added to the otherwise invisible fluid flow. Then two consecutive images (A and B) of a thin laser illuminated light sheet are taken by a CCD camera with a time-lag of a few milliseconds. From these two images one tries to estimate the local shift of the particles, for which it is common to use a cross-correlation function. Based on the displacement of the tracers and the time-lag, the local velocities can be determined. This method requires a high level of experience by its user, fine tuning of several parameters, and multiple pre- and post-processing steps of the data in order to obtain meaningful results. We present a new approach that is based on the matching problem in bipartite graphs. Ideally, each particle in image A is assigned to exactly one particle in image B, and in an optimal assignment, the sum of shift distances of all particles in A to particles in B is minimal. However, the real-world situation is far from being ideal, because of inhomogeneous particle sizes and shapes, inadequate illumination of the images, or particle losses due to a divergence out of the two-dimensional light sheet area into the surrounding three-dimensional space, to name just a few sources of imperfection. Our new method is implemented in MATLAB with a graphical user interface. We evaluate and compare it with the cross-correlation method using real measured data. We demonstrate that our new method requires less interaction with the user, no further post-processing steps, and produces less erroneous results. This article is based on the master thesis [5], written by the first coauthor, and supervised by all other coauthors.

We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.

As a result of specific constructs and features, many graphs do not admit OLD-sets. We extend the traditional OLD-set definition by relaxing the dominating property. Instead of requiring all nodes to be covered by an OLD-set, we seek what we call a maximum covering OLD-set. Every graph has a maximum covering OLD-set. Furthermore, maximum covering OLD-sets allow an exploration of the tradeoff between the number of sensors placed and the number of nodes covered.

A large part of revenue in hospitals is generated in surgical departments. In order to use available resources efficiently, we propose an innovative tactical optimization model to optimally allocate operating hours for operating rooms. An extensive simulation study is applied to evaluate the tactical plan with respect to main stakeholders. Results indicate strongly positive effects on staff and patients.

The Periodic Traveling Politician Problem (PTPP) deals with determining daily routes for a party leader who holds meetings in various cities during a campaign period of $$\tau $$ days. On a graph with static edge costs and time-dependent vertex profits, PTPP seeks a closed or open tour for each day. The objective is the maximization of the net benefit defined as the sum of rewards collected from meetings in the visited cities minus the traveling costs normalized into a compatible unit. The reward of a meeting in a city are linearly depreciated according to the meeting date and recency of the preceding meeting in the same city. We propose a MILP formulation in which we capture many real-world aspects of the PTPP.

In addition to cost and time, greenhouse gas (GHG) emissions have become a further command variable for planning processes in the transportation industry. A large number of scientific literature is devoted to the development of planning approaches taking into account the emissions of transport processes. In order to minimize a transport process’ emissions, many factors affecting emissions have been studied. Besides the total distance covered by a transport process, the modal split, payload, traveling speed as well as vehicle type and specifications are identified as most influential planning parameters.

The fill rate service measure describes the proportion of customers who commence service immediately upon arrival. Since, however, customers will usually tolerate a certain wait time, managers should consider the window fill rate in lieu of the fill rate. That is, the performance measure of interest is the probability that a customer is served within the tolerable wait time. In this paper, we develop approximation formulas for the window fill rate in a two-echelon, exchangeable-item repair system in which the upper echelon is a central depot and the lower echelon comprises multiple locations. We demonstrate the use of the formulas through a numerical example and measure the approximation error of the window fill rate formulas using simulation.

Redistricting is the redrawing of the boundaries of legislative districts for electoral purposes in such a way that Federal or state requirements are fulfilled. In 2015 the National Electoral Institute of Mexico carried out the redistricting process of 15 states using a nonlinear programming model where population equality and compactness were considered as conflicting objective functions, whereas other criteria, such as contiguity, were included as constraints. In order to find high quality redistricting plans in acceptable amounts of time, two automated redistricting algorithms were designed: a Simulated Annealing based algorithm, and an Artificial Bee Colony inspired algorithm. Computational results prove that the population based technique is more robust than its counterpart for this kind of problems.

This paper deals with the min-max fair emergency service system design under uncertain ability of service providing. Studied generalized system disutility follows the idea that the individual user’s disutility comes from more than one located center. We present here an advanced approximate algorithm for the min-max optimal emergency service system design, which is based on a radial formulation and valid exposing structures. Presented method enables its simple implementation within common optimization environment instead of special software development.

We optimize the routing of steel slabs between locations in a steel production facility during a one hour-long operational period. Steel slabs are heterogeneous items that appear at locations at different release times. Certain slabs need to be delivered to another location before their specified due time. They are transported by fleets that include standard vehicles as well as truck-and-trailer type vehicles. The vehicles visit several locations multiple times. The input is such that not all slabs can be delivered in time, therefore two objective functions are provided that are organized in a lexicographic fashion: First, we maximize the throughput. Second, we aim to minimize travel times. An exact solution can only be obtained for small problem settings. In order to solve larger instances, we developed a heuristic. The results show that the solutions obtained by the heuristic reveal significant improvements to the real world solutions provided by our industrial partner.

This paper considers an extended Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows (VRPSPDTW). For this problem we describe a simple but effective extension of a genetic algorithm (GA) based on chromosome permutation and a splitting procedure. For large instances it is obvious to use the original GA as benchmark. These approaches are applied on test instances for the considered problem and on Solomon instances.

Several publications on collaborative transportation planning problems (CTPPs) focus on schemes that ensure a fair assignment of collaborative profits. However, it is seldom taken into account that an even allocation of transportation resources (e.g. transportation requests) is also responsible for the viability and stability of horizontal carrier coalitions; particularly if dynamic CTPPs are considered. In this paper, the winner determination problem (WDP) of an auction-based request exchange is restricted by lower and upper bounds that respect an equality between transferred and received requests for carriers. In a computational study, the restricted WDP is applied to the dynamic collaborative traveling salesman problem.

Weather routing in maritime shipping is related to a shipping company’s objective to achieving maximum efficiency, economy and cost competitiveness by optimizing each voyage of a ship. A voyage can be optimized regarding cost, time, safety or a combination of these factors, while considering forecasted meteorological and oceanographic information as well as constraints given by geographic conditions, ship characteristics, emission regulations, safety requirements or time restrictions. A wide variety of mathematical models of the ship weather routing problem as well as different approaches to solve it can be found in the literature and are applied by numerous software systems. This paper presents two approaches to solve the ship weather routing problem, a graph algorithm and an evolutionary approach. Both approaches aim to minimize fuel costs, allowing for route and speed optimization. They are compared based on numerical examples with real-world data.

This study aims to improve the efficiency of container loading process at a seaport by optimizing the dynamic assignment of internal vehicle fleet in the process of moving containers from storage yards at maritime terminals to the train at the rail terminal. We formulate the problem into a stochastic dynamic programming model taking into account uncertain processing times. Numerical experiments based on a case study are performed to illustrate the effectiveness and the sensitivity of the model.

The capacitated vehicle routing problem with three-dimensional loading constraints (3L-CVRP) combines vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, the stability of packed goods. We consider a logistics company that repeatedly has to pick up goods at different sites. Often, the load of one site exceeds the volume capacity of a vehicle. Therefore, we focus on the 3L-CVRP with split delivery and propose a hybrid algorithm for this problem. It consists of a tabu search procedure for routing and some packing heuristics with different tasks. One packing heuristic generates packing plans for shuttle tours involving special sites with large-volume sets of goods. Another heuristic cares for packing plans for tours with numerous sites. The hybrid algorithm is tested with a set of instances which differs from often used 3L-CVRP test instances and comes from real industrial data, with up to 46 sites and 1549 boxes to be transported. The algorithm yields good results within short computing times of less than 1 min.

Biofuels derived from biomass can play a crucial role as one of the main sources of renewable energies. As logistics may represent up to 50% of biomass cost, it is necessary to design efficient biomass supply chains to provide bio-refineries with adequate quantities of biomass at reasonable prices and appropriate times. The task is challenging since, contrary to industrial logistics, the raw materials (oilseed and lignocellulosic crops) are produced slowly, seasonally, and with a limited yield, over vast territories. The paper proposes a Mixed Integer Linear Program (MILP) to optimize a multi-period and multi-biomass supply chain for several bio-refineries, at the tactical decision level. The locations of refineries can be fixed by the user or determined by the model. The aim is to minimize the total cost of the supply chain, including biomass production, pretreatments, storage, handling, bio-refineries setup and transportation, while satisfying given refinery demands in each period. The resulting MILP, already validated on medium-size instances, will be applied to a large-scale real case covering two regions of France (Champagne-Ardenne and Picardie) with 273 territorial units and 8 biomass types.

In recent publications, it is assumed that there are transportation requests which have to be fulfilled by certain resources (e.g., own vehicle fleet or external carriers) due to contractual obligations. These requests are known as compulsory requests. The contribution of this publication is to identify the increase in transportation costs caused by a combination of compulsory requests with different contractual obligations. To evaluate the impact of compulsory requests, an existing column generation-based heuristic with two solution strategies for handling compulsory requests is applied and the generated results are analyzed.

For a drug to be approved for human use, its safety and efficacy need to be evidenced through clinical trials. At present, patient recruitment is a major bottleneck in conducting clinical trials. Pharma and contract research organisations (CRO) are actively looking into optimisation of different aspects of patient recruitment. One of the avenues to approach this business problem is to improve the quality of selection of investigators/sites at the start of a trial. This study builds upon previous work that used Grammatical Evolution (GE) to evolve classification models to predict the future patient enrolment performance of investigators/sites considered for a trial. Selection of investigators/sites, depending on the business context, could benefit from the use of either especially conservative or more liberal predictive models. To address this business need, decision-tree type classifiers were evolved utilising different fitness functions to drive GE. The functions compared were classical accuracy, balanced accuracy and F-measure with different values of parameter beta. The issue of models’ generalisability was addressed by introduction of a validation procedure. The predictive power of the resultant GE-evolved models on the test set was compared with performance of a range of machine learning algorithms widely used for classification. The results of the study demonstrate that flexibility of GE induced classification models can be used to address business needs in the area of patient recruitment in clinical trials.

The article describes our work on an extension of the Inventory Routing Problem (IRP). While the basic formulation of the IRP combines delivery volume with vehicle routing decisions, and thus includes tactical and operative aspects, we here consider the strategic placement of the depot, also. In some first experiments, the effect of such a strategic decision on the inventory levels and routing costs in the supply chain is studied. Besides, potential improvements, i.e., savings in transportation costs are investigated. Our findings indicate that efficiency improvements are indeed achievable by extending the problem formulation towards the strategic planning level.

The Cable-Trench Problem (CTP) is the problem of minimizing the cost to connect buildings on a campus to a central server so that each building is connected directly to the server via a dedicated underground cable. The CTP is modeled by a weighted graph in which the vertices represent buildings and the edges represent the possible routes for digging trenches and laying cables between two buildings. In this paper, we define the Generalized Steiner CTP (GSCTP), which considers the situation in which a subset of the buildings is connected to the server and also the possibility that trench costs vary because of vegetation or physical obstacles, for example. The GSCTP has several natural applications, but we will focus on its nontrivial and novel application to the problem of digitally connecting microCT scan data of a vascular network with fully automated error correction. The CTP and its variants are NP-hard. However, we show that modifications to Prim’s algorithm find nearly optimal solutions to the GSCTP efficiently.

Operators deploy Small Cells in high traffic regions to boost the capacity of their wireless networks. However, User Equipments (UEs) at Small Cell edges experience severe interference from neighbouring high-powered Macro Cells. A fair trade-off between cell-edge and cell-centre performance can be realised by intelligently scheduling Small Cell attached UEs. Grammar-based Genetic Programming is employed to learn models that map measurement reports to schedules on a millisecond timescale. The evolved schedulers are then aggregated into ensembles. The proposed system significantly outperforms a state of the art benchmark algorithm and is within 10% of the estimated optimum.

In this paper, we investigate solving the Maximum Dispersion Problem (MaxDP). For a given set of weighted objects, the MaxDP consists in partitioning this set into a predefined number of groups, such that the overall dispersion of elements, assigned to the same group, is maximized. Furthermore, each group has a target weight and the total weight of each group must be within a specific interval around the target weight. It has been proven that the MaxDP is NP-hard and, consequently, difficult to solve by classical exact methods. In this work, we use variants of Variable Neighborhood Search (VNS) for solving the MaxDP. In order to evaluate the efficiency of VNS, we carried out some numerical experiments on randomly generated instances. The results of the VNS is compared with the solutions provided by the solver Gurobi. According to our results, the VNS gives high quality solutions for small instances and, in solving large instances, it provides some decent solutions for all instances; however, Gurobi fails to provide any solution for some of them.

In the process industry markets are facing new challenges: while product life cycles are becoming shorter, the differentiation of products grows. This leads to varying and uncertain product demands in time and location. As a reaction, the research focus shifts to modular production, which allow for a more flexible production network. Using small-scale plants, production locations can be located in direct proximity to resources or customers. In response to short-term demand changes, capacity modifications can be made by shifting modular units between locations or numbering up. In order to benefit from the flexibility of modular production, the structure of the network requests dynamic adaptions in every period. Subsequently, once the customer demand realizes, an optimal match between disposed production capacities and customer orders has to be determined. This decision situation imposes new challenges on planning tools, since frequent adjustments of the network configuration have to be computed based on uncertain demand. We develop stochastic and robust mixed-integer programming formulations to hedge against demand uncertainty. In a computational study the novel formulations are evaluated based on adjusted real-world data sets in terms of runtime and solution quality.

Carsharing is a transportation alternative that enables flexible use of a vehicle instead of owning it by paying trip-dependent fees. In recent years, this service denotes a considerable increase of new providers, which face an exponentially growing number of customers worldwide. As a consequence, rising vehicle utilization leads providers to contemplate revenue management elements. When focusing on station-based carsharing concepts, these are typically based on advance reservations. This makes them perfectly suitable for the application of demand-side management approaches. Demand-side management allows providers to optimize their revenues by accepting or rejecting certain trips. We respectively develop an optimization model for revenue management support. Based on an existing model of the hotel business, special consideration is drawn to carsharing related features. For instance, the implementation of a heterogeneously powered fleet allows providers to choose a certain limit of emissions to fulfill local requirements. We implement the mathematical model into the modeling environment GAMS using the solver Couenne. Conducted benchmarks show sensitivities under the variation of different input values, for example risk tolerances. In contrast to the often used first-come first-serve-principle, the results indicate the usefulness of the developed model in optimizing revenues of todays carsharing providers.

In airline revenue management, capacity is usually assumed to be fixed. However, capacity changes are common in practice. This contribution quantifies the value of information when systematically considering possible capacity changes in revenue optimization. It solves a stochastic model that anticipates capacity changes, given different levels of information. A computational study compares solution approaches with respect to the resulting revenue, seat load factor, and denied boarding.

The ongoing boom in e-commerce increases the importance of profitable and customer-oriented delivery services. Particularly in metropolitan areas, the high population density offers great potential for e-commerce, while uncertain demand and traffic conditions increase planning uncertainty. This contribution focuses on e-commerce delivery fulfillment (e-fulfillment) for attended last-mile delivery services in metropolitan areas. As the customer needs to be present for deliveries of groceries, for example, a service time window has to be agreed upon already when a customer’s order is accepted. We consider service time windows as a scarce resource and as the critical interface between order capture and order delivery. To optimally utilize this scarce resource, we propose combining concepts of revenue management and vehicle routing to extend tactical and operational planning for e-fulfillment. We define the research problem and provide a perspective on integrated planning for attended deliveries. Furthermore, we present the design of a virtual laboratory to support benchmarking in e-fulfillment research. To ensure realistic experimental settings, we plan to incorporate real-world data provided by a major e-grocery in Germany.

While cruise lines share a variety of characteristics with airlines, hotels and especially casinos, revenue management approaches which are suitable for other sectors of the hospitality industry have to be adapted in order to meet the special requirements of cruise lines. Until now, decision support systems, optimization models, as well as pricing and allocation policies for cruise line revenue management have attracted little attention in the field of operations research. Based on a review of the existing literature, research gaps are identified and possible approaches to close these gaps are suggested.

In retail, assortment planning refers to selecting a subset of products to offer that maximizes profit. Assortments can be planned for a single store or a retailer with multiple chain stores where demand varies between stores. In this paper, we assume that a retailer with a multitude of stores wants to specify her offered assortment. To suit all local preferences, regionalization and store-level assortment optimization are widely used in practice and lead to competitive advantages. When selecting regionalized assortments, a trade-off between expensive, customized assortments in every store and inexpensive, identical assortments in all stores that neglect demand variation is preferable. We formulate a stylized model for the regionalized assortment planning problem (APP) with capacity constraints and given demand. In our approach, a common assortment that is supplemented by regionalized products is selected. While products in the common assortment are offered in all stores, products in the local assortments are customized and vary from store to store. Concerning the computational complexity, we show that the APP is strongly NP-hard. The core of this hardness result lies in the selection of the common assortment. We formulate the APP as an integer program and provide algorithms and methods for obtaining approximate solutions and solving large-scale instances. Lastly, we perform computational experiments to analyze the benefits of regionalized assortment planning depending on the variation in customer demands between stores.

In the manufacturing industry, storing spare parts means capital commitment. The optimization of spare parts inventory is a real issue in the field and a precise forecast of the necessary spare parts is a major challenge. The complexity of determining the optimal number of spare parts increases when using the same type of component in different machines. To find the optimal number of spare parts, the right balance between provision costs and risk of machine downtimes has to be found. Several factors are influencing the optimum quantity of stored spare parts including the failure probability, provision costs and the number of installed components. Therefore, an optimization model addressing these requirements is developed. Determining the failure probability of a component or an entire machine is a key aspect when optimizing the spare parts inventory. Condition monitoring leads to a better assessment of the components failure probability. This results in a more precise forecast of the optimum spare parts inventory according to the actual condition of the respective component. Therefore, data from condition monitoring processes are considered when determining the optimal number of spare parts.

We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within $$\sqrt{6}/2$$ times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.

In this paper we study the problem of computing the expected cycle time of a storage and retrieval system executing single-command cycles and being operated according to the closest open location rule. Assuming that the arrivals of the storage and the retrieval orders at the storage follow independent Poisson processes, we first consider the case of homogeneous inventory and develop closed-form expressions for the steady-state probabilities of a given storage location being selected for storage or retrieval. The approach is then generalized to storages with multiple stock keeping units. Comparing our results with estimation formulas from industry standards shows that the latter tend to significantly underestimate the maximum throughput of storage and retrieval systems.

The growing globalization and the rapid technical development intensify competition for nearly all manufacturing companies and increase the pressure to act. For companies using tooling machines to process metal, there is only little potential to improve the processing itself. A holistic view on the production system, however, provides an opportunity for cost savings and optimization. Therefore a two-level concept for lot sizing and scheduling is presented, transferring two different lot sizing and scheduling models from the literature into an integrated one. Each of the two models has a different time scope and an adjusted level of detail. The solution behavior and solution quality is analyzed for different test instances, and the advantages and disadvantages of such a two-level concept are pointed out.

The demand for electrical power in industrial production processes arises often in high energy costs for companies. In the future volatile energy rates, which are a consequence of the increasing power generation from renewable energies, can influence these energy costs. In order to reduce the energy costs with the help of volatile energy rates, latter have to be considered in the production scheduling. To date, only few planning approaches in the field of job-shop scheduling deal with volatile energy rates. A transfer into planning tasks of serial production as the economic lot scheduling problem is missing. This contribution introduces a planning approach for the energy-oriented lot sizing and scheduling problem.

In this paper, we handle an audit scheduling problem in which the task requirements and the auditor experiences are quantified and forge a set of restrictions in team formation. We propose a mathematical model for this problem, propose two heuristics for its solution, and evaluate their performance through computational experiments.

Increasing emergence of large amounts of discarded products puts pressure on manufacturers in the consumer goods industry. They have to balance economic considerations with environmental expectations of their costumers and legal obligations imposed by the government body. In this context, efficient disassembly helps to enable profitable remanufacturing of end-of-life products or at least limit the losses from disposal. This study represents a novel approach to combine the problems of disassembly sequence planning and machine scheduling. In contrast to existing formulations in the research field, the proposed model explicitly considers divergence of the product structure as inherent feature of disassembly. As a result, disassembly operations related to separate sub-assemblies of the same product can be scheduled at the same time. The proposed mixed integer programming formulation is solved using commercial optimization software and first computational implications are drawn from a short numerical study.

In this work we propose and analyze a hybrid approach for the multi-mode resource investment problem with tardiness penalty (MRIPT). The MRIPT is a project scheduling problem where, for a given deadline, the objective is to minimize the costs of resources allocated to the project as well as tardiness penalty costs for not respecting the given deadline. For each project activity multiple execution modes with differing resource requirements and durations are given. In particular, we propose a large neighborhood search where destroy operators are applied to a feasible solution to obtain subproblems. These subproblems are solved with MIP-based recreate operators to obtain an improved solution.

Multi-Mode Resource-Constrained Multi-Project Scheduling Problems (MRCMPSP) with large solution search spaces cannot be optimized in an acceptable computation time. In this paper, we have focused on decomposition strategies for such large scale problems. Based on literature review a time-based decomposition approach was adopted for the present problem. With time-based decomposition approaches a schedule is divided into several time periods. All activities in a time period describe an independent problem, termed as a sub-problem. Due to the independent optimization of these sub-problems project information regarding the relationships among activities in different time periods is not considered. This loss of information has a negative impact on the overall solution quality. We developed a decomposition strategy to improve the interactions between the sub-problems for a better target performance while reducing the computation time. Based on an initial solution the sub-problems are created and sequentially optimized in a concept similar to rolling horizon heuristics. We introduce a transition stage with a constant and a variable component at the end of each partial schedule to improve the interactions among sub-problems and thus taking the volatile nature of the examined problems into account. In comparison, our approach proved to provide significant improvements in runtime and target performance.

We consider the flow shop problem with two machines and time delays with respect to the makespan, i.e., the maximum completion time. We recall the lower bounds of the literature and we propose new relaxation schemes. Moreover, we investigate a linear programming-based lower bound that includes the implementation of a new dominance rule and a valid inequality. A computational study that was carried out on a set of 480 instances including new hard ones shows that our new relaxation schemes outperform the state of the art lower bounds.

To ensure safe and efficient ship operations a proper schedule of crew tasks is necessary. This encompasses a work plan for the crew, consisting of appropriately qualified seafarers, which also complies with the rules of the Maritime Labour Convention (MLC). The optimized crew schedule can reduce crew costs for shipping companies and also help to avoid expensive ship detentions by port state authorities due to incompliances in the crew’s work plan. A mathematical model is presented for the crew scheduling problem, which is subject to complex rule sets for working and resting hours. In this model the mandatory tasks for safe ship operation and the crew qualification requirements for these tasks represent the main input parameters. They depend on variables such as the ship type and route and may differ substantially. Furthermore, the model considers common watch-keeping patterns and special constraints on mandatory tasks. This problem is formulated as mixed integer linear program. Numerical experiments with different small real data sets from business practice are also presented.

Managing energy consumption more sustainably and efficiently has been gaining increasing importance in all industrial planning processes. Energy aware scheduling (EAS) can be seen as a part of that trend. Overall, EAS can be subdivided into three main approaches. In detail, the energy consumption can be reduced by specific planning, time-dependent electricity cost might be exploited or the peak power may be decreased. In contrast to the majority of EAS models these ideas are adopted simultaneously in the proposed new extensive MILP formulation. In order to affect peak load and energy consumption, variable discrete production rates as well as heterogeneous parallel machines with different levels of efficiency are considered. As a result, the interdependencies of different energy aware scheduling approaches and especially a dilemma between peak power minimization and demand charge reduction can be shown.

We present lower bounds (LB) for the multi-mode resource-constrained project scheduling problem (MRCPSP). Traditionally, the LB for the MRCPSP are derived from the critical path method (CPM). Here, the mode with the shortest duration of each activity is chosen. We improve these LB. New earliest starting times (EST) are calculated by solving several integer programs with a standard solver. These new EST partially improve the EST calculated by the critical path method. This also reduces the number of variables in the model and, in the best case, proves optimality of the best known solutions. Computational results show that these new starting times provide a tighter bound than the LB obtained from CPM.

The overall dynamics of an airport are multifaceted and very complex. With the ever increasing number of visitors everyday it is important to understand their behaviour. In this paper we present a new macroscopic system dynamics model of the overall workings of a generic airport. The model follows passengers through to the gates modeling various different behaviors on the way there. It also includes implicitly the fleet composition, the number of lanes and explicitly the impact on the noise level. Extra effort was taken to allow for the inherent stochasticity of many of these multi-layered processes. To make it more flexible on- and off-peak times are implemented as well. Moreover random extreme events in the form of emergency landings and heightened security levels have been included. First results provide insight to the change in system behavior under these circumstances.

Consumer adoption of innovations is a key concern for strategic management in many companies as adoption ultimately drives the market success of new products. The respective adoption processes are inherently complex due to the social systems (i.e., the respective consumer markets) from which they arise. Markets characterized by the simultaneous presence of several multi-generation technologies, wherein products that rest upon successively introduced generations of technology compete against each other, constitute a particularly challenging case. Our agent-based model contributes to the field of technology diffusion research in that it accounts for novel and advanced product features in each technology generation, the reluctance of (some) users to switch to a new (as yet unfamiliar) technology, and various social influences between consumers. Calibrated with data from several sources, our results closely replicate the actual development of the German consumer computer market from 1994 to 2013.

The decomposition method for non-product form networks with non-exponentially distributed interarrival and service times assumes that nodes within the network can be treated being stochastically independent and internal flows can be approximated by renewal processes. The method consists of three phases to calculate the interarrival times of a node: merging, flow, splitting. Some well-known approximation formulas for ordinary single class open queueing networks calculate the characteristics in each phase for each node as shown by Kuehn, Chylla, Whitt and Pujolle/Ai. Node performance measures such as mean queue length are determined by using approximation formulas for non-Markovian queues. In 2011 the decomposition method was extended to open queueing networks with batch processing using the approximation formula described by Pujolle/Ai. A comparison with discrete event simulation as benchmark shows that the approach provides good results. Thus, the approach was expanded for the approximation given by Kuehn, Chylla and Whitt. Since the method consists of several phases it is possible to combine different formulas. For example, merging will be approximated by Kuehn and flow by Whitt. To perform an evaluation the benchmark was done in regard to the 2011 publication. Approximation formulas with the same approach generate similar results. In some cases, it is apparent that some formulas have advantages over other ones and a few tend to larger errors. Thus, the focus of interest particularly addresses the load and batch size changes within the network and the impact on the accuracy of the decomposition method as a fast solver or pre-evaluation for optimization using simulation.

Power generation companies have to ensure a secure supply of power to their customers at any time. Hence, this particular application context implies a special feature of shift planning where a very robust solution of assignment is needed. In daily business this means all business functions have to be staffed competently at any time, otherwise a smooth power plant operation cannot take place. In this regard, optimal shift assignment is a highly important and complex task, where reliability is prioritized with respect to all other criteria, e.g. employee’s interests. In order to test a shift configuration on operational level, we conceptualise a reactive framework to support tactical decision making. The concept switches between optimisation and stochastic simulation which takes uncertainty associated with employee sickness into account. An exemplary case study with realistic data of a power generation company analyses the operational consequences of uncertain absences on the performance of a given shift configuration.

CityGML is an XML based description standard for 3D city models that requires model buildings to have planar roof facets. Unfortunately, current tools that generate building models from airborne laser scanning point clouds violate this requirement to some extent. We propose a definition of approximate planarity and present a post-processing tool that establishes approximate planarity using linear optimization. It preserves the characteristic shape of roofs. In most cases, triangulation of non-planar facets is no longer needed to heal models. This not only reduces the number of facets and increases performance of applications that process city models, but also avoids disturbing edges in 3D prints.

Branch-and-bound algorithms for Mixed-Integer Programs (MIP) are studied for over 40 years [1, 3, 7]. Object-oriented frameworks for parallel branch-and-bound algorithms like ALPS [9], ParaSCIP [8], and PICO [5] are well known. Our aim is to develop a powerful yet easy-to-use parallel MIP-solver by combining open-source tools or frameworks that are platform independent and free of charge so that even small companies come to the benefit of an optimization suite. Licenses of commercial solvers like CPLEX or GUROBI are often not affordable for small companies. Our tool combines the Gnu Linear Programming Kit (GLPK) and the remote procedure call framework Thrift. To make our development independent of the GLPK-development, we use the GLPK-solvers as independently running processes. So we are able to profit from further development and algorithmic progress of GLPK in future. We describe how to combine these technologies to get an optimization suite for mid-sized problems and evaluate the power of our tool by solving some benchmark data from Chu and Beasley [4] and MIPLIB 2003 [2].

SAS Institute has long been recognized by Gartner (most recently in 2016, see Kart et al. Magic Quadrant for Advanced Analytics Platforms (09 February 2016|ID:G00275788), [1]) as leader in the magic quadrant for Advanced Analytics Platforms. Bundled in SAS/OR are the Institute’s offerings for solving a broad range of OR-problems on various software platforms. We present what appears to be the first independent benchmarking of SAS Institute’s OR-solvers. In the present paper we concentrate on the problem classes LP, MILP, Network and Infeasibility Detection.

We study a spare parts stochastic production/inventory problem of a manufacturer, where he has an option to source parts from a relatively inflexible conventional regular supplier ordering in large batches with long replenishment lead time, or alternatively from a flexible in-house or outsourced 3D printing facility. We derive the dynamic programming formulation for cost associated with utilizing the 3D printing supply option and give some insights into the structure of the optimal policy. In a numerical experiment, we compare the performance of this hybrid sourcing strategy with the regular sourcing option, and provide some managerial insights.

Due to a constantly growing competition among organizations and higher customer expectations, in the last decades companies started to realize the need for supply chain collaboration (SCC). Although the idea of SCC may sound easy in theory, SCCs in practice often fail. This can be explained by the fact that for a specific SCC a huge amount of drivers and resistors has to be taken into account by all parties involved. However, these drivers and resistors are often unknown or misunderstood by the parties, which leads to the fact that SCCs likely fail. To avoid this, we present a framework which provides a complete overview and the correct understanding of all possible drivers and resistors identified through an extensive literature review. The completeness of the framework in practice is investigated through interviews with companies. In theory, usually dyadic relationships are observed. The companies we interviewed participated in triangular relationships or in SCCs where even more than three parties were involved. Preliminary results indicate that even for these more complex relationships in practice the framework is complete.

Tactical supply chain planning in the chemical industry is a frequently recurring task, which typically involves not only automated planning procedures but also manual planning efforts. Competent application of optimization techniques in this context requires specialized skills and method-related knowledge. However, planners might have a background in overseeing production or comparable functions and personnel with expertise in optimization is scarce. Common simple heuristic planning approaches provided by ERP-systems do not even consider capacity constraints. This leads to considerable amounts of manual planning efforts. Still, for complex supply chains the resulting plans likely lack in quality. Available advanced heuristics can produce better plans but at the same time require expertise and maintenance efforts comparable to optimization based approaches. We introduce a concept of quality of supply network plans and investigate the potential for achieving balance between effort and plan quality by incorporating certain dimensions of quality in application friendly planning heuristics.

Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method (Nachtigall and Opitz, Solving periodic timetable optimisation problems by modulo simplex calculations 2008 [6]), a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers’ travel paths into consideration.

The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012.

Electric Vehicle Scheduling extends the traditional Vehicle Scheduling by restricting the range of deployed vehicles and considering the possibility to recharge a vehicle at some charging stations. A fundamental aspect of electro-mobility which hasn’t attract much attention within existing solution approaches for the E-VSP, is the functionality of charging an electric vehicle’s battery. In this paper, we propose models for the charging process of electric vehicles and analyse their impacts on resulting vehicle schedules. We focus on the question whether widely used assumptions concerning the charging times of electric vehicles, for instance constant or linear charging times, reflect the reality of electro-mobility sufficiently or should be considered in a more accurate way.