  We consider k mobile agents initially located at distinct nodes of an
undirected graph (on n nodes, with edge lengths) that have to deliver a single
item from a given source node s to a given target node t. The agents can move
along the edges of the graph, starting at time 0 with respect to the following:
Each agent i has a weight w_i that defines the rate of energy consumption while
travelling a distance in the graph, and a velocity v_i with which it can move.
  We are interested in schedules (operating the k agents) that result in a
small delivery time T (time when the package arrives at t), and small total
energy consumption E. Concretely, we ask for a schedule that: either (i)
Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast
delivery), or (iii) Minimizes epsilon*T + (1-epsilon)*E, for a given epsilon,
0<epsilon<1.
  We show that (i) is solvable in polynomial time, and show that (ii) is
polynomial-time solvable for uniform velocities and solvable in time O(n + k
log k) for arbitrary velocities on paths, but in general is NP-hard even on
planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We
show that there is a 3-approximation algorithm for (iii) using a single agent.
