Optimization of Supervising Strategy of Public Health Office Using Travelling Salesman Problem

This Bachelor thesis focuses on optimization of routes conducted by Public Health Office in Blansko in order to check performing of mandatory employee testing in companies which needs to be undergone to detect presence of antigen Sars-CoV-2. These audits consist of visiting each company from the subset of companies, and conducting audit to the extent specified by The Ministry of Health of the Czech Republic. Based on available resources defined by number of employees, car fleet and working hours, three possible scenarios of audits are designed. These scenarios lead to three mathematical models which are formulated using travelling salesman problem and it’s modified version with two travelling salesmen. Consequently, these models are solved in optimization software LINGO. Based on the optimal solution, three scenarios are compared taking total time and total expenses into account, and optimal strategy of audits is determined. This strategy leads to optimization of resource utilization compared to the current situation. But first of all, this thesis provides theoretical support for problem solution through the summary of well-known theoretical knowledge. It covers formulation of mathematical models of travelling salesman problem, description of it’s modifications, possible solution methods including heuristic and also metaheuristic methods and last but not least, history and computational complexity of travelling salesman problem.