Parameterized Algorithms for the Drone Delivery Problem

Instead of merely proving NP-hardness, we establish a much stronger result: no polynomial-time algorithm with any polynomially encodable approximation ratio exists, unless P=NP. See 1 In the following we only present a high-level overview, the complete proof can be found in the full version of the paper. To prove the inapproximability, we reduce from the PartitionInto-$k$ problem.

Note that in this subsection $k$ refers to the number of subsets (and not the agent set). The NP-hardness of PartitionInto-$k$ follows immediately from the hardness of Partition with $k=2$; however for the proof of Theorem 1 we require the stronger result that PartitionInto-$k$ is also NP-hard in the strong sense, which is included in the full version.

This is done by a straightforward reduction from 3-Partition, which was originally shown to be strongly NP-hard by Garey and Johnson [12] and for distinct integers by Hullet et al. [14]. It is particularly important that $k$ is part of the input; for a fixed $k$, the problem admits an FPTAS, as shown by Sahni [20].

To show that no approximation algorithm $𝒜$ with a polynomially encodable approximation ratio $a(n)$ can exist (unless P=NP), we demonstrate that such an algorithm could be used to solve PartitionInto-$k$ in polynomial time. We do so by constructing a DDT instance $I^{\prime }$ from a given PartitionInto-$k$ instance $I$ such that:

$I$ is a “yes”-instance of PartitionInto-$k$ if and only if $c_{𝒜}(I^{\prime })\le d\cdot a(n)$, where $c_{𝒜}(I^{\prime })$ is the delivery time of the schedule produced by $𝒜$ for the instance $I^{\prime }$ and the value $d$ is determined by the construction.

Let $I=(p_1,\mathrm{\dots },p_n)$ be an arbitrary PartitionInto-$k$ instance with distinct integers. We assume that the numbers are sorted in decreasing order, i.e., $p_1>\mathrm{\cdots }>p_n$. We denote the total sum of all elements by $P$.

For each object $p_i$ we create $k$ drones – one for each partition set. We refer to these drones as element agents and denote them by $e_{i,j}$, where $e_{i,j}$ is associated with object $p_i$ and partition set $j\in \{1,\mathrm{\dots },k\}$. The speed of a drone $e_{i,j}$ is denoted by $v_j$, meaning that all drones associated with the same partition set (i.e., with the same index $j$) share the same speed. We place several gadgets along the line and aim to ensure that each element agent can only be placed and transport the package at specific designated positions and not at arbitrary locations along the path. To achieve this, we employ two key mechanisms: first, we restrict the movement areas of the agents such that they are clearly unable to assist outside their interval. Second, we choose the ratios between the speeds $v_1,\mathrm{\dots },v_k$ to be sufficiently large, allowing us to define long intervals that certain agents cannot traverse in their entirety without exceeding the time bound $d\cdot a(n)$.

For each of the $k$ partition sets, we create a partition gadget, that enforces that the sum of the weights $p_i$ associated with the element agents $e_{i,j}$ placed at that gadget is at least $\frac{P}{k}$. Placing an element agent $e_{i,j}$ at a partition gadget can thus be interpreted as assigning $p_i$ to the corresponding partition set.

Additionally, for each object $p_i$ we construct a gadget $O_i$ – called an object gadget – that ensures each object is assigned to at most one partition set. This is done by requiring that exactly $k-1$ of the agents $e_{i,1},\mathrm{\dots },e_{i,k}$ must be present at the object gadget, resulting in at most one of them being placed at a partition gadget. As a result, we can ensure that each partition gadget ends up with a total weight of exactly $\frac{P}{k}$, if such a partition exists. If not, the construction forces a very large delivery time, causing the bound $d\cdot a(n)$ to be exceeded.

An example layout of the gadgets, ordered as $P_1,\mathrm{\dots },P_k,O_n,\mathrm{\dots },O_1$, is shown in Figure 3. Consecutive gadgets are placed sufficiently far apart so that only specially designated fast transition agents can traverse the gaps, ensuring that each element agent can contribute to at most one gadget.

We now design an FPT algorithm for DDT-SP on path graphs. As a parameter for our approach, we use the maximum overlap – the thickness $\sigma :={\max }_{u\in V(G)}|B_u|$, i.e., the largest number of agents covering any single vertex.

