Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems.

*(English)*Zbl 1374.90395Summary: 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. In order to solve the GCOP to optimality, a polynomial-sized Mixed-Integer Linear Programming (MIP) formulation and an exponential-sized MIP formulation are presented. While the first formulation is tackled by a state-of-the-art branch-and-bound (B&B) algorithm, the second formulation is approached by a specially tailored branch-and-cut (B&C) framework; moreover, the proposed B&C is further enhanced with valid inequalities, a lifting procedure for strengthening inequalities, as well as initialization and primal heuristics. The computational performance of the proposed approaches is assessed in an extensive computational study, using real-world instances that combine crowd-sourced data associated with the Pokémon GO game with street maps of three European cities, as well as instances derived from the TSPLIB testbed. The obtained results show that the B&C approach (i) largely outperforms the B&B algorithm, and that (ii) it is very effective for providing optimal or nearly-optimal solutions within reasonable running times for both sets of instances.

##### MSC:

90C35 | Programming involving graphs or networks |

90C10 | Integer programming |

90C27 | Combinatorial optimization |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |

##### Keywords:

combinatorial optimization; orienteering problem; generalized traveling salesman problem; integer programming; branch-and-cut
PDF
BibTeX
Cite

\textit{E. Álvarez-Miranda} et al., Eur. J. Oper. Res. 265, No. 2, 779--794 (2018; Zbl 1374.90395)

Full Text:
DOI

##### References:

[1] | Angelelli, E.; Archetti, C.; Vindigni, M., The clustered orienteering problem, European Journal of Operational Research, 238, 2, 404-414, (2014) · Zbl 1338.90421 |

[2] | Austria’s First PokeWalk, http://www.pokewalk.at/; 2016. Accessed 16.08.16. |

[3] | Awerbuch, B.; Azar, Y.; Blum, A.; Vempala, S., New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, SIAM Journal on Computing, 28, 1, 254-262, (1998) · Zbl 0916.90256 |

[4] | Balas, E., The prize-collecting traveling salesman problem, Networks, 19, 6, 621-636, (1989) · Zbl 0676.90089 |

[5] | Baldacci, R.; Bartolini, E.; Laporte, G., Some applications of the generalized vehicle routing problem, The Journal of the Operational Research Society, 61, 7, 1072-1077, (2010) · Zbl 1193.90036 |

[6] | Battarra, M.; Erdoğan, G.; Vigo, D., Exact algorithms for the clustered vehicle routing problem, Operations Research, 62, 1, 58-71, (2014) · Zbl 1291.90030 |

[7] | Bektaş, T.; Gouveia, L., Requiem for the Miller-Tucker-zemlin subtour elimination constraints?, European Journal of Operational Research, 236, 3, 820-832, (2014) · Zbl 1304.90168 |

[8] | Bérubé, J.; Gendrau, M.; Potvin, J., A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem, Networks, 54, 56-67, (2009) · Zbl 1203.90129 |

[9] | Bienstock, D.; Goemans, M.; Simchi-Levi, D.; Williamson, D., A note on the prize collecting traveling salesman problem, Mathematical Progamming, 59, 1-3, 413-420, (1993) · Zbl 0793.90089 |

[10] | Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transportation Science, 39, 1, 104-118, (2005) |

[11] | Bustle, Should you catch more than one of the same Pokémon? Why this strategy is a winning one. http://tinyurl.com/j5a27rh. Accessed 22.01.17. |

[12] | Chao, I.; Golden, B.; Wasil, E., Theory and methodology the team orienteering problem, European Journal of Operational Research, 88, 464-474, (1996) · Zbl 0911.90145 |

[13] | Cherkassky, B.; Goldberg, A., On implementing push-relabel method for the maximum flow problem, (Balas, E.; Clausen, J., Proceedings of international conference on integer programming and combinatorial optimization, IPCO IV, LNCS, Vol. 920, (1995), Springer), 157-171 |

