Research Article: Orienteering Problem with Functional Profits for multi-source dynamic path construction

Date Published: April 2, 2019

Publisher: Public Library of Science

Author(s): Ksenia D. Mukhina, Alexander A. Visheratin, Denis Nasonov, Vincent Yu.

http://doi.org/10.1371/journal.pone.0213777

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.

Partial Text

Orienteering problem (OP) is a class of routing problems, where the ultimate goal is to create a route through a given points of interest (PoIs), which would satisfy given conditions and constraints. Depending on domain PoIs can be touristic attraction places [1], crowdsourcing tasks [2] or safety places in case of emergency situations [3]. Diversity of possible applications led to a great variety of OP tasks from classic OP [4] and its generalization [5] to exotic ones dedicated to politician movements [6] or band tour planning [7]. But existing problems consider score of a certain place to be independent from other points in a route and from points of a search space, whereas in real life people when choosing place to visit usually take these aspects into account. For instance, after visiting several museums in a row user would likely prefer to have a break rather than to visit another museum, despite his or her personal interest in museums. Users also would choose next location in their route not from all locations in the city, but from those, which are more or less co-directional to a final location. To address this kind of scenarios we propose Orienteering Problem with Functional Profits (OPFP)—extension of classic Orienteering Problem, where node profit depends on a node position in the itinerary, other points in itinerary, and points in the dynamically changing search space.

Problem of path construction with weighted nodes was introduced in work [4] as Orienteering Problem (OP). OP has various extensions [16] regarding different aspects of route construction. Team Orienteering Problem (TOP) involves constructing of multiple routes from start to terminal node [12]. In Orienteering Problem with Time Windows (OPTW) [17] availability of certain location is taken into consideration. Some places could be unavailable at certain time intervals. In Time Dependent Orienteering Problem (TDOP) [18] time required for visiting the node is considered for edge cost calculation and time for transition from one node to another depends on start time. A set of mandatory nodes, which are must-see, is included in Orienteering Problem with Compulsory Vertices (OPCV) [19]. Existing touristic paths can be successfully used for construction of new itineraries [20].

Let us assume that G = < V, E > is a complete graph, where V = {v1…vN} is a set of locations with associated profit vector si ≥ 0, where i = 1, 2, …N, and E is a list of links between them with a cost vector bij. The aim of solving OPFP is to find the most profitable and convenient way to reach terminate node from the start node whose total cost does not exceed a budget vector B. Formally, the resulting route is represented as an ordered sequence of vertices C*={v1,…,vui,…,vN} where ui is position of vertex vi in final route and xij represent the fact that route includes an edge eij. Thus, OPFP can be formulated as an integer linear programming problem similar to other types of OPs [34]:
max∑i=1N-1f(si,Cui-1*)·∑j=2Nxij,(1)
subject to
∑i=1N-1xiN=∑j=2Nx1j=1(2)∑i=1N-1xir=∑j=2Nxrj≤1,∀r=2,…,N-1,(3)∑i=1N-1∑j=2Nbijxij≤B,(4)1≤ui≤N,∀i=1,2,…N,(5)ui-uj+1≤(N-1)(1-xij),∀i,j=2,…N,(6)xij={1,iftransitionfromitojisintheroute0,otherwise;,∀i,j=1,…,N,(7)

The majority of problems related to orienteering can be defined using three core components—set of PoIs, constraints and scoring function. The fourth core component—algorithm—utilizes other components in order to generate the best solution for a specific problem. We have developed a programming framework to make possible uniform and consistent development of algorithms for a wide range of orienteering problems—FOPS (Framework for Orienteering Problems Solving). Representations of four widespread OP types in terms of core components are available on GitHub (https://github.com/mukhinaks/fops). Main features of FOPS include:

To solve OPFP on a city scale, we required large and high-quality dataset containing data from multiple sources. With spreading of the Internet all around the world, social media now play a major role in tourism area from marketing aspects to information search and decision making [39]. Foursquare and Instagram are widely used for urban studies and for studying tourists and city residents behavior in particular [40]. Combination of multiple sources, Flickr and Wikipedia, was used in TripBuilder [41]. However, Wikipedia provides information only about a number of relevant places and limited by historical and well-known locations. But during city development buildings could be destroyed or organization may move to another place, and these factors lead to potentially outdated itineraries. Touristic resources such as TripAdvisor, Yahoo Travel or Lonely Planet [32] are used for itinerary construction as a filter for larger spatial datasets, like Flickr and Instagram. However, this results in a significant reduction of resulting datasets, and some interesting and popular places are lost due to their absence in city guides. That is why when creating combined dataset from diverse data sources it is very important to augment data instead of truncating it.

In this paper, we present an extension of classic OP—Orienteering Problem with Functional Profits (OPFP), where score of specific point depends on its characteristics, position in the route, and other points in the itinerary. For solving OPFP, we developed an open-source framework written in Go programming language (version 1.8.3) for solving orienteering problems, which utilizes four core components of OP (a set of points of interest, constraints, scoring function and solving algorithm) in its modular architecture. The modularity of our framework allows combining all components easily. It was demonstrated in our experiments through solving OP, OPCV, OPTW, TDOP along with OPFP. Experiments were conducted on a large multi-source dataset of Saint Petersburg, Russia, containing data from Instagram, TripAdvisor, Foursquare and official touristic website. Workstation was equipped by Intel(R) Core i7-3930K @ 3.20GHz processor, 32 GB RAM, Windows 7 SP1. Our framework is able to construct touristic paths for different OP types in less than one second for 100 points dataset, which outperforms known solutions.

 

Source:

http://doi.org/10.1371/journal.pone.0213777

 

Leave a Reply

Your email address will not be published.