Research Article
BibTex RIS Cite

Capacitated Multi Drone Assisted Vehicle Routing Problem

Year 2024, Volume: 37 Issue: 3, 1386 - 1415, 01.09.2024

Hasan Kavlak , Selçuk Kürşat İşleyen , Bilal Toklu

https://doi.org/10.35378/gujs.1340189

Abstract

This research delves into the dynamic landscape of transportation systems, with a specific focus on the integration of drones and conventional vehicles. The study presents a Mixed Integer Programming (MIP) model for the Capacitated Multi-Drone Assisted Vehicle Routing Problem (mDroneCVRP), aiming to minimize the time of the last vehicle's arrival at the warehouse. It is essential to highlight that the proposed model was effectively solved using the CPLEX algorithm within the GAMS framework, underscoring the sophistication of the solution approach. The integration of multiple drones into the routing process proves to be instrumental in significantly reducing service time, demonstrating the efficacy of synergizing drone and truck operations. As the number of nodes escalates, emphasizing the necessity for heuristic approaches to address larger instances, the study provides valuable insights into the judicious use of drones in synchronized routing operations. Furthermore, the research challenges conventional assumptions by permitting drones to take off from and land on different vehicles, thereby augmenting operational capabilities and adeptly tackling contemporary transportation challenges.

Keywords

Drone Unmanned aerial vehicle Capacitated vehicle routing problem Mixed integer programming