[14] | Chimani, M.; Gutwenger, C.; Jünger, M.; Klau, G. W.; Klein, K.; Mutzel, P., The open graph drawing framework (OGDF), (Tamassia, R., Handbook of graph drawing and visualization, (2014), CRC Press) |

[15] | Cook, W. Concorde TSP solver website. http://www.math.uwaterloo.ca/tsp/concorde/index.html. |

[16] | Dell’Amico, M.; Maffioli, F.; Sciomachen, A., A Lagrangian heuristic for the prize collecting travelling salesman problem, Annals of Operations Research, 81, 289-306, (1998) · Zbl 0908.90261 |

[17] | Dell’Amico, M.; Maffioli, F.; Väbrand, P., On prize-collecting tours and the asymmetric travelling salesman problem, International Transactions in Operational Research, 2, 297-308, (1995) · Zbl 0860.90121 |

[18] | Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-zemlin subtour elimination constraints, Operations Research Letters, 10, 1, 27-36, (1991) · Zbl 0723.90081 |

[19] | Feillet, D.; Dejax, P.; Gendreau, M., Travelling salesman problems with profits, Transportation Science, 39, 188-205, (2005) |

[20] | Financial Times, Pokémon GO crosses USD 250 millions in revenues since launch. http://www.ft.com/cms/s/0/2dd63522-5fdf-11e6-ae3f-77baadeb1c93.html; 2016. Accessed 13.08.16. |

[21] | Fischetti, M.; Lodi, A., Local branching, Mathematical Programming, 98, 1-3, 23-47, (2003) · Zbl 1060.90056 |

[22] | Fischetti, M.; Salazar-González, J.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45, 3, 378-394, (1997) · Zbl 0893.90164 |

[23] | Fischetti, M.; Salazar-González, J.; Toth, P., Solving the orienteering problem through branch-and-cut, INFORMS Journal on Computing, 10, 133-148, (1999) · Zbl 1034.90523 |

[24] | Fischetti, M.; Salazar-González, J.; Toth, P., The generalized traveling salesman problem and orienteering problems, (Gutin, G.; Punnen, A., The traveling salesman problem and its variations, Combinatorial optimization, Vol. 12, (2007), Kluwer), 609-662 · Zbl 1113.90352 |

[25] | Fischetti, M.; Toth, P., An additive approach for the optimal solution of the prize-collecting traveling salesman problem, (Golden, B.; Assad, A., Vehicle routing: Methods and studies, (1988), North Holland), 319-343 |

[26] | Gendreau, M.; Laporte, G.; Semet, F., A branch-and-cut algorithm for the undirected selective travelling salesman problem, Networks, 32, 263-273, (1998) · Zbl 1002.90044 |

[27] | Golden, B.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 307-318, (1987) · Zbl 0647.90099 |

[28] | Gunawan, A.; Chuin Lau, H.; Vansteenwegen, P., Orienteering problem: A survey of recent variants, solution approaches and applications, European Journal of Operational Research, 255, 2, 315-332, (2016) · Zbl 1346.90703 |

[29] | Gunawan, A.; Lau, H. C.; Vansteenwegen, P.; Lu, K., Well-tuned algorithms for the team orienteering problem with time windows, Journal of the Operational Research Society, 68, 8, 861-876, (2017) |

[30] | Haklay, M.; Weber, P., Openstreetmap: user-generated street maps, IEEE Pervasive Computing, 7, 4, 12-18, (2008) |

[31] | Helsgaun, K., Solving the equality generalized traveling salesman problem using the lin-kernighan-helsgaun algorithm, Mathematical Programming Computation, 7, 3, 269-287, (2015) · Zbl 1327.90259 |

[32] | Hodgson, J.; Laporte, G.; Semet, F., A covering tour model for planning mobile health care facilities in suhum district (ghana), Journal of Regional Science, 38, (1996) |

[33] | Kharpal, A. Mobile game revenue to pass console, PC for first time. http://www.cnbc.com/2016/04/22/mobile-game-revenue-to-pass-console-pc-for-first-time.html. Accessed 13.08.16. |

