Approximation algorithms for the bipartite traveling salesman problem

Abstract

Το Διμερές Πρόβλημα του Περιοδεύοντος Πωλητή (BTSP) αποτελεί επέκταση του κλασικού NP-Δύσκολο προβλήματος του Περιοδεύοντος Πωλητή (TSP), όπου οι κόμβοι χωρίζονται σε δύο διακριτά σύνολα και μια έγκυρη διαδρομή πρέπει να εναλλάσσεται μεταξύ τους. Αυτή η δομή ευθυγραμμίζεται με τις λειτουργίες Pick-and-Place (PnP) στη ρομποτική κατασκευή και εφοδιαστική, όπου ένας μεταφορέας κινείται μεταξύ θέσεων περισυλλογής και θέσεων απόθεσης για τη βέλτιστη μεταφορά. Η παρούσα διπλωματική εργασία διερευνά αλγορίθμους βελτιστοποίησης για την επίλυση του BTSP σε περιβάλλοντα PnP, αναλύοντας τους συμβιβασμούς μεταξύ ακριβών και ευρετικών μεθόδων. Από τη μία πλευρά, η Ακριβής Μέθοδος που χρησιμοποιείται διαμορφώνεται ως ένα Μοντέλο Ακέραιου Προγραμματισμού (IP), διασφαλίζοντας τη βέλτιστη λύση, αλλά καθίσταται υπολογιστικά απαιτητική καθώς το μέγεθος του προβλήματος αυξάνεται. Από την άλλη πλευρά, οι ευρετικές μέθοδοι επιτυγχάνουν μικρό κενό βέλτιστου, με τη μέθοδο του Nearest Neighbor (NN) να προσφέρει ταχείς χρόνους εκτέλεσης, ενώ η 2-opt, παρότι βελτιώνει την ποιότητα της λύσης, οδηγεί σε σημαντική αύξηση στο υπολογιστικό κόστος καθώς το μέγεθος του προβλήματος μεγαλώνει. Για την αξιολόγηση αυτών των μεθόδων, αναπτύχθηκε ένα πειραματικό πλαίσιο που δημιουργεί στιγμιότυπα προβλημάτων, την εκτέλεση των αντίστοιχων αλγορίθμων και αναλύει την απόδοσή τους με βάση το χρόνο εκτέλεσης και το κενό βέλτιστου. Τα ευρήματα αναδεικνύουν τη σημασία της επιλογής μεθόδου με βάση την κλίμακα του προβλήματος και τους υπολογιστικούς περιορισμούς. Η έρευνα αυτή συμβάλλει στην εξέλιξη της βελτιστοποίησης του BTSP στη βιομηχανική ρομποτική, παρέχοντας τη βάση για μελλοντική έρευνα σε κλιμακούμενα και έξυπνα συστήματα προγραμματισμού. Η μελλοντική έρευνα θα μπορούσε να εξετάσει την ενσωμάτωση τεχνικών μηχανικής μάθησης και ενισχυτικής μάθησης για την περαιτέρω βελτίωση της αποδοτικότητας και της προσαρμοστικότητας των λύσεων σε πραγματικό χρόνο στη βιομηχανική παραγωγή.

The Bipartite Traveling Salesman Problem (BTSP) is an extension of the classical NP hard problem of the Traveling Salesman Problem (TSP), where nodes are divided into two disjoint sets, and a valid tour must alternate between them. This structure aligns with Pick-and-Place (PnP) operations in robotic manufacturing and logistics, where a transfer agent moves between depots and terminal positions to optimize transportation. This thesis explores optimization algorithms for solving the BTSP in PnP environments, analyzing the trade-offs between exact and heuristic methods. On one hand, the Exact Method utilized an Integer Programming (IP) model, ensuring the optimal solution but becoming computationally expensive as the problem size increases. On the other hand, heuristic methods achieve a small optimality gap, with Nearest Neighbor (NN) offering fast execution times, while 2-opt, despite improving solution quality, also leads to a significant rise in computational cost as the problem size grows. To evaluate these methods, an experimental framework was developed to generate problem instances, run the corresponding algorithms, and analyze performance based on execution time and optimality gap. The findings highlight the importance of method selection based on problem scale and computational constraints. This research contributes to the advancement of BTSP optimization in industrial robotics, providing a foundation for future work in scalable and intelligent scheduling systems. Future research could explore the integration of machine learning and reinforcement learning to further enhance solution efficiency and adaptability in real-time manufacturing environments.