Framework for Orienteering Problem Solving (FOPS)
Published:
Orienteering problem (OP) is a routing problem, where the aim is to generate a path through set of nodes, which would maximize total score and would not exceed the budget. Fully-written in Go programming language our framework can be extended for solving different types of tasks with different algorithms; this was demonstrated by implementation of two popular algorithms for OP solving — Ant Colony Optimization and Recursive Greedy Algorithm. Computational efficiency of the framework was shown through solving four well-known OP types: classic Orienteering Problem (OP), Orienteering Problem with Compulsory Vertices (OPCV), Orienteering Problem with Time Windows (OPTW), and Time Dependent Orienteering Problem (TDOP) along with OPFP. Experiments were conducted on a large multi-source dataset for Saint Petersburg, Russia, containing data from Instagram, TripAdvisor, Foursquare and official touristic website. Our framework is able to construct touristic paths for different OP types within few seconds using dataset with thousands of points of interest.
Press coverage:
- The Guardian Want a more ‘authentic’ tourist experience? There’s an app for that - https://www.theguardian.com/cities/2017/sep/15/authentic-tourist-app-instagram-holiday (15.09.2017)
- Le Monde Des algorithmes pour guider les fans de foot en Russie - https://www.lemonde.fr/pixels/article/2018/07/06/des-algorithmes-pour-guider-les-fans-de-foot-en-russie_5327426_4408996.html (06.07.2018)
- Over a dozen mentions in Russian media (2017-2018)