Since each agent corresponds to an interval on the line, the intersection graph of agents is an interval graph. In such graphs, agents covering a common point form a clique, and each maximal clique corresponds to some point on the line [15]. As interval graphs are chordal, their treewidth equals the size of the largest clique minus one [19], which in our case implies $\text{w}=\sigma -1$. Thus, the treewidth of the intersection graph and the thickness parameter are equivalent. This structural property allows for a dynamic programming algorithm over a tree decomposition of the intersection graph. We define the event points as the start and end positions of all agent intervals, i.e., the multiset $\{s_a,f_a\mid a\in A\}$. We sort these events from left to right along the path (), resolving ties by placing start points before end points; the order among start points or among end points is chosen arbitrarily. In an optimal schedule, handovers occur only at these event points – specifically at $s_{a^{\prime }}$ or $f_a$ for a handover from $a$ to $a^{\prime }$ – since otherwise extending the faster agent’s segment would yield a strictly better or equally good schedule.

We interpret each event $e_i$ as a node in a tree decomposition that forms a path, see Fig. 2. We can consider the set of agents covering $e_i$, $Z_{e_i}$ as the bag at position $i$. If $e_i$ is the start vertex of some agent $a$, we say that $a$ is introduced to the bag, and if $e_i$ is the end point of some agent $a$, it is forgotten. We define a dynamic program over the path decomposition induced by this event sequence. At each $e_i$, we maintain:

• $\mathrm{■}$

  the bag $Z_{e_i}$ of agents covering $e_i$,

• $\mathrm{■}$

  a subset $S\subseteq Z_{e_i}$ of agents already used,

• $\mathrm{■}$

  a current carrier $a\in Z_{e_i}$ responsible for transporting the package from $e_i$ to $e_{i+1}$.

Since at most $\sigma$ agents cover any point, we have $|Z_{e_i}|\le \sigma$, and the number of subsets $S\subseteq Z_{e_i}$ (representing already-used agents) is bounded by $2^{\sigma }$. The dynamic programming table stores the minimum delivery time to reach $e_i$ under the assumption that agent $a$ will deliver it to $e_{i+1}$ and the current set of already used agents is $S$, denoted by $D[e_i,S,a]$. We assume no agent starts at $t$ or ends at $s$, as those movement intervals can be cut off without affecting the solution. Furthermore, at most one handover occurs per event point, and it happens only if $e_i=s_{a^{\prime }}$ or $e_i=f_a$, as argued before. While we only store delivery times in the DP table, the full delivery sequence can be reconstructed via backtracking.

In the following we always assume for some DP entry $D[e_i,S,a]$ that $a\in S$, otherwise the entry is defined as $\mathrm{\infty }$. Assume we have already computed all possible entries $D[e_{i-1},S\subseteq Z_{e_{i-1}},a\in Z_{e_{i-1}}]$ correctly, and now wish to compute $D[e_i,S\subseteq Z_{e_i},a\in Z_{e_i}]$.

The formal correctness of the following lemmas appears in the full version of the paper.

Given any DDT instance $(G,(s,t),A)$, we now create an instance $(G^{\prime },(s^{\prime },t^{\prime }),A^{\prime })$ that has equivalent schedules, but its intersection graph $G_I^{\prime }$ is simple and therefore any pair of agents overlap in at most one vertex. Each agent $a\in A$ originally moves on a (possibly overlapping) subgraph $G_a$ of $G$. To guarantee that no pair of agents share multiple vertices, we create a disjoint copy of every $G_a$ and relabel each vertex $u$ as $(u,a)$. The $k$ original agents are then confined to their respective copies $G_a^{\prime }$. Whenever two subgraphs $G_a$ and $G_b$ share a vertex $u$ in $G$, the transformed graph $G^{\prime }$ now contains two distinct copies, i.e., $(u,a)$ and $(u,b)$. We connect these copies of the same vertex by edges (of length 0) and introduce a dedicated auxiliary agent $h_u$ with speed $1$ and movement area restricted to the newly added edges of length 0 between the copies. Thus, the package can be transferred instantly between any two copies of the same original vertex, while original agents share no common vertex. The resulting instance preserves all feasible schedules with the same delivery time as the original one but it also satisfies the new constraint that any pair of agents shares at most one vertex, as any pair of original agents $a^{\prime },b^{\prime }$ does not share a common vertex in $G^{\prime }$, neither does any pair of helping agents $h_u,h_{u^{\prime }}$, and agents $a^{\prime }$ and $h_u$ may only intersect in $(u,a)$. In the full version of the paper, we formally define such a transformation and prove the following lemma.

