Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones
Unmanned Aerial Vehicles, commonly known as drones, have been widely used in transmission line inspection and traffic patrolling due to their flexibility and environmental adaptability. To take advantage of drones and overcome their limited endurance, the patrolling tasks are parallelized by concurr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/22/16/6077 |
| _version_ | 1797408071081787392 |
|---|---|
| author | Shuangxi Tian Honghui Chen Guohua Wu Jiaqi Cheng |
| author_facet | Shuangxi Tian Honghui Chen Guohua Wu Jiaqi Cheng |
| author_sort | Shuangxi Tian |
| collection | DOAJ |
| description | Unmanned Aerial Vehicles, commonly known as drones, have been widely used in transmission line inspection and traffic patrolling due to their flexibility and environmental adaptability. To take advantage of drones and overcome their limited endurance, the patrolling tasks are parallelized by concurrently dispatching the drones from a truck which travels on the road network to the nearby task arc. The road network considered in previous research is undirected; however, in reality, the road network usually contains unidirectional arcs, i.e., the road network is asymmetric. Hence, we propose an asymmetric coordinated vehicle-drones arc routing mode for traffic patrolling. In this mode, a truck travelling on an asymmetric road network with multiple drones needs to patrol multiple task arcs, and the drones can be launched and recovered at certain nodes on the truck route, making it possible for drones and the truck to patrol the task in parallel. The total patrol time is the objective function that needs to be minimized given the time limit constraints of drones. The whole problem can be considered as an asymmetric arc routing problem of coordinating a truck and multiple drones. To solve this problem, a large-scale neighborhood search with simulated annealing algorithm (LNS-SA) is proposed. Finally, extensive computation experiments and a real case are carried out. The experimental results show the efficiency of the proposed algorithm. Moreover, a detailed sensitivity analysis is performed on several drone-parameters of interest. |
| first_indexed | 2024-03-09T03:52:02Z |
| format | Article |
| id | doaj.art-f9e947f8b85148158e5a5d8a50cf7e65 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-09T03:52:02Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-f9e947f8b85148158e5a5d8a50cf7e652023-12-03T14:26:13ZengMDPI AGSensors1424-82202022-08-012216607710.3390/s22166077Asymmetric Arc Routing by Coordinating a Truck and Multiple DronesShuangxi Tian0Honghui Chen1Guohua Wu2Jiaqi Cheng3College of Systems Engineering, National University of Defense Technology, Changsha 410073, ChinaCollege of Systems Engineering, National University of Defense Technology, Changsha 410073, ChinaSchool of Traffic and Transportation Engineering, Central South University, Changsha 410075, ChinaSchool of Traffic and Transportation Engineering, Central South University, Changsha 410075, ChinaUnmanned Aerial Vehicles, commonly known as drones, have been widely used in transmission line inspection and traffic patrolling due to their flexibility and environmental adaptability. To take advantage of drones and overcome their limited endurance, the patrolling tasks are parallelized by concurrently dispatching the drones from a truck which travels on the road network to the nearby task arc. The road network considered in previous research is undirected; however, in reality, the road network usually contains unidirectional arcs, i.e., the road network is asymmetric. Hence, we propose an asymmetric coordinated vehicle-drones arc routing mode for traffic patrolling. In this mode, a truck travelling on an asymmetric road network with multiple drones needs to patrol multiple task arcs, and the drones can be launched and recovered at certain nodes on the truck route, making it possible for drones and the truck to patrol the task in parallel. The total patrol time is the objective function that needs to be minimized given the time limit constraints of drones. The whole problem can be considered as an asymmetric arc routing problem of coordinating a truck and multiple drones. To solve this problem, a large-scale neighborhood search with simulated annealing algorithm (LNS-SA) is proposed. Finally, extensive computation experiments and a real case are carried out. The experimental results show the efficiency of the proposed algorithm. Moreover, a detailed sensitivity analysis is performed on several drone-parameters of interest.https://www.mdpi.com/1424-8220/22/16/6077truck-drones arc routingtraffic patrollarge-scale neighborhood search |
| spellingShingle | Shuangxi Tian Honghui Chen Guohua Wu Jiaqi Cheng Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones Sensors truck-drones arc routing traffic patrol large-scale neighborhood search |
| title | Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones |
| title_full | Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones |
| title_fullStr | Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones |
| title_full_unstemmed | Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones |
| title_short | Asymmetric Arc Routing by Coordinating a Truck and Multiple Drones |
| title_sort | asymmetric arc routing by coordinating a truck and multiple drones |
| topic | truck-drones arc routing traffic patrol large-scale neighborhood search |
| url | https://www.mdpi.com/1424-8220/22/16/6077 |
| work_keys_str_mv | AT shuangxitian asymmetricarcroutingbycoordinatingatruckandmultipledrones AT honghuichen asymmetricarcroutingbycoordinatingatruckandmultipledrones AT guohuawu asymmetricarcroutingbycoordinatingatruckandmultipledrones AT jiaqicheng asymmetricarcroutingbycoordinatingatruckandmultipledrones |