[34] | Labbé, M.; Laporte, G., Maximizing user convenience and postal service efficiency in post box location, Belgian Journal of Operations Research, Statistics and Computer Science, 26, 21-35, (1986) |

[35] | Laporte, G.; Asef-Vaziri, A.; Sriskandarajah, C., Some applications of the generalized travelling salesman problem, The Journal of the Operational Research Society, 47, 12, 1461-1467, (1996) · Zbl 0873.90104 |

[36] | Laporte, G.; Mercure, H.; Nobert, Y., Generalized travelling salesman problem through n sets of nodes: the asymmetrical case, Discrete Applied Mathematics, 18, 2, 185-197, (1987) · Zbl 0633.90087 |

[37] | Laporte, G.; Nobert, Y., Generalized travelling salesman problem through n sets of nodes: an integer programming approach, INFOR, 21, 61-75, (1983) · Zbl 0524.90069 |

[38] | Lawler, E., Lenstra, J., Rinnoy Kan, H., & Shmoys, D. (Eds.) (1985). The traveling salesman problem: A guided tour of combinatorial optimization (1st ed.). Wiley. · Zbl 0562.00014 |

[39] | Lonely Planet, Head to Edinburgh if you like to try a Pokémon GO taxi tour. http://www.lonelyplanet.com/news/2016/07/27/try-pokemon-go-taxi-tour/; 2016. Accessed 12.08.16. |

[40] | Miller, C.; Tucker, A.; Zemlin, R., Integer programming formulation of traveling salesman problems, Journal of the ACM, 7, 4, 326-329, (1960) · Zbl 0100.15101 |

[41] | MobiPicker, 10 best augmented reality games like Pokemon GO. http://www.mobipicker.com/games-like-pokemon-go/. Accessed 13.08.16. |

[42] | Ozbaygin, G.; Yaman, H.; Karasan, O., Time constrained maximal covering salesman problem with weighted demands and partial coverage, Computers & Operations Research, 76, 226-237, (2016) · Zbl 1349.90117 |

[43] | PokeMapper. http://www.pokemapper.co; 2016. Accessed 27.07.16. |

[44] | Pokémon GO, Pokémon GO official website, http://www.pokemongo.com/; 2016. Accessed 03.08.16. |

[45] | PokeWalk, http://www.pokewalk.com/; 2016. Accessed 16.08.16. |

[46] | Rosenkrantz, D.; Stearns, R.; Lewis, P., An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing, 6, 3, 563-581, (1977) · Zbl 0364.90104 |

[47] | Schilde, M.; Doerner, K.; Hartl, R.; Kiechle, G., Metaheuristics for the bi-objective orienteering problem, Swarm Intelligence, 3, 179-201, (2009) |

[48] | Srivastava, S.; Kumar, S.; Garg, R.; Sen, P., Generalized travelling salesman problem through n sets of nodes, CORS Journal, 7, 97-101, (1969) · Zbl 0174.51305 |

[49] | Stamen Design, http://www.stamen.com. Accessed 13.08.16. |

[50] | Takahashi, H.; Matsuyama, A., An approximate solution for the Steiner problem in graphs, Mathematica Japonica, 24, 6, 573-577, (1980) · Zbl 0435.05036 |

[51] | Tasgetiren, M., A genetic algorithm with an adaptive penalty function for the orienteering problem, Journal of Economic and Social Research, 4, 2, 1-26, (2001) |

[52] | Tsiligirides, T., Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35, 9, 797-809, (1984) |

[53] | TSPLib, Library of sample instances for the TSP (and related problems). http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/. Accessed 03.08.16. |

[54] | Vansteenwegen, P.; Souffriau, W.; Van Oudheusden, D., The orienteering problem: A survey, European Journal of Operational Research, 209, 1, 1-10, (2011) · Zbl 1205.90253 |

[55] | Wikipedia, Pokémon GO Wikipedia article. https://en.wikipedia.org/wiki/Pok. Accessed 03.08.16. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.