University of West Attica
Algorithmic solutions to orienteering problems and applications
Abstract
dc:descriptionA 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).
Degree
thesis:*- Grantor dc:publisher
- University of West Attica
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Vathis, Nikolaos
- Βάθης, Νικόλαος
Subjects
dc:subject × 16- Πρόβλημα προσανατολισμού
- Πρόβλημα σχεδιασμού πακέτων διακοπών
- Πρόβλημα προσανατολισμού με περιορισμούς κατηγοριών κανονικής γλώσσας
- Συνδυαστική βελτιστοποίηση
- Orienteering problem
- Regular language-constrained orienteering problem
- Vacation planning problem
- COMBINATORIAL OPTIMIZATION
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών
- Λογισμικό (software)
- Computer and Information Sciences
- Natural Sciences
- Computer Science
- Software
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/58948