References

  • [1] Dantzig, G., Fulkerson, R., Johnson, S., “Solution of a large-scale traveling-salesman problem”, Journal of the operations research society of America, 2(4): 393-410, (1954).
  • [2] Dantzig, G. B., Ramser, J. H. , “The truck dispatching problem. Management science”, 6(1): 80-91, (1959).
  • [3] Murray, C. C., and Chu, A. G., “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transportation Research Part C: Emerging Technologies, 54: 86-109, (2015).
  • [4] Otto, A., Agatz, N., Campbell, J., Golden, B., and Pesch, E., “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey”, Networks, 72(4): 411-458, (2018).
  • [5] Bouman, P., Agatz, N., and Schmidt, M., “Dynamic programming approaches for the traveling salesman problem with drone”, Networks, 72(4): 528-542, (2018).
  • [6] Ha, Q. M., Deville, Y., Pham, Q. D., and Hà, M. H., “On the min-cost traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 86: 597-621, (2018).
  • [7] Ha, Q. M., Deville, Y., Pham, Q. D., and Ha, M. H., “Heuristic methods for the traveling salesman problem with drone”, Computer Science, (2015).
  • [8] Wang, X., Poikonen, S., and Golden, B., “The vehicle routing problem with drones: several worst-case results”, Optimization Letters, 11(4): 679-697, (2017).
  • [9] Poikonen, S., Wang, X., and Golden, B., “The vehicle routing problem with drones: Extended models and connections”, Networks, 70(1): 34-43, (2017).
  • [10] Ponza, A., “Optimization of drone-assisted parcel delivery”, MSc.Thesis, Management Engineering of Padua University, Padua, 80, (2016).
  • [11] Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., and Rich, R., “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm”, Journal of Industrial Engineering and Management, 9(2): 374, (2016).
  • [12] Mathew, N., Smith, S. L., and Waslander, S. L., “Planning paths for package delivery in heterogeneous multirobot teams”, IEEE Transactions on Automation Science and Engineering, 12(4): 1298-1308, (2015).
  • [13] Tokekar, P., Vander Hook, J., Mulla, D., and Isler, V., “Sensor planning for a symbiotic UAV and UGV system for precision agriculture”, IEEE Transactions on Robotics, 32: 1498–1511, (2016).
  • [14] Jia, S., and Zhang, L., “Modelling unmanned aerial vehicles base station in ground-to-air cooperative networks”, IET Communications, 11: 1187–1194, (2017).
  • [15] Wu, G., Pedrycz, W., Li, H., Ma, M., and Liu, J., “Coordinated planning of heterogeneous Earth observation resources”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46: 109–125, (2016).
  • [16] Savuran, H., and Karakaya, M., “Efficient route planning for an unmanned air vehicle deployed on a moving carrier”, Soft Computing, 20: 2905–2920, (2016).
  • [17] Viguria, A., Maza, I., and Ollero, A., “Distributed service-based cooperation in aerial/ground robot teams applied to fire detection and extinguishing missions”, Advanced Robotics, 24: 1–23, (2010).
  • [18] Luo, Z., Liu, Z., and Shi, J., “A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle”, Sensors, 17(5): 1144, (2017).
  • [19] Garone, E., Naldi, R., Casavola, A., Frazzoli, E., “Cooperative mission planning for a class of carrier-vehicle systems”, 49th IEEE Conference on Decision and Control (CDC), 1354–1359, (2010).
  • [20] Savuran, H., and Karakaya, M., “Route optimization method for unmanned air vehicle launched from a carrier”, Lecture Notes on Software Engineering, 3(4): 279–284, (2015).
  • [21] Ulmer, M. W., and Thomas, B. W., “Same‐day delivery with heterogeneous fleets of drones and vehicles”, Networks, 72(4): 475-505, (2018).
  • [22] Campbell, J. F., Sweeney, D. C., and II, Z. J., “Strategic design for delivery with trucks and drones”, In Technical Report, (2017).
  • [23] Carlsson, J. G., and Song, S., “Coordinated logistics with a truck and a drone”, Management Science, (2017).
  • [24] Daknama, R., and Kraus, E, “Vehicle routing with drones”, arXiv 1705.06431v1, (2017).
  • [25] Agatz, N., Bouman, P., and Schmidt, M., “Optimization approaches for the traveling salesman problem with drone”, Transportation Science, (2018).
  • [26] Chang, Y. S., and Lee, H. J., “Optimal delivery routing with wider drone-delivery areas along a shorter truck-route”, Expert Systems with Applications, 104: 307-317, (2018).
  • [27] Cheng, C., Adulyasak, Y., and Rousseau, L. M., “Formulations and Exact Algorithms for Drone Routing Problem”, Working Paper, (2018).
  • [28] Ham, A. M., “Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming”, Transportation Research Part C: Emerging Technologies, 91: 1-14, (2018).
  • [29] Yurek, E. E., and Ozmutlu, H. C., “A decomposition-based iterative optimization algorithm for traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 91: 249-262, (2018).
  • [30] Hu, M., Liu, W., Lu, J., Fu, R., Peng, K., Ma, X., and Liu, J., “On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection”, Future Generation Computer Systems, 94: 214-223, (2019).
  • [31] Jeong, H. Y., Lee, S., and Song, B. D., “Truck-Drone Hybrid Delivery Routing: Payload-Energy dependency and No-Fly Zones”, International Journal of Production Economics, (2019).
  • [32] Karak, A., and Abdelghany, K., “The hybrid vehicle-drone routing problem for pick-up and delivery services”, Transportation Research Part C: Emerging Technologies, 102: 427-449, (2019).
  • [33] Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., and Brunese, P. A., “Multiple Traveling Salesman Problem with Drones: Mathematical model and heuristic approach”, Computers & Industrial Engineering, (2019).
  • [34] Peng, K., Liu, W., Sun, Q., Ma, X., Hu, M., Wang, D., and Liu, J., “Wide-Area Vehicle-Drone Cooperative Sensing: Opportunities and Approaches”, IEEE Access, 7: 1818-1828, (2019).
  • [35] Roberti, R., and Ruthmair, M., “Exact methods for the traveling salesman problem with drone”, Optimization Online, (2019).
  • [36] Sacramento, D., Pisinger, D., and Ropke, S., “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones”, Transportation Research Part C: Emerging Technologies, 102: 289-315, (2019).
  • [37] Sah, B., “Drone Truck Combined Operation: Models and Algorithm”, Ph.D Thesis, State University of New York at Binghamton, (2019).
  • [38] Schermer, D., Moeini, M., and Wendt, O., “A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations”, Computers and Operations Research, 109: 134-158, (2019).
  • [39] Schermer, D., Moeini, M., and Wendt, O., “A matheuristic for the vehicle routing problem with drones and its variants”, Transportation Research Part C: Emerging Technologies, 106: 166-204, (2019b).
  • [40] Wang, D., Hu, P., Du, J., Zhou, P., Deng, T., and Hu, M., “Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones”, IEEE Internet of Things Journal, 6(6): 10483-10495, (2019).
  • [41] Wang, Z., and Sheu, J. B., “Vehicle routing problem with drones”, Transportation research part B: methodological, 122: 350-364, (2019).
  • [42] Kitjacharoenchai, P., Min, B. C., and Lee, S., “Two echelon vehicle routing problem with drones in last mile delivery”, International Journal of Production Economics, 225: 107598, (2020).
  • [43] Murray, C. C., and Raj, R., “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones”, Transportation Research Part C: Emerging Technologies, 110: 368-398, (2020).
  • [44] Poikonen, S., and Golden, B., “Multi-visit drone routing problem”, Computers & Operations Research, 113, 104802, (2020).
  • [45] Kundu, A, and Matis, T., “A delivery time reduction heuristic using drones under windy conditions”, Proceedings of the 2017 Industrial and Systems Engineering Conference, K. Coperich, E. Cudney, and H. Nembhard (eds.), Curran Associates, Inc., Red Hook, 1894–1899, (2017).
  • [46] Tamke, F., and Buscher, U., “The vehicle routing problem with drones and drone speed selection." Computers & Operations Research, 152: 106112, (2023).
  • [47] Zhou, H., Qin, H., Cheng, C., and Rousseau, L. M., “An exact algorithm for the two-echelon vehicle routing problem with drones”, Transportation Research Part B: Methodological, 168: 124-150, (2023).
  • [48] Xia, Y., Zeng, W., Zhang, C., and Yang, H., “A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones”, Transportation Research Part B: Methodological, 171: 80-110, (2023).

