We are motivated by the problem of computing multicast routing structures in wireless ad-hoc networks modelled by special classes of graphs including unit disk graphs, quasi-unit disk graphs and (λ + 1)-claw-free graphs. Multicast communication can be established by a tree known as Steiner tree. Wireless ad-hoc networks must operate using limited resources, therefore, the suitability of nodes for inclusion in a Steiner tree can vary widely between different nodes. We model this by assuming that each node of the network is assigned a weight that represents the cost of including it in the Steiner tree. Our goal is to compute a Steiner tree with minimum total node weight. However, in scenarios where nodes and links are not reliable, a tree has the drawback that it can be disconnected by the failure of even a single link or node in the network. Therefore, we also consider various fault-tolerant routing structures called 2-edge-connected Steiner subgraphs, k-edge-connected Steiner subgraphs, 2-vertex-connected Steiner subgraphs, and 2-edge-connected group Steiner subgraphs. The problems we consider are NP-hard, so we are interested in algorithms that compute provably good approximate solutions in polynomial time. We present a generalization of Steiner subgraph problems referred to as the node-weighted δ-Steiner subgraph problem, where δ represents connectivity requirements. We present an algorithm with approximation ratio 0.5dρ for the node-weighted δ-Steiner subgraph problem, where d is the bounded maximum degree of the solution subgraph, and ρ is the approximation ratio of the edge-weighted version of the δ-Steiner subgraph problem. We then shown how to construct solution subgraphs of bounded maximum degree d in several graph classes for our problem variants. As a result, we obtain algorithms for the problems we consider, on graph classes that admit subgraphs of small degree, whose approximation ratios are better than the best known ratios for the same problems on general graphs.

Hybridization of genetic algorithms (GAs) with local search techniques has received significant attention in recent years and is being widely used to solve real-world problems. These hybrid GAs, also called memetic algorithms (MAs), are able to incorporate other powerful techniques within the framework of GAs, working as a single unit and counterbalancing each other’s disadvantages. In this thesis, we propose a hybrid GA, called Sequence Based Memetic Algorithm (SBMA) with Inver Over (IO), for solving the travelling salesman problem (TSP). This is a 2-phase MA. The first phase (SBMA) consists of traditional binary operators, and the second phase is based on a unary operator. In SBMA, a tour is split into equal sub-tours. Further, the shortest tour is selected among the sub-tours and then optimized locally. The sub-tours are stored in the memory and then used to guide the evolutionary process via a kind of embedded local search. Additionally, we apply some techniques to adapt the key parameters based on whether the best individual within the population improves or not while also maintaining the diversity. After the first phase, the hybrid algorithm enters the second phase which is the Inver Over with elite population. Here, the IO is directed to get a clue from the elite population by adding and preserving good edges. We have also shown that the above approach can be extended to handle the dynamic TSP. The framework of our hybrid approach, along with the integration of the nearest neighbour list, applying 2-Opt local search on sub-tours and adaptive parameter control in the first phase, and the elite population with the rotating gene pool strategies in the second phase, works well for the DTSP. In order to test the performance of the proposed approach for the DTSP, experiments were carried out based on different DTSP test beds. From the study, it has been observed that the integrated heuristics or meta-heuristics are able to produce good-quality solutions for the DTSP. We also analysed the effect of the gene pool and immigrants generated with the nearest neighbour algorithm, which works well with all DTSP test instances, under different dynamics.

