Optimization of Drone Routing Problem with Energy Constraints and Charging Station Integration using Improved ParthenoGenetic Algorithm

Sugiarto Cokrowibowo; A. Amirul Asnan Cirua; Nuralamsah Zulkarnaim; Mahmuddin Mahmuddin

doi:10.52436/1.jutif.2026.7.4.5914

Authors

Sugiarto Cokrowibowo Department of Informatics, Universitas Sulawesi Barat, Indonesia
A. Amirul Asnan Cirua Department of Informatics, Universitas Sulawesi Barat, Indonesia
Nuralamsah Zulkarnaim Department of Informatics, Universitas Sulawesi Barat, Indonesia
Mahmuddin Department of Informatics, Universitas Sulawesi Barat, Indonesia

DOI:

https://doi.org/10.52436/1.jutif.2026.7.4.5914

Keywords:

Charging Station, Drone Routing Problem, Energy Constraints, Improved ParthenoGenetic Algorithm, Metaheuristic Optimization

Abstract

The development of Unmanned Aerial Vehicles (UAVs) has introduced new challenges in route optimization, particularly in the Drone Routing Problem (DRP), where limited battery capacity directly affects operational feasibility. This study aims to optimize DRP by considering energy constraints and charging station integration using the Improved ParthenoGenetic Algorithm (IPGA). The proposed method employs a sequence-based chromosome representation, an energy consumption model, and adaptive charging station insertion during fitness evaluation to ensure that the generated routes remain feasible under battery limitations. The performance of IPGA was evaluated using three datasets consisting of 10, 30, and 50 customers and compared with PGA, GA, and PSO based on best fitness, minimum total energy consumption, computation time, and convergence behavior. The results show that IPGA consistently achieved the highest best fitness and the lowest minimum total energy across all dataset scenarios. In the 50-customer dataset, IPGA reduced total energy consumption by 42.89%, 36.19%, and 57.32% compared with PGA, GA, and PSO, respectively. The convergence analysis also indicates that IPGA provides more stable fitness improvement, particularly in medium and large problem instances. These findings show that IPGA is effective for solving energy-constrained DRP and contributes to the development of adaptive metaheuristic optimization methods for intelligent UAV-based logistics and autonomous distribution systems.

Downloads

Download data is not yet available.

References

A. M. Raivi, S. M. A. Huda, M. M. Alam, and S. Moh, “Drone Routing for Drone-Based Delivery Systems : A Review of Trajectory Planning, Charging, and Security,” sensors, vol. 23, no. 3, p. 1463, 2023, doi: 10.3390/s23031463.

T. A. Rodrigues, J. Patrikar, N. L. Oliveira, H. S. Matthews, and S. Scherer, “Drone Flight Data Reveal Energy and Greenhouse Gas Emissions Savings for Very Small Package Delivery,” Patterns, vol. 3, no. 8, p. 100569, 2022, doi: 10.1016/j.patter.2022.100569.

Y. Wang, J. Li, X. Yang, and Q. Peng, “UAV – Ground Vehicle Collaborative Delivery in Emergency Response : A Review of Key Technologies and Future Trends,” Appl. Sci., vol. 15, no. 17, pp. 1–36, 2025, doi: 10.3390/app15179803.

P. Stodola and L. Kutej, “Multi-Depot Vehicle Routing Problem with Drones : Mathematical formulation, solution algorithm and experiments,” Expert Syst. Appl., vol. 241, p. 122483, 2024, doi: 10.1016/j.eswa.2023.122483.

M. R. Ghiasvand, D. Rahmani, and Mohammad Moshref-Javadi, “Data-driven robust optimization for a multi-trip truck-drone routing problem,” Expert Syst. Appl., vol. 241, p. 122485, 2024, doi: 10.1016/j.eswa.2023.122485.

M. Moshref-Javadi and M. Winkenbach, “Applications and Research avenues for drone-based models in logistics : A classification and review,” Expert Syst. Appl., vol. 177, p. 114854, 2021, doi: 10.1016/j.eswa.2021.114854.

J. Zhang, J. F. Campbell, D. C. S. Ii, and A. C. Hupman, “Energy consumption models for delivery drones : A comparison and assessment,” Transp. Res. Part D, vol. 90, p. 102668, 2021, doi: 10.1016/j.trd.2020.102668.

X. Wang, Z. Liu, and X. Li, “Optimal delivery route planning for a fleet of heterogeneous drones : A rescheduling-based genetic algorithm approach,” Comput. Ind. Eng., vol. 179, no. January 2022, p. 109179, 2023, doi: 10.1016/j.cie.2023.109179.

M. Meskar and A. Ahmadi-Javid, “Optimizing Drone Delivery Paths from Shared Bases: A Location-Routing Problem with Realistic Energy Constraints,” J. Intell. Robot. Syst., vol. 110, no. 4, 2024, doi: 10.1007/s10846-024-02129-9.

Y. Li, M. Liu, and D. Jiang, “Application of Unmanned Aerial Vehicles in Logistics: A Literature Review,” Sustain., vol. 14, no. 21, 2022, doi: 10.3390/su142114473.

A. Moadab, F. Farajzadeh, and O. F. Valilai, “Drone routing problem model for last ‑ mile delivery using the public transportation capacity as moving charging stations,” Sci. Rep., vol. 12, pp. 1–16, 2025, doi: 10.1038/s41598-022-10408-4.

M. Fan et al., “Deep Reinforcement Learning for UAV Routing in The Presence of Multiple Charging Stations,” IEEE Trans. Veh. Technol., vol. 72, no. 5, pp. 1–15, 2022, doi: 10.1109/TVT.2022.3232607.

