This diploma thesis deals with finding the optimal route for running footraces. This work seeks to find a link that determines a lap with a predetermined beginning and a goal at the same time, given the possibility of 251 intersections. This model is derived from the travelling salesman problem, whose primary task is to pass the specified set of places according to the shortest route or in the shortest possible time and to return back to the starting point while visiting each place only once. Of... show full abstractThis diploma thesis deals with finding the optimal route for running footraces. This work seeks to find a link that determines a lap with a predetermined beginning and a goal at the same time, given the possibility of 251 intersections. This model is derived from the travelling salesman problem, whose primary task is to pass the specified set of places according to the shortest route or in the shortest possible time and to return back to the starting point while visiting each place only once. Of course, the routes searched for in this work may be differentiated in several aspects. First of all, it is not necessary to include all of the places you can visit multiple times. The resulting route does not have to be the shortest, but it should have a certain span of distance, as the height metrics obtained are the key factor for optimization. A solution with the exact methods will be demonstrated by the LINGO optimization software, but only for a higher computational difficulty with a limited range of tasks, 21 junctions in the city center. Determining a longer route on a larger set of intersections will allow for derived heuristics with working names: the furthest neighbor with the smallest ascent and a minimal profile change. Part of the thesis is a detailed description of the mathematical model used, the general procedure, along with both a demonstration and an analysis of the applied heuristics. |