選區劃分近年來在台灣一直是備受關注的問題，由於選舉法規的修改以及行政區域的調整，選區必須重新調整，因此自動化的選區劃分方法也逐漸受到重視。過去的研究往往以不同的方法自動的劃分選區，而這類的方法常使用類似的功能進行選區劃分與評估。研究者彼此間缺乏一套可互享資源的標準或機制，往往導致新的研究者必須耗費甚多的時間來重新設計或開發這些類似的功能。 本論文中，我們提出一套機制以及整合此套機制的系統架構，可以減少自動化劃分選區軟體的開發成本。我們結合地理資訊系統內部結構，淬取圖層中的線段，改良自動劃分選區所採用的單元，再利用線段在各圖層間的相位關係，建立新的相鄰定義與相鄰關係，從而能改善選區劃分的方法與劃分結果評估之效能。 實作中，我們以所有台灣23個縣市的圖層來測試我們的機制，實驗結果顯示我們的機制可以有效的判斷選區邊界對選區形狀完整性造成的影響，同時，採用淬取之線段來計算，能大幅降低評估選區形狀所需之時間。 / Electoral districting has received more attentions in Taiwan in recent years due to the change of electoral regulations or the change of the administrative districts. As a result, automatic electoral districting mechanism has also gotten more attentions gradually. Previous researches used various approaches in solving these problems and tend to adopt similar mechanisms in region districting or in results evaluation. The lack of standards or mechanisms in sharing the developing resources yields tremendous time wasting in rebuilding such functions. In this thesis, we proposed a set of mechanisms as well as the system architecture that integrates these mechanisms. Using this system, one can reduce the costs in developing automatic electoral districting software. We also designed a system architecture that integrates these mechanisms and helps to reduce the maintenance costs. We extracted the arc properties from the coverage data layer in GIS to improve the basic unit used in the automatic electoral districting. We proposed a new concept of adjacency relations and used the topological relations in various data layers to construct these new adjacency relations. Using these new relations, one could improve the electoral districting developing processes as well as the efficiency of performance evaluations. We used all twenty-three counties and cities of Taiwan to test our mechanisms. Experimental results shown that our mechanisms could determine the influences of districts’ boundaries to the districts’ shapes effectively. Moreover, using the extract arcs, one could reduce the time required in evaluating the districts’ shape dramatically.

