Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Charalambopoulos, Nikolaos
- Χαραλαμπόπουλος, Νικόλαος
Subjects
dc:subject × 18- Ευρετικοί αλγόριθμοι
- Δρομολόγηση πλοίων
- Γενετικός αλγόριθμος
- Heuristic algorithms
- Ship routing and scheduling
- Genetic algorithm
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Τεχνητή νοημοσύνη
- Οικονομικά και Επιχειρήσεις
- Κοινωνικές Επιστήμες
- Διοικητική Επιστήμη και Επιχειρησιακή Έρευνα
- Computer and Information Sciences
- Natural Sciences
- Artificial Intelligence
- Economics and Business
- Social Sciences
- Management Science and Operations Research
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/59305