Ευρετικοί αλγόριθμοι για το πρόβλημα δρομολόγησης πλοίων

Abstract

This thesis considers the heuristic solution of the ship routing problem (SRP). SRP involves planning the most efficient paths for vessels to follow, considering factors like port visits, fuel consumption, and weather. It has been proved to be a computational intractable problem, belonging to the class of NP-hard problems. Meaning that, exact solution methods are impractical for large instances. The thesis addresses three challenging variants of SRP through the development of novel algorithmic approaches:1. Container Ship Routing (CSR): The aim is to find cost-effective port-to-port routes for a fleet of container ships. A new non-canonical Genetic Algorithm (GA) was designed to tackle this problem, outperforming existing solutions in both benchmark and real-case scenarios.2. Ship Weather Routing (SWR): This is a pathfinding problem that aims to determine the optimal route for a ship traveling from a starting port to a destination port while accounting for weather conditions such as wind, waves, and sea currents. Noting the similarities between the SWR and Robot Motion Planning (RMP) problem, we introduced the Probabilistic Roadmap (PRM) approach (originally successful in Robotics) into the maritime domain to address SWR. Within this framework, we developed a novel, robust, real-time path planning algorithm capable of effectively solving SWR under dynamic and changing weather conditions.3. Container Ship Weather Routing (CSWR): This problem extends CSR by additionally considering weather conditions during the voyage. Combining aspects of both CSR and SWR, it requires the planning of optimal fleet routes while accounting for environmental impacts. To address this challenge, a novel hybrid solution approach was developed, effectively integrating a GA and PRM. The GA determines the optimal sequence of port visits for each ship, while PRM computes the exact weather-aware paths between ports. It is important to highlight that this is the first approach reported in the literature that simultaneously addresses both routing and weather considerations.

Αυτή η διατριβή εξετάζει την ευρετική λύση του προβλήματος δρομολόγησης πλοίων (ΠΔΠ). Το ΠΔΠ περιλαμβάνει τον σχεδιασμό των πιο αποτελεσματικών διαδρομών που πρέπει να ακολουθήσουν τα πλοία, λαμβάνοντας υπόψη παράγοντες όπως οι επισκέψεις σε λιμάνια, η κατανάλωση καυσίμου και ο καιρός. Έχει αποδειχθεί ότι είναι ένα υπολογιστικά δυσεπίλυτο πρόβλημα, που ανήκει στην κατηγορία των NP-hard προβλημάτων. Αυτό σημαίνει ότι οι ακριβείς μέθοδοι επίλυσης είναι μη πρακτικές για μεγάλες περιπτώσεις προβλημάτων. Η διατριβή εξετάζει τρεις απαιτητικές παραλλαγές του ΠΔΠ μέσω της ανάπτυξης καινοτόμων αλγοριθμικών προσεγγίσεων: 1. Δρομολόγηση Πλοίων Εμπορευματοκιβωτίων (ΔΠΕ): Στόχος είναι η εύρεση οικονομικά αποδοτικών διαδρομών από λιμάνι σε λιμάνι για έναν στόλο πλοίων μεταφοράς εμπορευματοκιβωτίων. Ένας νέος μη-κανονικός Γενετικός Αλγόριθμος (GA) σχεδιάστηκε για να αντιμετωπίσει αυτό το πρόβλημα, ξεπερνώντας τις υπάρχουσες λύσεις τόσο σε σενάρια προβλημάτων αναφοράς όσο και σε πραγματικά σενάρια. 2. Δρομολόγηση Πλοίων με βάση τις Καιρικές συνθήκες (ΔΠΚ): Πρόκειται για ένα πρόβλημα εύρεσης διαδρομής που στοχεύει στον προσδιορισμό της βέλτιστης διαδρομής για ένα πλοίο που ταξιδεύει από ένα λιμάνι εκκίνησης σε ένα λιμάνι προορισμό, λαμβάνοντας υπόψη καιρικές συνθήκες όπως ο άνεμος, τα κύματα και τα θαλάσσια ρεύματα. Σημειώνοντας τις ομοιότητες μεταξύ του προβλήματος ΔΠΚ και του προβλήματος του Σχεδιασμού Κίνησης Ρομπότ (ΣΚΡ), εισαγάγαμε την προσέγγιση του Στοχαστικού Οδικού Χάρτη (ΣΟΧ) (αρχικά επιτυχημένη στη Ρομποτική) στον ναυτιλιακό τομέα για την αντιμετώπιση του προβλήματος ΔΠΚ. Σε αυτό το πλαίσιο, αναπτύξαμε έναν νέο, ισχυρό αλγόριθμο σχεδιασμού διαδρομής σε πραγματικό χρόνο, ικανό να λύσει αποτελεσματικά το πρόβλημα ΔΠΚ υπό δυναμικές και μεταβαλλόμενες καιρικές συνθήκες. 3. Δρομολόγηση Πλοίων Εμπορευματοκιβωτίων με βάση τις Καιρικές συνθήκες (ΔΠΕΚ): Αυτό το πρόβλημα επεκτείνει το πρόβλημα ΔΠΕ λαμβάνοντας επιπλέον υπόψη τις καιρικές συνθήκες κατά τη διάρκεια του ταξιδιού. Αυτό το πρόβλημα, συνδυάζοντας πτυχές τόσο του προβλήματος ΔΠΕ όσο και του προβλήματος ΔΠΚ, απαιτεί τον σχεδιασμό βέλτιστων διαδρομών για έναν στόλο, λαμβάνοντας παράλληλα υπόψη τις περιβαλλοντικές επιπτώσεις. Για την αντιμετώπιση αυτής της πρόκλησης, αναπτύχθηκε μια νέα υβριδική προσέγγιση λύσης, ενσωματώνοντας αποτελεσματικά έναν Γενετικό Αλγόριθμο (ΓΑ) και μια μέθοδο ΣΟΧ. Ο ΓΑ καθορίζει τη βέλτιστη ακολουθία επισκέψεων σε λιμάνια για κάθε πλοίο, ενώ η μέθοδος ΣΟΧ υπολογίζει τις ακριβείς διαδρομές μεταξύ των λιμένων με επίγνωση του καιρού. Είναι σημαντικό να τονιστεί ότι αυτή είναι η πρώτη προσέγγιση που αναφέρεται στη βιβλιογραφία που αντιμετωπίζει ταυτόχρονα τόσο τις δρομολογήσεις όσο και τις καιρικές συνθήκες.