Year 2024, Volume: 37 Issue: 3, 1386 - 1415, 01.09.2024

Hasan Kavlak , Selçuk Kürşat İşleyen , Bilal Toklu

https://doi.org/10.35378/gujs.1340189

Abstract

References

  • [1] Dantzig, G., Fulkerson, R., Johnson, S., “Solution of a large-scale traveling-salesman problem”, Journal of the operations research society of America, 2(4): 393-410, (1954).
  • [2] Dantzig, G. B., Ramser, J. H. , “The truck dispatching problem. Management science”, 6(1): 80-91, (1959).
  • [3] Murray, C. C., and Chu, A. G., “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transportation Research Part C: Emerging Technologies, 54: 86-109, (2015).
  • [4] Otto, A., Agatz, N., Campbell, J., Golden, B., and Pesch, E., “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey”, Networks, 72(4): 411-458, (2018).
  • [5] Bouman, P., Agatz, N., and Schmidt, M., “Dynamic programming approaches for the traveling salesman problem with drone”, Networks, 72(4): 528-542, (2018).
  • [6] Ha, Q. M., Deville, Y., Pham, Q. D., and Hà, M. H., “On the min-cost traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 86: 597-621, (2018).
  • [7] Ha, Q. M., Deville, Y., Pham, Q. D., and Ha, M. H., “Heuristic methods for the traveling salesman problem with drone”, Computer Science, (2015).
  • [8] Wang, X., Poikonen, S., and Golden, B., “The vehicle routing problem with drones: several worst-case results”, Optimization Letters, 11(4): 679-697, (2017).
  • [9] Poikonen, S., Wang, X., and Golden, B., “The vehicle routing problem with drones: Extended models and connections”, Networks, 70(1): 34-43, (2017).
  • [10] Ponza, A., “Optimization of drone-assisted parcel delivery”, MSc.Thesis, Management Engineering of Padua University, Padua, 80, (2016).
  • [11] Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., and Rich, R., “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm”, Journal of Industrial Engineering and Management, 9(2): 374, (2016).
  • [12] Mathew, N., Smith, S. L., and Waslander, S. L., “Planning paths for package delivery in heterogeneous multirobot teams”, IEEE Transactions on Automation Science and Engineering, 12(4): 1298-1308, (2015).
  • [13] Tokekar, P., Vander Hook, J., Mulla, D., and Isler, V., “Sensor planning for a symbiotic UAV and UGV system for precision agriculture”, IEEE Transactions on Robotics, 32: 1498–1511, (2016).
  • [14] Jia, S., and Zhang, L., “Modelling unmanned aerial vehicles base station in ground-to-air cooperative networks”, IET Communications, 11: 1187–1194, (2017).
  • [15] Wu, G., Pedrycz, W., Li, H., Ma, M., and Liu, J., “Coordinated planning of heterogeneous Earth observation resources”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46: 109–125, (2016).
  • [16] Savuran, H., and Karakaya, M., “Efficient route planning for an unmanned air vehicle deployed on a moving carrier”, Soft Computing, 20: 2905–2920, (2016).
  • [17] Viguria, A., Maza, I., and Ollero, A., “Distributed service-based cooperation in aerial/ground robot teams applied to fire detection and extinguishing missions”, Advanced Robotics, 24: 1–23, (2010).
  • [18] Luo, Z., Liu, Z., and Shi, J., “A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle”, Sensors, 17(5): 1144, (2017).
  • [19] Garone, E., Naldi, R., Casavola, A., Frazzoli, E., “Cooperative mission planning for a class of carrier-vehicle systems”, 49th IEEE Conference on Decision and Control (CDC), 1354–1359, (2010).
  • [20] Savuran, H., and Karakaya, M., “Route optimization method for unmanned air vehicle launched from a carrier”, Lecture Notes on Software Engineering, 3(4): 279–284, (2015).
  • [21] Ulmer, M. W., and Thomas, B. W., “Same‐day delivery with heterogeneous fleets of drones and vehicles”, Networks, 72(4): 475-505, (2018).
  • [22] Campbell, J. F., Sweeney, D. C., and II, Z. J., “Strategic design for delivery with trucks and drones”, In Technical Report, (2017).
  • [23] Carlsson, J. G., and Song, S., “Coordinated logistics with a truck and a drone”, Management Science, (2017).
  • [24] Daknama, R., and Kraus, E, “Vehicle routing with drones”, arXiv 1705.06431v1, (2017).
  • [25] Agatz, N., Bouman, P., and Schmidt, M., “Optimization approaches for the traveling salesman problem with drone”, Transportation Science, (2018).
  • [26] Chang, Y. S., and Lee, H. J., “Optimal delivery routing with wider drone-delivery areas along a shorter truck-route”, Expert Systems with Applications, 104: 307-317, (2018).
  • [27] Cheng, C., Adulyasak, Y., and Rousseau, L. M., “Formulations and Exact Algorithms for Drone Routing Problem”, Working Paper, (2018).
  • [28] Ham, A. M., “Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming”, Transportation Research Part C: Emerging Technologies, 91: 1-14, (2018).
  • [29] Yurek, E. E., and Ozmutlu, H. C., “A decomposition-based iterative optimization algorithm for traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 91: 249-262, (2018).
  • [30] Hu, M., Liu, W., Lu, J., Fu, R., Peng, K., Ma, X., and Liu, J., “On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection”, Future Generation Computer Systems, 94: 214-223, (2019).
  • [31] Jeong, H. Y., Lee, S., and Song, B. D., “Truck-Drone Hybrid Delivery Routing: Payload-Energy dependency and No-Fly Zones”, International Journal of Production Economics, (2019).
  • [32] Karak, A., and Abdelghany, K., “The hybrid vehicle-drone routing problem for pick-up and delivery services”, Transportation Research Part C: Emerging Technologies, 102: 427-449, (2019).
  • [33] Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., and Brunese, P. A., “Multiple Traveling Salesman Problem with Drones: Mathematical model and heuristic approach”, Computers & Industrial Engineering, (2019).
  • [34] Peng, K., Liu, W., Sun, Q., Ma, X., Hu, M., Wang, D., and Liu, J., “Wide-Area Vehicle-Drone Cooperative Sensing: Opportunities and Approaches”, IEEE Access, 7: 1818-1828, (2019).
  • [35] Roberti, R., and Ruthmair, M., “Exact methods for the traveling salesman problem with drone”, Optimization Online, (2019).
  • [36] Sacramento, D., Pisinger, D., and Ropke, S., “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones”, Transportation Research Part C: Emerging Technologies, 102: 289-315, (2019).
  • [37] Sah, B., “Drone Truck Combined Operation: Models and Algorithm”, Ph.D Thesis, State University of New York at Binghamton, (2019).
  • [38] Schermer, D., Moeini, M., and Wendt, O., “A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations”, Computers and Operations Research, 109: 134-158, (2019).
  • [39] Schermer, D., Moeini, M., and Wendt, O., “A matheuristic for the vehicle routing problem with drones and its variants”, Transportation Research Part C: Emerging Technologies, 106: 166-204, (2019b).
  • [40] Wang, D., Hu, P., Du, J., Zhou, P., Deng, T., and Hu, M., “Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones”, IEEE Internet of Things Journal, 6(6): 10483-10495, (2019).
  • [41] Wang, Z., and Sheu, J. B., “Vehicle routing problem with drones”, Transportation research part B: methodological, 122: 350-364, (2019).
  • [42] Kitjacharoenchai, P., Min, B. C., and Lee, S., “Two echelon vehicle routing problem with drones in last mile delivery”, International Journal of Production Economics, 225: 107598, (2020).
  • [43] Murray, C. C., and Raj, R., “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones”, Transportation Research Part C: Emerging Technologies, 110: 368-398, (2020).
  • [44] Poikonen, S., and Golden, B., “Multi-visit drone routing problem”, Computers & Operations Research, 113, 104802, (2020).
  • [45] Kundu, A, and Matis, T., “A delivery time reduction heuristic using drones under windy conditions”, Proceedings of the 2017 Industrial and Systems Engineering Conference, K. Coperich, E. Cudney, and H. Nembhard (eds.), Curran Associates, Inc., Red Hook, 1894–1899, (2017).
  • [46] Tamke, F., and Buscher, U., “The vehicle routing problem with drones and drone speed selection." Computers & Operations Research, 152: 106112, (2023).
  • [47] Zhou, H., Qin, H., Cheng, C., and Rousseau, L. M., “An exact algorithm for the two-echelon vehicle routing problem with drones”, Transportation Research Part B: Methodological, 168: 124-150, (2023).
  • [48] Xia, Y., Zeng, W., Zhang, C., and Yang, H., “A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones”, Transportation Research Part B: Methodological, 171: 80-110, (2023).
