pith. sign in

arxiv: 2604.23015 · v1 · submitted 2026-04-24 · 💻 cs.DS

Approximating Energy-Constrained Drone Delivery Packing Problem for Last-Mile Logistics

Saswata Jana , Partha Sarathi Mandal This is my paper

Pith reviewed 2026-05-08 09:53 UTC · model grok-4.3

classification 💻 cs.DS
keywords drone deliverypacking problemapproximation algorithmbattery constraintslast-mile logisticsbin packinginterval compatibility
0
0 comments X

The pith

The energy-constrained drone delivery packing problem admits approximation algorithms with factors between constant and 4+ψ depending on battery stations and interval conflicts.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops approximation algorithms for the Drone-Delivery Packing Problem, where parcels with delivery intervals and costs must be assigned to drones that share battery stations along a truck route. The objective is to minimize the number of drones while respecting a fixed battery budget and interval compatibility constraints. When no battery stations exist, the problem reduces to a bin-packing variant solved by first-fit decreasing with a constant-factor guarantee. Non-conflicting intervals allow a (2 + ψ) approximation, while the general case with stations and conflicting intervals yields a (4 + ψ) bound that improves to (3 + ψ) if stations perform battery swaps. These guarantees matter for last-mile logistics because they bound how many drones are needed in hybrid truck-drone systems under realistic energy limits.

Core claim

The authors prove that the Drone-Delivery Packing Problem admits a constant-factor approximation via first-fit decreasing when battery stations are absent, a (2 + ψ) approximation when intervals are non-conflicting, and a (4 + ψ) approximation when battery stations and conflicting intervals are both present; the latter improves to (3 + ψ) when stations act as swapping points, where ψ is determined by the battery budget together with the minimum and maximum parcel delivery costs.

What carries the argument

The family of approximation algorithms that extend first-fit decreasing bin packing to enforce battery budgets and interval compatibility when assigning parcels to drones.

If this is right

  • Absence of battery stations reduces the problem to a standard bin-packing variant solved by first-fit decreasing.
  • Non-conflicting delivery intervals tighten the guarantee from (4 + ψ) to (2 + ψ).
  • Presence of battery stations with recharging yields the (4 + ψ) ratio for conflicting intervals.
  • Replacing recharging with battery swapping at stations improves the ratio to (3 + ψ).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The dependence of ψ on battery budget versus delivery costs implies that larger relative battery capacity produces approximations closer to optimal.
  • The same modeling approach could be tested on real delivery traces to measure how often the computed drone counts match actual fleet sizes.
  • Extending the model to allow variable drone speeds or traffic-dependent battery drain would preserve the same algorithmic structure.
  • These ratios could guide fleet sizing decisions in hybrid delivery networks by providing worst-case bounds on required drones.

Load-bearing premise

The battery budget is known and fixed in advance, and all drone assignments remain compatible with the modeled battery stations and interval constraints.

What would settle it

An explicit instance of parcels, costs, intervals, and battery budget on which the algorithm's drone count exceeds the true minimum by more than the claimed ratio for the given ψ value.

Figures

Figures reproduced from arXiv: 2604.23015 by Partha Sarathi Mandal, Saswata Jana.

Figure 2
Figure 2. Figure 2: Representation of delivery time intervals I = {I1, I2, · · · , I8} and swapping time intervals I c = {I c 1 , I c 2} Example view at source ↗
Figure 3
Figure 3. Figure 3: Performance Evaluation for DDP-NS. 6.2 Experimental results view at source ↗
Figure 4
Figure 4. Figure 4: Performance Evaluation for DDP-NC view at source ↗
Figure 5
Figure 5. Figure 5: Performance Evaluation for DDP-SC. 7 Conclusion In this paper, we studied the Drone-delivery Packing Problem. We discussed about three vari￾ants of the problem based on the conflicting characteristics of the delivery intervals and the presence of battery service stations. For each variant, we propose a distinct approximation algorithm and empirically compare its performance with the optimal solution. We de… view at source ↗
Figure 6
Figure 6. Figure 6: An example of DDP-NC with 3 waiting intervals and 23 delivery intervals. view at source ↗
Figure 7
Figure 7. Figure 7: An example of DDP-SC with two waiting time intervals and 17 delivery intervals. view at source ↗
Figure 10
Figure 10. Figure 10: Coloring the ver￾tices of Gb 1 from the matching. The size of the maximum matching of Gb 1 is 2, let (5, 7) and (6, 8) be the matching edges. So, x1 = 2, and z1 = 4. We now color the vertices of G1 with max{ω, z1} = 4 colors. The vertices 5 and 7 get the same color, say “blue”. Then the vertices 6 and 8 get the color same color, say “red”. Then, the unmatched vertices 4 and 9 get the different colors, say… view at source ↗
read the original abstract

