Metaheuristics for the Order Batching Problem in Manual Order Picking Systems

In manual order picking systems, order pickers walk or drive through a distribution warehouse in order to collect items which are requested by (internal or external) customers. In order to perform these operations efficiently, it is usually required that customer orders are combined into (more substantial) picking orders of limited size. The Order Batching Problem considered in this paper deals with the question of how a given set of customer orders should be combined such that the total length of all tours is minimized which are necessary to collect all items. The authors introduce two metaheuristic approaches for the solution of this problem: the first one is based on Iterated Local Search; the second on Ant Colony Optimization. In a series of extensive numerical experiments, the newly developed approaches are benchmarked against classic solution methods. It is demonstrated that the proposed methods are not only superior to existing methods but provide solutions which may allow distribution warehouses to be operated significantly more efficiently.

Entwicklung einer Methodik zur Generierung einer Datenbasis für Optimierungssysteme in der maritimen Leercontainerlogistik

Dieser Beitrag stellt ein Vorgehen zur Entwicklung einer Methodik zur Generierung einer praxisnahen Datenbasis für numerische Untersuchungen im Rahmen der maritimen Leercontainerlogistik vor. Das Vorgehen wird an einem exemplarischen Anwendungsfall verdeutlicht. Die Resultate sollen Testläufe für Szenarien der Leercontainerlogistik unterstützen und somit eine Basis für die Entwicklung und Bewertung organisatorischer Verbesserungsansätze, mathematischer Optimierungsmodelle, entsprechender Lösungsalgorithmen und praxisnaher Simulationsumgebungen bilden.

A Nonstationary Space-Time Gaussian Process Model for Partially Converged Simulations

In the context of expensive numerical experiments, a promising solution for alleviating the computational costs consists of using partially converged simulations instead of exact solutions. The gain in computational time is at the price of precision in the response. This work addresses the issue of fitting a Gaussian process model to partially converged simulation data for further use in prediction. The main challenge consists of the adequate approximation of the error due to partial convergence, which is correlated in both design variables and time directions. Here, we propose fitting a Gaussian process in the joint space of design parameters and computational time. The model is constructed by building a nonstationary covariance kernel that reflects accurately the actual structure of the error. Practical solutions are proposed for solving parameter estimation issues associated with the proposed model. The method is applied to a computational fluid dynamics test case and shows significant improvement in prediction compared to a classical kriging model.

Discontinuous Galerkin finite element approximation of quasilinear elliptic boundary value problems II: Strongly monotone quasi-Newtonian flows

In this article, we develop the a priori and a posteriori error analysis of hp-version interior penalty discontinuous Galerkin finite element methods for strongly monotone quasi-Newtonian fluid flows in a bounded Lipschitz domain Ω ⊂ ℝd, d = 2, 3. In the latter case, computable upper and lower bounds on the error are derived in terms of a natural energy norm, which are explicit in the local mesh size and local polynomial degree of the approximating finite element method. A series of numerical experiments illustrate the performance of the proposed a posteriori error indicators within an automatic hp-adaptive refinement algorithm.

Fast parallel kriging-based stepwise uncertainty reduction with application to the identification of an excursion set

Stepwise uncertainty reduction (SUR) strategies aim at constructing a sequence of points for evaluating a function  f in such a way that the residual uncertainty about a quantity of interest progressively decreases to zero. Using such strategies in the framework of Gaussian process modeling has been shown to be efficient for estimating the volume of excursion of f above a fixed threshold. However, SUR strategies remain cumbersome to use in practice because of their high computational complexity, and the fact that they deliver a single point at each iteration. In this article we introduce several multipoint sampling criteria, allowing the selection of batches of points at which f can be evaluated in parallel. Such criteria are of particular interest when f is costly to evaluate and several CPUs are simultaneously available. We also manage to drastically reduce the computational cost of these strategies through the use of closed form formulas. We illustrate their performances in various numerical experiments, including a nuclear safety test case. Basic notions about kriging, auxiliary problems, complexity calculations, R code, and data are available online as supplementary materials.

