Algorithmic solutions to orienteering problems and applications

Abstract

A tourist that wants to make the most out of the limited number of days staying in a foreign city. A truck driver trying to deliver the most parcels in a single day. A helicopter trying to find survivors after an earthquake. Three events that seem different, but have a thing in common: The optimal solution can be described by the same family of algorithmic problems, variations of the Orienteering Problem (OP).The OP is an algorithmic problem which is described as follows: Given (a) a graph where all nodes are tagged with a profit and a visiting time, and edges are tagged with a travelling time, (b) the initial and final node, as well as (c) the time budget allotted for visiting nodes, find a simple path that originates from the initial node and terminates at the final node, whose traversal does not exceed the time budget (i.e., the sum of the visiting times of all nodes in the path plus the travelling times between selected nodes is less or equal to the time budget), while maximizing the sum of all profits. Alongside its variants, OP models a multitude of real-world scenarios. Examples of such scenarios are tourist itineraries in foreign cities that visit Points of Interest (POIs), responding to natural disasters such as earthquakes or floods, or surveilling areas with Unmanned Aerial Vehicles (UAVs).Regarding the case of tourists visiting POIs, each node corresponds to a single POI, profits denote a metric on the quality of each POI, while visiting times model the time a tourist will remain at each POI; therefore, solving the OP produces the daily itinerary of the tourist. Conversely, if nodes correspond to collapsed buildings, and the profit denotes the probability that injured people are trapped in each collapsed building, solving the OP should optimize the rescue plan of the first responders. Naturally, the OP is not realistic in its simplest form; constraints such as opening hours of POIs or tourist preferences are not taken into account for the tourism case. Also, first responders first need to set up field hospitals, and the positioning of these hospitals might prove vital for saving lives. Therefore, it is necessary to consider variations of OP with additional parameters and constraints. The OP and its variations are NP-Hard problems. As such, finding optimal solutions for non-trivial instances is generally infeasible. Instead, practical approaches rely on heuristic methods to generate sufficiently good solutions within a reasonable time frame. In this dissertation, we tackle two variants of the OP: The Vacation Planning Problem (VPP) and the Regular Language-Constrained Orienteering Problem with Time Windows (RLC-OPTW).