J. Li et al., “Energy-efficient large-scale low-altitude delivery: Integrating charging station location and UAV route planning by a cascade optimization framework,” Aerosp. Sci. Technol., vol. 168, p. 111119, 2026, doi: https://doi.org/10.1016/j.ast.2025.111119.

S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm : past , present , and future,” Multimed. Tools Appl., vol. 80, pp. 8091–8126, 2021, doi: 10.1007/s11042-020-10139-6.

S. Cavani, M. Iori, and R. Roberti, “Exact methods for the traveling salesman problem with multiple drones,” Transp. Res. Part C, vol. 130, p. 103280, 2021, doi: 10.1016/j.trc.2021.103280.

J. Qiao, S. Li, M. Liu, Z. Yang, J. Chen, and P. Liu, “A modified particle swarm optimization algorithm for a vehicle scheduling problem with soft time windows,” Sci. Rep., pp. 1–18, 2023, doi: 10.1038/s41598-023-45543-z.

A. Hussain, S. Riaz, M. S. Amjad, and E. ul Haq, “Genetic algorithm with a new round-robin based tournament selection : Statistical properties analysis,” PLoS One, vol. 17, no. 9, pp. 1–14, 2022, doi: 10.1371/journal.pone.0274456.

N. Li and G. Li, “Hybrid partheno-genetic algorithm for multi-depot perishable food delivery problem with mixed time windows,” Ann. Oper. Res., pp. 757–788, 2022, doi: 10.1007/s10479-022-04747-8.

Y. Liu, Z. Wang, and J. Liu, “A Quick Pheromone Matrix Adaptation Ant Colony Optimization for Dynamic Customers in the Vehicle Routing Problem,” J. Mar. Sci. Eng., vol. 12, no. 7, 2024, doi: 10.3390/jmse12071167.

Y. Xue et al., “A Hybrid Ant Colony Optimization and Dynamic Window Method for Real-Time Navigation of USVs,” sensors, vol. 25, no. 19, pp. 1–15, 2025, doi: 10.3390/s25196181.

X. Li et al., “Adaptive Deep Ant Colony Optimization – Asymmetric Strategy Network Twin Delayed Deep Deterministic Policy Gradient Algorithm : Path Planning for Mobile Robots in Dynamic Environments,” Electron., 2024, doi: 10.3390/electronics13204071.

H. Pan, X. You, S. Liu, and D. Zhang, “Pearson correlation coefficient-based pheromone refactoring mechanism for multi-colony ant colony optimization,” Appl. Intell., pp. 752–774, 2020, doi: 10.1007/s10489-020-01841-x.

A. S. Rosas-carrillo, A. Solís-santomé, C. Silva-sánchez, and O. Camacho-nieto, “UAV Path Planning Using an Adaptive Strategy for the Particle Swarm Optimization Algorithm,” drones, vol. 9, no. 3, pp. 1–17, 2025, doi: 10.3390/drones9030170.

Z. Wang, X. Fang, H. Li, and H. Jin, “An Improved Partheno-Genetic Algorithm with Reproduction Mechanism for the Multiple Traveling Salesperson Problem,” IEEE Access, vol. 8, pp. 102607–102615, 2020, doi: 10.1109/ACCESS.2020.2998539.

A. Momenikorbekandi and M. F. Abbod, “A Novel Metaheuristic Hybrid Parthenogenetic Algorithm for Job Shop Scheduling Problems: Applying an Optimization Model,” IEEE Access, vol. 11, no. April, pp. 56027–56045, 2023, doi: 10.1109/ACCESS.2023.3278372.

M. F. Ibrahim, M. . Putri, D. Farista, and D. M. Utama, “An Improved Genetic Algorithm for Vehicle Routing Problem Pick-up and Delivery with Time Windows,” J. Tek. Ind., vol. 22, no. 1, pp. 1–17, 2021, doi: 10.22219/jtiumm.vol22.no1.1-17.

H. S. Carvalho, A. Pilastri, R. Novais, and P. Cortez, “RanCoord — A random geographic coordinates generator for transport and logistics research and development activities,” Softw. Impacts, vol. 14, no. Desember, p. 100428, 2022, doi: 10.1016/j.simpa.2022.100428.

S. A. Vásquez, G. Angulo, and M. A. Klapp, “An exact solution method for the TSP with Drone based on decomposition,” Comput. Oper. Res., vol. 127, no. March, p. 105127, 2021, doi: 10.1016/j.cor.2020.105127.

F. Aljalaud and Y. Alohali, “Optimizing Autonomous Multi-UAV Path Planning for Inspection Missions: A Comparative Study of Genetic and Stochastic Hill Climbing Algorithms,” Energies, vol. 18, no. 1, pp. 1–22, 2025, doi: 10.3390/en18010050.

A. Resky, Zaitun, and D. T. Teppa, “Evaluating Swarm-Genetics for VRPTW : Robustness Across Seeds and Fleet Efficiency on Solomon Benchmarks,” Mandalika Math. Educ. J., vol. 7, no. 4, pp. 2192–2206, 2025, doi: 10.29303/jm.v7i4.10213.

P. Lou, K. Xu, J. Yan, and Z. Xiao, “An Improved Partheno-Genetic Algorithm for Open Path Multi-Depot Multiple Traveling Salesmen Problem,” J. Phys. Conf. Ser., 2021, doi: 10.1088/1742-6596/1848/1/012002.