An Evolutionary Algorithm For the Vehicle Routing Problem with Drones with Interceptions

• URL: http://arxiv.org/abs/2409.14173v1
• Date: Sat, 21 Sep 2024 15:26:24 GMT
• Title: An Evolutionary Algorithm For the Vehicle Routing Problem with Drones with Interceptions
• Authors: Carlos Pambo, Jacomine Grobler,
• Abstract summary: The use of trucks and drones as a solution to last-mile delivery challenges is a new and promising research direction explored in this paper. This paper proposes an evolutionary algorithm to solve the vehicle routing problem with drones with interception.
• Score: 0.2455468619225742
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The use of trucks and drones as a solution to address last-mile delivery challenges is a new and promising research direction explored in this paper. The variation of the problem where the drone can intercept the truck while in movement or at the customer location is part of an optimisation problem called the vehicle routing problem with drones with interception (VRPDi). This paper proposes an evolutionary algorithm to solve the VRPDi. In this variation of the VRPDi, multiple pairs of trucks and drones need to be scheduled. The pairs leave and return to a depot location together or separately to make deliveries to customer nodes. The drone can intercept the truck after the delivery or meet up with the truck at the following customer location. The algorithm was executed on the travelling salesman problem with drones (TSPD) datasets by Bouman et al. (2015), and the performance of the algorithm was compared by benchmarking the results of the VRPDi against the results of the VRP of the same dataset. This comparison showed improvements in total delivery time between 39% and 60%. Further detailed analysis of the algorithm results examined the total delivery time, distance, node delivery scheduling and the degree of diversity during the algorithm execution. This analysis also considered how the algorithm handled the VRPDi constraints. The results of the algorithm were then benchmarked against algorithms in Dillon et al. (2023) and Ernst (2024). The latter solved the problem with a maximum drone distance constraint added to the VRPDi. The analysis and benchmarking of the algorithm results showed that the algorithm satisfactorily solved 50 and 100-nodes problems in a reasonable amount of time, and the solutions found were better than those found by the algorithms in Dillon et al. (2023) and Ernst (2024) for the same problems.

Related papers

• VRPD-DT: Vehicle Routing Problem with Drones Under Dynamically Changing Traffic Conditions [12.323383132739195]
  We present a novel problem called the vehicle routing problem with drones under dynamically changing traffic conditions (VRPD-DT) We design a novel cost model that factors in the actual travel distance and projected travel time, computed using a machine learning-driven travel time prediction algorithm. A variable neighborhood descent (VND) algorithm is developed to find the optimal truck-drone routes under the dynamics of traffic conditions.
  arXiv  Detail & Related papers  (2024-04-13T19:28:24Z)
• A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem [0.0]
  This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a self-adaptive genetic algorithm. In FSTSP, optimisation is to minimise the total time to visit all locations while strategically deploying a drone to serve hard-to-reach customer locations.
  arXiv  Detail & Related papers  (2023-10-23T08:51:02Z)
• A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone [0.8287206589886881]
  There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) This study presents a hybrid genetic algorithm for solving TSPD and FSTSP by incorporating local search and dynamic programming.
  arXiv  Detail & Related papers  (2023-03-01T16:11:09Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Rethinking Drone-Based Search and Rescue with Aerial Person Detection [79.76669658740902]
  The visual inspection of aerial drone footage is an integral part of land search and rescue (SAR) operations today. We propose a novel deep learning algorithm to automate this aerial person detection (APD) task. We present the novel Aerial Inspection RetinaNet (AIR) algorithm as the combination of these contributions.
  arXiv  Detail & Related papers  (2021-11-17T21:48:31Z)
• Feeling of Presence Maximization: mmWave-Enabled Virtual Reality Meets Deep Reinforcement Learning [76.46530937296066]
  This paper investigates the problem of providing ultra-reliable and energy-efficient virtual reality (VR) experiences for wireless mobile users. To ensure reliable ultra-high-definition (UHD) video frame delivery to mobile users, a coordinated multipoint (CoMP) transmission technique and millimeter wave (mmWave) communications are exploited.
  arXiv  Detail & Related papers  (2021-06-03T08:35:10Z)
• Distributed Multi-agent Meta Learning for Trajectory Design in Wireless Drone Networks [151.27147513363502]
  This paper studies the problem of the trajectory design for a group of energyconstrained drones operating in dynamic wireless network environments. A value based reinforcement learning (VDRL) solution and a metatraining mechanism is proposed.
  arXiv  Detail & Related papers  (2020-12-06T01:30:12Z)
• Multi-Agent Reinforcement Learning in NOMA-aided UAV Networks for Cellular Offloading [59.32570888309133]
  A novel framework is proposed for cellular offloading with the aid of multiple unmanned aerial vehicles (UAVs) Non-orthogonal multiple access (NOMA) technique is employed at each UAV to further improve the spectrum efficiency of the wireless network. A mutual deep Q-network (MDQN) algorithm is proposed to jointly determine the optimal 3D trajectory and power allocation of UAVs.
  arXiv  Detail & Related papers  (2020-10-18T20:22:05Z)
• Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet of Drones Performing Monitoring Missions [4.477547027158141]
  We show how to schedule the travel path of a set of drones across a graph where the nodes need to be visited multiple times at pre-defined points in time. The proposed formulation can be applied in several domains such as the monitoring of traffic flows in a transportation network, or the monitoring of remote locations to assist search and rescue missions. In a detailed evaluation, it is observed that the greedy algorithm has near-optimal performance as it is on average at 92.06% of the optimal, while it can potentially scale up to settings with hundreds of drones and locations.
  arXiv  Detail & Related papers  (2020-06-02T09:17:18Z)
• 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)
• Algorithms for Optimizing Fleet Staging of Air Ambulances [0.0]
  This research structured an optimal coverage problem with integer linear programming. A Gurobi was programmed with the developed model and timed for performance. A solution implementing base ranking followed by both local and Tabu search-based algorithms was created.
  arXiv  Detail & Related papers  (2020-01-10T04:32:28Z)

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.