Monte Carlo modeling of polarized light propagation: Stokes vs Jones - Part I

This bipartite comparative study aims at inspecting the similarities and differences between the Jones and Stokes–Mueller formalisms when modeling polarized light propagation with numerical simulations of the Monte Carlo type. In this first part, we review the theoretical concepts that concern light propagation and detection with both pure and partially/totally unpolarized states. The latter case involving fluctuations, or “depolarizing effects,” is of special interest here: Jones and Stokes–Mueller are equally apt to model such effects and are expected to yield identical results. In a second, ensuing paper, empirical evidence is provided by means of numerical experiments, using both formalisms.

Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations

Multi-objective optimization algorithms aim at finding Pareto-optimal solutions. Recovering Pareto fronts or Pareto sets from a limited number of function evaluations are challenging problems. A popular approach in the case of expensive-to-evaluate functions is to appeal to metamodels. Kriging has been shown efficient as a base for sequential multi-objective optimization, notably through infill sampling criteria balancing exploitation and exploration such as the Expected Hypervolume Improvement. Here we consider Kriging metamodels not only for selecting new points, but as a tool for estimating the whole Pareto front and quantifying how much uncertainty remains on it at any stage of Kriging-based multi-objective optimization algorithms. Our approach relies on the Gaussian process interpretation of Kriging, and bases upon conditional simulations. Using concepts from random set theory, we propose to adapt the Vorob’ev expectation and deviation to capture the variability of the set of non-dominated points. Numerical experiments illustrate the potential of the proposed workflow, and it is shown on examples how Gaussian process simulations and the estimated Vorob’ev deviation can be used to monitor the ability of Kriging-based multi-objective optimization algorithms to accurately learn the Pareto front.

The hp-adaptive FEM based on continuous Sobolev embeddings: isotropic refinements

The aim of this paper is to present a new class of smoothness testing strategies in the context of hp-adaptive refinements based on continuous Sobolev embeddings. In addition to deriving a modified form of the 1d smoothness indicators introduced in [26], they will be extended and applied to a higher dimensional framework. A few numerical experiments in the context of the hp-adaptive FEM for a linear elliptic PDE will be performed.

Fully Adaptive Newton--Galerkin Methods for Semilinear Elliptic Partial Differential Equations

In this paper we develop an adaptive procedure for the numerical solution of general, semilinear elliptic problems with possible singular perturbations. Our approach combines both prediction-type adaptive Newton methods and a linear adaptive finite element discretization (based on a robust a posteriori error analysis), thereby leading to a fully adaptive Newton–Galerkin scheme. Numerical experiments underline the robustness and reliability of the proposed approach for various examples

Fast Update of Conditional Simulation Ensembles

Gaussian random field (GRF) conditional simulation is a key ingredient in many spatial statistics problems for computing Monte-Carlo estimators and quantifying uncertainties on non-linear functionals of GRFs conditional on data. Conditional simulations are known to often be computer intensive, especially when appealing to matrix decomposition approaches with a large number of simulation points. This work studies settings where conditioning observations are assimilated batch sequentially, with one point or a batch of points at each stage. Assuming that conditional simulations have been performed at a previous stage, the goal is to take advantage of already available sample paths and by-products to produce updated conditional simulations at mini- mal cost. Explicit formulae are provided, which allow updating an ensemble of sample paths conditioned on n ≥ 0 observations to an ensemble conditioned on n + q observations, for arbitrary q ≥ 1. Compared to direct approaches, the proposed formulae proveto substantially reduce computational complexity. Moreover, these formulae explicitly exhibit how the q new observations are updating the old sample paths. Detailed complexity calculations highlighting the benefits of this approach with respect to state-of-the-art algorithms are provided and are complemented by numerical experiments.

