This thesis deals with the existence and properties of certain types of covering spaces. It contains the discussion of a generalization of the notion of simple connectedness and several well-known theorems depending on this. / Thesis / Master of Science (MS)

We consider a hierarchical maximal covering location problem to locate p health centers and q hospitals in such a way that maximum demand is covered, where health centers and hospitals have successively inclusive hierarchy. Demands are 3 types: demand requiring low-level service only, demand requiring high-level service only, and demand requiring both levels of service at the same time. All types of requirements of a demand point should be either covered by hospital providing both levels of service or referred to hospital via health center since a demand point is not covered unless all levels of requirements are satisfied. Thus, a health center cannot be opened unless it is suitable to refer its covered demand to a hospital. Referral is defined as coverage of health centers by hospitals. We also added partial coverage to this complex hierarchic structure, that is, a demand point is fully covered up to the minimum critical distance, non-covered after the maximum critical distance and covered with a decreasing quality while increasing distance to the facility between minimum and maximum critical distances. We developed an MIP formulation to solve the Hierarchical Maximal Covering Location Problem with referral in the presence of partial coverage. We solved small-size problems optimally using GAMS. For large-size problems we developed a Genetic Algorithm that gives near-optimal results quickly. We tested our Genetic Algorithm on randomly generated problems of sizes up to 1000 nodes.

In this study, a bi-objective capacitated facility location problem is presented which includes partial coverage concept and relocation of facility nodes. In partial coverage, a predefined distance between a demand node and a facility node is assumed to be fully covered. After the predefined distance, the service level commences to decay linearly. The problem is designed to consider the existence of already functioning facility nodes. It is allowed to close these existing facilities and open new facilities in potential sites. However, existing facility nodes are strongly favored against new facility nodes. The objectives are the maximization of the weighted total coverage and the minimization of number of facility nodes. A novel interactive multi-objective evolutionary algorithm is proposed to solve this problem, I-TREA. I-TREA is originated from NSGA-II and designed for interactive methods benefiting from quality infeasible solutions. The performance of I-TREA is benchmarked with a modified version of NSGA-II on randomly generated problems with various sizes and utility functions.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第17873号 / 工博第3782号 / 新制||工||1578(附属図書館) / 30693 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 教授 藤井 聡, 准教授 宇野 伸宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Significant advances have been made in the research and development of electric vehicles (EV’s). Along with the major challenge of energy storage, being also addressed is the efficient design of system energy transfer and consumption. This has had the effect of fundamentally changing perspectives across the mobility and transportation sector. Applied predominantly to road-going vehicles, the industrial context of non-road Electric Vehicles (nrEV’s) and specifically the use of manned electric forklift trucks integrated within the production related materials handling system has, to-date, received far less attention. The overarching aim of this research is to examine the impact and potential for the use of contactless occasional recharging of nrEV’s integrated within a manufacturing line, recognising the need to balance the (sometimes competing) demands of delivering sustainable production while exercising environmental responsibility. Meeting the objectives of this research resulted in the development of a location allocation model for electric charging station determination based on a fundamental understanding of the nature and quality of process inherent key performance indicators (KPI’s) as well as comprehensive process and energy monitoring while considering both Lean and Green Management perspectives. The integration of the generated knowledge and information into a generally valid simulation tool for occasional charging system implementation allows to more thoroughly investigate the impact from occasional charging to overall efficiency and sustainability to be realised. An investigation into relevant literature identified the need for specifically generated energy consumption data and confirmed the need for an energy optimisation model specific to the area of production related materials handling. Empirical data collected from repeated standardised materials handling operations within a selected production related materials handling environment resulted in the development of the Standard Energy Consumption Activity tool (SECA). Further work within this pilot study confirmed the tool as capable of generating reliable and valid data and confirmed the SECA tool as a generally applicable benchmark for energy consumption determination in material handling based on fractional process functions. Integrating this approach into a comprehensive process analysis and charging infrastructure optimisation resulted in the development of an Excel-based simulation model. The (Occasional Charging Station Location Model) OCSLM is based upon Maximal Covering Location Modelling and an endogenous covering distance definition in order to simulate process related potentials and optimal charging system implementation allocations, the target being to increase vehicles usable battery energy. A comprehensive case study based upon six individual and one combined data set confirmed the general and wider applicability of the OCSLM model while the application of the model provides a set of novel results. The application demonstrated a theoretical increase in usable battery energy of between 40% and 60% and within the same case study the impact of technology implementation identified that a reduction in battery and system cost of between 5% and 45% can be realised. However, the use of contactless power transfer resulted in an increase in CO2 emissions of up to 6.89% revealing a negative impact to overall ecology from the use of this energy transfer system. Depending on the availability of fast connecting, contact based energy transmission systems, the approach and results of OCSLM have shown to be directly applicable to contact based systems with resulting CO2 emissions decreasing by 0.94% at an energy transfer efficiency of 96%. Further novelty, of benefit to both academic and industry practice, was realised through the framework and information of the research with the provision of SECA as a process function-based and generally applicable energy consumption standard, OCSLM as a Maximal Covering Location Modell with a focus on occasional charging based on an endogenous covering distance and integrating detailed energy and process monitoring into electric charging station allocation, and the methodology for the application of this approach for fast connecting contactless and contact charging models and cases.

