Distributed constraint optimization for addressing vessel rotation planning problems

A 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 constraints. Even though DCOPs have been studied since the 1990s, there are only a few attempts to address real world problems using this formalism, mainly because of the complexity of the solution algorithms. In this paper, we compare 4 state-of-the-art DCOP approaches to solve the vessel rotation planning problem (VRPP), which concerns deciding on the optimal sequence of vessel visits to different terminals in a large seaport. We hereby also consider two agent structures: a single layer and a multi-layer structure. For each of the structures, we compare the four different algorithms for solving DCOPs, aiming at studying how the algorithms perform in VRPPs of increasing sizes. We assess the methods based on the size and quantity of messages exchanged, computation time, and quality of solutions.