A two-stage approach to the Multiple-Agent Orienteering Problem with Stochastic Weight and Capacity Constraints

¹ School of Management, Hangzhou Dianzi University, 310018 Zhejiang, P.R. China
² Experimental Center of Data Science and Intelligent Decision, Hangzhou Dianzi University, Hangzhou 310018, P.R. China
³ Zhejiang Lab, 310018 Zhejiang, P.R. China

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 6 February 2024
Accepted: 10 December 2025

Abstract

The Multiple-Agent Orienteering Problem with Capacity Constraints (MAOPCC) is one kind of routing problem that finds applications in both tourism and transportation industries. The MAOPCC aims to find feasible routes with maximum profit while considering time constraints. In this paper, we extend the MAOPCC to the Multiple-Agent Orienteering Problem with Stochastic Weight and Capacity Constraints (MAOPCCSW) to address the uncertainty in practical situations. The problem is solved using a two-stage stochastic model with recourse and hard time constraints. The model considers the effect of stochastic weights on the expected total profit value during the modeling stage. The two-stage model is solved with Sample Average Approximation (SAA), which converges to the optimal solution with a high computational cost. Therefore, to solve large instances, a heuristic method is developed, which utilizes the problem structure of the MAOPCCSW and explicitly considers relevant uncertainties. In our experimental analysis, we demonstrate the effectiveness of the MAOPCCSW method, which outperforms both the standard deterministic method and the deterministic method amended with real-time information.