No description available.

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

Census operations are very important events in the history of a nation. These operations cover every bit of land and property of the country and its citizens. Census data is also known as demographic data providing valuable information to various users, particularly planners to know the trends in the key areas. Since 2006, Turkey aims to produce this census data not as &ldquo / de-facto&rdquo / (static) but as &ldquo / de-jure&rdquo / (real-time) by the new Address Based Register Information System (ABPRS). Besides, by this new register based census, personal information is matched with their address information and censuses gained a spatial dimension. Data obtained from this kind of a system can be a great input for the creation of &ldquo / small statistical areas (SSAs)&rdquo / which can compose of street blocks or any other small geographical unit to which social data can be referenced and to establish a complete census geography for Turkey. Because, statistics on large administrative units are only necessary for policy design only at an extremely abstracted level of analysis which is far from &quot / real&quot / problems as experienced by individuals. In this thesis, it is aimed to employ some spatial clustering and districting methodologies to automatically produce SSAs which are basically built upon the ABPRS data that is geo-referenced with the aid of geographical information systems (GIS) and thus help improving the census geography concept which is limited with only higher level administrative boundaries in Turkey. In order to have a clear idea of what strategy to choose for its realization, small area identification criteria and methodologies are searched by looking into the United Nations&rsquo / recommendations and by taking some national and international applications into consideration. In addition, spatial clustering methods are examined for obtaining SSAs which fulfills these criteria in an automated fashion. Simulated annealing on k-means clustering, only k-means clustering and simulated annealing on k-means clustering of Self-Organizing Map (SOM) unified distances are deemed as suitable methods. Then these methods are implemented on parcel and block datasets having either raw data or socio-economic status (SES) indices in nine neighborhoods of Ke&ccedil / i&ouml / ren whose graphical and non-graphical raw data are manipulated, geo-referenced and combined in common basemaps. Consequently, simulated annealing refinement on k-means clustering of SOM u-distances is selected as the optimum method for constructing SSAs for all datasets after making a comparative quality assessment study which allows us to see how much each method obeyed the basic criteria of small area identification while creating SSA layers.

This thesis develops quantitative methods which incorporate transportation modeling for tactical and operational home health logistics planning problems. We define home health nurse routing and scheduling (HHNRS) problems, which are dynamic periodic routing and scheduling problems with fixed appointment times, where a set of patients must be visited by a home health nurse according to a prescribed weekly frequency for a prescribed number of consecutive weeks during a planning horizon, and each patient visit must be assigned an appointment time belonging to an allowable menu of equally-spaced times. Patient requests are revealed incrementally, and appointment time selections must be made without knowledge of future requests. First, a static problem variant is studied to understand the impact of fixed appointment times on routing and scheduling decisions, independent of other complicating factors in the HHNRS problem. The costs of offering fixed appointment times are quantified, and purely distance-based heuristics are shown to have potential limitations for appointment time problems unless proposed arc cost transformations are used. Building on this result, a new rolling horizon capacity-based heuristic is developed for HHNRS problems. The heuristic considers interactions between travel times, service times, and the fixed appointment time menu when inserting appointments for currently revealed patient requests into partial nurse schedules. The heuristic is shown to outperform a distance-based heuristic on metrics which emphasize meeting as much patient demand as possible. The home health nurse districting (HHND) problem is a tactical planning problem which influences HHNRS problem solution quality. A set of geographic zones must be partitioned into districts to be served by home health nurses, such that workload is balanced across districts and nurse travel is minimized. A set partitioning model for HHND is formulated and a column generation heuristic is developed which integrates ideas from optimization and local search. Methods for estimating district travel and workload are developed and implemented within the heuristic, which outperforms local search on test instances.

