Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP

• URL: http://arxiv.org/abs/2304.13832v1
• Date: Wed, 26 Apr 2023 21:19:36 GMT
• Title: Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP
• Authors: Andr\'e Rossi Kuroswiski and Humberto Baldessarini Pires and Angelo Passaro and Lamartine Nogueira Frutuoso and Edson Luiz Fran\c{c}a Senne
• Abstract summary: This work presents a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP) The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers. The HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specifics and a local search phase.
• Score: 0.39373541926236766
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The increasing use of drones to perform various tasks has motivated an exponential growth of research aimed at optimizing the use of these means, benefiting both military and civilian applications, including logistics delivery. In this sense, the combined use of trucks and drones has been explored with great interest by Operations Research. This work presents mathematical formulations in Mixed Integer Linear Programming and proposes a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP), in which truck and drone cooperate. The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers, and the HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specific heuristics and a local search phase.

Related papers

• A Distance Similarity-based Genetic Optimization Algorithm for Satellite Ground Network Planning Considering Feeding Mode [53.71516191515285]
  The low transmission efficiency of the satellite data relay back mission has become a problem that is currently constraining the construction of the system. We propose a distance similarity-based genetic optimization algorithm (DSGA), which considers the state characteristics between the tasks. The results of simulation experiments show that the DSGA can effectively solve the SGNPFM problem.
  arXiv  Detail & Related papers  (2024-08-29T06:57:45Z)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  This paper proposes a weight-aware deep reinforcement learning (WADRL) approach designed to address the multiobjective vehicle routing problem with time windows (MOVRPTW) The Non-dominated sorting genetic algorithm-II (NSGA-II) method is then employed to optimize the outcomes produced by the WADRL.
  arXiv  Detail & Related papers  (2024-07-18T02:46:06Z)
• UAV-enabled Collaborative Beamforming via Multi-Agent Deep Reinforcement Learning [79.16150966434299]
  We formulate a UAV-enabled collaborative beamforming multi-objective optimization problem (UCBMOP) to maximize the transmission rate of the UVAA and minimize the energy consumption of all UAVs. We use the heterogeneous-agent trust region policy optimization (HATRPO) as the basic framework, and then propose an improved HATRPO algorithm, namely HATRPO-UCB.
  arXiv  Detail & Related papers  (2024-04-11T03:19:22Z)
• 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)
• Multi-agricultural Machinery Collaborative Task Assignment Based on Improved Genetic Hybrid Optimization Algorithm [0.0]
  This study proposes a method for multi-agricultural machinery collaborative task assignment based on an improved genetic hybrid optimisation algorithm. The developed hybrid algorithm can effectively reduce path costs, and the efficiency of the assignment outcomes surpasses that of the classical genetic algorithm.
  arXiv  Detail & Related papers  (2023-12-07T12:42:40Z)
• 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 Reinforcement Learning-assisted Genetic Programming Algorithm for Team Formation Problem Considering Person-Job Matching [70.28786574064694]
  A reinforcement learning-assisted genetic programming algorithm (RL-GP) is proposed to enhance the quality of solutions. The hyper-heuristic rules obtained through efficient learning can be utilized as decision-making aids when forming project teams.
  arXiv  Detail & Related papers  (2023-04-08T14:32:12Z)
• 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)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulate is an evolutionary optimization algorithm and software package for global optimization. We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration. We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
  arXiv  Detail & Related papers  (2023-01-20T18:17:34Z)
• Enhanced Teaching-Learning-based Optimization for 3D Path Planning of Multicopter UAVs [2.0305676256390934]
  This paper introduces a new path planning algorithm for unmanned aerial vehicles (UAVs) based on the teaching-learning-based optimization technique. We first define an objective function that incorporates requirements on the path length and constraints on the movement and safe operation of UAVs. The algorithm named Multi-subject TLBO is then proposed to minimize the formulated objective function.
  arXiv  Detail & Related papers  (2022-05-31T16:00:32Z)
• 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)

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.