A Multicriteria Districting Heuristic For The Aggregation Of Zones And Its Use In Computing Origin-Destination Matrices

Abstract

Territorial aggregation is an important issue in many traditional applications, such as political districting, plant location, health care zoning, and travel demand study, In particular, in travel demand analysis one is interested in estimating travel flows between origins and destinations, The number of trips performed between origin i and destination, j is represented by the (i, j)-th entry of an Origin-Destination (OD) matrix. In order to define the OD matrix, a discrete set of origins and destinations is needed, and territorial aggregation methods are used precisely to choose these origins and destinations. Typically, a survey is performed to collect data on travel between the selected origins and destinations. However, when the survey OD matrix is large and sparse, problems in the estimation of travel demand may arise. This drawback can be avoided by further aggregating the origins and destinations on which travel demand is evaluated and by obtaining a new and smaller OD matrix where each cell entry carries a greater value. The corresponding map is then exploited to calibrate the statistical model used to estimate the original disaggregated travel flows. In this work, we first suggest a set of optimally criteria which can be used to find “good” territorial aggregations and we adopt the Old Bachelor Acceptance heuristic to identify them. In order to understand the trade-off between these criteria, we introduce appropriate optimality indexes and we minimize their weighted combinations with several different sets of weights. Our application refers to the city of Rome and the actual study, which involved statisticians, engineers and operations researchers, was supported by the local government (Comune di Roma). Our experimental results on the city of Rome show that the Old Bachelor Acceptance heuristic finds aggregations with low values for all the indexes simultaneously. In particular, our results lead to the conclusion that certain sets of weights must be adopted if one wants to be sure to find “good” aggregations.

Résumé

L'agrégation territoriale est une question importante dans de nombreuses applications telles que le découpage électoral, la localisation de structures industrielles, la répartition en zones du système sanitaire, et l'étude de la demande de déplacements. En particulier, en ce qui concerne l'analyse de la demande de déplacements, nous voulons estimer les flux entre les origines et les destinations de déplacements. Le nombre de déplacements entre une origine i et une destination j est représentée par l'entrée (i, j) d'une matrice Origine-Destination (OD). Afin de définir la matrice OD, il faut disposer d'un ensemble discret d'origines et de destinations, et les méthodes d'agrégation territoriale sont utilisées à cette fin. Habituellement, une enquête permettra de collecter des données sur les déplacements entre les origines et les destinations choisies. Toutefois quand la matrice OD de l'enquête est grande et creuse, des problèmes duns l'estimation de la demande de déplacements peuvent se produire. Cet inconvénient peut être évité en agrégeant ultérieurement les origines et les destinations sur lesquelles la demande est évaluée, en obtenant une nouvelle matrice OD plus petite où les valeurs des entrées sont plus grandes que dans la matrice initiale. La carte d'origines et destinations obtenue est exploitée pour calibrer le modèle statistique utilisé pour estimer les flux de déplacements desagrégés originaux. Dans ce travail, nous suggérons premièrement une série de critères qui peuvent être utilisés pour trouver de “bonnes” agrégations territoriales et nous adoptons l'algorithme heuristique Old Bachelor Acceptante pour les identifier. Afin de comprendre le trade-off entre ces critères, nous introduisons les index correspondants et nous minimisons leurs combinaisons pondérées avec plusieurs séries différentes de poids. La ville de Rome est l'objet de notre application, issue d'une étude qui a impliqué la collaboration de statisticiens, d'ingénieurs et d'experts en recherche opérationnelle et a été soutenue par le gouvernement local (la commune de Rome). Nos résultats expérimentaux sur la ville de Rome montrent que les agrégations trouvées par l'algorithme heuristique Old Bachelor Acceptance produisent des valeurs basses pour tous les index simultanément. En particulier, nos résultats mènent à la conclusion que certaines séries de poids doivent être adoptées pour être sûr de trouver les “bonnes” agrégations.

Key Words:

• Territorial aggregation
• local search
• multicriteria optimization
• OD matrices

Mots-clés:

• agrégation territoriale
• recherche locale
• optimisation multi-critère
• matrices origines-destinations

Additional information

Notes on contributors

Federica Ricca

Federica Ricca is researcher fellow al the Department of Statistics and Probability of the University of Rome “La Sapienza”. She got her laurea (= Italian M.S.) in Economic Statistics cum laude at the University of Rome “La Sapienza” and she earned her Ph.D. in Operations Research at the same University. Her main research interests are graph partitioning, with applications to political districting, and location problems. She is co-author of the book “Evaluation and Optimization of Electoral Systems”. SIAM Monographs on Discrete Mathematics and Applications, SIAM, Society for Industrial and Applied Mathematics, Philadelphia 1999.