Graph-based Airspace Control and Path Optimization for Last-Mile Delivery Drones
Resumo
Drones in last-mile delivery introduce challenges in airspace management, collision avoidance, and route optimization. This MSc dissertation models the shared airspace as a time-expanded graph and formulates the Last-Mile Delivery Drone (LMDD) problem as a Multi-Agent Path Finding (MAPF) instance, solved exactly by a multi-commodity-flow Mixed-Integer Linear Program and, at scale, by a prioritized breadth-first heuristic running in O(P1.5K) for P cells and K drones. Virtual per-drone source and sink vertices make variable take-off times, zero-cost loitering, and synchronized landings first-class in the flow model, and priority insertion supports emergency re-tasking at O(1) cost. The dissertation produced a Computers & Operations Research paper; its edge-centric methodology subsequently led to graph neural networks for flightdelay prediction (Physica A) and to a spectral edge-centrality theory for directed networks (under review).
Referências
Choudhury, S., Solovey, K., Kochenderfer, M., and Pavone, M. (2022). Coordinated multi-agent pathfinding for drones and trucks over road networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’22, page 272–280, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
Dukkanci, O., Campbell, J. F., and Kara, B. Y. (2023). Facility location decisions for drone delivery: A literature review. European Journal of Operational Research.
Franco, J. L., Curtis, V. V., Senne, E. L. F., and Verri, F. A. N. (2025). An exact method and a heuristic for last-mile delivery drones routing with centralized graph-based airspace control. Computers & Operations Research, 178:107006.
Franco, J. L., Machado Neto, M. V., Verri, F. A. N., and Amancio, D. R. (2026a). Graph machine learning for flight delay prediction due to holding maneuver. Physica A: Statistical Mechanics and Its Applications, 685:131318.
Franco, J. L., Peron, T., Dal Col, A., Petronetto, F., Verri, F. A. N., Tokuda, E. K., and Nonato, L. G. (2026b). SVD incidence centrality: A unified spectral framework for node and edge analysis in directed networks and hypergraphs. arXiv:2602.15736. Under review at Physical Review E.
Geft, T. (2023). Fine-grained complexity analysis of multi-agent path finding on 2d grids. Proceedings of the Sixteenth International Symposium on Combinatorial Search, 16(1).
Huhn, P. and Borgwardt, K. H. (2002). Interior-point methods: Worst case and average case analysis of a phase-i algorithm and a termination procedure. Journal of Complexity, 18(3):833–910.
Lam, E., Le Bodic, P., Harabor, D. D., and Stuckey, P. J. (2019). Branchand-cut-and-price for multi-agent pathfinding. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 1289–1296. International Joint Conferences on Artificial Intelligence Organization.
Lubin, M., Dowson, O., Dias Garcia, J., Huchette, J., Legat, B., and Vielma, J. P. (2023). JuMP 1.0: Recent improvements to a modeling language for mathematical optimization. Mathematical Programming Computation.
Ma, H., Harabor, D., Stuckey, P. J., Li, J., and Koenig, S. (2019). Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7643–7650.
Nebel, B. (2020). On the computational complexity of multi-agent pathfinding on directed graphs. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1):212–216.
Nemhauser, G. L. and Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience.
Prevot, T., Rios, J., Kopardekar, P., III, J. E. R., Johnson, M., and Jung, J. (2016). UAS Traffic Management (UTM) Concept of Operations to Safely Enable Low Altitude Flight Operations.
Sharon, G., Stern, R., Felner, A., and Sturtevant, N. R. (2015). Conflictbased search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40–66.
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T., et al. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search, volume 10, pages 151–158.
Surynek, P. (2022). Problem compilation for multi-agent path finding: a survey. In Raedt, L. D., editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 5615–5622. International Joint Conferences on Artificial Intelligence Organization. Survey Track.
Verri, F. A. N., Marcondes, C. A. C., Loubach, D. S., Sbruzzi, E. F., Marques, J. C., Júnior, L. A. P., Maximo, M. R. O. D. A., and Curtis, V. V. (2020). An analysis on tradable permit models for last-mile delivery drones. IEEE Access, 8:186279–186290.
Yu, J. and LaValle, S. M. (2014). Multi-agent path planning and network flow. In Algorithmic Foundations of Robotics X (WAFR) 2012, Springer Tracts in Advanced Robotics, Vol. 86, pages 157–173. Springer.
Čáp, M., Novák, P., Kleiner, A., and Selecký, M. (2015). Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering, 12(3):835–849.
Dukkanci, O., Campbell, J. F., and Kara, B. Y. (2023). Facility location decisions for drone delivery: A literature review. European Journal of Operational Research.
Franco, J. L., Curtis, V. V., Senne, E. L. F., and Verri, F. A. N. (2025). An exact method and a heuristic for last-mile delivery drones routing with centralized graph-based airspace control. Computers & Operations Research, 178:107006.
Franco, J. L., Machado Neto, M. V., Verri, F. A. N., and Amancio, D. R. (2026a). Graph machine learning for flight delay prediction due to holding maneuver. Physica A: Statistical Mechanics and Its Applications, 685:131318.
Franco, J. L., Peron, T., Dal Col, A., Petronetto, F., Verri, F. A. N., Tokuda, E. K., and Nonato, L. G. (2026b). SVD incidence centrality: A unified spectral framework for node and edge analysis in directed networks and hypergraphs. arXiv:2602.15736. Under review at Physical Review E.
Geft, T. (2023). Fine-grained complexity analysis of multi-agent path finding on 2d grids. Proceedings of the Sixteenth International Symposium on Combinatorial Search, 16(1).
Huhn, P. and Borgwardt, K. H. (2002). Interior-point methods: Worst case and average case analysis of a phase-i algorithm and a termination procedure. Journal of Complexity, 18(3):833–910.
Lam, E., Le Bodic, P., Harabor, D. D., and Stuckey, P. J. (2019). Branchand-cut-and-price for multi-agent pathfinding. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 1289–1296. International Joint Conferences on Artificial Intelligence Organization.
Lubin, M., Dowson, O., Dias Garcia, J., Huchette, J., Legat, B., and Vielma, J. P. (2023). JuMP 1.0: Recent improvements to a modeling language for mathematical optimization. Mathematical Programming Computation.
Ma, H., Harabor, D., Stuckey, P. J., Li, J., and Koenig, S. (2019). Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7643–7650.
Nebel, B. (2020). On the computational complexity of multi-agent pathfinding on directed graphs. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1):212–216.
Nemhauser, G. L. and Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience.
Prevot, T., Rios, J., Kopardekar, P., III, J. E. R., Johnson, M., and Jung, J. (2016). UAS Traffic Management (UTM) Concept of Operations to Safely Enable Low Altitude Flight Operations.
Sharon, G., Stern, R., Felner, A., and Sturtevant, N. R. (2015). Conflictbased search for optimal multi-agent pathfinding. Artificial Intelligence, 219:40–66.
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, L., Kumar, T., et al. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search, volume 10, pages 151–158.
Surynek, P. (2022). Problem compilation for multi-agent path finding: a survey. In Raedt, L. D., editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 5615–5622. International Joint Conferences on Artificial Intelligence Organization. Survey Track.
Verri, F. A. N., Marcondes, C. A. C., Loubach, D. S., Sbruzzi, E. F., Marques, J. C., Júnior, L. A. P., Maximo, M. R. O. D. A., and Curtis, V. V. (2020). An analysis on tradable permit models for last-mile delivery drones. IEEE Access, 8:186279–186290.
Yu, J. and LaValle, S. M. (2014). Multi-agent path planning and network flow. In Algorithmic Foundations of Robotics X (WAFR) 2012, Springer Tracts in Advanced Robotics, Vol. 86, pages 157–173. Springer.
Čáp, M., Novák, P., Kleiner, A., and Selecký, M. (2015). Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering, 12(3):835–849.
Publicado
19/10/2026
Como Citar
FRANCO, Jorge Luiz; VERRI, Filipe Alves Neto.
Graph-based Airspace Control and Path Optimization for Last-Mile Delivery Drones. In: CONCURSO DE TESES E DISSERTAÇÕES EM INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (CTDIAC), 15. , 2026, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 1-13.
DOI: https://doi.org/10.5753/ctdiac.2026.25245.