There are 48 citations in total.

Details

Primary Language English
Subjects Packaging, Storage and Transportation (Excl. Food and Agricultural Products)
Journal Section Industrial Engineering
Authors

Hasan Kavlak 0000-0002-8639-5626

Selçuk Kürşat İşleyen 0000-0003-2387-7799

Bilal Toklu 0000-0001-5094-1501

Early Pub Date April 2, 2024
Publication Date September 1, 2024
Published in Issue Year 2024 Volume: 37 Issue: 3

Cite

APA Kavlak, H., İşleyen, S. K., & Toklu, B. (2024). Capacitated Multi Drone Assisted Vehicle Routing Problem. Gazi University Journal of Science, 37(3), 1386-1415. https://doi.org/10.35378/gujs.1340189
AMA Kavlak H, İşleyen SK, Toklu B. Capacitated Multi Drone Assisted Vehicle Routing Problem. Gazi University Journal of Science. September 2024;37(3):1386-1415. doi:10.35378/gujs.1340189
Chicago Kavlak, Hasan, Selçuk Kürşat İşleyen, and Bilal Toklu. “Capacitated Multi Drone Assisted Vehicle Routing Problem”. Gazi University Journal of Science 37, no. 3 (September 2024): 1386-1415. https://doi.org/10.35378/gujs.1340189.
EndNote Kavlak H, İşleyen SK, Toklu B (September 1, 2024) Capacitated Multi Drone Assisted Vehicle Routing Problem. Gazi University Journal of Science 37 3 1386–1415.
IEEE H. Kavlak, S. K. İşleyen, and B. Toklu, “Capacitated Multi Drone Assisted Vehicle Routing Problem”, Gazi University Journal of Science, vol. 37, no. 3, pp. 1386–1415, 2024, doi: 10.35378/gujs.1340189.
ISNAD Kavlak, Hasan et al. “Capacitated Multi Drone Assisted Vehicle Routing Problem”. Gazi University Journal of Science 37/3 (September 2024), 1386-1415. https://doi.org/10.35378/gujs.1340189.
JAMA Kavlak H, İşleyen SK, Toklu B. Capacitated Multi Drone Assisted Vehicle Routing Problem. Gazi University Journal of Science. 2024;37:1386–1415.
MLA Kavlak, Hasan et al. “Capacitated Multi Drone Assisted Vehicle Routing Problem”. Gazi University Journal of Science, vol. 37, no. 3, 2024, pp. 1386-15, doi:10.35378/gujs.1340189.
Vancouver Kavlak H, İşleyen SK, Toklu B. Capacitated Multi Drone Assisted Vehicle Routing Problem. Gazi University Journal of Science. 2024;37(3):1386-415.