A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone

• URL: http://arxiv.org/abs/2112.12545v1
• Date: Wed, 22 Dec 2021 04:59:44 GMT
• Title: A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone
• Authors: Aigerim Bogyrbayeva. Taehyun Yoon, Hanbum Ko, Sungbin Lim, Hyokun Yun, Changhyun Kwon
• Abstract summary: We propose an attention-LSTM decoder hybrid model, in which the decoder's hidden state can represent the sequence of actions made. We empirically demonstrate that such a hybrid model improves upon a purely attention-based model for both solution quality and computational efficiency. Our experiments on the min-max Capacitated Vehicle Routing Problem (mmCVRP) also confirm that the hybrid model is more suitable for coordinated routing of multiple vehicles than the attention-based model.
• Score: 6.364514310476583
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various routing problems, including the Traveling Salesman Problem (TSP). Unfortunately, they perform poorly for the TSP with Drone (TSP-D), requiring routing a heterogeneous fleet of vehicles in coordination -- a truck and a drone. In TSP-D, the two vehicles are moving in tandem and may need to wait at a node for the other vehicle to join. State-less attention-based decoder fails to make such coordination between vehicles. We propose an attention encoder-LSTM decoder hybrid model, in which the decoder's hidden state can represent the sequence of actions made. We empirically demonstrate that such a hybrid model improves upon a purely attention-based model for both solution quality and computational efficiency. Our experiments on the min-max Capacitated Vehicle Routing Problem (mmCVRP) also confirm that the hybrid model is more suitable for coordinated routing of multiple vehicles than the attention-based model.

Related papers

• Semantic Communication for Cooperative Perception using HARQ [51.148203799109304]
  We leverage an importance map to distill critical semantic information, introducing a cooperative perception semantic communication framework. To counter the challenges posed by time-varying multipath fading, our approach incorporates the use of frequency-division multiplexing (OFDM) along with channel estimation and equalization strategies. We introduce a novel semantic error detection method that is integrated with our semantic communication framework in the spirit of hybrid automatic repeated request (HARQ)
  arXiv  Detail & Related papers  (2024-08-29T08:53:26Z)
• 4D ASR: Joint Beam Search Integrating CTC, Attention, Transducer, and Mask Predict Decoders [53.297697898510194]
  We propose a joint modeling scheme where four decoders share the same encoder -- we refer to this as 4D modeling. To efficiently train the 4D model, we introduce a two-stage training strategy that stabilizes multitask learning. In addition, we propose three novel one-pass beam search algorithms by combining three decoders.
  arXiv  Detail & Related papers  (2024-06-05T05:18:20Z)
• Deep Reinforcement Learning for Multi-Truck Vehicle Routing Problems with Multi-Leg Demand Routes [0.9423257767158634]
  We develop new extensions to existing encoder-decoder attention models which allow them to handle multiple trucks and multi-leg routing requirements. Our models have the advantage that they can be trained for a small number of trucks and nodes, and then embedded into a large supply chain to yield solutions for larger numbers of trucks and nodes.
  arXiv  Detail & Related papers  (2024-01-08T21:13:07Z)
• Complexity Matters: Rethinking the Latent Space for Generative Modeling [65.64763873078114]
  In generative modeling, numerous successful approaches leverage a low-dimensional latent space, e.g., Stable Diffusion. In this study, we aim to shed light on this under-explored topic by rethinking the latent space from the perspective of model complexity.
  arXiv  Detail & Related papers  (2023-07-17T07:12:29Z)
• Convergence of Communications, Control, and Machine Learning for Secure and Autonomous Vehicle Navigation [78.60496411542549]
  Connected and autonomous vehicles (CAVs) can reduce human errors in traffic accidents, increase road efficiency, and execute various tasks. Reaping these benefits requires CAVs to autonomously navigate to target destinations. This article proposes solutions using the convergence of communication theory, control theory, and machine learning to enable effective and secure CAV navigation.
  arXiv  Detail & Related papers  (2023-07-05T21:38:36Z)
• Reinforcement Learning for Multi-Truck Vehicle Routing Problems [0.0]
  We develop new extensions to encoder-decoder models for vehicle routing that allow for complex supply chains. We show how our model, even if trained only for a small number of trucks, can be embedded into a large supply chain to yield viable solutions.
  arXiv  Detail & Related papers  (2022-11-30T15:37:53Z)
• Coordinating CAV Swarms at Intersections with a Deep Learning Model [24.188603833058146]
  Connected and automated vehicles (CAVs) are viewed as a special kind of robots that have the potential to significantly improve the safety and efficiency of traffic. Here, we introduce a novel cooperative driving algorithm (AlphaOrder) that combines offline deep learning and online tree searching to find a near-optimal passing order in real-time.
  arXiv  Detail & Related papers  (2022-11-10T02:14:36Z)
• COOPERNAUT: End-to-End Driving with Cooperative Perception for Networked Vehicles [54.61668577827041]
  We introduce COOPERNAUT, an end-to-end learning model that uses cross-vehicle perception for vision-based cooperative driving. Our experiments on AutoCastSim suggest that our cooperative perception driving models lead to a 40% improvement in average success rate.
  arXiv  Detail & Related papers  (2022-05-04T17:55:12Z)
• Multi-intersection Traffic Optimisation: A Benchmark Dataset and a Strong Baseline [85.9210953301628]
  Control of traffic signals is fundamental and critical to alleviate traffic congestion in urban areas. Because of the high complexity of modelling the problem, experimental settings of current works are often inconsistent. We propose a novel and strong baseline model based on deep reinforcement learning with the encoder-decoder structure.
  arXiv  Detail & Related papers  (2021-01-24T03:55:39Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  This paper presents a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC) It has shown significant computational advantages in solving optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management.
  arXiv  Detail & Related papers  (2020-05-26T01:47:39Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems. Traditional methods incur the dilemma between computational efficiency and solution quality. We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
  arXiv  Detail & Related papers  (2020-02-13T14:26:27Z)

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.