Collaboration between drones and trucks in a last-mile delivery system offers numerous benefits and reduces many challenges of the traditional delivery system. Here, we introduce Drone-Delivery Packing Problem, where a set of parcels, associated with delivery intervals and cost, should be delivered to customer locations. The system comprises a set of identical drones and battery stations along truck's route, where drones swap depleted batteries or recharge them. The objective is to find assignment for all parcels by using the minimum number of drones, subject to the battery budget and compatibility of each drone's assignment. We consider three variants of the problem, based on conflicting characteristics and existence of battery service stations. All are NP-hard, and we have proposed approximation algorithms for each. When there are no battery stations, we propose a constant factor approximation algorithm using first fit decreasing bin packing algorithm. When the intervals are non-conflicting, we design a $(2+ \psi)$-approximation algorithm. In the presence of both battery stations and conflicting intervals, we present a $(4+\psi)$-approximation algorithm. The algorithm is later modified into a $(3+\psi)$-approximation algorithm when the battery service stations act as swapping stations. Here $\psi$ is a function of battery budget, minimum and maximum cost of the deliveries. Finally, we validate our results and compare the performance with the optimum on different instances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper introduces the Drone-Delivery Packing Problem (DDPP) for last-mile logistics, involving assignment of parcels (each with delivery intervals and costs) to identical drones under a fixed battery budget, with optional battery stations for recharging or swapping. It considers three variants based on interval conflicts and station presence, proves all NP-hard, and gives approximation algorithms: a constant-factor algorithm (via first-fit decreasing bin packing) when no stations exist; a (2+ψ)-approximation when intervals are non-conflicting; a (4+ψ)-approximation when both stations and conflicts are present; and a modified (3+ψ)-approximation when stations act as swapping stations. Here ψ is a function of the battery budget B and the min/max delivery costs. The work concludes with empirical validation comparing algorithm performance to optima on synthetic instances.

Significance. If the claimed ratios are correct, the paper supplies the first explicit polynomial-time approximation guarantees for this energy-constrained drone-packing setting, extending standard bin-packing and interval-scheduling primitives to battery and compatibility constraints. The constructive nature of the algorithms and the explicit dependence of ψ on B and cost parameters are strengths that could support practical deployment in drone-truck hybrid logistics.

major comments (2)
  1. [Abstract] Abstract and high-level description: the explicit functional form of ψ (in terms of B, c_min, c_max) is never stated, yet all four approximation ratios are expressed solely in terms of ψ; without this definition the claimed bounds cannot be evaluated or compared to prior work on resource-constrained scheduling.
  2. [Section on swapping stations (presumably §5)] The reduction from the general case to the swapping-station variant (yielding the improvement from 4+ψ to 3+ψ) is described only at the level of 'the algorithm is later modified'; the change in the charging argument or the handling of interval conflicts under swapping must be shown explicitly, as this step is load-bearing for the best ratio claimed.
