Pavement Condition Inspection as an Optimization Problem on the Czech Road Network

Thesis title: Kontrola stavu vozovky jako optimalizační problém nad silniční sítí ČR
Author: Rušikvas, Adam
Thesis type: Bakalářská práce
Supervisor: Lacko, Jindřich
Opponents: Rejthar, Jan
Thesis language: Česky
Abstract:
Práce řeší optimalizační úlohu plánování denních kontrolních tras pro inspekci silničních oprav v reálném firemním prostředí. Cílem je naplánovat trasu jednoho vozidla, která v rámci časo- vého rozpočtu pracovní směny maximalizuje pokrytí různorodých kontrolních situací. Úloha je formalizována jako single-vehicle open Set Orienteering Problem s pevným startovním bodem, proměnnými servisními časy a klastrovou logikou, v níž návštěva libovolného člena klastru pokrývá celou skupinu. Práce předkládá matematickou formulaci jako MILP s eli- minací subcyklů metodou Miller-Tucker-Zemlin a souběžně implementuje dvoufázovou heu- ristiku (greedy konstrukci a lokální prohledávání VND). Oba přístupy jsou experimentálně porovnány na dvou reálných instancích odvozených z firemních dat – Plzeňský kraj (140 bodů, 65 klastrů) a Ústecký kraj (718 bodů, 250 klastrů) – v symetrickém designu šestnácti běhů. Heuristika konzistentně dosahuje profitu 191–218 za méně než tři sekundy, zatímco exaktní MILP solver HiGHS ani po pěti hodinách výpočtu nedosáhne ani poloviny tohoto profitu a u větší instance havaruje na nedostatku paměti. Doplňkové strukturované expertní posou- zení dvěma pracovníky firmy hodnotí praktickou použitelnost navržených tras průměrem 4,6 z 5 bodů.
Keywords: Set Orienteering Problem; smíšené celočíselné lineární programování; konstruktivní heuristika; lokální prohledávání; klastrová logika; plánování kontrolních tras; kombinatorická optimalizace
Thesis title: Pavement Condition Inspection as an Optimization Problem on the Czech Road Network
Author: Rušikvas, Adam
Thesis type: Bachelor thesis
Supervisor: Lacko, Jindřich
Opponents: Rejthar, Jan
Thesis language: Česky
Abstract:
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.
Keywords: Set Orienteering Problem; mixed-integer linear programming; constructive heuristic; local search; cluster-based scoring; inspection route planning; combinatorial optimization

Information about study

Study programme: Data Analytics
Type of study programme: Bakalářský studijní program
Assigned degree: Bc.
Institutions assigning academic degree: Vysoká škola ekonomická v Praze
Faculty: Faculty of Informatics and Statistics
Department: Department of Econometrics

Information on submission and defense

Date of assignment: 16. 10. 2025
Date of submission: 11. 5. 2026
Date of defense: 16. 6. 2026
Identifier in the InSIS system: https://insis.vse.cz/zp/94086/podrobnosti

Files for download

    Last update: