Reinforcement Learning for Multi-Truck Vehicle Routing Problems

• URL: http://arxiv.org/abs/2211.17078v3
• Date: Fri, 27 Dec 2024 16:42:17 GMT
• Title: Reinforcement Learning for Multi-Truck Vehicle Routing Problems
• Authors: Joshua Levin, Randall Correll, Takanori Ide, Takafumi Suzuki, Saito Takaho, Alan Arai,
• Abstract summary: We develop new extensions to existing encoder-decoder attention models which allow them to handle multiple trucks and multi-leg routing requirements.<n>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.
• Score: 0.9423257767158634
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep reinforcement learning (RL) has been shown to be effective in producing approximate solutions to some vehicle routing problems (VRPs), especially when using policies generated by encoder-decoder attention mechanisms. While these techniques have been quite successful for relatively simple problem instances, there are still under-researched and highly complex VRP variants for which no effective RL method has been demonstrated. In this work we focus on one such VRP variant, which contains multiple trucks and multi-leg routing requirements. In these problems, demand is required to move along sequences of nodes, instead of just from a start node to an end node. With the goal of making deep RL a viable strategy for real-world industrial-scale supply chain logistics, 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. We test our approach on a real supply chain environment arising in the operations of Japanese automotive parts manufacturer Aisin Corporation, and find that our algorithm outperforms Aisin's previous best solution.

Related papers

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL [80.10358123795946]
  We develop a framework for building multi-turn RL algorithms for fine-tuning large language models. Our framework adopts a hierarchical RL approach and runs two RL algorithms in parallel. Empirically, we find that ArCHer significantly improves efficiency and performance on agent tasks.
  arXiv  Detail & Related papers  (2024-02-29T18:45:56Z)
• 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)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• 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)
• Automated Reinforcement Learning (AutoRL): A Survey and Open Problems [92.73407630874841]
  Automated Reinforcement Learning (AutoRL) involves not only standard applications of AutoML but also includes additional challenges unique to RL. We provide a common taxonomy, discuss each area in detail and pose open problems which would be of interest to researchers going forward.
  arXiv  Detail & Related papers  (2022-01-11T12:41:43Z)
• 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)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  We propose Deep Policy Dynamic Programming (D PDP) to combine the strengths of learned neurals with those of dynamic programming algorithms. D PDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP) and the vehicle routing problem (VRP) and show that the neural policy improves the performance of (restricted) DP algorithms.
  arXiv  Detail & Related papers  (2021-02-23T15:33:57Z)
• 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)
• 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)

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.