minor comments (3)
  1. [Abstract] The constant-factor algorithm for the no-station case is stated to use FFD but the concrete ratio (e.g., 11/9 or 3/2) is not given; this should be stated explicitly for completeness.
  2. [Introduction / Problem Definition] Notation for battery budget B, interval compatibility, and drone-station assignment constraints should be introduced with a formal problem statement (IP or decision version) before the algorithmic sections.
  3. [Experimental results] Empirical section: the number of instances, ranges for B, interval lengths, and how optimality is computed (exact solver or lower bound) are not summarized in the abstract; a table of average ratios versus optimum would strengthen the validation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments and the opportunity to clarify our manuscript. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and high-level description: the explicit functional form of ψ (in terms of B, c_min, c_max) is never stated, yet all four approximation ratios are expressed solely in terms of ψ; without this definition the claimed bounds cannot be evaluated or compared to prior work on resource-constrained scheduling.

    Authors: We agree that the abstract and high-level description would benefit from the explicit functional form of ψ. The manuscript defines ψ in the technical sections as a function of the battery budget B and the minimum/maximum delivery costs (c_min, c_max), but we will revise the abstract to state the precise expression explicitly so that the approximation ratios can be evaluated directly. revision: yes

  2. Referee: [Section on swapping stations (presumably §5)] The reduction from the general case to the swapping-station variant (yielding the improvement from 4+ψ to 3+ψ) is described only at the level of 'the algorithm is later modified'; the change in the charging argument or the handling of interval conflicts under swapping must be shown explicitly, as this step is load-bearing for the best ratio claimed.

    Authors: We acknowledge that the description of the modification for the swapping-station case is too brief. In the revised manuscript we will expand the relevant section to explicitly detail the changes to the charging argument and the handling of interval conflicts when stations function as swapping stations, together with the proof establishing the improved (3+ψ) ratio. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives approximation ratios ((4+ψ), (3+ψ), (2+ψ), and constant-factor) via explicit constructive algorithms: first-fit-decreasing bin packing for the no-stations case, plus custom interval-compatible assignments and battery-budget accounting for the other variants. These steps rely on standard bin-packing and scheduling primitives whose analysis is independent of the target ratios; no equation equates a claimed ratio to a fitted parameter, no self-citation is invoked as a uniqueness theorem, and no ansatz is smuggled. The modeling assumptions (known fixed battery budget, interval non-overlap) are stated upfront and do not presuppose the approximation guarantees.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the new problem definition, standard NP-hardness results for packing and scheduling, and the correctness of the reduction to first-fit decreasing plus the analysis that produces the ψ-dependent ratios.

axioms (1)
  • domain assumption All variants of the Drone-Delivery Packing Problem are NP-hard.
    Stated directly in the abstract for the three variants considered.