Districts are intermediary legislative institutions that structure the relationship between constituents and legislatures. Situated between citizens and their elected representatives, districts mediate citizen-legislator interaction, and may have wide-reaching effects on the representational relationship. By creating a political community, defining its interests by delineating its scale and boundaries, and structuring interaction between constituents and their elected representatives, districts shape the representational relationship. District characteristics alter the representational experience for constituents with very real consequences for trust in government, evaluations of legislative institutions and representatives, perceptions of responsiveness, and the degree and type of constituent-legislator communication. Three district characteristics are examined: the population size of legislative districts (constituency size), the shape of district boundaries (geographical compactness, and the extent to which district boundaries follow pre-existing political subdivision boundaries (boundary coterminousness). Using Census data and GIS, measures of these characteristics are created for every state legislative and congressional district (post-2000 redistricting) in the United States. These characteristics are combined with public opinion data to test for their influence on attitudes toward government, legislative institutions, and legislators, as well as the closeness of the representational relationship. The findings suggest constituency size is an important determinant of evaluations of government, institutions, and legislators at both the state and congressional level. The geographical districting principles of compactness and coterminousness influence the amount of constituent-legislator communication, knowledge of representatives, and in-person contact with representatives, primarily at the congressional district level. For decades, legislative districts have been drawn as if they matter only for the electoral success of legislative candidates and the partisan and racial groups those candidates represent. The primary contribution of this work is to show that districts matter beyond defining the dominant partisan or racial attributes of district constituents. Districts influence how representation is experienced by constituents.

Within the framework of economic constraints and demographic changes which the health care sector is confronted to, the Home Health Care (HHC) which has been created sixty years ago, has known an important growth during this last decade. The main objective of this alternative to the traditional hospitalization consists in solving the problem of hospitals' capacity saturation by allowing earlier discharge of patients from hospital or by avoiding their admission while improving or maintaining the medical, psychological and social welfare of these patients. In this thesis, we are interested in the operations management within the HHC structures. In the first part of this thesis, we develop a qualitative analysis of the operations management in the HHC context. More specifically, we identify the complexity factors that operations management has to face up within this type of structures. For each complexity factor, we discuss how it can affect the organization of the care delivery. These factors pertain to the diversity of the services proposed, the location of care delivery, the uncertainty sources, etc. Thereafter, we survey operations management based models proposed in the literature within the HHC context. Based on this literature review, we identify several emerging issues, relevant from an organizational point of view, that have not been studied in the literature and thus represent unexplored opportunities for operations management researchers. In the second part of this thesis, we are interested in the partitioning of the area where the HCC structure operates into districts. This districting approach fits the policies of improvement of the quality of care delivered to patients and the working conditions of care givers as well as costs' reduction. We begin by proposing a classification of the different criteria that may be considered in the districting problem. We then propose two mathematical formulations for the HHC districting problem for which we consider criteria such as the workload balance, compactness, compatibility and indivisibility of basic units. After that, we present a numerical analysis of the computational experiments carried out on randomly generated instances to validate these two models. We also present two possible exploitations of these models and propose two extensions to these basic formulations. After formulating the problem with a static approach, we also develop a dynamic extension which allows the integration of the different variations that can be observed within the activities of an HHC structure from period to period. We then introduce a new partitioning criterion that concerns the continuity of care evaluated on the basis of two sub-criteria. Depending on the preferences of the decision-makers concerning the sub-criteria related to the continuity of care in the districting problem, we then distinguish three scenarios for which we propose the associated mathematical formulations.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática. / The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.

Dans le cadre des contraintes économiques et des évolutions démographiques auxquelles doit faire face le secteur de la santé, l’Hospitalisation à Domicile (HAD) qui a été créée il y a une soixantaine d’années s’est largement développée en France durant cette dernière décennie. L’objectif principal de cette alternative à l’hospitalisation complète est de raccourcir les séjours hospitaliers voire même de les éviter en vue de remédier à l’engorgement des hôpitaux tout en améliorant les conditions de vie des patients. Dans cette thèse, nous nous intéressons à la gestion des opérations dans les structures d’HAD. Dans la première partie, nous développons une analyse qualitative de la gestion des opérations dans les établissements d’HAD. De façon plus détaillée, nous identifions les différents facteurs de complexité auxquels la gestion des opérations doit faire face dans ce type de structures. Ces facteurs peuvent concerner la diversité de l’offre des services, le lieu de production des soins, les sources d’incertitudes, etc. Nous présentons ensuite les travaux existants dans la littérature qui s’intéressent à la gestion des opérations dans les HADs. Sur la base de cette synthèse, nous identifions des pistes de recherche qui n’ont pas encore été traitées dans la littérature. Dans la deuxième partie, nous nous intéressons à la problématique de partitionnement géographique du territoire desservi par une structure d’HAD. Cette approche de partitionnement peut s’insérer dans une politique d’amélioration de la qualité du service des soins délivrés aux patients et des conditions de travail des équipes soignantes. Nous commençons d’abord par proposer une classification des différents critères utilisés dans la littérature pour modéliser ce problème. Nous proposons ensuite deux modèles de partitionnement prenant en compte un ensemble de critères tels que l’équilibre de la charge de travail, la compacité, la compatibilité et l’indivisibilité des unités de base. Nous présentons également quelques exploitations possibles de ces modèles et proposons deux extensions à la formulation de base. Après avoir formulé le problème avec une approche statique, nous développons également une extension dynamique qui permet d’intégrer les différentes variations pouvant être observées dans l’activité d’une HAD d’une période à l’autre. Nous introduisons un nouveau critère de partitionnement qui concerne la continuité des soins, évaluée sur la base de deux sous-critères. En fonction des préférences des décideurs par rapport à la prise en compte de la continuité des soins dans le problème de partitionnement, nous distinguons alors trois scénarii pour lesquels nous proposons les modèles associés / Within the framework of economic constraints and demographic changes which the health care sector is confronted to, the Home Health Care (HHC) which has been created sixty years ago, has known an important growth during this last decade. The main objective of this alternative to the traditional hospitalization consists in solving the problem of hospitals’ capacity saturation by allowing earlier discharge of patients from hospital or by avoiding their admission while improving or maintaining the medical, psychological and social welfare of these patients. In this thesis, we are interested in the operations management within the HHC structures. In the first part of this thesis, we develop a qualitative analysis of the operations management in the HHC context. More specifically, we identify the complexity factors that operations management has to face up within this type of structures. For each complexity factor, we discuss how it can affect the organization of the care delivery. These factors pertain to the diversity of the services proposed, the location of care delivery, the uncertainty sources, etc. Thereafter, we survey operations management based models proposed in the literature within the HHC context. Based on this literature review, we identify several emerging issues, relevant from an organizational point of view, that have not been studied in the literature and thus represent unexplored opportunities for operations management researchers. In the second part of this thesis, we are interested in the partitioning of the area where the HCC structure operates into districts. This districting approach fits the policies of improvement of the quality of care delivered to patients and the working conditions of care givers as well as costs’ reduction. We begin by proposing a classification of the different criteria that may be considered in the districting problem. We then propose two mathematical formulations for the HHC districting problem for which we consider criteria such as the workload balance, compactness, compatibility and indivisibility of basic units. After that, we present a numerical analysis of the computational experiments carried out on randomly generated instances to validate these two models. We also present two possible exploitations of these models and propose two extensions to these basic formulations. After formulating the problem with a static approach, we also develop a dynamic extension which allows the integration of the different variations that can be observed within the activities of an HHC structure from period to period. We then introduce a new partitioning criterion that concerns the continuity of care evaluated on the basis of two sub-criteria. Depending on the preferences of the decision-makers concerning the sub-criteria related to the continuity of care in the districting problem, we then distinguish three scenarios for which we propose the associated mathematical formulations.

This dissertation presents spatial partitioning algorithms to solve location-allocation problems. Location-allocations problems pertain to both the selection of facilities to serve demand at demand points and the assignment of demand points to the selected or known facilities. In the first part of this dissertation, we focus on the well known and well-researched location-allocation problem, the "p-median problem", which is a distance-based location-allocation problem that involves selection and allocation of p facilities for n demand points. We evaluate the performance of existing p-median heuristic algorithms and investigate the impact of the scale of the problem, and the spatial distribution of demand points on the performance of these algorithms. Based on the results from this comparative study, we present guidelines for location analysts to aid them in selecting the best heuristic and corresponding parameters depending on the problem at hand. Additionally, we found that existing heuristic algorithms are not suitable for solving large-scale p-median problems in a reasonable amount of time. We present a density-based decomposition methodology to solve large-scale p-median problems efficiently. This algorithm identifies dense clusters in the region and uses a MapReduce procedure to select facilities in the clustered regions independently and combine the solutions from the subproblems. Lastly, we present a novel greedy heuristic algorithm to solve the contiguity constrained fixed facility demand distribution problem. The objective of this problem is to create contiguous service areas for the facilities such that the demand at all facilities is uniform or proportional to the available resources, while the distance between demand points and facilities is minimized. The results in this research are shown in the context of creating emergency response plans for bio-emergencies. The algorithms are used to select Point of Dispensing (POD) locations (if not known) and map them to population regions to ensure that all affected individuals are assigned to a POD facility.

Due to a variety of political, economic, and technological factors, many national electricity industries around the globe are transforming from non-competitive monopolies with centralized systems to decentralized operations with competitive business units. This process, commonly referred to as deregulation (or liberalization) is driven by the belief that a monopolistic industry fails to achieve economic efficiency for consumers over the long run. Deregulation has occurred in a number of industries such as: aviation, natural gas, transportation, and telecommunications. The most recent movement involving the deregulation of the electricity marketplace is expected to yield consumer benefit as well. To facilitate deregulation of the electricity marketplace, competitive business units must be established to manage various functions and services independently. In addition, these business units must be given physical property rights for certain parts of the transmission and distribution network in order to provide reliable service and make effective business decisions. However, partitioning a physical power grid into economically viable districts involves many considerations. We refer to this complex problem as the electrical power districting problem. This research is intended to identify the necessary and fundamental characteristics to appropriately model and solve an electrical power districting problem. Specifically, the objectives of this research are five-fold. First, to identify the issues relevant to electrical power districting problems. Second, to investigate the similarities and differences of electrical power districting problems with other districting problems published in the research literature. Third, to develop and recommend an appropriate solution methodology for electrical power districting problems. Fourth, to demonstrate the effectiveness of the proposed solution method for a specific case of electric power districting in the Republic of Ghana, with data provided by the World Bank. Finally, to develop a decision support system for the decision makers at the World Bank for solving Ghana's electrical power districting problem. / Ph. D.

Dans ce document, nous étudions deux problèmes de sectorisation et proposons plusieurs méthodes de résolution exactes basées sur la décomposition de Dantzig-Wolfe et la génération de colonnes. Nous proposons deux modélisations en fonction de la manière d’appréhender l’objectif du problème qui consiste à obtenir des secteurs compacts. Pour chacune des modélisations, nous comparons des approches de résolution exactes basées sur des formulations compactes ou sur des formulations étendues obtenues par la décomposition de Dantzig-Wolfe. Le premier type de modèles proposé définit la fonction objectif à la manière d’un problème de p-median. Concernant les méthodes de résolution pour ce type de modèle, l’accent est mis sur l’accélération de la convergence de l’algorithme de génération de colonnes en mettant en place des techniques d’agrégation de contraintes afin de réduire la dégénérescence de l’algorithme du simplexe. Les expérimentations numériques montrent que la méthode d’agrégation de contraintes proposée permet effectivement de réduire le nombre d’itérations dégénérées. Cependant, elle ne suffit pas à accélérer l’algorithme de branch-and-price. Le choix d’utilisation de la formulation compacte ou de la formulation étendue dépend du type d’instances résolu. Le second type de modèles formule l’objectif d’une manière assez proche de celui des problèmes de p-centre. L’utilisation d’un tel objectif complexifie la résolution des sous-problèmes de génération de colonnes. L’accent est donc mis sur la conception d’algorithmes de branch-and-bound et de programmation dynamique pour les résoudre efficacement. Les expériences montrent que l’algorithme de branch-and-price surpasse les approches de résolution utilisant une formulation compacte du problème. / In this document, we study two districting problems and propose several exact methods, based on Dantzig-Wolfe decomposition and column generation, to solve them. For each model, we compare exact approaches based either on compact formulations or on extended formulations obtained using Dantzig-Wolfe decomposition. The first type of model that we propose defines the objective function in a p-median problem fashion. Regarding the methods used to solve that kind of model, we emphasize accelerating the convergence of the column generation algorithm by designing constraint aggregation techniques in order to reduce the degeneracy in the simplex algorithm. Numerical experiments show that this constraint aggregation method indeed reduces the proportion of degenerated iterations. However, it is not enough to speed up the branch-and-price algorithm. Choosing to tackle the problem through either a compact formulation or an extended formulation depends on the structure of the instances to solve. The second type of model formulates the objective function in a way quite similar to that of p-centre problems. Using such an objective function induces complex column generation subproblems. We focus on designing branch-and-bound and dynamic programming algorithms in order to solve them efficiently. Experiments show that the branch-and-price approach surpasses any proposed method based on compact formulations of the problem.