Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems

Eduardo Álvarez-Miranda, Martin Luipersbeck and Markus Sinnl

European Journal of Operational Research, 2018, vol. 265, issue 2, 779-794

Abstract: In this paper, a new routing problem, referred to as the Generalized Clustered Orienteering Problem (GCOP), is studied. The problem is motivated by the mobile phone game Pokémon GO, an augmented reality game for mobile devices holding a record-breaking reception: within the first month of its release, more than 100 million users have installed the game on their devices. The game’s immense popularity has spawned several side businesses, including taxi-tours visiting locations where the game can be played, as well as companies offering to play the game for users during times when they cannot. Further applications arise in typical operative transportation problems that seek for tours that are both time-effective and profitable. Besides the typical traveling distances, in the GCOP we also have prizes or revenues associated with the nodes. Additionally, we are given with K node subsets (clusters) and a budget B for the length of the tour. The optimization task is to find a tour that maximizes the total collected prize while ensuring that (i) at least one node of each cluster is visited, and (ii) the total distance of the tour does not exceed the budget B.

Keywords: Combinatorial optimization; Orienteering Problem; Generalized traveling salesman problem; Integer programming; Branch-and-cut (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717307245
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:265:y:2018:i:2:p:779-794

DOI: 10.1016/j.ejor.2017.08.012

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().