  We consider the problem of delivering $m$ messages between specified
source-target pairs in a weighted undirected graph, by $k$ mobile agents
initially located at distinct nodes of the graph. Each agent consumes energy
proportional to the distance it travels in the graph and we are interested in
optimizing the total energy consumption for the team of agents. Unlike previous
related work, we consider heterogeneous agents with different rates of energy
consumption (weights~$w_i$). To solve the delivery problem, agents face three
major challenges: \emph{Collaboration} (how to work together on each message),
\emph{Planning} (which route to take) and \emph{Coordination} (how to assign
agents to messages).
  We first show that the delivery problem can be 2-approximated \emph{without}
collaborating and that this is best possible, i.e., we show that the
\emph{benefit of collaboration} is 2 in general. We also show that the benefit
of collaboration for a single message is~$1/\ln 2 \approx 1.44$. Planning turns
out to be \NP-hard to approximate even for a single agent, but can be
2-approximated in polynomial time if agents have unit capacities and do not
collaborate. We further show that coordination is \NP-hard even for agents with
unit capacity, but can be efficiently solved exactly if they have uniform
weights. Finally, we give a polynomial-time
$(4\max\tfrac{w_i}{w_j})$-approximation for message delivery with unit
capacities.