Résumé indisponible. / A healthcare network or health system consists of all organizations, actions and people who participate to promote, restore or maintain people’s health. The health care systems in many developed countries are facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. Increasing healthcare costs has created new alternatives to traditional hospitalization in which one is Home Health Care (HHC). Home health care or domiciliary care is the provision of health care and assistance to people in their own homes, according to a formal assessment of their needs. HHC has attained a specific place in healthcare network. HHC programs have now been successfully implemented in many countries. The purpose of HHC is to provide the care and support needed to assist patients to live independently in their own homes. HHC is primarily performed by means of personal visitations of healthcare workers to patients in their homes, where they provide care assistance according to patients’ needs. In this thesis we have considered different aspects of planning problems for home health care services. The efficient use of resources is necessary in continuous healthcare services. To meet the increased demand of HHC, operation research specialist can play an important role by solving the various combinatorial optimization problems arising in HHC. These problems can be tactical, strategic or operational with respect to planning horizon. Strategic problems are those which help in attaining long term goals or objectives, e.g. higher level of quality for HHC patients and efficient use of resources. These strategic objectives can be achieved through tactical i.e. medium term panning and operational planning i.e. short term planning. The main purpose of our thesis is to identify these potential optimization problems and solve them via recent metaheuristics. HHC is an alternative to traditional hospitalization and has got a significant share in the organization of healthcare in developed countries. The change in aging demographics, recent development in technology and the increase in the demand of healthcare services are major reasons for this rapid growth. Some studies show HHC as a tool to reduce costs of care, which is a major preoccupation in developed countries. Some others reveal that it leads to the improvement of patients’ satisfaction without increasing the resources. Home health care, i.e. visiting and nursing patients in their homes, is a flourishing realm in the medical industry. The number of companies has grown largely both in public and private sectors. The staffing needs for HHC companies have been expanded as well. Also they face the problem of assigning geographically dispersed patients to home healthcare workers and preparing daily schedules for these workers. The challenge of this problem is to combine aspects of vehicle routing and staff rostering. Both of them are well known NP- hard combinatorial optimization problems, it means the amount of computational time required to find solution increases exponentially with problem size. Home healthcare workers scheduling problem is difficult to solve optimally due to presence of large number of constraints. These are two types of constraints: hard constraints and soft constraints. The hard constraints are the restrictions to be fulfilled for the schedules to be applicable and soft constraints are preferences to improve the quality of these schedules. (...)

台灣地區在2010年的行政區域調整中，有三個區域進行縣市合併，合併後的縣市其選區必須重新劃分，而進行劃分時有三個因素可以做為縣市合併後衍生之選區劃分原則，分別是縣市融合、大市效應與優勢現象。這三個因素在以往的選區劃分中甚少被提及，因此本論文特別討論考慮這三個因素的選區劃分。 由於大市效應或優勢現象產生的原因是單一選區中有太多的選舉人口來自縣市合併前的同一行政區，因此我們在劃分前處理中，先對人口過多的行政區進行分割，然後進行選區劃分。為促進縣市融合，我們優先考慮將原縣市交界區域的行政區域劃分至選區，然後才考慮非交界區的行政區域。劃分的過程中，我們參考最多限制優先的原則，透過貪婪演算法進行劃分，劃分結束後再進行選區調整，以求能滿足中選會對選區人口數等相關的規定。 我們在論文中提出了選區評估的指標，可以對縣市融合、大市效應與優勢現象進行衡量與評估，以便作為劃分結果的比較與參考。 最後我們透過對合併後的高雄縣市進行選區劃分，以說明我們整體的概念與方法。根據我們的劃分原則與方法，我們的劃分結果產生6個縣市融合的選區，而中選會所公布的選區劃分結果，沒有任何符合縣市融合精神的選區。同時，相較於中選會的結果，我們的劃分方式有較好的大市效應指標與優勢現象指標。 / During the administrative district adjustment of Taiwan in 2010, three regions conducted the city and county merges. The electoral districts must be redistricted after these merges. There are new issues, related to the merge of city and county, which have seldom being discussed before, namely, the city-county integration, the overpopulation-region effect, and the dominance phenomenon. In this thesis, we will consider these issues as the new principles to be included in electoral districting. The reason that causes overpopulation-region effect or dominance phenomenon is due to too much of population comes from the same administrative district in the city of county prior to the merge. One could avoid these by dividing the overpopulation borough before carrying out the electoral districting. In order to promote the city and county integration, we give priority to these administrative districts on the junction regions of the original city and county configurations before considering the administrative districts on the non-junction regions. The most constraint principles and greedy algorithms are employed in the actual electoral districting processes. After the first districting, we conduct a region adjustment to comply with the regulations of the Central Election Commission (CEC). We also proposed the assessment indices that can be used to evaluate the possible effects due to the city-county integration, the overpopulation-region effect, and the dominance phenomenon. Using these indices, one can compare the results of various districting outcomes. Finally, we illustrated our idea and methods by actually districting the merged region of Kaohsiung city and county. According to our mechanism, we produced six city-county integrated electoral districts where no city-county integrated electoral district was found in the CEC’s districting results. In addition, the districting results produced by our method have better overpopulation-region effect index and better dominance phenomenon index than that announced by CEC.