Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints

• Main Authors: WANG, Wenjie, LAU, Hoong Chuin, CHENG, Shih-Fen
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Databases and Information Systems; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4019; https://ink.library.smu.edu.sg/context/sis_research/article/5021/viewcontent/Exact_and_heuristic_approaches_for_the_multi_agent_orienteering_problem_with_capacity_constraints.pdf
• Institution: Singapore Management University

This paper introduces and addresses a new multiagent variant of the orienteering problem (OP), namely the multi-agent orienteering problem with capacity constraints (MAOPCC). Different from the existing variants of OP, MAOPCC allows a group of visitors to concurrently visit a node but limits the number of visitors simultaneously being served at each node. In this work, we solve MAOPCC in a centralized manner and optimize the total collected rewards of all agents. A branch and bound algorithm is first proposed to find an optimal MAOPCC solution. Since finding an optimal solution for MAOPCC can become intractable as the number of vertices and agents increases, a computationally efficient sequential algorithm that sacrifices the solution quality is then proposed. Finally, a probabilistic iterated local search algorithm is developed to find a sufficiently good solution in a reasonable time. Our experimental results show that the latter strikes a good tradeoff between the solution quality and the computational time incurred.