The Vehicle Routing Problem (VRP) has been extensively studied
over the last twenty years, because it is an abstraction of many
real-life logistics problems. In its multiple-depot variant
(MDVRP), the routes of vehicles located at various depots must be
optimized to serve a number of customers. In this paper, we
investigate how to protect the privacy of delivery companies, when
each depot is owned by a different company with a limited view of
the overall problem. Companies then need to exchange messages with
each other to coordinate the assignment of customers to depots. We
show how Distributed Constraint Optimization (DCOP) can be used to
solve the assignment problem using distributed computation, and we
study the guarantees that can be provided with respect to the
protection of each company’s knowledge about the problem.