Rešavanje diskretnih lokacijskih problema primenom metode promenljivih okolina

Abstract

Predmet ovog rada je analiza i re²avanje dva diskretna lokacijska problema: problema odre ivanja lokacija autobuskih terminala (engl. Bus Terminal Location Problem - BTLP) i problema uspostavljanja centara za produºenu negu pacijenata (engl. Long-term Care Facility Location Problem - LTCFLP). U radu je prikazana metoda promenljivih okolina (engl. Variable Neighborhood Search - VNS) za re²avanje BTLP i LTCFLP problema. VNS je metaheuristika vo ena jednim re- ²enjem i zasnovana je na sistemati£noj pretrazi okolina re²enja prostora pretrage. Sastoji se iz dve faze, faze razmrdavanja i faze lokalne pretrage. BTLP predstavlja diskretan lokacijski problem koji podrazumeva uspostavljanje velikih autobuskih terminala kako bi se omogu¢ila ²to kvalitetnija usluga klijentima. Klijenti predstavljaju lokacije autobuskih i metro stanica javnog prevoza. Za re²avanje BTLP problema VNS metodom predstavljena je unapre ena lokalna pretraga zasnovana na brzoj zameni okolina. Metoda je paralelizovana (PVNS) i postignuto je zna£ajno vremensko ubrzanje metode u zavisnosti od broja jezgara procesora na kome se izvr²ava. Predloºena PVNS metoda daje re²enja boljeg kvaliteta u odnosu na poznata re²enja BTLP problema iz literature. Algoritam je testiran i na ve¢im instancama problema dobijenih modikacijom biblioteke instanci za problem trgova£kog putnika i predstavljeni su rezultati metode na ovim instancama. LTCFLP je nastao kao deo planiranja sistema zdravstvene za²tite u Juºnoj Koreji. Klijenti predstavljaju lokacije na kojima se nalaze grupe pacijenata kojima je potrebna produºena nega, dok uspostavljeni centri predstavljaju lokacije na kojima ¢e se izgraditi zdravstveni centri koji ¢e pruºati negu pacijentima. Unapred je zadato n lokacija na kojima mogu biti uspostavljeni centri. Potrebno je odabrati najvi²e K lokacija za uspostavljanje zdravstvenih centara tako da oni budu ²to ravnomernije optere¢eni zahtevima klijenata. Za re²avanje LTCFLP problema VNS metodom predstavljena je struktura podataka zasnovana na brzoj zameni okolina uz pomo¢ koje je vremenska sloºenost jedne iteracije lokalne pretrage smanjena na O(nmax(n;K2)) u odnosu na vremensku sloºenosti poznatu u literaturi O(K2 n2). Smanjena vremenska sloºenost predstavljene lokalne pretrage dovela je do boljih rezultata zbog ve¢eg broja iteracija VNS algoritma koje koje se mogu izvr²iti u kra¢em vremenskom periodu. Prikazani su rezultati predstavljenog algoritma koji nadma- ²aju poznate rezultate iz literature.

This paper considers two discrete location problems: Bus Terminal Location Problem (BTLP) and Long-term Care Facility Location Problem (LTCFLP). Variable Neighborhood Search (VNS) method for solving BTLP and LTCFLP is presented in this paper. VNS is a single-solution based metaheuristic based on systematic change of neighborhoods while searching for optimal solution of the problem. It consists two main phases: shake phase and local search phase. BTLP is a discrete location problem which considers locating bus terminals in order to provide the highest possible quality of public service to the clients. Clients are presented as public transportation stations, such as bus or metro stations. VNS algorithm is used for solving BTLP. This algorithm uses improved local search based on ecient neighborhood interchange. VNS is parallelized (PVNS) which leads to signicant time improvement in function of the processor core count. Computational results show that proposed PVNS method improves existing results from the literature in terms of quality. Larger instances, based on instances from the Traveling Salesman Problem library, are presented and computational results for those instances are reported. LTCFLP is created as a part of health care infrastructure planning in South Korea. Clients are considered as groups of patients with a need of long-term health care, while established facilities present locations where the centers that provide health care services should be built. Predened are n locations where centers are to be established. This problem seeks at most K locations to establish health centers so they are to be equally loaded with clients demand. For solving LTCFLP, by using VNS algorithm, data structure based on fast interchange is presented. It reduces the time complexity of one iteration of local search algorithm to O(n max(n;K2)) comparing to the known time complexity from the literature O(K2 n2). Reduced time complexity of the presented VNS leads to better quality solutions, due to larger number of VNS iterations that can be performed in less computational time. This paper presents computational results that outperform the best known results from the literature.