| Abstract : | H παρούσα διπλωματική εργασία διερευνά τη γενίκευση του Προβλήματος Προσανατολισμού Συνόλων (Set Orienteering Problem - SOP) για πολλαπλά οχήματα. Το SOP στοχεύει να βρει τη βέλτιστη διαδρομή ενός οχήματος χωρίς να υπερβαίνουν ένα συγκεκριμένο χρονικό περιορισμό. Κύριος σκοπός είναι η μεγιστοποίηση του κέρδους που συλλέγεται από την εξυπηρέτηση των πελατών. Ένα ακόμα βασικό χαρακτηριστικό είναι ότι οι πελάτες ομαδοποιούνται σε συστάδες και η συλλογή του κέρδους πραγματοποιείται αρκεί να εξυπηρετηθεί ένας πελάτης της συστάδας. Στη γενίκευση του προβλήματος που αντιμετωπίζεται σε αυτή την εργασία, πολλά οχήματα είναι διαθέσιμα για συλλογή κερδών.Παρέχεται μια μαθηματική διατύπωση MIP (Mixed Integer Programming), η οποία ενσωματώνει όλους τους περιορισμούς και έχει ως στόχο της τη μεγιστοποίηση του εισπραχθέν κέρδος.Ο προτεινόμενος αλγόριθμος βασίζεται σε υπάρχουσες μεθόδους για το SOP και ενσωματώνει νέα χαρακτηριστικά για να ληφθούν υπόψη πολλαπλά οχήματα. Ο αλγόριθμος αποτελείται από δύο κύρια μέρη, την κατασκευή της αρχικής λύσης με μια άπληστη μέθοδο κατασκευής και τη βελτίωση της αρχικής λύσης με μια επαναληπτική μέθοδο τοπικής αναζήτησης. Η υλοποίηση του αλγορίθμου γίνεται σε Python. Υπολογιστικά πειράματα σε περιπτώσεις αναφοράς καταδεικνύουν την αποτελεσματικότητα της προτεινόμενης προσέγγισης όσον αφορά την ποιότητα της λύσης. Συνοπτικά, παρατηρήθηκε ότι η τελική λύση των προβλημάτων βελτιώνεται με τη μέθοδο τοπικής αναζήτησης σε πολύ ικανοποιητικό βαθμό. Συγκεκριμένα, στο 100% των περιπτώσεων για 3 διαθέσιμα οχήματα με μέση αύξηση κέρδους 12,66% και στο 92% των περιπτώσεων για 4 διαθέσιμα οχήματα με μέσο όρο 9,23%. Συνολικά, αυτή η διατριβή συμβάλλει στην πρόοδο της έρευνας για το SOP και τις επεκτάσεις του, ιδιαίτερα στο πλαίσιο πολλαπλών οχημάτων. Ο προτεινόμενος αλγόριθμος παρέχει ένα πολύτιμο εργαλείο για την επίλυση προβλημάτων του πραγματικού κόσμου που περιλαμβάνουν συλλογή κερδών από πολλαπλά οχήματα.
This dissertation investigates the generalization of the Set Orienteering Problem (SOP) for multiple vehicles. The SOP aims to find the optimal closed tour of a single vehicle that maximizes the collected profit within a given time limit. Customers are grouped into clusters, and each cluster is associated with a profit that is collected if at least one customer is served from it. In the generalization of the problem addressed in this work, multiple vehicles are available for profit collection.We provide a MIP (Mixed Integer Programming) mathematical formulation, which incorporates all the constraints and has as its objective function the maximization of the collected profit. The proposed algorithm builds on existing methods for the SOP and incorporates new features to account for multiple vehicles. The algorithm consists of two main parts, the construction of the initial solution by a greedy construction method and the improvement of the initial solution by an iterative local search method.The implementation of the algorithm is done in Python. Computational experiments on benchmark instances demonstrate the effectiveness of the proposed approach in terms of solution quality. In summary, it was observed that the final solution of the problems is improved by the local search method to a very satisfactory degree. Specifically, in 100% of cases for 3 available vehicles with an average profit increase of 12.66% and in 92% of cases for 4 available vehicles with an average of 9.23%.Overall, this dissertation contributes to the advancement of research on the SOP and its extensions, particularly in the context of multiple vehicles. The proposed algorithm provides a valuable tool for solving real-world problems that involve profit collection by multiple vehicles.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.