Back to search

University of Patras

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/59305

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Charalambopoulos, Nikolaos; Χαραλαμπόπουλος, Νικόλαος. Ευρετικοί αλγόριθμοι για το πρόβλημα δρομολόγησης πλοίων. University of Patras, 2025. http://hdl.handle.net/10442/hedi/59305