Design and implementation of mathematical metaheuristic algorithms for solving the mathematical transportation problem in deterministic and fuzzy environments

Abstract

This doctoral thesis elucidates the research conducted in addressing the Transport Problem, a crucial component in the functioning of industrial enterprises as well as in both public and private transportation sectors. To address the problem, two novel algorithms rooted in the Particle Swarm Optimization (PSO) framework were devised and executed. The first proposed algorithm, TrigAC-PSO, empowered each individual particle, instilling a sense of autonomy and confidence, enabling them to independently navigate toward optimal positions while leveraging their own experiences for enhanced learning. Beginning with a modest influence from its cognitive component while allowing the social component to dominate, the particle gradually gains greater autonomy as the iterations progress, breaking free from the constraints imposed by the swarm. By the final iteration, the particle consolidates its experiences from the optimal positions previously encountered and re-aligns itself with the swarm, engaging in a reciprocal exchange of information with the other members. This culminates in a harmonious equilibrium of knowledge and movement. It is significant to highlight that this research introduces a pioneering method that empowers each particle to leverage its unique capabilities and strengths, allowing it to navigate the solution space independently of the swarm's guidance. The second proposed variation, FSVAC, exhibits a high degree of combinatorial complexity, as it incorporates contributions from both individual particles and the swarm at regular intervals throughout the iterations. These two variations were rigorously evaluated across 32 different problems and subsequently compared with established algorithms, where they demonstrated their superiority by delivering solutions distinguished by absolute completeness and precision. The results obtained from the specific algorithms represent the most impressive outcomes to date for the particular problems examined, with TricAC-PSO rightfully claiming the top position. The research focusing on the effectiveness of TricAC-PSO, we conducted experiments under conditions of uncertainty, modeling transportation costs and problem solutions using fuzzy numbers. TricAC-PSO was tested across 28 scenarios involving both classical and generalized fuzzy numbers. Subsequently, it was benchmarked against both well-established and contemporary algorithms, yielding highly satisfactory results that provided near-optimal solutions to intricate and complex challenges. Ultimately, the esteemed Urban Transit Routing Problem was a significant focus of this doctoral thesis. The application of Particle Swarm Optimization algorithm to well-documented road networks in the international literature yielded remarkable findings regarding multi-route challenges. This innovative approach successfully met passenger expectations while minimizing travel time, delivering an impressive solution to complex routing issues.

Στην παρούσα Διδακτορική Διατριβή παρουσιάζεται η έρευνα που πραγματοποιήθηκε στα πλαίσια της εκπόνησης της επίλυση του προβλήματος μεταφοράς, το οποίο αποτελεί ζωτικό κομμάτι στη λειτουργία των επιχειρήσεων της βιομηχανίας αλλά και του δημόσιου και ιδιωτικού τομέα μεταφοράς. Για την επίλυση του σχεδιάστηκαν και εφαρμόστηκαν δύο νέοι αλγόριθμοι οι οποίοι στηρίχθηκαν στον αλγόριθμο Βελτιστοποίησης Σμήνους Σωματιδίων (Particle Swarm Optimization algorithm- PSO). O πρώτος αλγόριθμος που σχεδιάστηκε, ο TrigAC-PSO, έδωσε πρωτοβουλίες και έδειξε εμπιστοσύνη στο κάθε σωματίδιο ξεχωριστά να αναζητήσει από μόνο του την καλύτερη θέση και να εκπαιδευτεί μέσα από τα δικά του βιώματα. Ξεκινώντας με μία μικρή τιμή στη γνωστική του συνιστώσα και με την κοινωνική συνιστώσα να υπερτερεί, με το πέρας των επαναλήψεων, δίνεται όλο και περισσότερη ελευθερία στις κινήσεις του σωματιδίου, ξεφεύγοντας από την κατήχηση του σμήνους. Στην τελευταία επανάληψη, το σωματίδιο συλλέγοντας τις εμπειρίες του ως προς τις καλύτερες θέσεις που επισκέφτηκε, συγχρονίζεται ξανά με το σμήνος και ανταλλάσσει τις πληροφορίες με το υπόλοιπα σωματίδια - ερχόμενοι σε μία ισορροπία γνώσεων και κινήσεων. Άξιο αναφοράς αποτελεί το γεγονός ότι είναι η πρώτη φορά που μία μέθοδος εμπιστεύεται τις ικανότητες και τις δυνάμεις του κάθε σωματιδίου αφήνοντας το να ανακαλύψει το πεδίο των λύσεων χωρίς την καθοδήγηση του σμήνους. Η δεύτερη παραλλαγή του PSO , FSVAC, είναι άκρως συνδυαστική καθώς με το πέρας των επαναλήψεων υπάρχει συμμετοχή τόσο του σωματιδίου όσο και του σμήνους σε διαφορετικά τακτά διαστήματα. Οι δύο αυτές παραλλαγές δοκιμάστηκαν σε 32 προβλήματα και έπειτα συγκρίθηκαν με δημοφιλείς αλγόριθμούς όπου απέδειξαν την υπεροχή τους πετυχαίνοντας λύσεις οι οποίες χαρακτηρίζονται από απόλυτη πληρότητα και ακρίβεια. Αξίζει να σημειωθεί ότι τα αποτελέσματα που σημείωσαν οι συγκεκριμένοι αλγόριθμοι είναι τα μέχρι τώρα καλύτερα αποτελέσματα που έχουν επιτευχθεί στα συγκεκριμένα προβλήματα που δοκιμάστηκαν, με τον TricAC-PSO να καταλαμβάνει επάξια την πρώτη θέση. Στο ερευνητικό κομμάτι ως προς την αποτελεσματικότητα του TricAC-PSO, διεξάγαμε πειράματα υπό το ρίσκο της αβεβαιότητας, αναπαριστώντας τα κόστη μεταφοράς αλλά και τις λύσεις των προβλημάτων με ασαφείς αριθμούς . Ο TricAC-PSO εφαρμόστηκε σε 28 περιπτώσεις που περιλάμβαναν τόσο κλασικούς όσο και γενικευμένους ασαφείς αριθμούς. Στη συνέχεια συγκρίθηκε τόσο με παλιούς εδραιωμένους όσο και μοντέρνους αλγόριθμους και τα αποτελέσματα του TricAC-PSO ήταν πάρα πολύ ικανοποιητικά δίνοντας λύσεις κοντά στις βέλτιστες σε πολύπλοκα και σύνθετα προβλήματα. Τέλος, μέρος της εν λόγω διδακτορικής διατριβής αποτέλεσε και το γνωστό πρόβλημα Δρομολόγησης Αστικών Οχημάτων (Urban Vehicle Routing Problem-UVRP) όπου η εφαρμογή του αλγορίθμου βελτιστοποίησης σμήνους σωματιδίων σε δημοφιλή στη διεθνή βιβλιογραφία οδικά δίκτυα έφερε εκπληκτικά αποτελέσματα σε προβλήματα πολλαπλών διαδρομών, ικανοποιώντας απόλυτα και σε ελάχιστο χρόνο τις προσδοκίες των επιβατών.