A Matheuristic Approach for the Bi-Objective and Multi-Source Team Orienteering Problem with Prioritized Nodes

Abstract

This work proposes a matheuristic approach that combines heuristic techniques with mathematical optimization to address a bi-objective, multi-source team orienteering problem. During the exploration phase, nodes are assigned to depots using a biased-randomized round-robin heuristic, guided by a ranking criterion based on marginal distances. This step aims to generate diverse mappings and identify those that lead to promising solutions under a convex combination of the two objectives: total reward and number of priority nodes visited. In the exploitation phase, an intensive search is applied to a subset of elite mappings, further improving the quality of the solutions. The method produces a Pareto frontier, offering a range of trade-offs between the two objectives. Computational experiments on adapted benchmark instances confirm the method’s ability to generate high-quality or near-optimal solutions, often outperforming exact methods under realistic time constraints.