Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 76-82 |
| Number of pages | 7 |
| Journal | Computers and Operations Research |
| Volume | 41 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Jan 2014 |
Funding
This work was supported by PROMEP/103.5/13/6644 and UANL-PAICYT 2011-2012 , and by the Canadian Natural Sciences and Engineering Research Council under Grants RGPIN41978 and 39682-10 . This support is gratefully acknowledged. Thanks are due to a referee who provided valuable comments.
Keywords
- Adaptive large neighborhood search
- Node routing
- Operations planning
- Tasks scheduling
- Team orienteering problem
ASJC Scopus subject areas
- General Computer Science
- Modelling and Simulation
- Management Science and Operations Research