Distributed constraint optimization for addressing vessel rotation planning problems

作者：Li Shijie^*; Negenborn Rudy R; Lodewijks Gabriel

来源：Engineering Applications of Artificial Intelligence, 2016, 48: 159-172.

DOI：10.1016/j.engappai.2015.11.001

• Multi-agent systems
• Distributed constraint satisfaction
• Vessel rotation planning

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.

• 出版日期2016-2