Let $(G,(s,t),A)$ be a drone delivery instance in which each pair of agents $a,a^{\prime }\in A$ intersects in at most one vertex. For an agent $u\in A$, we define $N_u:=\{v\in V(G_I)\mid \{u,v\}\in E(G_I)\}$. Let $D:A\times A\to V(G)\cup \{-\}$ be a function that returns for two agents $a_i,a_j$ their unique intersection point $V_i\cap V_j$ if it exists and $-$ otherwise. Let $G_I$ be the intersection graph, and assume we have a nice tree decomposition $𝒯=(𝕋,{\{X_t\}}_{t\in V(𝕋)})$ of $G_I$ of width w and maximum degree $\mathrm{\Delta }={\max }_{u\in V(G_I)}|N_u|$.

We now design a dynamic program over $𝒯$ that is parameterized by w and $\mathrm{\Delta }$ and computes the optimal agent tour. The algorithm is inspired by standard treewidth-based DP techniques for TSP¹¹1See e.g. http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2, page 17.. For each node $t\in V(𝕋)$, we process the subgraph $G_t=(V_t,E_t)$.

A delivery tour can be modeled as an ordered sequence $(a_1,a_2,\mathrm{\dots },a_b)$ of agents. Each contiguous subsequence $A_{i,j}=(a_i,\mathrm{\dots },a_j)$ induces a valid subpath in $G_t$, if the corresponding edges $\{a_l,a_{l+1}\}\in E(G_t)$ for all $l\in [i,j-1]$, and $a_i,a_j\in X_t$. Intermediate agents $a_l$ with incur cost $d_{a_l}(D(a_{l-1},a_l),D(a_l,a_{l+1}))$.

However, to determine the cost of agents $a_i,a_j$ we require knowledge about the corresponding unknown preceding and succeeding agents to determine entry and exit points. Thus, the DP state additionally stores for the boundary agents in $X_t$ their assumed predecessor and successor. This allows consistent cost computation when merging subpaths at join nodes.

We slightly modify the input instance to streamline boundary cases: we add two artificial agents $a_s$ and $a_t$, each covering only vertex $s$ and $t$ respectively, and having zero speed. The unique intersection property extends naturally to these agents. We now additionally require any valid delivery tour to start with $a_s$ and end with $a_t$. Both agents are required to be always contained in any bag, increasing the treewidth by exactly 2. Note that the actual delivery can still start at $s$, since $a_s$ can immediately hand over the package at no cost.

To simplify boundary handling, we also introduce auxiliary agents $a_s^{\prime }$ and $a_t^{\prime }$, each identical to $a_s$ and $a_t$, but always assumed to lie outside the tree decomposition (i.e., they are never contained in any bag). A delivery tour will now implicitly require the tour to start with $a_s^{\prime }$ and end with $a_t^{\prime }$. Together, this guarantees that for each boundary agent, which always includes $a_s$ and $a_t$, its predecessor and successor are explicitly known, enabling us to compute exact cost for partial solutions.

Each DP state $D[t,B_t^0,B_t^1,B_t^2,M,\widehat{A},\widehat{Z}]$ represents the optimal forest of paths in subgraph $G_t$ that connects agents according to the following:

• $\mathrm{■}$

  $B_t^i\subseteq X_t$ for $i\in \{0,1,2\}$ contains all agents with degree exactly $i$

• $\mathrm{■}$

  $M\subseteq B_t^1\times B_t^1$ encodes directed pairwise path endpoints as a matching

• $\mathrm{■}$

  $\widehat{A}$ and $\widehat{Z}$ assign known predecessor/successor agents to agents in $B_t^1$:

  • –

    $\widehat{A}$ maps to a neighbor agent s.t. the corresponding edge is not contained in $E_t$

  • –

    $\widehat{Z}$ maps to the neighbor s.t. the corresponding edge is contained in $E_t$

