Back to Search
Start Over
Orienteering Problem with Functional Profits for multi-source dynamic path construction
- Source :
- PLoS ONE, PLoS ONE, Vol 14, Iss 4, p e0213777 (2019)
- Publication Year :
- 2019
- Publisher :
- Public Library of Science, 2019.
-
Abstract
- 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. In this paper, we present an extension of classic OP-Orienteering Problem with Functional Profits (OPFP), where the score of a specific point depends on its characteristics, position in the route, and other points in the route. For solving OPFP, we developed an open-source framework for solving orienteering problems, which utilizes four core components of OP in its modular architecture. 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.
- Subjects :
- Linear programming
Computer science
0211 other engineering and technologies
Social Sciences
Orienteering
02 engineering and technology
Russia
Social Networking
Mathematical and Statistical Techniques
Open Science
Sociology
0202 electrical engineering, electronic engineering, information engineering
Psychology
Data Mining
Greedy algorithm
Problem Solving
021103 operations research
Multidisciplinary
Data Processing
Applied Mathematics
Simulation and Modeling
Programming, Linear
Social Networks
Physical Sciences
Medicine
020201 artificial intelligence & image processing
Information Technology
Algorithms
Network Analysis
Open Source Software
Research Article
Optimization
Mathematical optimization
Computer and Information Sciences
Science Policy
Science
Research and Analysis Methods
Set (abstract data type)
Computer Software
Humans
Computer Simulation
Linear Programming
Cognitive Psychology
Biology and Life Sciences
Path (graph theory)
Cognitive Science
Programming Languages
Routing (electronic design automation)
Mathematical Functions
Multi-source
Mathematics
Software
Neuroscience
Subjects
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 14
- Issue :
- 4
- Database :
- OpenAIRE
- Journal :
- PLoS ONE
- Accession number :
- edsair.doi.dedup.....6c7d3ba7d88f95f52395f276dbf05482