90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (29)
- Doctoral Thesis (1)
Language
- English (30)
Has Fulltext
- yes (30) (remove)
Keywords
Institute
We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.
Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.
In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes.
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.
The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the
timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.
Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.
We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.
We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.
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.
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.
Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and
airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.
Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.
Planning and operating railway transportation systems is an extremely
hard task due to the combinatorial complexity of the underlying discrete
optimization problems, the technical intricacies, and the immense size of
the problem instances. Because of that, however, mathematical models
and optimization techniques can result in large gains for both railway cus-
tomers and operators, e.g., in terms of cost reductions or service quality
improvements. In the last years a large and growing group of researchers
in the OR community have devoted their attention to this domain devel-
oping mathematical models and optimization approaches to tackle many
of the relevant problems in the railway planning process. However, there
is still a gap to bridge between theory and practice, with
a few notable exceptions. In this paper we address three success stories,
namely, long-term freight train routing (part I), mid-term rolling stock
rotation planning (part II), and real-time train dispatching (part III). In
each case, we describe real-life, successful implementations. We will dis-
cuss the individual problem setting, survey the optimization literature,
and focus on particular aspects addressed by the mathematical models.
We demonstrate on concrete applications how mathematical optimization
can support railway planning and operations. This gives proof that math-
ematical optimization can support the planning of rolling stock resources.
Thus, mathematical models and optimization can lead to a greater effi-
ciency of railway operations and will serve as a powerful and innovative
tool to meet recent challenges of the railway industry.
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an
opportunity for high-achieving graduate-level students to work in teams on a
real-world research project proposed by a sponsor from industry or the public
sector. Each G-RIPS team consists of four international students (two from
the US and two from European universities), an academic mentor, and an industrial sponsor.
This is the report of the Rail-Lab project on the definition and integration of
robustness aspects into optimizing rolling stock schedules. In general, there is
a trade-off for complex systems between robustness and efficiency. The ambitious
goal was to explore this trade-off by implementing numerical simulations and
developing analytic models.
In rolling stock planning a very large set of industrial railway requirements,
such as vehicle composition, maintenance constraints, infrastructure capacity,
and regularity aspects, have to be considered in an integrated model. General
hypergraphs provide the modeling power to tackle those requirements.
Furthermore, integer programming approaches are able to produce high quality
solutions for the deterministic problem.
When stochastic time delays are considered, the mathematical programming problem
is much more complex and presents additional challenges. Thus, we started with a
basic variant of the deterministic case, i.e., we are only considering
hypergraphs representing vehicle composition and regularity.
We transfered solution approaches for robust optimization
from the airline industry to the setting of railways and attained a
reasonable measure of robustness. Finally, we present and discuss different
methods to optimize this robustness measure.
The Cycle Embedding Problem
(2014)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects.
In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites.
We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
Sports rankings are obtained by applying a system of rules to evaluate the
performance of the participants in a competition.
We consider rankings that result from assigning an ordinal rank to each
competitor according to their performance.
We develop an integer programming model for rankings that allows us
to calculate the number of points needed to guarantee
a team the ith position, as well as the minimum number of points
that could yield the ith place.
The model is very general and can thus be applied to many types of sports.
We discuss examples coming from football (soccer), ice hockey, and
Formula~1. We answer various questions and debunk a few myths along the way.
Are 40 points enough to avoid relegation in the Bundesliga?
Do 95 points guarantee the participation of a team in the NHL playoffs?
Moreover, in the season restructuration currently under consideration in the NHL,
will it be easier or harder to access the playoffs?
Is it possible to win the Formula~1 World Championship without winning at least one race
or without even climbing once on the podium?
Finally, we observe that the optimal solutions of the aforementioned model
are associated to extreme situations which are unlikely to happen. Thus,
to get closer to realistic scenarios, we enhance the model by adding some
constraints inferred from the results of the previous years.
Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.
This paper provides a highly integrated solution approach for rolling stock
planning problems in the context of intercity passenger traffic. The main
contributions are a generic hypergraph based mixed integer programming
model and an integrated algorithm for the considered rolling stock rotation
planning problem. The new developed approach is able to handle a very large
set of industrial railway requirements, such as vehicle composition,
maintenance constraints, infrastructure capacity, and regularity aspects.
By the integration of this large bundle of technical railway aspects, we show
that our approach has the power to produce implementable rolling stock
rotations for our industrial cooperation partner DB Fernverkehr.
This is the first time that the rolling stock rotations at DB Fernverkehr
could be optimized by an automated system utilizing advanced mathematical
programming techniques.
Railway Track Allocation
(2012)
This article gives an overview of the results of the author's PhD thesis. The thesis deals with the
mathematical optimization for the efficient use of
railway infrastructure. We address the optimal allocation of the available
railway track capacity - the track allocation problem. This track allocation
problem is a major challenge for a railway company, independent of whether
a free market, a private monopoly, or a public monopoly is given. Planning
and operating railway transportation systems is extremely hard due to the
combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances.
Mathematical models and optimization techniques can result in huge gains
for both railway customers and operators, e.g., in terms of cost reductions or
service quality improvements. We tackle this challenge by developing novel
mathematical models and associated innovative algorithmic solution methods
for large scale instances. We made considerable progress on solving track
allocation problems by two main features - a novel modeling approach for the
macroscopic track allocation problem and algorithmic improvements based on the
utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the
optimal allocation of the available railway track capacity - the track allocation problem.
This track allocation problem is a major challenge for a railway company, independent of
whether a free market, a private monopoly, or a public monopoly is given.
Planning and operating railway transportation systems is extremely hard due
to the combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization
techniques can result in huge gains for both railway customers and operators, e.g.,
in terms of cost reductions or service quality improvements.
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic
solution methods for large scale instances. This allows us to produce for the first time reliable
solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
The opening chapter gives a comprehensive overview on railway planning problems.
This provides insights into the regulatory and technical framework,
it discusses the interaction of several planning steps, and identifies optimization potentials in
railway transportation. The remainder of the thesis is comprised of two major parts.
The first part is concerned with modeling railway systems to allow for resource and capacity analysis.
Railway capacity has basically two dimensions, a space dimension which are the physical
infrastructure elements as well as a time dimension that refers to the train movements, i.e.,
occupation or blocking times, on the physical infrastructure. Railway safety systems operate
on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through.
Two trains reserving the same block of the infrastructure within the same point in time is called block conflict.
Therefore, models for railway capacity involve the definition
and calculation of reasonable running and associated reservation and
blocking times to allow for a conflict free allocation.
In the second and main part of the thesis, the optimal track
allocation problem for macroscopic models of the railway system is considered.
The literature for related problems is surveyed.
A graph-theoretic model for the track allocation problem is
developed. In that model optimal track allocations correspond to
conflict-free paths in special time-expanded graphs.
Furthermore, we made considerable progress on solving track allocation problems by two
main features - a novel modeling approach for the macroscopic track
allocation problem and algorithmic improvements based on the
utilization of the bundle method.
Finally, we go back to practice and present in the last chapter several case
studies using the tools netcast and tsopt.
We provide a computational comparison of
our new models and standard packing models used in the literature.
Our computational experience indicates that our approach, i.e.,
``configuration models'', outperforms other models. Moreover, the rapid branching
heuristic and the bundle method enable us to produce high quality solutions for very large scale
instances, which has not been possible before.
In addition, we present results for a theoretical and rather visionary auction framework
for track allocation. We discuss several auction design questions and analyze experiments of
various auction simulations.
The highlights are results for the Simplon corridor in Switzerland.
We optimized the train traffic through this tunnel using our models and
software tools.
To the best knowledge of the author and confirmed by several railway
practitioners this was the first time that fully automatically produced
track allocations on a macroscopic scale fulfill the requirements
of the originating microscopic model, withstand the evaluation in the
microscopic simulation tool OpenTrack, and exploit the infrastructure capacity.
This documents the success of our approach in practice and the usefulness
and applicability of mathematical optimization to railway track allocation.
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
We propose a model for the integrated optimization of vehicle
rotations and vehicle compositions in long distance railway passenger
transport. The main contribution of the paper is a hypergraph model
that is able to handle the challenging technical requirements as
well as very general stipulations with respect to the ``regularity''
of a schedule. The hypergraph model directly generalizes network
flow models, replacing arcs with hyperarcs. Although NP-hard in
general, the model is computationally well-behaved in practice. High
quality solutions can be produced in reasonable time using high
performance Integer Programming techniques, in particular, column
generation and rapid branching. We show that, in this way,
large-scale real world instances of our cooperation partner DB
Fernverkehr can be solved.
Today the railway timetabling process and the track allocation
is one of the most challenging problems to solve by a railway infrastructure provider.
Especially due to the deregulation of the transport market in the recent years several
suppliers of railway traffic have entered the market. This leads to an increase of slot requests
and then it is natural that conflicts occur among them.
Furthermore, railway infrastructure networks consist of very expensive assets, even more
they are rigid due to the long-term upgrade process.
In order to make best use of these valuable infrastructure and to ensure economic operation,
efficient planning of the railway operation is indispensable.
Mathematical optimization models and algorithmic methodology can help
to automatize and tackle these challenges.
Our contribution in this paper is to present a renewed planning process
due to the liberalization in Europe and a general framework to
support the integration of simulation and optimization for
railway capacity allocation.