A variety of approaches have been used to solve a variety of combinatorial optimisation problems. Many of those approaches are tailored to the particular problem being addressed. Recently, there has been a growing number of studies towards providing more general search methodologies than currently exist which are applicable to different problem domains without requiring any algorithmic modification. Hyper-heuristics represent a class of such general methodologies which are capable of automating the design of search process via generating new heuristics and/or mixing existing heuristics to solve hard computational problems. This study focuses on the design of selection hyper-heuristics which attempt to improve an initially created solution iteratively through heuristic selection and move acceptance processes and their application to the real-world healthcare scheduling problems, particularly, nurse rostering and surgery admission planning. One of the top previously proposed general hyper-heuristic methodology was an adaptive hyper-heuristic consisting of many parameters, although their values were either fixed or set during the search process, with a complicated design. This approach ranked the first at an international cross-domain heuristic search challenge among twenty other competitors for solving instances from six different problem domains, including maximum satisfiability, one dimensional bin packing, permutation flow shop, personnel scheduling, travelling salesman, vehicle routing problems. The hyper-heuristics submitted to the competition along with the problem domain implementations can now be considered as the benchmark for hyper-heuristics. This thesis describes two new easy-to-implement selection hyper-heuristics and their variants based on iterated and greedy search strategies. A crucial feature of the proposed hyper-heuristics is that they necessitate setting of less number of parameters when compared to many of the existing approaches. This entails an easier and more efficient implementation, since less time and effort is required for parameter tuning. The empirical results show that our most efficient and effective hyper-heuristic which contains only a single parameter outperforms the top ranking algorithm from the challenge when evaluated across all six problem domains. Moreover, experiments using additional nurse rostering problems which are different than the ones used in the challenge and surgery scheduling problems show that the results found by the proposed hyper-heuristics are very competitive, yielding with the best known solutions in some cases.

Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας. Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος. / In this thesis, at short, we present the Travelling Salesman Problem with approximations algorithms, some practical applications and related problems of the main problem. A travelling salesman wants to visit each of a set of towns exactly once starting from and returning to his home town. One of his problems is to find the shortest such trip. We present a self-contained introduction into algorithmic and computational aspects of the TSP along with their theoretical prerequisites as seen from the point of view of an operations researcher who wants to solve practical instances. This thesis is intended to be a guideline of the reader confronted with the question of how to attack a TSP instance depending on its size, its structural properties. Theoretical results are presented in a form which make clear their importance in the design of algorithms for approximate but provably good, and optimal solutions of the TSP.

Το πρόβλημα εύρεσης συντομότερων διαδρομών είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε αυτό το πρόβλημα αναζητείται η συντομότερη διαδρομή μεταξύ δύο δεδομένων σημείων ελαχιστοποιώντας ένα κριτήριο κόστους. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην εύρεση διαδρομών σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει εκτός από την διανυμένη απόσταση και η ελαχιστοποίηση του χρόνου και του κόστους. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές τις περιπτώσεις η καλύτερη λύση δεν μπορεί να οριστεί με μονοσήμαντο τρόπο, και συνεπώς καταφεύγουμε σε αντισταθμίσεις μεταξύ των παραγόντων, που είναι γνωστές ως σύνολο λύσεων κατά Pareto. Παρόλο που για το πρόβλημα μονοκριτηριακής εύρεσης συντομότερων διαδρομών υπάρχουν πολλοί αποδοτικοί αλγόριθμοι για την επίλυση του προβλήματος, το αντίστοιχο πολυκριτηριακό πρόβλημα είναι πολύ πιο σύνθετο. Μέχρι τώρα, αυτό το πρόβλημα έχει αποδειχθεί ότι είναι NP-πλήρες. Επιπλέον, έχει αποδειχθεί ότι το πλήθος των λύσεων σε αυτό το πρόβλημα αυξάνεται εκθετικά σε σχέση με το μέγεθος της εισόδου. Υπάρχουν δύο βασικές προσεγγίσεις επίλυσης τέτοιων προβλημάτων, όπου εξετάζονται πολλαπλά κριτήρια. α) Η πρώτη μέθοδος βρίσκει προσεγγιστικές λύσης κατά έναν ορισμένο παράγοντα. Οι προσεγγιστικές μέθοδοι δεν βρίσκουν απαραίτητα ακριβείς λύσεις, αλλά είναι σχετικά γρήγορες και προσφέρουν εγγύηση για το ποσοστό απόκλισης από την βέλτιστη λύση. β) Η δεύτερη μέθοδος χρησιμοποιεί ευρετικές βελτιώσεις για να επιταχύνει τους ήδη υπάρχοντες αλγορίθμους. Τέτοιες τεχνικές βρίσκουν ακριβείς λύσεις, και το ζητούμενο είναι να επιτευχθεί μια πολύ καλή χρονική απόδοση. Στην παρούσα διπλωματική εργασία επικεντρωνόμαστε στην δεύτερη μέθοδο, υποκινούμενοι από την μεγάλη ζήτηση πρακτικών εφαρμογών για εύρεση αποτελεσματικής και ακριβούς λύσης του προβλήματος συντομότερων διαδρομών υπό πολλαπλά κριτήρια. Πιο συγκεκριμένα, στην εργασία αυτή παρουσιάζουμε ένα ενοποιημένο πλαίσιο για την αποδοτική επίλυση αυτών των προβλημάτων. Προτείνουμε νέες μεθόδους ή βελτιώσεις των υπαρχόντων. Υλοποιήσαμε τις μεθόδους που παρουσιάζουμε συνοδεύοντάς τις με μια εκτενή πειραματική μελέτη πάνω σε δίκτυα ευρείας κλίμακας. / We present new implementations of heuristic algorithms for the solution of the multiobjective shortest path problem, using a new graph structure specifically suited for large scale road networks. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.