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

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 num...

Full description

Saved in:
Bibliographic Details
Main Authors: WANG, Wenjie, LAU, Hoong Chuin, CHENG, Shih-Fen
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2018
Subjects:
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-5021
record_format dspace
spelling sg-smu-ink.sis_research-50212018-12-07T05:31:36Z Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints WANG, Wenjie LAU, Hoong Chuin CHENG, Shih-Fen 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. 2018-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4019 info:doi/10.1109/SSCI.2017.8285329 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 http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Databases and Information Systems Software Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Databases and Information Systems
Software Engineering
spellingShingle Databases and Information Systems
Software Engineering
WANG, Wenjie
LAU, Hoong Chuin
CHENG, Shih-Fen
Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
description 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.
format text
author WANG, Wenjie
LAU, Hoong Chuin
CHENG, Shih-Fen
author_facet WANG, Wenjie
LAU, Hoong Chuin
CHENG, Shih-Fen
author_sort WANG, Wenjie
title Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
title_short Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
title_full Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
title_fullStr Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
title_full_unstemmed Exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
title_sort exact and heuristic approaches for the multi-agent orienteering problem with capacity constraints
publisher Institutional Knowledge at Singapore Management University
publishDate 2018
url 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
_version_ 1770574132599062528