A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone

• URL: http://arxiv.org/abs/2303.00614v2
• Date: Tue, 30 Apr 2024 01:06:29 GMT
• Title: A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
• Authors: Sasan Mahmoudinazlou, Changhyun Kwon,
• Abstract summary: 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.
• Score: 0.8287206589886881
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve using a drone in conjunction with a truck for package delivery. This study presents a hybrid genetic algorithm for solving TSPD and FSTSP by incorporating local search and dynamic programming. Similar algorithms exist in the literature. Our algorithm, however, considers more sophisticated chromosomes and less computationally complex dynamic programming to enable broader exploration by the genetic algorithm and efficient exploitation through dynamic programming and local search. The key contribution of this paper is the discovery of how decision-making processes for solving TSPD and FSTSP should be divided among the layers of genetic algorithm, dynamic programming, and local search. In particular, our genetic algorithm generates the truck and the drone sequences separately and encodes them in a type-aware chromosome, wherein each customer is assigned to either the truck or the drone. We apply local search to each chromosome, which is decoded by dynamic programming for fitness evaluation. Our new algorithm is shown to outperform existing algorithms on most benchmark instances in both quality and time. Our algorithms found the new best solutions for 538 TSPD instances out of 920 and 74 FSTSP instances out of 132.

Related papers

• 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 for the min-max Multiple Traveling Salesman Problem [0.9790236766474201]
  This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against benchmark sets.
  arXiv  Detail & Related papers  (2023-07-14T01:57:10Z)
• Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP [0.39373541926236766]
  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.
  arXiv  Detail & Related papers  (2023-04-26T21:19:36Z)
• 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)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence. We present a method that mitigates this issue to a certain extent.
  arXiv  Detail & Related papers  (2021-08-11T10:42:11Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• Combining Geometric and Information-Theoretic Approaches for Multi-Robot Exploration [16.010307336422148]
  We show that the exploration time of our algorithm is competitive (as a function of $p$) with respect to the offline optimal exploration algorithm. The algorithm is based on a single-robot polygon exploration algorithm, a tree exploration algorithm for higher level planning and a submodular orienteering algorithm for lower level planning.
  arXiv  Detail & Related papers  (2020-04-15T02:02: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.