An efficient algorithm for the fast delivery problem

DOI10.1007/978-3-030-25027-0_12MaRDI QIDQ2291419zbMATH OpenOpenAlexFDO

Authors Iago A. Carvalho, Kleitos Papadopoulos, Thomas Erlebach

Publication date 30 January 2020

Full work available at URL https://arxiv.org/abs/1904.09142

zbMATH Keywords

Dijkstra's algorithmmobile agentspolynomial-time algorithmtime-dependent shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Artificial intelligence for robotics (68T40) Transportation, logistics and supply chain management (90B06)

Abstract: We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in a source node s, to a destination node y. The delivery is achieved by the collective effort of the autonomous mobile agents, which can carry and exchange the package among them. The objective is to compute a delivery schedule that minimizes the delivery time of the package. In this paper, we propose an O(kn log n + km) time algorithm for this problem. This improves the previous state-of-the-art O(k^2 m + k n^2 + APSP) time algorithm for this problem, where APSP stands for the running-time of an algorithm for the All-Pairs Shortest Paths problem.

Recommendations

• On the fast delivery problem with one or two packages
• Energy-efficient fast delivery by mobile agents
• Collective fast delivery by energy-efficient agents
• scientific article; zbMATH DE number 6862102
• Collaborative delivery on a fixed path with homogeneous energy-constrained agents

Cited in

(7)

• Energy-efficient fast delivery by mobile agents
• On the fast delivery problem with one or two packages
• Collective fast delivery by energy-efficient agents
• An algorithm for optimal shipments with given frequencies
• New approximation algorithms for the heterogeneous weighted delivery problem
• New approximation algorithms for the heterogeneous weighted delivery problem
• Message Delivery in the Plane by Robots with Different Speeds

This page was built for publication: An efficient algorithm for the fast delivery problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291419)