In this study, our aim is to determine the locations of bottle banks used in collecting recycled glass. The collection of recycled glass is done by a fleet of vehicles that visit some predetermined collection points, like restaurants and hospitals. The location of bottle banks depends on the closeness of the banks to the population zones where the recycled class is generated, and to the closeness of the banks to the predetermined collection points. A mathematical model, which combines the maximal covering problem in the presence of partial coverage and vehicle routing problem with profits, is presented. Heuristic procedures are proposed for the solution of the problem. Computational results based on generated test problems are provided. We also discuss a case study, where bottle banks are located in Yenimahalle, a district of Ankara

In this study, we propose a bi-objective facility location model that considers both partial coverage and service to uncovered demands. In this model, it is assumed that the demand nodes within the predefined distance of opened facilities are fully covered and after that distance the coverage level linearly decreases. The objectives are the maximization of the sum of full and partial coverage the minimization of the maximum distance between uncovered demand nodes and their closest opened facilities. We apply two existing Multi Objective Genetic Algorithms (MOGAs), NSGA-II and SPEA-II to the problem. We determine the drawbacks of these MOGAs and develop a new MOGA called modified SPEA-II (mSPEA-II) to avoid the drawbacks. In this method, the fitness function of SPEA-II is modified and the crowding distance calculation of NSGA-II is used. The performance of mSPEA-II is tested on randomly generated problems of different sizes. The results are compared with the solutions resulting from NSGA-II and SPEA-II. Our experiments show that mSPEA-II outperforms both NSGA-II and SPEA-II.

In this study, a metaheuristic procedure, particularly a variable neighborhood search procedure, is proposed to solve the combined location and selective traveling salesman problem in glass recycling. The collection of used glass is done by a collecting vehicle that visits a number of predefined collection centers, like restaurants and hospitals that are going to be referred to as compulsory points. Meanwhile, it is desired to locate a predetermined number of bottle banks to residential areas. The aim is to determine the location of these bottle banks and the route of the collecting vehicle so that all compulsory points and all bottle banks are visited and the maximum profit is obtained. Population zones are defined in residential areas and it is assumed that the people in a particular population zone will recycle their used glass to the closest bottle bank that fully or partially covers their zone. A Variable Neighborhood Search algorithm and its variant have been utilized for the solution of the problem. Computational experiments have been made on small and medium scale test problems, randomly generated and adapted from the literature.

