Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time Windows Variation

• URL: http://arxiv.org/abs/2003.07124v1
• Date: Mon, 16 Mar 2020 11:27:21 GMT
• Title: Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time Windows Variation
• Authors: Fatih Semiz and Faruk Polat
• Abstract summary: In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. We address this by considering a Vehicle Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. These difficulties are even greater if the area coverage must continue throughout a specific time window. We address this by considering a Vehicle Routing Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously without violating time windows. In this problem, our aim is to find a way to cover all areas with the necessary number of UAVs during the time windows, minimize the total distance traveled, and provide a fast solution by satisfying the additional constraint that each agent has limited fuel. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs. Then we solve transportation problems with the simplex algorithm to generate the solution. The performance of the proposed algorithm and other implemented algorithms to compare the solution quality is evaluated on example scenarios with practical problem sizes.

Related papers

• A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem [14.9829752183927]
  The latency location routing problem integrates the facility location problem and the cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers. We propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm.
  arXiv  Detail & Related papers  (2024-03-21T13:54:03Z)
• Constrained multi-objective optimization for multi-UAV planning [5.574995936464475]
  In this work, this problem has been solved using a multi-objective evolutionary algorithm combined with a constraint satisfaction problem model. The algorithm has been tested on several missions of increasing complexity, and the computational complexity of the different element considered in the missions has been studied.
  arXiv  Detail & Related papers  (2024-02-09T17:39:02Z)
• Solving Complex Multi-UAV Mission Planning Problems using Multi-objective Genetic Algorithms [4.198865250277024]
  This paper presents a new Multi-Objective Genetic Algorithm for solving complex Mission Planning Problems (MPP) A hybrid fitness function has been designed using a Constraint Satisfaction Problem (CSP) to check if solutions are valid. Experimental results show that the new algorithm is able to obtain good solutions, however as the problem becomes more complex, the optimal solutions also become harder to find.
  arXiv  Detail & Related papers  (2024-02-09T16:13:21Z)
• Solving the Team Orienteering Problem with Transformers [46.93254771681026]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• A Case Study of Vehicle Route Optimization [2.2101681534594237]
  In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.
  arXiv  Detail & Related papers  (2021-11-17T13:10:55Z)
• A Multi-UAV System for Exploration and Target Finding in Cluttered and GPS-Denied Environments [68.31522961125589]
  We propose a framework for a team of UAVs to cooperatively explore and find a target in complex GPS-denied environments with obstacles. The team of UAVs autonomously navigates, explores, detects, and finds the target in a cluttered environment with a known map. Results indicate that the proposed multi-UAV system has improvements in terms of time-cost, the proportion of search area surveyed, as well as successful rates for search and rescue missions.
  arXiv  Detail & Related papers  (2021-07-19T12:54:04Z)
• Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows [0.0]
  Territory Design for Dynamic Multi-Period Vehicle Routing Problem with Time Windows (TD-DMPVRPTW) This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers. Customers and their demands vary dynamically over time.
  arXiv  Detail & Related papers  (2020-12-18T20:50:32Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Congestion-aware Evacuation Routing using Augmented Reality Devices [96.68280427555808]
  We present a congestion-aware routing solution for indoor evacuation, which produces real-time individual-customized evacuation routes among multiple destinations. A population density map, obtained on-the-fly by aggregating locations of evacuees from user-end Augmented Reality (AR) devices, is used to model the congestion distribution inside a building.
  arXiv  Detail & Related papers  (2020-04-25T22:54:35Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.