Each path $P_j$ in a feasible forest $F$ must satisfy the following conditions:

• $\mathrm{■}$

  The endpoints of $P_j$ lie in $B_t^1$ and every agent $a\in B_t^i$ has degree $i$ in $F$

• $\mathrm{■}$

  For every pair $(a,a^{\prime })\in M$, there must be a path $P_j$ in $F$ with both of these as endpoints

The cost of a forest $F$ is then evaluated using the previously mentioned reasoning of computing the cost of every individual agent measured by its two neighboring agents in the corresponding sequence. For convenience we will sometimes represent functions as set of tuples, i.e. $\widehat{A}=\{(u,\widehat{A}(u))\mid u\in V(G_t)\}$.

For the root node $r$ the DP entry $D[r,\mathrm{\varnothing },\{a_s,a_t\},\mathrm{\varnothing },\{(a_s,a_t)\},\{(a_s,a_s^{\prime }),(a_t,a_t^{\prime })\},\widehat{Z}]$ captures the optimal path from $a_s$ to $a_t$, if $\widehat{Z}$ correctly encodes the adjacent agents to $a_s$ and $a_t$ in an optimal sequence. By iterating over all valid candidates for the neighbors $u\in N_{a_s}\setminus \{a_s^{\prime }\}$ and $v\in N_{a_t}\setminus \{a_t^{\prime }\}$ we determine the optimal solution.

To compute the delivery cost of a sequence of agents, we use the predecessor/successor assignment $\widehat{A}$. For an agent $a$ of degree 1 we write $\widehat{A}(a)$ to denote the predecessor (if $a$ is the start of a path) or successor (if $a$ is the end), and its other adjacent agent by $\widehat{Z}(a)$ and the partner of $a$ in the matching $M$ by $M(a)$. We will refer to $\widehat{A}(a)$ as the predecessor/successor partner (or psp for short) and to $\widehat{Z}(a)$ as the next/previous interior partner (or npip).

For a feasible forest $S=\{S_1,\mathrm{\dots },S_b\}\subseteq E_t$, each component $S_i=(a_1,\mathrm{\dots },a_{\mathrm{\ell }})$ corresponds to a path of agents starting and ending at agents in $B_t^1$. Using $\widehat{A}$, we extend each such path to the sequence ${\widehat{S}}_i=({\widehat{a}}_0,a_1,\mathrm{\dots },a_{\mathrm{\ell }},{\widehat{a}}_{\mathrm{\ell }+1})$, where ${\widehat{a}}_0=\widehat{A}(a_1)$ and ${\widehat{a}}_{\mathrm{\ell }+1}=\widehat{A}(a_{\mathrm{\ell }})$. These agents define the handover points at the start and end of the path that involves agents $a_1$ and $a_{\mathrm{\ell }}$, which is necessary to compute the full cost contribution of each agent.

The cost of the extended sequence ${\widehat{S}}_i$ is given by $c({\widehat{S}}_i)={\sum }_{j=1}^{l_i}{d}_{{\widehat{a}}_j}(D({\widehat{a}}_{j-1},{\widehat{a}}_j),D({\widehat{a}}_j,{\widehat{a}}_{j+1})).$ Setting the predecessor of $a_s$ as $a_s^{\prime }$ and the successor of $a_t$ as $a_t^{\prime }$ ensures sequences starting at $a_s$ or ending at $a_t$ are correctly computed as well. In this case we will incur an additional cost of 0, since these agents must immediately handover the package at their respective vertex.

The total cost of the solution $S$ is the sum over all component sequences, i.e., $c(S):={\sum }_{i=1}^{b}c({\widehat{S}}_i)$. In the following we write $\widehat{A}(S_i)$ for the extended sequence ${\widehat{S}}_i$. Finally, for any solution $S\subseteq E(G_I)$ and node $t\in V(𝕋)$ we define $S[t]:=S\cap E_t$ and say that $S$ induces the instance $(t,B_t^0,B_t^1,B_t^2,M,\widehat{A},\widehat{Z})$ if

• $\mathrm{■}$

  each $a\in B_t^i$ has degree $i$ in $S[t]$,

• $\mathrm{■}$

  each pair $(u,v)\in M$ is connected by a path in $S[t]$ with $\widehat{A}(u),\widehat{A}(v)$ as their psp agents, and

