Dizertačné práce

Návrh priestorovo rozsiahlych kritických obslužných systémov na sieťach

Autor práce: Ing. Matej Cebecauer
Školiteľ: doc. Ing. Ľuboš Buzna, PhD.
Dátum obhajoby: 25.8.2015
Študijný program: 9.2.9 Aplikovaná informatika
Oponent 1: prof. Ing. Peter Závodný, CSc.
Oponent 2: doc. Ing. Josef Volek, CSc.
Oponent 3: prof. Ing. Petr Cenek, CSc.

Slovenský abstrakt:
Cebecauer Matej, Ing.: Návrh priestorovo rozsiahlych kritických obslužných systémov na sieťach (dizertačná práca). Žilinská univerzita v Žiline. Fakulta riadenia a informatiky. Katedra matematických metód a operačnej analýzy. Dizertačná práca sa zaoberá návrhom priestorovo rozsiahlych verejných obslužných systémov. Príkladom takýchto systémov sú stanice rýchlej záchrannej služby, hasičské zbrojnice a policajné stanice. Takéto obslužné systémy sú kritické pre každodenné fungovanie spoločnosti. Efektívny návrh a riadenie týchto systémov vyžaduje spracovanie a zohľadnenie veľkého množstvo dát. V posledných rokoch sa podstatne zlepšila dostupnosť geografických dát. My používame OpenStreetMap dáta k lokalizovaniu umiestnení potencionálnych zákazníkov a extrahovanie cestnej siete, ktorá je použitá na prístup alebo distribúciu služieb. Za zákazníkov pokladáme všetkých obyvateľov geografického územia úlohy. Na priestorový odhad požiadavky na systém využívame dostupné populačné rastre. Ľudia menia svoju polohu v priebehu dňa, čo ma za následok aj zmeny v požiadavke na obslužný systém. Ako prvé v tejto práci vyšetríme to, aký veľký vplyv na optimálny návrh obslužného systému môže mať použité časovo-priestorové rozloženie dopytu. Porovnávame dva optimálne návrhy, ktoré odpovedajú dvom profilom dopytu, nočný profil, keď väčšina obyvateľstva sa nachádza v svojich domovoch a profil odvodený od 24-hodinového priemeru hustoty obyvateľstva. Naša analýza odhalila, že efektivita systému nie je závislá len na stratégii umiestnenia stredísk, ale nepresný časovo-priestorový model rozmiestnenia dopytu môže významne ovplyvniť samotný návrh ale aj vyhodnotenie efektivity už existujúceho obslužného systému. Ďalej sa v práci venujeme návrhu priestorovo rozsiahlych verejných obslužných systémov. V prípade keď je úloha príliš veľká aby bolo nájdené jej optimálne riešenie v rozumnom čase, alebo ju nie je možné udržať v počítačovej pamäti, tak vtedy je agregácia bežne používaný nástroj, ktorý umožňuje transformovať úlohu do menších rozmerov. Použitie agregácie so sebou prináša stratu optimality v dôsledku chýb agregácie. Vplyv týchto chýb môže byť významný, obzvlášť v prípade riešenia priestorovo rozsiahlych úloh s veľkým počtom potencionálnych zákazníkov. V tejto práci prezentujeme nový re-agregačný prístup, ktorý iteratívne minimalizuje zdroje chýb agregácie. Tento prístup je univerzálny, a môže byť ľahko rozšírený pre rôzne umiestňovacie úlohy. K vyhodnoteniu chyby optimality používame testovacie úlohy, pri ktorých je možné nájsť exaktné riešenie. Aby sme otestovali možnosti nášho prístupu, aplikovali sme ho na úlohy dosahujúce takmer 670 000 potencionálnych zákazníkov. Výpočtové experimenty odhalili, že re-agregačná heuristika dosahuje dobrú efektivitu ako pri bežne používaných veľkostiach úloh tak aj pri extrémne veľkých úlohách o p-mediáne a úlohách o lexikografickom minimaxe. Tento prístup umožňuje nájdenie riešení lepšej kvality ako exaktný algoritmus aplikovaný na agregovanú úlohu. Kľúčové slová: návrh verejného obslužného systému, p-medián, lexikografický minimax, agregácia, heuristika, OpenStreetMap, populačný raster, priestorové plánovanie

Anglický abstrakt:
Cebecauer Matej, Ing.: Design of the spatially large critical service systems on networks. (dissertation thesis). University of Žilina. Faculty of Management Science and Informatics. Department of Mathematical Methods and Operations Research. The subject of the dissertation thesis is the public service systems design. Examples of such systems are emergency health-care, police or fire brigades, which are critical for day-to-day functioning of the society. To design and operate these systems efficiently a lot of data needs to be collected and properly utilised. In recent years, the availability of volunteered geographic information has been rapidly growing. Here, we use the OpenStreetMap data to model the demand points, which approximate the geographical location of customers, and the road network, which is used to access or to distribute services. We consider all inhabitants as customers, and therefore to estimate the demand; we use the available population grids. People are changing their location in the course of the day and thus the demand for services is changing accordingly. First, in this thesis, we investigate how the used demand model affects the optimal design of a public service system. We calculate and compare efficient designs corresponding to two demand profiles, a night time demand profile, when the majority of inhabitants rests at home and the demand profile derived from the 24-hours average of the population density. Our analyses reveal that the efficiency of the service system is not only depended on the placement strategy, but imprecise demand model may have significant effects when designing a system as well as when evaluating its efficiency. Second, when a location problem is too large to be computed in a reasonable time or if it is impossible to store it in the computer memory, an aggregation is commonly used tool that allows for transforming it to smaller size. Typically, an aggregation method is used only once, in the initial phase, before the solving process. An unavoidable consequence of the aggregation is the loss of optimality due to aggregation errors. The effects of aggregation errors might be significant, especially, when solving spatially large problems with huge number of potential customers. Here, we propose new re-aggregation approach, which iteratively minimizes sources of the aggregation errors. The proposed approach is versatile and thus it can be easily extended to other location problems. To investigate the optimality error, we use benchmarks that can be computed exactly and to test the applicability of our approach, we study large benchmarks reaching 670 000 customers. Numerical experiments reveal that the re-aggregation heuristic works well for commonly used, as well as for extremely large sizes of the p-median and the lexicographic minimax problems. The approach allows for finding solutions of higher quality than the state-of-the-art exact method that is applied to the aggregated problem. Keywords: public service systems, p-median problem, lexicographic minimax, aggregation, heuristic, OpenStreetMap, population grids, spatial planning and policy.


0
študentov
0
učiteľov
0
partnerov

Partneri FRI

Projekty FRI