Μοντελοποίηση και αλγοριθμική επίλυση του προβλήματος δρομολόγησης συνδυασμού επίγειων και μη στελεχωμένων εναέριων οχημάτων

Abstract

Modem supply chains are inclined to redesign their operations in order to accommodate the environmental goals that many countries have set for the future. In urban and suburban transportation in particular, the transition to electric means of transportation is expected to significantly improve the life quality of populations. A type of electric vehicle which has the potential to vastly change urban transportation is the Unmanned Aerial Vehicles (UAV), commonly known as the drone.This thesis approaches the use of UAVs in routing problems, in both humanitarian and commercial applications. In particular, two problems are modeled, which utilize UAVs for search and rescue operations, and two problems which utilize UAVs for parcel deliveries in urban logistics. The first problem presented is the Cumulative Unmanned Aerial Vehicle Routing Problem which addresses search and rescue operations. These operations can be considered as problems which aim at minimizing the time required to cover the area of interest. The proposed approach transforms the underlying coverage problem to a vehicle routing problem using UAVs, incorporating the objective of the search and the limitations regarding the UAVs’ range. The second problem, addressing search and rescue operations is the Moving Peak Drone Search Problem. In this problem, the movement of the victims are taken in consideration, thus it is a dynamic optimization problem. The goal is to maximize the value of the locations which are covered by the UAVs, during the operation. The next problem presented is the Electric Vehicle Routing Problem with Drones, which applies to commercial applications, having the two vehicle types cooperating, in order to overcome their limitations and offer their individual benefits. The goal is to minimize the total energy consumption required for completing the parcel delivery operation. The second problem in this category is the Energy Minimizing Drone Routing Problem with Pickups and Deliveries, which addresses courier operations, such as those used in online trading between individuals. The goal is to minimize the energy required to complete the transportation of the parcels.

Οι σύγχρονες εφοδιαστικές αλυσίδες καλούνται να ανασχεδιάσουν τις διαδικασίες τους προκειμένου αυτές να εναρμονιστούν με τους περιβαλλοντικούς στόχους που πολλές χώρες έχουν θέσει για το εγγύς μέλλον. Ειδικότερα, στον τομέα των αστικών και περιαστικών μεταφορών, η μετάβαση στην ηλεκτροκίνηση αναμένεται να αναβαθμίσει σημαντικά την ποιότητα ζωής των κατοίκων των πόλεων. Ένας τύπος ηλεκτρικού οχήματος που έχει τη δυνατότητα να αλλάξει άρδην τις αστικές μεταφορές είναι τα Μη Στελεχωμένα Εναέρια Οχήματα (Unmanned Aerial Vehicles - UAV ), γνωστά ως «drones».Η παρούσα διδακτορική διατριβή πραγματεύεται τη χρήση των UAV σε προβλήματα δρομολόγησης οχημάτων που αφορούν ανθρωπιστικές και εμπορικές εφαρμογές. Συγκεκριμένα, μοντελοποιεί και επιλύει δύο προβλήματα όπου τα UAV χρησιμοποιούνται σε αποστολές έρευνας και διάσωσης, και δύο προβλήματα που αφορούν τη χρήση τους για τη μεταφορά εμπορευμάτων στον αστικό ιστό πόλεων. Αρχικά παρουσιάζεται το Συσσωρευτικό Πρόβλημα Δρομολόγησης UAV που έχειεφαρμογή σε αποστολές έρευνας και διάσωσης. Οι αποστολές αυτές αποτελούν προβλήματα ελαχιστοποίησης του χρόνου που απαιτείται για την κάλυψη μιας περιοχής ενδιαφέροντος. Η προτεινόμενη μεθοδολογία μετατρέπει το πρόβλημα κάλυψης σε ένα πρόβλημα δρομολόγησης UAV, ενσωματώνοντας σε αυτό τον αντικειμενικό στόχο της αποστολής και τους περιορισμούς που διέπουν την αυτονομία των UAV. Το δεύτερο πρόβλημα που προτείνεται για τη μοντελοποίηση σεναρίων έρευνας, είναι το Πρόβλημα Αναζήτησης Κινούμενων Κορυφών με UAV. Σε αυτό λαμβάνεται υπόψη η κίνηση των αγνοουμένων εντός της περιοχής ενδιαφέροντος, επομένως αποτελεί ένα δυναμικό πρόβλημα βελτιστοποίησης. Στόχος του προβλήματος είναι η μεγιστοποίηση της αξίας των σημείων που καλύπτουν UAV, για το σύνολο του χρόνου που διαρκεί η έρευνα. Στη συνέχεια παρουσιάζεται το Πρόβλημα Δρομολόγησης συνδυασμού Ηλεκτρικών Οχημάτων Δρόμου και UAV, όπου αφορά εμπορικές εφαρμογές, με τους δύο τύπους ηλεκτρικών οχημάτων να λειτουργούν συνεργατικά προκειμένου να παρακάμψουν τις αδυναμίες τους και να προσφέρουν τα πλεονεκτήματά τους. Στόχος του προβλήματος είναι η ελαχιστοποίηση της συνολικά καταναλισκόμενης ενέργειας που απαιτείται για την παράδοση δεμάτων. Το δεύτερο πρόβλημα που προτείνεται σε αυτή την κατηγορία είναι το Πρόβλημα Ελαχιστοποίησης Ενέργειας Δρομολόγησης UAV με Παραλαβές και Παραδόσεις. Σε αυτό μοντελοποιούνται υπηρεσίες ταχυμεταφορών με χρήση UAV μεταξύ ιδιωτών και έχει εφαρμογή σε αγοραπωλησίες μέσω των μέσων κοινωνικής δικτύωσης. Στόχος είναι η ελαχιστοποίηση της ενέργειας που απαιτείται για την εκτέλεση του μεταφορικού έργου.