Friday, 11:45-13:15 - Seminarraum 101/103 Helmut-Schmidt-Universität, Hamburg
Districting is the problem of grouping small spatial (geographic) areas, such as ZIP code areas or traffic analysis zones, into larger spatial districts. According to the motivating application, such as sales territory design, land acquisition, and political districting, the districts must satisfy certain properties (contiguity, f.e.).
The session cover the following presentations:
- Redistricting in Mexico
- Toll zone planning for road-based traffic
- Pilgrim camp layout planning for the annual Hajj operation of the Al-Mashaaer Metro system
- Revenue maximizing tariff zone planning
1 - Redistricting in Mexico
Eric
Alfredo Rincón-García, Sergio de-los-Cobos-Silva, Miguel Angel Gutierrez,
Antonin Ponsich, Roman Anselmo Mora-Gutiérrez, Pedro Lara-velÁzquez
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, travel times between
municipalities, and indigenous population were included as constraints.
Besides, 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, for the first time in Mexico, a
population based technique was used, an Artificial Bee Colony inspired
algorithm. The primary purpose of this presentation is to describe the main
characteristics of this redistricting process. To address this issue, we
provide a description of the problem, and a brief overview of the inner working
mode of both optimization algorithms. Finally we include computational results
that prove that the population based technique is more robust its counterpart
for this kind of problems.
2
- Toll zone planning for road-based traffic
Martin
Tschöke, Sven Müller, Sascha Ruja
In
light of the increasing attention on economic, environmental and health impacts
of road traffic, methods for controlling its volume and density gain more and
more importance. Especially legislators look into ways of letting users of road
traffic contribute to covering infrastructure and maintenance cost. One
important instrument in this respect is the introduction of toll collection
systems and toll zones. In this paper, we introduce a new approach for planning
toll zones that maximizes operational income. Overall revenue is determined on
the basis of the total number of trips, number of toll zones passed and the
price for passing a toll zone. As in tariff zone planning for public transportation,
we further consider that users of road traffic are price sensitive and adapt
their behavior with respect to the price structure of the system. We develop a
MIP model that constructs consistent toll zones on the basis of a set of
transitivity constraints. The model’s applicability to real world cases is
demonstrated by applying it to data from the San Francisco Bay Area using GAMS/
CPLEX. In addition to an analysis of model specific properties, the impact of
the price-pertoll- zone on the total number of trips and on overall profit is
examined.
3
- Pilgrim camp layout planning for the annual Hajj operation of the Al-Mashaaer
Metro system
Matthes
Koch
During
the annual great Islamic pilgrimage, or Hajj, 2 - 5 million pilgrims gather at
the holy sites of Makkah, Saudi-Arabia, to perform their religious duties. The
rituals must be performed at specified locations and within specified time
windows over the course of several days in order to complete Hajj successfully.
The mass movement of the pilgrims is supported by a metro system, which
transports about 400-500 thousand pilgrims between the holy sites. Because
pilgrim travel group data varies from year to year, the layout of pilgrim camps
is planned every year anew. Camp layouts for the pilgrim groups that use the metro
system must respect requirements of crowd management as well as general
logistic requirements like street-access, toilet-access, separation of
nationalities and others. We propose a mathematical planning approach to solve
this camp layout problem which can be easily coupled with our established
approach to the pilgrim group timetabling problem for the metro system.
4
- Revenue Maximizing Tariff Zone Planning
Knut
Haase, Sven Müller
The
counting zones tariff system is the prevailing system in metropolitan areas,
such as London, Boston, and Perth. For the counting zones tariff system, the
corresponding tariff is determined by the product of the number of zones passed
on the trip from origin to destination and the price per zone. In this paper,
we contribute to the scant literature on public transport tariff zone design by
a new model for the tariff zone design problem. The objective is to maximize
the expected total revenue taking into account contiguous tariff zones and
discrete fare levels. Demand as a function of tariff is measured as the number
of public transport trips between origin and destination. For a given fare we
compute the expected revenue for each origin-destination pair and the number of
tariff zones passed. We present various MIP formulations yielding different
zone patterns. Numerical examples based on artificial data are discussed.