Modelling and optimisation of routes for reading electrometers

Cílem této práce je využít metody matematického modelování pro účely optimalizace tras při odečtech elektroměrů, které provádí výkonní zaměstnanci společnosti ČEZ Distribuce a.s. Mnoho firem se zaměřuje na objíždění míst za různým účelem, stejně jako ČEZ Distribuce a.s. Pokud se vhodně zvolí výchozí pozice a pořadí míst, která je nutné navštívit, mohou se výrazně ušetřit náklady a zejména čas. Vzhledem ke složitosti problému je vhodným řešením použití nástrojů matematického modelování v optimalizačním softwaru. Nabízí se zde úloha o pokrytí pro nalezení míst k najímání nových zaměstnanců, tj. k nalezení optimálních výchozích pozic tras. Po té lze optimalizovat trasy jednotlivých zaměstnanců, např. pomocí úlohy obchodního cestujícího. Práce ukazuje aplikaci těchto modelů na reálná data, která společnost poskytla, a seznamuje čtenáře nejen s úlohami matematického modelování a se softwarem pro nalezení řešení, ale i s heuristickými metodami, které lze použít pro nalezení dobrého řešení v krátkém čase. Vzhledem k velké výpočetní náročnosti modelů jsou heuristické metody na místě. Práce rovněž shrnuje výsledky a porovnává je se stávajícím řešením, které ČEZ nyní používá.The purpose of the thesis is to use methods from mathematical modelling in order to optimize routes taken by workers of ČEZ Distribuce a.s., who read electrometers. In many companies employees have to visit places from different reasons, as well as in ČEZ Distribuce a.s. If the initial position and the order of places are chosen properly, costs and time can be saved. Due to the complexity of the problem, suitable approach is using methods form mathematical modelling in optimisation software. A good tool for finding places, where it would be suitable to find new employees, can be set-covering problem. After that it is possible to optimise routes for these employees e.g. by using travelling salesman problem. The thesis shows application of these models on real data (provided by ČEZ company) and acquaints readers not only mathematical models and optimisation software for finding results, but also heuristic methods that find good solution in short time. Due to extreme compute intensiveness of mathematical models heuristics are appropriate to use. The thesis also concludes results and compares them with solution that is currently being used in ČEZ