Indiana University-Purdue University Indianapolis (IUPUI) / While optimization techniques have been studied since 300 B.C. when Euclid first considered the minimal distance between a point and a line, it wasn’t until 1966 that location optimization was first applied to a problem in healthcare. Location optimization techniques are capable of increasing efficiency and equity in the placement of many types of services, including those within the healthcare industry, thus enhancing quality of life. Medical imaging is a healthcare service which helps to determine medical diagnoses in acute and preventive care settings. It provides physicians with information guiding treatment and returning a patient back to optimal health. In this study, a retrospective analysis of the locations of current medical imaging centers in central Indiana is performed, and alternate placement as determined using optimization techniques is considered and compared. This study focuses on reducing the drive time experienced by the population within the study area to their nearest imaging facility. Location optimization models such as the P-Median model, the Maximum Covering model, and Clustering and Partitioning are often used in the field of operations research to solve location problems, but are lesser known within the discipline of Geographic Information Science. This study was intended to demonstrate the capabilities of these powerful algorithms and to increase understanding of how they may be applied to problems within healthcare. While the P-Median model is effective at reducing the overall drive time for a given network set, individuals within the network may experience lengthy drive times. The results further indicate that while the Maximum Covering model is more equitable than the P-Median model, it produces large sets of assigned individuals overwhelming the capacity of one imaging center. Finally, the Clustering and Partitioning method is effective at limiting the number of individuals assigned to a given imaging center, but it does not provide information regarding average drive time for those individuals. In the end, it is determined that a capacitated Maximal Covering model would be the preferred method for solving this particular location problem.

<p>This thesis is devoted to introducing new problem formulations and exact solution methods for a class of continuous covering location models. The manuscript includes three self-contained studies which are organized as in the following. </p> <p> In the first study, we introduce the planar expropriation problem with non-rigid rectangular facilities which has many applications in regional planning and undesirable facility location domains. This model is proposed for determining the locations and formations of two-dimensional rectangular facilities. Based on the geometric properties of such facilities, we developed a new formulation which does not require employing distance measures. The resulting model is a mixed integer nonlinear program. For solving this new model, we derived a continuous branch-and-bound framework utilizing linear approximations for the tradeoff curve associated with the facility formation alternatives. Further, we developed new problem generation and bounding strategies suitable for this particular branch-and-bound procedure. We designed a computational study where we compared this algorithm with two well-known mixed integer nonlinear programming solvers. Computational experience showed that the branch-and-bound procedure we developed performs better than BARON and SBB both in terms of processing time and size of the branching tree.</p> <p> The second study is referred to as the planar maximal covering problem with single convex polygonal shapes and it has ample applications in transmitter location, inspection of geometric shapes and directional antenna location. In this study, we investigated maximal point containment by any convex polygonal shape in the Euclidean plane. Using a fundamental separation property of convex sets, we derived a mixed integer linear formulation for this problem. We were able to identify two types of special cuts based on the geometric properties of the shapes under study, which were later employed for developing a branch-and-cut procedure for solving this particular location model. We also evaluated the resultant bound quality after employing the afore-mentioned cuts. </p> <p> In the third study, we discuss the dynamic planar expropriation problem with single convex polygonal shapes. We showed how the basic problem formulations discussed in the first two studies extend to their diametric opposites, and further to models in higher dimensions. Subsequently, we allowed a dynamic setting where the shape under study is expected to function over a finite planning horizon and the system parameters such as the fixed point locations and expropriation costs are subject to change. The shape was permitted to relocate at the beginning of each time period according to particular relocation costs. We showed that this dynamic problem structure can be decomposed into a set of static problems under a particular vector of relocations. We discussed the solution of this model by two enumeration procedures. Subsequently, we derived an incomplete dynamic programming procedure which is suitable for this distinct problem structure. In this method, there is no need to evaluate all the branches of the branching tree and one proceeds with keeping the minimum stage cost. The evaluation of a branch is postponed until relocation takes place in the lower-level problems. With this postponing structure, the procedure turned out to be superior to the two enumeration procedures in terms of tree size. </p> / Thesis / Doctor of Philosophy (PhD)