  The paper presents an ant colony optimization metaheuristic for collaborative
planning. Collaborative planning is used to coordinate individual plans of
self-interested decision makers with private information in order to increase
the overall benefit of the coalition. The method consists of a new search graph
based on encoded solutions. Distributed and private information is integrated
via voting mechanisms and via a simple but effective collaborative local search
procedure. The approach is applied to a distributed variant of the multi-level
lot-sizing problem and evaluated by means of 352 benchmark instances from the
literature. The proposed approach clearly outperforms existing approaches on
the sets of medium and large sized instances. While the best method in the
literature so far achieves an average deviation from the best known
non-distributed solutions of 46 percent for the set of the largest instances,
for example, the presented approach reduces the average deviation to only 5
percent.
