Metódy pre riešenie úlohy návrhu turnusov pre elektrobusy vo verejnej doprave
Autor práce: Ing. Maroš JanovecŠkoliteľ: doc. Ing. Michal Koháni, PhD.
Dátum obhajoby: 19.8.2021
Študijný program: inteligentné informačné systémy
Oponent 1: prof. Ing. Ivan Brezina, CSc.
Oponent 2: doc. Ing. Dušan Teichmann, Ph.D.
Slovenský abstrakt:
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
Anglický abstrakt:
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
Autoreferát dizertačnej práce
Text práce