Optimizing Routes and Clusters: Overcoming Obstacles with Advanced Geometric Algorithms
Advanced algorithms developed by Leonidas Theocharous navigate obstacles, enhancing the efficiency of route planning and clustering for real-world applications.
Navigating obstacle-filled environments poses significant challenges for classic optimization problems: challenges like buildings and rivers complicate finding optimal routes or grouping locations. Traditional algorithms for tasks like finding the shortest path assume open spaces, which often makes them impractical in real-world scenarios.
PhD researcher Leonidas Theocharous addressed these issues in his thesis, by developing new algorithms that account for obstacles, enhancing their effectiveness for route planning and clustering. These improvements are particularly valuable in logistics, transportation, and urban planning, where navigating around obstacles is crucial. He defended his thesis on Wednesday, October 23rd.
Introduction to TSP with Obstacles
Theocharous’ thesis presented a new approach to the (TSP), which involves finding the shortest route for someone delivering packages. This new version, called the TSP with Obstacles, focused on visiting all client locations while avoiding obstacles like buildings and rivers.
Theocharous’ research specifically examined cases where all client locations were inside a simple shape called a polygon, using the edges of the polygon as the obstacles to navigate around. The Traveling Salesman Problem is a fundamental challenge in logistics and delivery services, making it crucial to optimize routes effectively.
Algorithm Development and Real-World Applications
To solve the TSP with Obstacles, Theocharous introduced a new algorithm that could find solutions more quickly, especially for larger problems. He also explored other classic problems affected by obstacles, such as the , which involved grouping points in a way that minimized the maximum distance any point had to travel to reach its nearest center.
By considering obstacles, these new algorithms became more useful in real-life situations like logistics and city planning. Overall, this work improved the understanding of geometric algorithms in challenging environments and paved the way for future research in this field.
Research conclusions
Theocharous’ research can greatly improve many areas by helping people navigate complex environments with obstacles. For delivery companies, this means they could find faster routes, which would lead to quicker package deliveries and satisfied customers.
Urban planners could use these findings to create better transportation systems, reducing traffic jams.
In emergencies, first responders could reach people in need more quickly, potentially saving lives.Additionally, this research helps advance self-driving technology and encourages more studies in this area while also benefiting the environment by reducing fuel use and emissions.
Overall, it could make a valuable contribution to building a more efficient, connected, and sustainable world.
Title of PhD thesis:
Supervisors: prof.dr. M.T. de Berg,
Media contact
Latest news
