Aug 29, 2016

Districting Problems in Business and Public Organizations

I am co-chairing (together with Knut Haase) the session (FC-08) Districting Problems in Business and Public Organizations at the International Conference on Operations Research of the German Operations Research Society, Hamburg (Germany)
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:

  1. Redistricting in Mexico
  2. Toll zone planning for road-based traffic
  3. Pilgrim camp layout planning for the annual Hajj operation of the Al-Mashaaer Metro system
  4. 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.