A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem
This paper focuses on a modified Multi-Depot Unmanned Aerial Vehicle Routing Problem (MMDUAVRP). Comparing to classic multi-depot vehicle routing problem, our studied problem has no constraints to restrict the depot where the Unmanned Aerial Vehicle (UAV) departs and returns. This work aims to minim...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9492093/ |
| _version_ | 1823938878342430720 |
|---|---|
| author | Xiaohui Li Peifan Li Yi Zhao Lu Zhang Yuan Dong |
| author_facet | Xiaohui Li Peifan Li Yi Zhao Lu Zhang Yuan Dong |
| author_sort | Xiaohui Li |
| collection | DOAJ |
| description | This paper focuses on a modified Multi-Depot Unmanned Aerial Vehicle Routing Problem (MMDUAVRP). Comparing to classic multi-depot vehicle routing problem, our studied problem has no constraints to restrict the depot where the Unmanned Aerial Vehicle (UAV) departs and returns. This work aims to minimize the number of UAVs and total distance traveled by all UAVs. This problem is mathematically formulated in this paper and a heuristic-assignment based hybrid large neighborhood search(HLNS) is proposed to solve it. Extensive computational experiments are conducted to verify the performance of HLNS. The HLNS algorithm was first tested on Multi Traveling Salesman Problem which is a simplified version of the MMDUAVRP, and high quality solutions have been obtained. Experimental results by compared with CPLEX and other well-known algorithms suggest that our proposed algorithm provides better solutions within a comparatively shorter period of time. In addition, we also conduct sensitivity analysis on the location of depots and task points that may affect the total cost of solution. |
| first_indexed | 2024-12-17T02:51:59Z |
| format | Article |
| id | doaj.art-1010ea588bed496d80328766c17c8498 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-17T02:51:59Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-1010ea588bed496d80328766c17c84982022-12-21T22:06:23ZengIEEEIEEE Access2169-35362021-01-01910411510412610.1109/ACCESS.2021.30988639492093A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing ProblemXiaohui Li0https://orcid.org/0000-0001-5026-8513Peifan Li1Yi Zhao2https://orcid.org/0000-0002-1139-8320Lu Zhang3https://orcid.org/0000-0002-1819-0098Yuan Dong4School of Electronics and Control Engineering, Chang’an University, Xi’an, ChinaSchool of Electronics and Control Engineering, Chang’an University, Xi’an, ChinaSchool of Electronics and Control Engineering, Chang’an University, Xi’an, ChinaSchool of Electronics and Control Engineering, Chang’an University, Xi’an, ChinaSchool of Electronics and Control Engineering, Chang’an University, Xi’an, ChinaThis paper focuses on a modified Multi-Depot Unmanned Aerial Vehicle Routing Problem (MMDUAVRP). Comparing to classic multi-depot vehicle routing problem, our studied problem has no constraints to restrict the depot where the Unmanned Aerial Vehicle (UAV) departs and returns. This work aims to minimize the number of UAVs and total distance traveled by all UAVs. This problem is mathematically formulated in this paper and a heuristic-assignment based hybrid large neighborhood search(HLNS) is proposed to solve it. Extensive computational experiments are conducted to verify the performance of HLNS. The HLNS algorithm was first tested on Multi Traveling Salesman Problem which is a simplified version of the MMDUAVRP, and high quality solutions have been obtained. Experimental results by compared with CPLEX and other well-known algorithms suggest that our proposed algorithm provides better solutions within a comparatively shorter period of time. In addition, we also conduct sensitivity analysis on the location of depots and task points that may affect the total cost of solution.https://ieeexplore.ieee.org/document/9492093/Unmanned aerial vehiclerouting problemlarge neighborhood searchlocal search |
| spellingShingle | Xiaohui Li Peifan Li Yi Zhao Lu Zhang Yuan Dong A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem IEEE Access Unmanned aerial vehicle routing problem large neighborhood search local search |
| title | A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem |
| title_full | A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem |
| title_fullStr | A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem |
| title_full_unstemmed | A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem |
| title_short | A Hybrid Large Neighborhood Search Algorithm for Solving the Multi Depot UAV Swarm Routing Problem |
| title_sort | hybrid large neighborhood search algorithm for solving the multi depot uav swarm routing problem |
| topic | Unmanned aerial vehicle routing problem large neighborhood search local search |
| url | https://ieeexplore.ieee.org/document/9492093/ |
| work_keys_str_mv | AT xiaohuili ahybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT peifanli ahybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT yizhao ahybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT luzhang ahybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT yuandong ahybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT xiaohuili hybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT peifanli hybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT yizhao hybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT luzhang hybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem AT yuandong hybridlargeneighborhoodsearchalgorithmforsolvingthemultidepotuavswarmroutingproblem |