• $\mathrm{■}$

  for each npip agent $a$ on a path, the adjacent agent corresponds to $\widehat{Z}(a)$.

For an example instance and corresponding agent degrees, see Figure 4. In the following arguments we will for simplicity assume that any DP entry contains the actual forest. If each DP entry only contains its cost one can, by simple recursive pointer-logic, compute the optimal solution in the end recursively. Therefore, we will argue correctness of each entry by considering the actual forest, but derive the computational runtime as if only the cost is saved in every DP entry.

The following lemma shows that indeed it is enough to prove correctness for every subinstance in the DP to derive the optimal solution. The proof is provided in the full version of the paper.

Leaf node: At a leaf node $t$, only $a_s,a_t$ are present and no edges exist. The only valid forest is the empty one with cost 0, so we set $D[t,B_t^0,B_t^1,B_t^2,M,\widehat{A},\widehat{Z}]=\{\mathrm{\varnothing }\}$.

Introduce node: Let $t$ be an introduce node with child $t^{\prime }$ and $X_t=X_{t^{\prime }}\cup \{v\}$. Since $v$ has no incident edges at this point, it must have degree 0 in any valid solution, i.e., $v\in B_t^0$. Therefore $v$ does not influence any solution derived for $t^{\prime }$ and we set $D[t,B_t^0,B_t^1,B_t^2,M,\widehat{A},\widehat{Z}]=D[t^{\prime },B_t^0\setminus \{v\},B_t^1,B_t^2,M,\widehat{A},\widehat{Z}]$.

Forget node: Let $t$ be a forget node with child $t^{\prime }$ and $X_t=X_{t^{\prime }}\setminus \{v\}$. Since $v\notin X_t$ and $v\ne a_s^{\prime },a_t^{\prime }$, it must have degree either $0$ or $2$ in any feasible solution, depending on whether $v$ was used in the respective optimal solution. Therefore, we check both corresponding entries at the child node $t^{\prime }$ and choose the one with minimum cost.

Introduce edge node: Let $t$ be an introduce-edge node with child $t^{\prime }$ and let $e=\{u,v\}$ be the newly introduced edge. If $e$ is not used in the optimal solution, we reuse the solution from $t^{\prime }$. Otherwise, we consider the instance where the degrees of $u$ and $v$ are decreased by 1 and consider all valid choices for their next potential npip agent via $\widehat{Z}$. Additionally, we update $M$ accordingly to reflect all possible new pairings that are possible for solutions containing $e$.

Join node: Let $t$ be a join node with children $t_1$ and $t_2$. To compute an optimal solution, we combine compatible solutions from both children while ensuring degrees, matching, psp agents and npip agents correctly align, and take the solution with minimal cost.

Using these lemmata, we establish the final theorem, with the complete proof included in the full version of this work. See 3

We now briefly describe an exact algorithm for computing optimal schedules when the intersection graph of the underlying graph forms a tree. While this may seem similar to the setting previously considered, it does not follow directly, as the treewidth may be constant, but the vertex degrees can be unbounded.

We first show how to compute an optimal solution for any instance, given a fixed order of agents $(a_1,\mathrm{\dots },a_b)$ in the optimal schedule.

For this, we build a layered directed graph $G^{\prime }$ whose layers represent successive handovers:

• $\mathrm{■}$

  Layer $0$: single vertex $v_s$ representing the source $s$.

• $\mathrm{■}$

  Layer $i(1\le i\le b)$: one vertex for every intersection point of the movement areas of $a_i$ and $a_{i+1}$ (for $i=b$ the region of $a_{b+1}$ is the sink region containing $t$).

• $\mathrm{■}$

  Layer $b+1$: single vertex $v_t$ for the destination $t$.

Edges connect every vertex in layer $i-1$ to every vertex in layer $i$; the weight equals the travel time of agent $a_i$ between these two points. Thus each $s$–$t$ path in $G^{\prime }$ selects exactly one handover point per layer and has length equal to the total delivery time for that sequence of drones. Conversely, any schedule that uses these agents in this particular order defines such a path. Hence, the shortest path in $G^{\prime }$ yields the optimal schedule for the given order, which can easily be computed.