Prihlásenie

JANOVEC, Maroš: Metódy pre riešenie úlohy návrhu turnusov elektrobusov vo verejnej doprave [Dizertačná práca]. Žilinská univerzita v Žiline. Fakulta riadenia a informatiky, Katedra matematických metód a operačnej analýzy. Školiteľ: doc. Ing. Michal Koháni, PhD. Žilinská univerzita v Žiline, Fakulta riadenia a informatiky, 2021. 130 s. V poslednej dobe začínajú získavať na význame elektrické vozidlá, keďže ich prevádzkové náklady sú podstatne nižšie ako v prípade konvenčných vozidiel. Zároveň sa ich používaním znižujú emisie CO2, čím sa prispieva k zlepšeniu životného prostredia. Jednou z oblastí, kde je možné nasadiť elektrické vozidlá, je verejná doprava. V rámci tejto oblasti je možné vymeniť konvenčný autobus za elektrický autobus, keďže ich možnosti nasadenia sú veľmi podobné. Pri nasadení elektrických autobusov je nutné riešiť viaceré optimalizačné úlohy ako návrh siete nabíjacích staníc, návrh liniek, návrh turnusov vozidiel a posádok, kde na rozdiel od riešenia týchto úloh v prípade konvenčných vozidiel je nutné brať do úvahy špecifické črty, ktorými sa líšia od konvenčných autobusov. Sú to napríklad obmedzený dojazd a dlhý čas nabíjania. V tejto práci sa budeme zaoberať riešením úlohy návrhu turnusov elektrických autobusov vo verejnej doprave. V práci sú popísané základné pojmy pre úlohu návrhu turnusov, ďalej je zadefinovaná úloha návrhu turnusov vozidiel, špecifiká súvisiace s prevádzkou elektrických autobusov a prehľad súčasného riešenia danej problematiky. V práci sa ďalej prezentuje definícia úlohy návrhu turnusov pre elektrické autobusy vo verejnej doprave, ako aj navrhnutý matematický model. Okrem riešenia pomocou matematického modelu je navrhnutých aj niekoľko metód na riešenie tejto úlohy. Prvou navrhnutou metódou je metóda redukcie vstupov s využitím riešenia pomocou matematického modelu a IP solvera, ktorá je schopná redukovať množstvo spojov ich spájaním, čím zmenší rozmer úlohy, ktorá sa následne rieši pomocou matematického modelu. Druhá metóda je založená na prístupe generovania stĺpcov, kde boli navrhnuté špecifické algoritmy na riešenie pod-problému založené na algoritme hľadania k-najkratších ciest. Treťou navrhnutou metódou bola implementácia metaheuristiky Grouping genetic algorithm, ktorá je špecifická pre prácu s rozdeľovaním celej množiny prvkov do skupín. Všetky navrhnuté metódy boli otestované na testovacích sadách úloh vytvorených z reálnych dát prevádzky MHD v meste Žilina. Každá metóda bola skúmaná z pohľadu získaných výsledkov ako aj času výpočtu a boli porovnané voči optimálnym výsledkom získaným pomocou riešenia matematického modelu, respektíve voči dolnej hranici riešenia v prípade úloh väčšieho rozsahu, kde nebolo možné získať optimálne riešenie. V závere práce boli všetky navrhnuté metódy porovnané a vyhodnotené. Kľúčové slová: návrh turnusov, elektrické autobusy, matematické modelovanie, exaktný prístup, generovanie stĺpcov, metaheuristiky, Grouping genetic algorithm, redukcia dát

JANOVEC, Maroš: Solving methods for the electric bus scheduling problem in public transport systems [Dissertation thesis]. University of Žilina. Faculty of Management Science and Informatics, Department of Mathematical Methods and Operations Research Supervisor: doc. Ing. Michal Koháni, PhD. University of Žilina, Faculty of Management Science and Informatics, 2021. 130 p. In recent years the electric vehicles are gaining a lot of interest, due to the lower operational costs than conventional vehicles. Also, with the usage of electric vehicles, the CO2 emissions are decreased, which has great importance in improving the living environment. One of the fields, where we can deploy electric vehicles is public transport. In this environment, the change from a conventional bus to an electric bus is possible, because of the similar deployment options. However, during the deployment of electric buses problems like the design of charging network, design of lines, design of vehicle and crew schedules need to be addressed, because of the differences of electric buses from conventional buses like limited driving range and long recharging time. In this work, we address the problem of designing the electric bus schedules in the public transport system. In the text the basic terms of vehicle scheduling problem are described. Next, the problem of vehicle scheduling and the specifics of electric buses are defined as well as the overview of current solutions on this topic. In the thesis, the definition of the electric bus scheduling problem is defined with the formulation of the mathematical model. Besides the solution via the mathematical model, we propose several methods for the solution of the designed problem. The first proposed method is a method based on the input reduction heuristic with the application of a mathematical model and IP solver. This method is able to reduce the number of service trips by grouping them. The grouping decreases the size of the problem and then the problem is solved by the mathematical model. The second method is based on the column generation approach, where we designed algorithms for solving the subproblem phase, specific for our case of electric bus scheduling based on the k-shortest path algorithm. The third proposed method is an implementation of a metaheuristic Grouping genetic algorithm, which is specific to work with a partitioning of a whole set of elements into groups. All the proposed methods were tested on datasets generated from real data provided by public transport system provider in the city of Žilina. Each proposed method was researched from the point of obtained results as well as the computation time and the obtained results were compared to the optimal results gained by solving the mathematical model, or alternatively to the lower bound of the solution in the case of larger datasets, where optimal results could not be obtained. At the end of the thesis, all the methods were compared and evaluated. Key words: scheduling, electric buses, mathematical model, exact approach, column generation, metaheuristics, Grouping genetic algorithm, data reduction