Ένας τουρίστας που θέλει να εκμεταλλευτεί στο έπακρο τις λίγες μέρες διακοπών σε μία ξένη πόλη. Ένας οδηγός φορτηγού που προσπαθεί να παραδώσει όσο το δυνατόν περισσότερα δέματα μέσα σε μία μέρα. Ένα ελικόπτερο διάσωσης που ψάχνει να βρει επιζώντες μετά από ένα σεισμό. Τρία φαινομενικά διαφορετικά ζητήματα, που όμως έχουν ένα κοινό στοιχείο: Η βέλτιστη λύση περιγράφεται από την ίδια οικογένεια αλγοριθμικών προβλημάτων, παραλλαγών του Προβλήματος Προσανατολισμού (Orienteering Problem (OP)).Το Πρόβλημα Προσανατολισμού είναι ένα αλγοριθμικό πρόβλημα το οποίο περιγράφεται ως εξής: Δοθέντος ενός γράφου όπου οι κόμβοι είναι επισημειωμένοι με ένα κέρδος και ένα χρόνο επίσκεψης/εξυπηρέτησης ενώ οι ακμές είναι επισημειωμένες με ένα χρόνο μετάβασης, ενός αρχικού και ενός τελικού κόμβου, όπως και ενός συνολικού χρονικού περιορισμού για επισκέψεις σε κόμβους, ζητείται η εύρεση ενός απλού μονοπατιού που αρχίζει από τον αρχικό κόμβο και τερματίζει στον τελικό κόμβο, του οποίου ο χρόνος διάσχισης συμμορφώνεται με το συνολικό χρονικό περιορισμό (δηλαδή το άθροισμα των επί μέρους χρόνων επίσκεψης και των χρόνων μετάβασης δεν ξεπερνά τον χρονικό περιορισμό), ενώ μεγιστοποιεί το άθροισμα των κερδών των κόμβων από τους οποίους διέρχεται. Μαζί με τις παραλλαγές του, το Πρόβλημα Προσανατολισμού μοντελοποιεί πληθώρα πραγματικών σεναρίων. Παραδείγματα τέτοιων σεναρίων είναι η επίσκεψη ενός τουρίστα σε μία ξένη πόλη η οποία περιλαμβάνει περιήγηση σε σημεία ενδιαφέροντος, ανταπόκριση σε καταστροφές όπως σεισμοί ή πλημμύρες, ή επίβλεψη περιοχών με συστήματα μη επανδρωμένων αεροσκαφών (ΣμηΕΑ). Αναφορικά με την περίπτωση τουριστών που επισκέπτονται σημεία ενδιαφέροντος, αν υποθέσουμε ότι κάθε κόμβος αντιστοιχεί σε ένα σημείο ενδιαφέροντος και ότι τα κέρδη αποτελούν μία μετρική της ποιότητας των σημείων ενδιαφέροντος, ενώ οι χρόνοι μοντελοποιούν το χρόνο που πρόκειται να παραμείνει ένας τουρίστας σε κάθε σημείο ενδιαφέροντος, μία λύση στο αλγοριθμικό πρόβλημα παρέχει το ημερήσιο πρόγραμμα επισκέψεων του τουρίστα, δηλαδή μία διαδρομή από ένα σημείο προς ένα καταληκτικό σημείο που περιλαμβάνει μία διατεταγμένη λίστα επισκέψεων σε επιλεγμένα σημεία ενδιαφέροντος. Αντίστοιχα, αν φανταστούμε ότι οι κόμβοι αντιστοιχούν σε περιοχές όπου ενδέχεται να υπάρχουν τραυματίες, με το κέρδος να μοντελοποιεί την πιθανότητα να βρεθεί εκεί κάποιος τραυματίας, μία λύση του αντίστοιχου Προβλήματος Προσανατολισμού μπορεί να μας καθοδηγήσει στο να βελτιστοποιήσουμε την ανταπόκριση των δυνάμεων διάσωσης. Φυσικά, στην απλή μορφή του, το Πρόβλημα Προσανατολισμού δεν είναι απόλυτα ρεαλιστικό, αφού δεν λαμβάνει υπόψη παράγοντες όπως π.χ. τις ώρες που ένα σημείο ενδιαφέροντος είναι ανοιχτό, τις προτιμήσεις ενός τουρίστα στο είδος των σημείων ενδιαφέροντος που θέλει να επισκεφτεί, ή, στην περίπτωση της διαχείρισης καταστροφών, το ότι πρέπει να καθοριστούν αρχικά τα σημεία στα οποία θα στηθούν πρόχειρα ιατρεία, από τα οποία θα ξεκινούν οι επιχειρήσεις έρευνας και διάσωσης. Επομένως, απαιτείται να χρησιμοποιηθούν παραλλαγές του Προβλήματος Προσανατολισμού με επιπλέον παραμέτρους και περιορισμούς. Το Πρόβλημα Προσανατολισμού και οι παραλλαγές του είναι NP-Δύσκολα προβλήματα. Ως εκ τούτου, η εύρεση της βέλτιστης λύσης σε μη τετριμμένα σενάρια είναι συνήθως ανέφικτη. Αντίθετα, ρεαλιστικές προσεγγίσεις του προβλήματος επιτυγχάνονται μέσω της χρήσης ευρετικών μεθόδων. Στα πλαίσια αυτής της διατριβής θα ασχοληθούμε με δύο παραλλαγές του Προβλήματος Προσανατολισμού: Το Πρόβλημα Σχεδιασμού Πακέτων Διακοπών και το Πρόβλημα Προσανατολισμού με Περιορισμούς Κατηγοριών Κανονικής Γλώσσας.