title: Επίλυση του προβλήματος προγραμματισμού κρηπιδωτού γερανού (QCSP) με χρήση του αλγορίθμου βελτιστοποίησης σμήνους σωματιδίων (PSO)
title: Solving the Quay Crane Scheduling Problem (QCSP) using the Particle Swarm Optimization algorithm (PSO)
Creators: name: Δημακης Γεωργιος-Ραφαηλ
Publisher: name: Technical University of Crete
Year: 2023

description: Η παρούσα διπλωματική εργασία έχει ως αντικείμενο μελέτης ένα από τα σημαντικότερα προβλήματα στο κόσμο της σύγχρονης ναυτιλίας. Στο πρόβλημα προγραμματισμού κρηπιδωτού γερανού (QCSP) ,σκοπός είναι η δημιουργία ενός χρονοδιαγράμματος γερανών, το οποίο ορίζει μια ώρα έναρξης για κάθε εργασία σε έναν γερανό. Αρχικά, η θεώρηση αυτού του προβλήματος βασίζεται στην τεχνολογία των κρηπιδωτών γερανών. Γενικά, ένα κρηπιδωτό σύστημα γερανών αποτελείται από πολλαπλούς γερανούς τοποθετημένους σε σιδηροδρομικές γραμμές παράλληλα στην αποβάθρα. Από το πρίσμα της επίλυσης, στους βασικούς περιορισμούς για κάθε γερανό περιλαμβάνεται η διατήρηση της απόστασης ασφάλειας και οι διαφορετικοί χρόνοι ενεργοποίησης των γερανών. Αντίστοιχα, κάθε ελλιμενισμένο σκάφος προς εξυπηρέτηση διαθέτει μια σειρά εργασιών μεταφόρτωσης εμπορευματοκιβωτίων όπου κάθε εργασία διαφοροποιείται σε χρόνο εκτέλεσης και θέσης. Με άλλα λόγια, αποσκοπούμε σε μια βέλτιστη αλληλουχία αντιστοίχισης εργασιών με γερανούς εκμεταλλευόμενοι τα παραπάνω χαρακτηριστικά για την διαμόρφωση ενός προγράμματος εργασιών που ελαχιστοποιεί τον χρόνο διεκπεραίωσης τους. Για την επίτευξη των παραπάνω, χρησιμοποιείται ο αλγόριθμος Σμήνους Σωματιδίων (PSO) ο όποιος ανήκει στην κατηγορία των αλγορίθμων swarm intelligence.Η θεωρία πίσω από αυτόν τον αλγόριθμο βασίζεται στον ορισμό μιας λύσης ως σωματίδιο μέσα σε έναν χώρο. Επιπρόσθετα, ο μηχανισμός του αλγορίθμου βασίζεται στην δημιουργία ενός σμήνους σωματιδίων(λύσεων) σε ένα χώρο(διάστημα τιμών  - χώρος λύσεων) και έπειτα την μετακίνηση του σωματιδίου μας(αρχική λύση) χρησιμοποιώντας τις θέσεις των άλλων σωματιδίων σε συνάφεια με τις εξισώσεις ταχύτητας και μετατόπισης για να φτάσει σε καλύτερη θέση(βέλτιστη λύση).
description: This thesis has as its object of study one of the most important problems in the world of modern shipping. In the quay crane scheduling problem (QCSP), the goal is to create a crane schedule, which defines a start time for each job on a crane. Initially, the consideration of this problem is based on the technology of quay cranes. Generally, a platform crane system consists of multiple cranes placed on rails parallel to the dock. From the perspective of solving, the main constraints for each crane include maintaining the safety distance and the different activation times of the cranes. Accordingly, each docked vessel for service has a series of container transshipment tasks where each task is differentiated in execution time and location. In other words, we aim for an optimal task matching sequence with cranes by exploiting the above features to form a task schedule that minimizes their processing time. To achieve the above, the Particle Swarm algorithm (PSO) is used, which belongs to the category of swarm intelligence algorithms. The theory behind this algorithm is based on the definition of a solution as a particle in a space. Additionally, the mechanism of the algorithm is based on creating a swarm of particles (solutions) in a space (value space  - solution space) and then moving our particle (initial solution) using the positions of the other particles in relation to the velocity and displacement equations to reach a better position (optimal solution).