Attractive orienteering problem with proximity and timing interactions

Nickolas K. Freeman, Burcu B. Keskin and İbrahim Çapar

European Journal of Operational Research, 2018, vol. 266, issue 1, 354-370

Abstract: We consider an attractive orienteering problem for planning entertainment events. Specifically, we seek to determine a profit-maximizing tour and event plan among a set of candidate locations over a fixed time horizon. The revenue from a particular event depends on the total attendance. We approximate the total attendance to events using a time-varying attraction measure that accounts for the event location and time as well as events nearby in location and time. The influence of events nearby in location and time is known as the performance shadow. The profit calculation accounts for costs associated with travel to locations and holding events. We formulate a mixed-integer programming model that considers several practical constraints. However, the computational complexity of the problem forces us to develop local search and scatter search based heuristic methods to solve larger instances. We compare the performance of the exact formulation and heuristics using test cases based on regional and national tours within the continental U.S and a real life scenario based on U2’s 2017 Joshua Tree tour. A scatter search-based heuristic outperforms all other methods in the experiment. This heuristic is able to find optimal solutions for smaller instances that are solved optimally by a commercial solver. For larger instances, the heuristic outperforms the profit of the best feasible solution returned by the commercial solver by 32.0%. Finally, for the real life comparison, the scatter search based heuristic improves the profit associated with the CPLEX solution and the actual tour by 52.9% and 16.5%, respectively.

Keywords: OR in entertainment; Heuristics; Orienteering problem; Attractive salesman problem; Mathematical modeling (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717308469
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:266:y:2018:i:1:p:354-370

DOI: 10.1016/j.ejor.2017.09.025

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 ().