Physical and Biological Controls on the Latitudinal Asymmetry of Surface Nutrients and pCO(2) in the Central and Eastern Equatorial Pacific

Surface nutrients and dissolved inorganic carbon (DIC) in the central (CEP) and eastern equatorial Pacific (EEP) show much higher concentrations to the south than to the north of the equator. In this study, the physical and biological controls on this asymmetry are investigated using a coupled physical-biogeochemical model. Two numerical experiments are conducted to examine the effects of asymmetrical photosynthetic efficiency (a) due to asymmetrical iron supply about the equator. The experiment with asymmetrical photosynthesis produces improved results as compared with historical observations. A nitrate budget analysis suggests that in the EEP the divergence of upwelling waters controls the surface nitrate asymmetry with additional contribution from the South Equatorial Current (SEC) carrying nutrient-rich Peru upwelling water. The changes of a affect the surface nitrate distribution but not the overall asymmetry. The SEC further carries excess nitrate to the west and thus extends the asymmetry in the east to the CEP. In the CEP, however, stronger northward than southward transport tends to reduce the nitrate asymmetry, while the asymmetrical photosynthesis would help to maintain it. Similar processes also control the distributions of surface silicate and DIC in the equatorial Pacific, which is also affected by the air-sea CO(2) exchange. The asymmetrical photosynthesis influences the distribution of surface DIC, pCO(2), and the air-sea CO(2) flux, by redistributing about 20% CO(2) flux from the north to the south of the equator. Owing to the adjustment of air-sea CO(2) flux, however, the net surface DIC change is smaller than the direct change associated with primary production.

Marine Isotope Stage (MIS) 11 results of model data with Community Climate System Model version 3 including the Dynamic Global Vegetation Model (CCSM3-DGVM) in NetCDF format at global and regional scale

The climate of Marine Isotope Stage (MIS) 11, the interglacial roughly 400,000 years ago, is investigated for four time slices, 416, 410, 400, and 394 ka. The overall picture is that MIS 11 was a relatively warm interglacial in comparison to preindustrial, with Northern Hemisphere (NH) summer temperatures early in MIS 11 (416-410 ka) warmer than preindustrial, though winters were cooler. Later in MIS 11, especially around 400 ka, conditions were cooler in the NH summer, mainly in the high latitudes. Climate changes simulated by the models were mainly driven by insolation changes, with the exception of two local feedbacks that amplify climate changes. Here, the NH high latitudes, where reductions in sea ice cover lead to a winter warming early in MIS 11, as well as the tropics, where monsoon changes lead to stronger climate variations than one would expect on the basis of latitudinal mean insolation change alone, are especially prominent. The results support a northward expansion of trees at the expense of grasses in the high northern latitudes early during MIS 11, especially in northern Asia and North America.

Model simulation output data (CCSM3) related to uplift of African topography and the intensification of upwelling in the Benguela region

The Benguela Current, located off the west coast of southern Africa, is tied to a highly productive upwelling system**1. Over the past 12 million years, the current has cooled, and upwelling has intensified**2, 3, 4. These changes have been variously linked to atmospheric and oceanic changes associated with the glaciation of Antarctica and global cooling**5, the closure of the Central American Seaway**1, 6 or the further restriction of the Indonesian Seaway**3. The upwelling intensification also occurred during a period of substantial uplift of the African continent**7, 8. Here we use a coupled ocean-atmosphere general circulation model to test the effect of African uplift on Benguela upwelling. In our simulations, uplift in the East African Rift system and in southern and southwestern Africa induces an intensification of coastal low-level winds, which leads to increased oceanic upwelling of cool subsurface waters. We compare the effect of African uplift with the simulated impact of the Central American Seaway closure9, Indonesian Throughflow restriction10 and Antarctic glaciation**11, and find that African uplift has at least an equally strong influence as each of the three other factors. We therefore conclude that African uplift was an important factor in driving the cooling and strengthening of the Benguela Current and coastal upwelling during the late Miocene and Pliocene epochs.