We consider the problem of collaboratively delivering a package from a specified source node s to a designated target node t in an undirected graph G = (V,E), using k mobile agents. Each agent i starts at time 0 at a node p_i and can move along edges subject to two parameters: Its weight w_i, which denotes the rate of energy consumption while travelling, and its velocity v_i, which defines the speed with which agent i can travel. We are interested in operating the agents such that we minimize the total energy consumption ε and the delivery time T (time when the package arrives at t). Specifically, we axe after a schedule of the agents that lexicographically minimizes the tuple (ε,T). We show that this problem can be solved in polynomial time O(k|V|~2 + APSP), where O(APSP) denotes the running time of an all-pair shortest-paths algorithm. This completes previous research which shows that minimizing only ε or only T is polynomial-time solvable [6,7], while minimizing a convex combination of ε and T, or lexicographically minimizing the tuple (T, ε) are both NP-hard [7].
展开▼
机译：我们考虑了使用k个移动代理在无向图G =（V，E）中从指定的源节点s到指定的目标节点t协同交付程序包的问题。每个代理i从时间0开始在节点p_i处，并且可以沿边缘移动，服从两个参数：其权重w_i（表示行进时的能量消耗率）和速度v_i，该速度定义代理i可以行进的速度。我们对操作代理很感兴趣，这样我们可以使总能耗ε和交货时间T（包装到达t的时间）最小化。具体来说，我们按照词典的顺序将那些在字典上使元组（ε，T）最小化的代理人砍掉。我们证明这个问题可以在多项式时间O（k | V |〜2 + APSP）中解决，其中O（APSP）表示全对最短路径算法的运行时间。这完成了先前的研究，表明仅最小化ε或T仅是多项式时间可解的[6,7]，而最小化ε和T的凸组合，或在字典上最小化元组（T，ε）都是NP难的[ 7]。
展开▼
