No description available.

Zugl.: Münster (Westfalen), Univ., Diss., 2005 u.d.T.: Rohleder, Andreas: Ein Vorschlag zur Erzeugung von Kandidatenmengen zur Unterstützung der heuristischen Lösung des geometrischen zweidimensionalen Traveling Salesman Problems

Universiẗat, Diss., 2005 u.d.T.: Rohleder, Andreas: Ein Vorschlag zur Erzeugung von Kandidatenmengen zur Unterstützung der heuristischen Lösung des geometrischen zweidimensionalen Traveling Salesman Problems--Münster (Westfalen).

Kiel, University, Diss., 2001.

Zugl.: Düsseldorf, Universiẗat, Diss., 1999.

Techn. Hochsch., Diss., 2000--Aachen.

Thesis(B.Sc.(Hons. ))--University of Adelaide, dept. of Mathematics, 1968.

University, Diss., 2001--Saarbrücken.

Unmanned aerial vehicles (UAVs) are becoming increasingly popular for surveillance in civil and military applications. Vehicles built for this purpose vary in their sensing capabilities, speed and maneuverability. It is therefore natural to assume that a team of UAVs given the mission of visiting a set of targets would include vehicles with differing capabilities. This paper addresses the problem of assigning each vehicle a sequence of targets to visit such that the mission is completed with the least "cost" possible given that the team of vehicles is heterogeneous. In order to simplify the problem the capabilities of each vehicle are modeled as cost to travel from one target to another. In other words, if a vehicle is particularly suited to visit a certain target, the cost for that vehicle to visit that target is low compared to the other vehicles in the team. After applying this simplification, the problem can be posed as an instance of the combinatorial problem called the Heterogeneous Travelling Salesman Problem (HTSP). This paper presents a transformation of a Heterogenous, Multiple Depot, Multiple Traveling Salesman Problem (HMDMTSP) into a single, Asymmetric, Traveling Salesman Problem (ATSP). As a result, algorithms available for the single salesman problem can be used to solve the HMDMTSP. To show the effectiveness of the transformation, the well known Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results show that good quality solutions can be obtained for the HMDMTSP relatively fast. Additional complications to the sequencing problem come in the form of precedence constraints which prescribe a partial order in which nodes must be visited. In this context the sequencing problem was studied seperately using the Linear Program (LP) relaxation of a Mixed Integer Linear Program (MILP) formulation of the combinatorial problem known as the "Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP).

Σ’ αυτή τη διπλωματική εργασία, παρουσιάζουμε προσεγγιστικούς αλγόριθμους για το Πρόβλημα του Πλανόδιου Πωλητή, μερικές πρακτικές εφαρμογές και κάποιες σχετικές παραλλαγές του κύριου προβλήματος. Ένας πλανόδιος πωλητής θέλει να επισκεφθεί κάθε πόλη ενός συνόλου πόλεων ακριβώς μια φορά ξεκινώντας και επιστρέφοντας στην αρχική πόλη. Το κύριο πρόβλημά του είναι να βρει τη συντομότερη διαδρομή. Παρουσιάζουμε μια αυτόνομη εισαγωγή σε αλγοριθμικές και υπολογιστικές απόψεις του προβλήματος μαζί με τις θεωρητικές απαραίτητες προϋποθέσεις τους από την σκοπιά της Επιχειρησιακής Έρευνας. Η διπλωματική αποσκοπεί να παρουσιάσει τις διαδικασίες επίλυσης του Προβλήματος του Πλανόδιου Πωλητή ανάλογα με το μέγεθος και τη δομή του. Θεωρητικά αποτελέσματα παρουσιάζονται σε μορφή που να καθιστούν σαφή τη σημασία τους στο σχεδιασμό των προσεγγιστικών αλγόριθμων για αποδεδειγμένα καλές ή/και βέλτιστες λύσεις του Προβλήματος. / 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.