The multi-district team orienteering problem

This paper introduces the multi-district team orienteering problem. In this problem, one must schedule a set of mandatory and optional tasks located in several districts, within a planning horizon. The total available time determined by the length of the planning horizon must be distributed among the districts. All mandatory tasks within each district must be performed, while the other tasks can be performed if time allows. A positive profit or score is collected whenever an optional task is performed. Additionally, some incompatibility constraints between tasks are taken into account. The objective is to determine a schedule for a set of tasks to be performed daily within each district, while maximizing the total collected profit. A mixed integer formulation and an adaptive large neighborhood search heuristic are proposed for this problem. The performance of the proposed algorithm is assessed over a large set of randomly generated instances. Computational results confirm the efficiency of the algorithm.