Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

1-2018

Abstract

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.

Discipline

Databases and Information Systems | Software Engineering

Research Areas

Data Science and Engineering

Publication

Proceedings of 2017 IEEE Symposium Series on Computational Intelligence, Hilton Hawaiian Village Resort Honolulu, United States, November 27 - December 1

First Page

1

Last Page

7

ISBN

9781538627259

Identifier

10.1109/SSCI.2017.8285329

Publisher

Institute of Electrical and Electronics Engineers Inc.

City or Country

Honolulu, HI

Additional URL

https://doi.org/10.1109/SSCI.2017.8285329

Download

Share

COinS