Μεθευρετικές μέθοδοι και τεχνικές εμπνευσμένες από τον κβαντικό υπολογισμό για αλγόριθμους βελτιστοποίησης
Date Issued
August 11, 2020
Type
Διδακτορική Διατριβή
Abstract
The composition of this dissertation concerns the field of Algorithm Optimization and more specifically the field of Combinatorial Optimization (CO).Fundamentally, it deals with the exploration of Metaheuristic methods based on conventional and unconventional methods, inspired by quantum computational techniques, with the aim of applying them to optimization algorithms to solve real-world problems. Specifically, we present the quantum-inspired qGVNS (quantum General Variable Neighborhood Search) method, which is used to solve the Travelling Salesman Problem (TSP in short) as well as its variant of Travelling Salesman Problem with Time Windows, (TSPTW in short). The ultimate goal is to solve real-world problems that have been modeled as optimization problems (TSP or TSPTW) using the unconventional metaheuristic methods we have developed.The Travelling Salesman Problem is used as a reference point in many optimization methods and has many applications in many different areas, such as artificial intelligence, bio computing, routing optimization and elsewhere. In this dissertation we particularly explore the version of the TSP problem, which consists of some additional limitations, such as time windows. This version is known as TSPTW (Travelling Salesman Problem with Time Windows).Based on the Travelling Salesman Problem (TSP) but also the problem of the Travelling Salesman Problem with time windows (TSPTW) we solved the problem of grabage collection from the real world, in two different versions. The simple problem of garb collection as well as the problem of waste collection with time windows.We proceed to a detailed and thorough comparative and performance analysis between the new quantum-inspired method that we proposed and other conventional methods. This dissertation concludes with a presentation of some key points and bibliography related to quantum optimization and quantum annealing.
Subjects