pith-pipeline@v0.9.0 · 5544 in / 1124 out tokens · 32751 ms · 2026-05-08T09:53:09.223375+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Approximation algorithms for drone delivery packing prob- lem,

    S. Jana and P. S. Mandal, “Approximation algorithms for drone delivery packing prob- lem,” inProceedings of the 24th International Conference on Distributed Computing and Networking, 2023, pp. 262–269. 37

    work page 2023

  2. [2]

    Last-mile delivery concepts: a survey from an operational research perspective,

    N. Boysen, S. Fedtke, and S. Schwerdfeger, “Last-mile delivery concepts: a survey from an operational research perspective,”OR Spectrum, vol. 43, pp. 1–58, 03 2021

    work page 2021

  3. [3]

    Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing co2 emissions in the delivery service industry,

    A. Goodchild and J. Toy, “Delivery by drone: An evaluation of unmanned aerial vehicle technology in reducing co2 emissions in the delivery service industry,”Transportation Research Part D: Transport and Environment, vol. 61, pp. 58–67, 2018

    work page 2018

  4. [4]

    Application of drone in agriculture: A review,

    G. Dutta and P. Goswami, “Application of drone in agriculture: A review,”International Journal of Chemical Studies, vol. 8, pp. 181–187, 10 2020

    work page 2020

  5. [5]

    Scheduling diagnostic testing kit deliveries with the mothership and drone routing problem,

    H. J. Park, R. Mirjalili, M. J. Cˆ ot´ e, and G. J. Lim, “Scheduling diagnostic testing kit deliveries with the mothership and drone routing problem,”J. Intell. Robotics Syst., vol. 105, no. 2, jun 2022

    work page 2022

  6. [6]

    Drones and possibilities of their using,

    P. Kardasz and J. Doskocz, “Drones and possibilities of their using,”Journal of Civil & Environmental Engineering, vol. 6, 01 2016

    work page 2016

  7. [7]

    On the scheduling of conflictual deliveries in a last-mile delivery scenario with truck-carried drones,

    F. Betti Sorbelli, F. Cor` o, S. K. Das, L. Palazzetti, and C. M. Pinotti, “On the scheduling of conflictual deliveries in a last-mile delivery scenario with truck-carried drones,”Pervasive and Mobile Computing, vol. 87, p. 101700, 2022

    work page 2022

  8. [8]

    Approximation algorithms for drone delivery scheduling with a fixed number of drones,

    S. Jana and P. S. Mandal, “Approximation algorithms for drone delivery scheduling with a fixed number of drones,”Theoretical Computer Science, vol. 991, p. 114442, 2024

    work page 2024

  9. [9]

    The traveling salesman problem: An overview of exact and approximate algorithms,

    G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,”European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, 1992

    work page 1992

  10. [10]

    The vehicle routing problem: An overview of exact and approximate algorithms,

    ——, “The vehicle routing problem: An overview of exact and approximate algorithms,” European journal of operational research, vol. 59, no. 3, pp. 345–358, 1992

    work page 1992

  11. [11]

    Online vehicle routing problems: A survey,

    P. Jaillet and M. R. Wagner, “Online vehicle routing problems: A survey,”The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 221–237, 2008

    work page 2008

  12. [12]

    The recharging vehicle routing problem,

    R. G. Conrad and M. A. Figliozzi, “The recharging vehicle routing problem,” inProceedings of the 2011 industrial engineering research conference, vol. 8. IISE Norcross, GA, 2011

    work page 2011

  13. [13]

    The electric vehicle routing problem with time windows and multiple recharging options,

    H. Mao, J. Shi, Y. Zhou, and G. Zhang, “The electric vehicle routing problem with time windows and multiple recharging options,”IEEE Access, vol. 8, pp. 114 864–114 875, 2020. 38

    work page 2020

  14. [14]

    Electric vehicle routing problem with time windows, recharging stations and battery swapping stations,

    A. Verma, “Electric vehicle routing problem with time windows, recharging stations and battery swapping stations,”EURO Journal on Transportation and Logistics, vol. 7, no. 4, pp. 415–451, 2018

    work page 2018

  15. [15]

    The flying sidekick traveling salesman problem: Opti- mization of drone-assisted parcel delivery,

    C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Opti- mization of drone-assisted parcel delivery,”Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86–109, 2015

    work page 2015

  16. [16]

    On a cooperative truck-and-drone delivery system,

    G. C. Cri¸ san and E. Nechita, “On a cooperative truck-and-drone delivery system,”Procedia Computer Science, vol. 159, pp. 38–47, 2019, knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 23rd International Conference KES2019

    work page 2019

  17. [17]

    The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones,

    C. C. Murray and R. Raj, “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones,”Transportation Research Part C: Emerging Tech- nologies, vol. 110, pp. 368–398, 2020

    work page 2020

  18. [18]

    Vehicle routing with drones,

    R. Daknama and E. Kraus, “Vehicle routing with drones,”ArXiv, vol. abs/1705.06431, 2017

    work page arXiv 2017

  19. [19]

    The vehicle routing problem with drones: several worst-case results,

    X. Wang, S. Poikonen, and B. Golden, “The vehicle routing problem with drones: several worst-case results,”Optimization Letters, vol. 11, pp. 679–697, 2017

    work page 2017

  20. [20]

    Age-optimal uav scheduling for data collection with battery recharging,

    G. Ahani, D. Yuan, and Y. Zhao, “Age-optimal uav scheduling for data collection with battery recharging,”IEEE Communications Letters, vol. 25, no. 4, pp. 1254–1258, 2020

    work page 2020

  21. [21]

    A hybrid battery charging approach for drone-aided border surveillance scheduling,

    S. J. Kim and G. J. Lim, “A hybrid battery charging approach for drone-aided border surveillance scheduling,”Drones, vol. 2, no. 4, p. 38, 2018

    work page 2018

  22. [22]

    Battery assignment and scheduling for drone delivery businesses,

    S. Park, L. Zhang, and S. Chakraborty, “Battery assignment and scheduling for drone delivery businesses,” in2017 IEEE/ACM International Symposium on Low Power Elec- tronics and Design (ISLPED). IEEE, 2017, pp. 1–6

    work page 2017

  23. [23]

    Drone delivery from trucks: Drone scheduling for given truck routes,

    N. Boysen, D. Briskorn, S. Fedtke, and S. Schwerdfeger, “Drone delivery from trucks: Drone scheduling for given truck routes,”Networks, vol. 72, pp. 506 – 527, 2018

    work page 2018

  24. [24]

    E. G. Coffman, M. R. Garey, and D. S. Johnson,Approximation Algorithms for Bin- Packing — An Updated Survey. Vienna: Springer Vienna, 1984, pp. 49–106. 39

    work page 1984

  25. [25]

    West,Introduction to Graph Theory, ser

    D. West,Introduction to Graph Theory, ser. Introduction to Graph Theory. Prentice Hall, 1996

    work page 1996

  26. [26]

    Complexity of generalized colourings of chordal graphs,

    J. Stacho, “Complexity of generalized colourings of chordal graphs,” Ph.D. dissertation, CAN, 2008, aAINR46826

    work page 2008

  27. [27]

    On bin packing with conflicts,

    L. Epstein and A. Levin, “On bin packing with conflicts,”SIAM Journal on Optimization, vol. 19, no. 3, pp. 1270–1298, 2008

    work page 2008

  28. [28]

    The tight bound of first fit decreasing bin-packing algorithm is ffd (i)≤11/9 opt (i)+ 6/9,

    G. D´ osa, “The tight bound of first fit decreasing bin-packing algorithm is ffd (i)≤11/9 opt (i)+ 6/9,” inInternational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Springer, 2007, pp. 1–11

    work page 2007

  29. [29]

    New worst-case results for the bin-packing problem,

    D. Simchi-Levi, “New worst-case results for the bin-packing problem,”Naval Research Logistics (NRL), pp. 579–585, 1994

    work page 1994

  30. [30]

    M. R. Garey and D. S. Johnson,Computers and intractability. wh freeman New York, 2002, vol. 29

    work page 2002

  31. [31]

    Maximum matchings via gaussian elimination,

    M. Mucha and P. Sankowski, “Maximum matchings via gaussian elimination,” in45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2004, pp. 248– 255

    work page 2004

  32. [32]

    A refined laser method and faster matrix multiplication,

    J. Alman and V. V. Williams, “A refined laser method and faster matrix multiplication,” TheoretiCS, vol. 3, 2024

    work page 2024

  33. [33]

    Strategic design for delivery with trucks and drones,

    J. F. Campbell, D. Sweeney, and J. Zhang, “Strategic design for delivery with trucks and drones,”Supply chain analytics report SCMA (04 2017), pp. 47–55, 2017

    work page 2017

  34. [34]

    Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery,

    J. K. Stolaroff, C. Samaras, E. R. O’Neill, A. Lubers, A. S. Mitchell, and D. Ceperley, “Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery,”Nature communications, vol. 9, no. 1, p. 409, 2018. 40 8 Appendix 8.1 ILP Here, we present an integer linear program for the DDP-SC, assuming the battery stations are the swa...

    work page 2018

  35. [35]

    The variableM >> Bis a very large constant. min X i∈M yi (7) subject tox ij ≤y i ∀i∈ M,∀j∈ N + (8) X i∈M xij = 1,∀j∈ N + ∩ N(9) xij +x ik ≤1,∀i∈ M,∀j, k∈ N + withz jk = 1 (10) 0≤u ij ≤B∀i∈ M,∀j∈ N + (11) ui1 =B−cost(1)·x i1,∀i∈ M(12) uij =u ij−1 −cost(j)·x ij,∀i∈ M,∀j∈ N + ∩ N \ {1}(13) uij ≥B·x ij,∀i∈ M,∀j∈ N + ∩ R(14) 41 uij ≤u ij−1 +M·x ij,∀i∈ M,∀j∈ N ...

    work page

  36. [36]

    ForI 2, we assign the blockS f irst 2 to one of the drones exceptD last 0 (=ϕ) and the drones assigned toI 1

    Both drones will be at full capacity before processing the intervalI 8. ForI 2, we assign the blockS f irst 2 to one of the drones exceptD last 0 (=ϕ) and the drones assigned toI 1. So, we assign the block{I 7, I10, I13}toD 4. Then the block{I 8, I11}assign to D1 and the block{I 9, I12}assign toD 2. So,D last 2 =D 4. Thereafter, we recharge/swap the drone...

    work page

  37. [37]

    ForI 3, we assign the blockS f irst 3 to one of the drones exceptD last 1 (=D 3) and the drones assigned toI 2

    All of them will be at full capacity before processing the intervalI 15. ForI 3, we assign the blockS f irst 3 to one of the drones exceptD last 1 (=D 3) and the drones assigned toI 2. So, we assign the block{I 14, I16, I18}toD 5. Then the block{I 15, I19}is assigned toD 1 and the block{I 17}is assigned toD 2. So,D last 3 =D 1. Thereafter, we recharge/swa...

    work page

  38. [38]

    blue”. Then the vertices 6 and 8 get the color same color, say “red

    All of them will be at full capacity before processing the intervalI 21. Finally forI 4, we assign the blockS f irst 4 to one of the drones exceptD last 2 (=D 4) and the drones assigned toI 3. So, we assign the block{I 20, I22}toD 3. Then the block{I 21, I23}is assigned toD 2, and the algorithm terminates. 8.3 Illustration of Mod-Alg-DDP-SC Consider an in...

    work page