We develop a model based on stochastic discrete-time controlled dynamical systems in order to derive optimal policies for controlling the material flow in supply networks. Each node in the network is ...described as a transducer such that the dynamics of the material and information flows within the entire network can be expressed by a system of first-order difference equations, where some inputs to the system act as external disturbances. We apply methods from constrained robust optimal control to compute the explicit control law as a function of the current state. For the numerical examples considered, these control laws correspond to certain classes of optimal ordering policies from inventory management while avoiding, however, any a priori assumptions about the general form of the policy.
Sustainable management of groundwater resources is of crucial importance for regions where freshwater supply is naturally limited. Long-term planning of groundwater usage requires computer-based ...decision support tools: on the one hand, they must be able to predict the complex system dynamics with sufficient accuracy, on the other, they must allow exploring management scenarios with respect to different criteria such as sustainability, cost, etc. In this paper, we present a multiobjective evolutionary algorithm for groundwater management that optimizes the placement and the operation of pumping facilities over time, while considering multiple neighboring regions which are economically independent. The algorithm helps in investigating the cost tradeoffs between the different regions by providing an approximation of the Pareto-optimal set, and its capabilities are demonstrated on a three-region problem. The application of the proposed methodology can also serve as a benchmark problem as shown in this paper. The corresponding implementation is freely available as a precompiled module at http://www.tik.ee.ethz.ch/pisa.
Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on ...obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of ɛ-dominance. Though bounds on the quality of the limit approximation—which are entirely determined by the archiving strategy and the value of ɛ—have been obtained, the strategies do not guarantee to obtain a gap free approximation of the Pareto front. That is, such approximations
can reveal gaps in the sense that points
in the Pareto front can exist such that the distance of
to any image point
(
),
∈
, is “large.” Since such gap free approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included in the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs, we give some numerical results to visualize the behavior of the different archiving strategies. Finally, we demonstrate the potential for a possible hybridization of a given stochastic search algorithm with a particular local search strategy—multi-objective continuation methods—by showing that the concept of ɛ-dominance can be integrated into this approach in a suitable way.
We address the problem of generating detailed conflict-free railway schedules for given sets of train lines and frequencies. To solve this problem for large railway networks, we propose a network ...decomposition into condensation and compensation zones. Condensation zones contain main station areas, where capacity is limited and trains are required to travel with maximum speed. They are connected by compensation zones, where traffic is less dense and time reserves can be introduced for increasing stability. In this paper, we focus on the scheduling problem in condensation zones. To gain structure in the schedule we enforce a time discretisation which reduces the problem size considerably and also the cognitive load of the dispatchers. The problem is formulated as an independent set problem in a conflict graph, which is then solved using a fixed-point iteration heuristic. Results show that even large-scale problems with dense timetables and large topologies can be solved quickly.
In this paper, we examine the problem of maintaining an approximation of the set of nondominated points visited during a multiobjective optimization, a problem commonly known as archiving. Most of ...the currently available archiving algorithms are reviewed, and what is known about their convergence and approximation properties is summarized. The main scenario considered is the restricted case where the archive must be updated online as points are generated one by one, and at most a fixed number of points are to be stored in the archive at any one time. In this scenario, the \documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vartriangleleft$\end{document}-monotonicity of an archiving algorithm is proposed as a weaker, but more practical, property than negative efficiency preservation. This paper shows that hypervolume-based archivers and a recently proposed multi-level grid archiver have this property. On the other hand, the archiving methods used by SPEA2 and NSGA-II do not, and they may \documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vartriangleleft$\end{document}-deteriorate with time. The \documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vartriangleleft$\end{document}-monotonicity property has meaning on any input sequence of points. We also classify archivers according to limit properties, i.e. convergence and approximation properties of the archiver in the limit of infinite (input) samples from a finite space with strictly positive generation probabilities for all points. This paper establishes a number of research questions, and provides the initial framework and analysis for answering them.
In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation ...that should capture the entire solution set in a suitable sense, which will be defined using the concept of
ε
-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.
Many railway companies in Europe operate periodic timetables. Yet most timetables are not entirely periodic but have a mixture of different periodicities and many exceptions to cope with changing ...demand. Current approaches for automatic timetable generation are not able to deal with such partially periodic structures but consider only fully periodic inputs. We therefore introduce the periodic Service Intention (pSI) as a framework where customer-relevant information about train services can be described, including their periodicity information. We then address the problem of finding a feasible timetable that fulfills the requirements specified in a pSI without the need for manual post-processing. We solve this problem by projecting intended train runs over equivalence classes and thereby reducing the pSI to an augmented instance of periodic timetabling. Thus it is possible to use existing models for periodic scheduling, such as Periodic Event Scheduling Problem, to generate periodic timetables with partial periodicity, which are finally rolled out to obtain the desired daily schedule according to the commercial requirements of the pSI. Results for a test case from the timetable for central Switzerland in 2008 show that this approach needs only slightly longer computation time than for a fully periodic instance, but the additional time is compensated by the fact that post-processing becomes unnecessary and by the better quality of the solution. The approach is particularly well suited for offers with a strong periodicity but some irregularities, which could not be treated properly by existing methods.
Based on the regulation of grid fees and the regulatory requirements on the quality of supply, grid operators attempt to find an optimal balance between costs and quality of supply. One main aspect ...of the quality of supply is the non-availability of supply, which strongly depends on the duration of the restoration process after incidents and therefore on the availability of resources. Focusing on the operational processes after incidents in low-, medium-, and high-voltage grids, this paper presents a detailed grid operation model which allows to quantify the relation between the configuration of resources and the corresponding costs and quality of supply. To assess the “risk” of incidents with no interruption of supply, the
power-at-risk is introduced. Depending on legal, regulatory, or strategic requirements, the model allows to evaluate and compare different configurations of resources and the resulting quality of supply.