Publications       Rudy Negenborn
Associate Professor
Team & Themes

Title:Distributed constraint optimization methods for addressing vessel rotation planning problems
Authors:S. Li, R.R. Negenborn, G. Lodewijks

Journal:Engineering Applications of Artificial Intelligence

Abstract:Distributed constraint optimization problem (DCOP) is a description of constraint optimization problem where variables and constraints are distributed among a group of agents, and where each agent can only interact with agents that share a common constraints. However, there are only few attempts to address real world scenarios using this formalism mainly because of the complexity associated with those algorithms. In this paper, we propose a DCOP approach to solve vessel rotation planning problem (VRPP), which concerns deciding the optimal sequence of vessel visits to different terminals in a large seaport. As solving DCOP problems is NP-hard, increasing the number of variables increases the complexity of the problem exponentially, we propose two ways to reduce the computational complexity both on agent structure level and on DCOP structure level. In addition, we compare four different algorithms for DCOP, aiming at studying how they perform in VRPP of increasing sizes and also how the two different agent structure, as well as two different DCOP structure perform. We measure the size and quantity of exchanged messages, simulated time, and also quality of solutions which is related to the particular domain we use. This study can shed light in the issues of how the algorithms perform to applied to problems other than those reported in literature.

Reference:S. Li, R.R. Negenborn, G. Lodewijks. Distributed constraint optimization methods for addressing vessel rotation planning problems. Engineering Applications of Artificial Intelligence, vol. 48, pp. 159-172, February 2016.
Request:A copy of this publication.

Send me any comments.