Kontrola stavu vozovky jako optimalizační problém nad silniční sítí ČR

This thesis addresses the optimization problem of planning daily inspection routes for road repair quality control in a real-world corporate setting. The objective is to plan a single- vehicle route that, within the time budget of one work shift, maximizes the coverage of diverse inspection situations. The problem is formalized as a single-vehicle open Set Orien- teering Problem with a fixed start, variable service times, and cluster-based scoring, where visiting any member of a cluster covers the entire group. The thesis presents a mathematical MILP formulation with Miller-Tucker-Zemlin subtour elimination and concurrently imple- ments a two-phase heuristic (greedy construction and VND local search). Both approaches are experimentally compared on two real instances derived from corporate data – the Plzeň Region (140 points, 65 clusters) and the Ústí Region (718 points, 250 clusters) – in a sym- metric design of sixteen runs. The heuristic consistently achieves profits of 191–218 in under three seconds, whereas the exact MILP solver HiGHS fails to reach even half of this profit after five hours of computation and crashes due to memory exhaustion on the larger instance. A supplementary structured expert assessment by two company employees rates the practical usability of the proposed routes at an average of 4.6 out of 5 points.