Επιχειρησιακή έρευνα στον τομέα της ναυτιλίας: υποστήριξη αποφάσεων δρομολήγησης πλοίων για μεταφορά φορτίων

Abstract

Vessels routing of a maritime companies fleet and cargo selection for a vessel’s chartering are the two problems which are addressed in this thesis. A number of characteristics of these two problems have leaded the research to different techniques compared to the corresponding techniques that are used in classical vehicle routing problems. In the majority of the techniques that have been used to solve the problem of vessels routing, all feasible scheduled routes that each vessel can execute for the transfer of a set of cargos are generated a priori. This thesis proposes a new method for generating all feasible routes of a vessel for the transfer of a set of cargos. The proposed method uses a backtracking algorithm along with time and capacity constraints in order to reduce the search space and generate the schedule routes in a reasonable time. The advantage of the proposed method in contrast to the majority of methods which are presented in literature is that in the generated routes the vessel can transfer more than one cargo per voyage. According to experimental results presented in this thesis, the proposed method is faster in some cases than the only method presented in the literature that generate routes in which vessels can transfer more than one cargo per voyage. Additionally, in the experimental results section, a comparison with an exhaustive method for generating routes is presented. A computational study that depicts the influence of cargoes characteristics in the performance of the proposed method is also reported. The innovation of this thesis is extended with the presentation of a new method that evaluates the generated routes. The evaluation methods presented in the literature use the total profit of each route as the only criterion for evaluating vessel routes. Although the total profit can be considered as sufficient criterion for the vessels routing problem, it cannot satisfy the requirements of cargo selection problem that is faced by the tramp shipping companies. The proposed evaluation method tries to satisfy these requirements by adding the criterion of the profit rate and the reliability of each route. The reliability of a route depends on the reliability of the cargoes transferred by the route which in turns depends on the reliability of the person that represents each cargo or on the certainty of cargoes information. Experimental results depict the influence that cargo characteristics and parameters values of the evaluation method have on the results of the evaluation method. The thesis ends up with the presentation of the proposed methods integration, in a web information system that can be used to support decision making of maritime companies that operates in tramp shipping.

Η δρομολόγηση του στόλου που διαθέτει μια ναυτιλιακή εταιρεία και η επιλογή φορτίων για την ναύλωση των πλοίων είναι τα δυο προβλήματα με τα οποία πραγματεύεται η παρούσα διατριβή. Οι ιδιαιτερότητες των προβλημάτων αυτών έχουν οδηγήσει τους ερευνητές σε διαφορετικές μεθόδους επίλυσής τους σε σχέση με τους τρόπους επίλυσης των προβλημάτων δρομολόγησης στόλου οχημάτων. Στην πλειοψηφία των μεθόδων αυτών κατά την επίλυση του προβλήματος επιχειρείται η εύρεση όλων των εφικτών δρομολογίων που μπορεί να εκτελέσει κάθε πλοίο του στόλου για την μεταφορά των φορτίων που πρέπει να μεταφερθούν. Η παρούσα διατριβή προτείνει μια νέα μέθοδο δημιουργίας όλων των εφικτών δρομολογίων για την μεταφορά ενός συνόλου φορτίων από ένα πλοίο. Η προτεινόμενη μέθοδος είναι μια μέθοδος οπισθοδρόμησης, η οποία με την χρήση περιορισμών χωρητικότητας και χρονικών παραθύρων περιορίζει το μέγεθος του χώρου αναζήτησης έτσι ώστε να δημιουργήσει όλα τα εφικτά δρομολόγια σε σύντομο χρονικό διάστημα. Η προτεινόμενη μέθοδος σε σχέση με την πλειοψηφία των μεθόδων που καταγράφονται στην βιβλιογραφία έχει το πλεονέκτημα ότι επιτρέπει την παράλληλη μεταφορά δύο ή περισσότερων φορτίων από ένα πλοίο στο ίδιο δρομολόγιο. Σύμφωνα με τα πειραματικά αποτελέσματα που παραθέτονται η προτεινόμενη μέθοδος είναι ταχύτερη σε ορισμένες περιπτώσεις και από την μοναδική ερευνητική εργασία που υπάρχει στην βιβλιογραφία η οποία επίσης επιτρέπει την παράλληλη μεταφορά φορτίων κατά την δημιουργία των δρομολογίων. Στα πειραματικά αποτελέσματα της προτεινόμενης μεθόδου που καταγράφονται στην διατριβή, πέρα από την σύγκριση με άλλες δημοσιευμένες μεθόδους συμπεριλαμβάνεται και η σύγκριση με την εξαντλητική μέθοδο δημιουργίας δρομολογίων καθώς και μια ανάλυση της επιρροής των χαρακτηριστικών των φορτίων στα χαρακτηριστικά των δρομολογίων που δημιουργούνται. Η καινοτομία της διατριβής επεκτείνεται με την παρουσίαση μιας νέας μεθόδου συγκριτικής αξιολόγησης των δρομολογίων. Η αξιολόγηση των δρομολογίων στις υπάρχουσες εργασίες γίνεται με μοναδικό κριτήριο το συνολικό κέρδος ή κόστος που επιφέρει το κάθε δρομολόγιο. Αν και το κόστος ή το κέρδος είναι επαρκή κριτήρια για την περίπτωση του προβλήματος δρομολόγησης στόλου, στην περίπτωση του προβλήματος επιλογής φορτίων κρίνονται ανεπαρκή καθώς δεν καλύπτουν τις ιδιαιτερότητες του προβλήματος αυτού. Τις ιδιαιτερότητες αυτές επιχειρεί να καλύψει η προτεινόμενη μέθοδος η οποία πέρα από το κέρδος του δρομολογίου χρησιμοποιεί ως κριτήριο τον ρυθμό με τον οποίο επιφέρει κέρδη το δρομολόγιο καθώς και το κριτήριο της αξιοπιστίας κάθε δρομολογίου. Η αξιοπιστία ενός δρομολογίου απορρέει από τα φορτία τα οποία μεταφέρει καθώς η ύπαρξη του κάθε φορτίου και η ακρίβεια των στοιχείων που είναι γνωστά για αυτό δεν μπορούν να θεωρηθούν απόλυτα αξιόπιστα. Η παρουσίαση της προτεινόμενης μεθόδου συνοδεύεται από πειραματικά αποτελέσματα τα οποία αναδεικνύουν την επιρροή των παραμέτρων της μεθόδου αλλά και των χαρακτηριστικών των φορτίων που χρησιμοποιούνται για την δημιουργία των δρομολογίων, στα αποτελέσματα αξιολόγησης. Τέλος παρουσιάζεται η ενσωμάτωση των προτεινόμενων μεθόδων δημιουργίας δρομολογίων και αξιολόγησης αυτών σε ένα ολοκληρωμένο δικτυακό πληροφοριακό σύστημα. Το σύστημα αυτό παρέχει υπηρεσίες υποστήριξης αποφάσεων για την επιλογή φορτίων σε ναυτιλιακές εταιρείες.