Biography
Prof. Theodore Tsiligiridis
Prof. Theodore Tsiligiridis
Agricultural University of Athens, Greece
Title: Algorithmic approaches for Orienteering Applications
Abstract: 

Orienteering Problem (OP), also known in the literature as Selective Traveling Salesman Problem (sTSP) and Maximum Collection Problem (MCP) is an NP-hard routing problem, where the aim is to develop a route through a given nodes or Points-of-Interest (PoIs), which would satisfy given conditions and constraints. In the classic OP each PoI has a prize or score and the goal is to maximize the total score of PoIs visited, while keeping the total length of the route below a maximum length, say Tmax. One of the PoIs is assumed to be the origin and if the model selects it, the route is finished. Infeasible solutions are prevented by allowing to visit a PoI if after visiting it a return to the origin is still possible within the Tmax constraint. OP can be considered as a special case of the well-known TSP problem, but without enough time to visit all the cities (nodes). PoIs may belong to many application domains, such as touristic attraction/trip design places, mobile-crowdsourcing tasks, data collection missions for Unmanned Area Vehicles (UAVs), home fuel delivery, safety places in emergency situations. Many interesting variants have been introduced, such as the Generalized OP (GOP), the Stochastic OP (SOP), the Arc OP (AOP), the Multi-agent (MOP) or the CLUstered (CluOP), among others. In addition, diversity of possible applications led to a wide range of OP variants the classical one being the Team OP (TOP), which constructs multiple routes from the origin/end, the OP with Time Windows (OPTW), which construct routes according to the availability/unavailability of PoIs at specific time intervals, and the Time Dependent OP (TDOP) in which the travel time between two locations depends on the departure time at the first location. 

Exact algorithmic solutions for the OP are usually based on branch and bound or dynamic programming techniques and are of limited use, as they can only solve small problem instances. Consequently, approximation algorithms and heuristics are used. Most of them are employing a two-step approach of partial path construction and improvement. Meta-heuristics, such as genetic algorithms, neural networks, ant colony optimization, tabu search, as well as variable neighborhood search, have been tested as well. Current studies of OPs involve complex constraints, whereas the scores of the PoIs remain fixed. In Multi-Objective OP (MOOP) PoIs are combined to classes or categories, as for example landmarks, shopping, culture, leisure, etc., and each PoI provides different benefits for each class. In this case focus is placed on tours in order to find all Pareto efficient ones and let the tourist select the one to follow. Reward dependence on length of staying in some place was introduced in the OP with variable profits. 

However, the classical OP/TOP as well as its variants is still of great interest, particularly of modeling tourist trip planning and logistics applications. Existing touristic cases assume the scores of the PoIs to be independent from each other. In addition, to optimize results, the travel recommendation system needs to consider various attributes of tourist interest when a tourist chooses a place to visit. For this reason, social sensing, by means of sentiment analysis, for automatically customizing the solutions to OP/TOP enhances the user satisfaction in a tourist trip planning context and opens a new era towards to big data, geospatial databases, and personalized tourism recommendations. Incorporating exact or heuristic OP/TOP algorithms derived from previous studies that had been improved after embedding tourist preferences, such as touring time, tour days, budget, types of PoIs to visit, types of tour packages, etc., is now of a great challenge.