In many situations, agents optimize their own operations locally but their local problems are interdependent. We consider the problem of coordinating these local problems to find a globally optimal solution. We model the coordination problem as a Distributed Constraint Optimization Problem that can take advantage of the locality of interactions, and then show how incremental elicitation and solving techniques can minimize the effort required. We illustrate the approach on an example of coordinating logistics service providers, for example couriers in a delivery company.