Traffic Signal Optimization

Abstract

S rostoucí velikostí měst a zhoršující se dopravní situací je optimalizace světelných křižovatek stále důležitějším problémem pro zajištění efektivní dopravy ve městech. Tato práce zkoumá zjednodušenou verzi tohoto reálného problému, která byla původně zadána v soutěži Google Hash Code. Cílem je optimalizovat nastavení semaforů na městských křižovatkách tak, aby co nejvíce aut dorazilo do cíle před stanoveným časovým limitem a zároveň se minimalizoval celkový čas strávený v dopravě. Vyvíjíme rychlý a efektivní simulátor, který umožňuje vyhodnocovat navržená řešení pro tento problém. S pomocí tohoto simulátoru následně optimalizujeme nastavení semaforů pomocí tří heuristických algoritmů: genetického algoritmu, horolezeckého algoritmu a simulovaného žíhání. Tyto algoritmy experimentálně porovnáváme na zadaných datových sadách a dosahujeme no- vých nejlepších výsledků na dvou z nich.

As cities grow and traffic congestion worsens, traffic signal optimization is becoming an increasingly important real-world problem for ensuring efficient urban mobility. This thesis explores a simplified version of this problem, originally presented in the Google Hash Code competition. The task involves optimizing the schedules of traffic lights at city intersections to maximize the number of cars reaching their destinations before a deadline, while minimizing the overall time spent in traffic. We develop a fast and efficient simulator to evaluate solutions for the task. We then integrate this simulator into an optimization pipeline with three heuristic algorithms: Genetic Algorithm, Hill Climbing, and Simulated Annealing. We experimentally compare these algorithms on the provided datasets, achieving new best scores on two datasets.