Refine
Year of publication
Document Type
- ZIB-Report (29)
- In Proceedings (14)
- Article (9)
- Book chapter (7)
- Master's Thesis (2)
- Book (1)
- Doctoral Thesis (1)
- Other (1)
Is part of the Bibliography
- no (64)
Keywords
- online algorithms (5)
- online optimization (4)
- Online-Optimierung (3)
- elevator control (3)
- probabilistic analysis (3)
- Aufzugssteuerung (2)
- Stochastische Dominanz (2)
- acyclic orientations (2)
- bipolar orientations (2)
- branch-and-bound (2)
Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.
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.
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.
We study combinatorial structures in large-scale mixed-integer (nonlinear) programming problems arising in gas network optimization. We propose a preprocessing strategy exploiting the observation that a large part of the combinatorial complexity arises in certain subnetworks. Our approach analyzes these subnetworks and the combinatorial structure of the flows within these subnetworks in order to provide alternative models with a stronger combinatorial structure that can be exploited by off-the-shelve solvers. In particular, we consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. We propose a refined model that allows to precompute tighter bounds for each operation mode and a number of model variants based on the refined model exploiting these tighter bounds. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode. We evaluate our model variants on reference benchmark data, showing that they reduce the average running time between 10% for easy instances and 46% for hard instances. Moreover, for three of four considered networks, the average number of search tree nodes is at least halved, showing the effectivity of our model variants to guide the solver’s search.
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. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.
The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of $\frac{1+\sqrt{2}}{2}$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm.
Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.
In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.
In 2005 the European Union liberalized the gas market with a disruptive change
and decoupled trading of natural gas from its transport. The gas is now trans-
ported by independent so-called transmissions system operators or TSOs. The
market model established by the European Union views the gas transmission
network as a black box, providing shippers (gas traders and consumers) the
opportunity to transport gas from any entry to any exit. TSOs are required
to offer the maximum possible capacities at each entry and exit such that any
resulting gas flow can be realized by the network. The revenue from selling these
capacities more than one billion Euro in Germany alone, but overestimating the
capacity might compromise the security of supply. Therefore, evaluating the
available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out
to develop a new toolset for evaluating gas network capacities. The goals and
the challenges as they occurred in the project are described, as well as the
developments and design decisions taken to meet the requirements.
Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.
We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm.
We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
The task of an elevator control is to schedule the elevators of a group such
that small waiting and travel times for the passengers are obtained. We present an exact
reoptimization algorithm for this problem. A reoptimization algorithm computes a
new schedule for the elevator group each time a new passenger arrives. Our algorithm
uses column generation techniques and is, to the best of our knowledge, the first exact
reoptimization algorithms for a group of passenger elevators. To solve the column
generation problem, we propose a Branch & Bound method.
This extended abstract is about algorithms for controlling elevator systems employing destination hall calls, i.e. the passenger provides his destination floor when calling an elevator. We present the first exact algorithm for controlling a group of elevators and report on simulation results indicating that destination hall call systems outperform conventional systems.