Reinforcement Learning for Multi-Truck Vehicle Routing Problems

• URL: http://arxiv.org/abs/2211.17078v1
• Date: Wed, 30 Nov 2022 15:37:53 GMT
• Title: Reinforcement Learning for Multi-Truck Vehicle Routing Problems
• Authors: Randall Correll (1), Sean J. Weinberg (1), Fabio Sanches (1), Takanori Ide (2), Takafumi Suzuki (3) ((1) QC Ware Corp Palo Alto, (2) AISIN CORPORATION Tokyo, (3) Aisin Technical Center of America San Jose)
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vehicle routing problems and other combinatorial optimization problems have been approximately solved by reinforcement learning agents with policies based on encoder-decoder models with attention mechanisms. These techniques are of substantial interest but still cannot solve the complex routing problems that arise in a realistic setting which can have many trucks and complex requirements. With the aim of making reinforcement learning a viable technique for supply chain optimization, we develop new extensions to encoder-decoder models for vehicle routing that allow for complex supply chains using classical computing today and quantum computing in the future. We make two major generalizations. First, our model allows for routing problems with multiple trucks. Second, we move away from the simple requirement of having a truck deliver items from nodes to one special depot node, and instead allow for a complex tensor demand structure. 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.

Related papers

• 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)
• 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)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• Quantum Neural Networks for a Supply Chain Logistics Application [0.0]
  We investigate one such hybrid algorithm on a problem of substantial importance: vehicle routing for supply chain logistics with multiple trucks and complex demand structure. We use reinforcement learning with neural networks with embedded quantum circuits. We find results comparable to human truck assignment.
  arXiv  Detail & Related papers  (2022-11-30T15:35:53Z)
• Supply Chain Logistics with Quantum and Classical Annealing Algorithms [0.0]
  Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance. We investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
  arXiv  Detail & Related papers  (2022-05-09T17:36:21Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone [6.364514310476583]
  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.
  arXiv  Detail & Related papers  (2021-12-22T04:59:44Z)
• 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)
• UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers [108.92194081987967]
  We make the first attempt to explore a universal multi-agent reinforcement learning pipeline, designing one single architecture to fit tasks. Unlike previous RNN-based models, we utilize a transformer-based model to generate a flexible policy. The proposed model, named as Universal Policy Decoupling Transformer (UPDeT), further relaxes the action restriction and makes the multi-agent task's decision process more explainable.
  arXiv  Detail & Related papers  (2021-01-20T07:24:24Z)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  We propose a graph neural network based model that is able to perform multi-agent routing based on learned value in a sparsely connected graph. We show that our model trained with only two agents on graphs with a maximum of 25 nodes can easily generalize to situations with more agents and/or nodes.
  arXiv  Detail & Related papers  (2020-07-09T22:16:45Z)
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention [6.155158115218501]
  We develop a policy model that is able to start and extend multiple routes concurrently by using attention on the joint action space of several tours. In comprehensive experiments on three variants of the vehicle routing problem with time windows we show that our model called JAMPR works well for different problem sizes and outperforms the existing state-of-the-art constructive model.
  arXiv  Detail & Related papers  (2020-06-16T12:08:10Z)

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.