Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem

• URL: http://arxiv.org/abs/2307.12136v2
• Date: Tue, 11 Jun 2024 09:57:23 GMT
• Title: Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem
• Authors: Stefan Schoepf, Stephen Mak, Julian Senoner, Liming Xu, Netland Torbjörn, Alexandra Brintrup,
• Abstract summary: Collaborative vehicle routing has been proposed as a solution to increase efficiency. Current operations research methods suffer from non-linear scaling with increasing problem size. We develop a reinforcement learning model to solve the three-dimensional loading capacitated vehicle routing problem in approximately linear time.
• Score: 40.50169360761464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Heavy goods vehicles are vital backbones of the supply chain delivery system but also contribute significantly to carbon emissions with only 60% loading efficiency in the United Kingdom. Collaborative vehicle routing has been proposed as a solution to increase efficiency, but challenges remain to make this a possibility. One key challenge is the efficient computation of viable solutions for co-loading and routing. Current operations research methods suffer from non-linear scaling with increasing problem size and are therefore bound to limited geographic areas to compute results in time for day-to-day operations. This only allows for local optima in routing and leaves global optimisation potential untouched. We develop a reinforcement learning model to solve the three-dimensional loading capacitated vehicle routing problem in approximately linear time. While this problem has been studied extensively in operations research, no publications on solving it with reinforcement learning exist. We demonstrate the favourable scaling of our reinforcement learning model and benchmark our routing performance against state-of-the-art methods. The model performs within an average gap of 3.83% to 8.10% compared to established methods. Our model not only represents a promising first step towards large-scale logistics optimisation with reinforcement learning but also lays the foundation for this research stream. GitHub: https://github.com/if-loops/3L-CVRP

Related papers

• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem [0.09831489366502298]
  This study addresses a gap in the utilization of Reinforcement Learning (RL) and Machine Learning (ML) techniques in solving the Vehicle Routing Problem (SVRP) We propose a novel end-to-end framework that comprehensively addresses the key sources of SVRP and utilizes an RL agent with a simple yet effective architecture and a tailored training method. Our proposed model demonstrates superior performance compared to a widely adopted state-of-the-art meeuristic, achieving a significant 3.43% reduction in travel costs.
  arXiv  Detail & Related papers  (2023-11-13T19:46:22Z)
• 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)
• Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
  This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an model with the capability of fast adaptation to new tasks during inference.
  arXiv  Detail & Related papers  (2023-05-31T06:14:34Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAV [65.07776277630228]
  We propose a double-level deep reinforcement learning (DL-DRL) approach based on a divide and conquer framework (DCF) Particularly, we design an encoder-decoder structured policy network in our upper-level DRL model to allocate the tasks to different UAVs. We also exploit another attention based policy network in our lower-level DRL model to construct the route for each UAV, with the objective to maximize the number of executed tasks.
  arXiv  Detail & Related papers  (2022-08-04T04:35:53Z)
• Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
  State-of-the-art approaches learn a policy using reinforcement learning, and the learnt policy acts as a pseudo solver. These approaches have demonstrated good performance in some cases, but given the large search space typical of routing problem, they can converge too quickly to poor policy. We propose entropy regularised reinforcement learning (ERRL) that supports exploration by providing more policies.
  arXiv  Detail & Related papers  (2020-12-24T14:18:56Z)
• A Three-Stage Algorithm for the Large Scale Dynamic Vehicle Routing Problem with an Industry 4.0 Approach [3.6317403990273402]
  Industry 4.0 is a concept which concentrates on mobility and real-time integration. The aim of this research is to solve large-scale DVRP (LSDVRP)
  arXiv  Detail & Related papers  (2020-08-26T10:39:36Z)
• 2nd Place Scheme on Action Recognition Track of ECCV 2020 VIPriors Challenges: An Efficient Optical Flow Stream Guided Framework [57.847010327319964]
  We propose a data-efficient framework that can train the model from scratch on small datasets. Specifically, by introducing a 3D central difference convolution operation, we proposed a novel C3D neural network-based two-stream framework. It is proved that our method can achieve a promising result even without a pre-trained model on large scale datasets.
  arXiv  Detail & Related papers  (2020-08-10T09:50:28Z)
• Batch-Augmented Multi-Agent Reinforcement Learning for Efficient Traffic Signal Optimization [9.456254189014127]
  The proposed framework reduces traffic congestion by 36% in terms of waiting time compared with the currently used fixed-time traffic signal plan. Our experiments show that the proposed framework reduces traffic congestion by 36% in terms of waiting time compared with the currently used fixed-time traffic signal plan.
  arXiv  Detail & Related papers  (2020-05-19T17:53:05Z)
• Data Freshness and Energy-Efficient UAV Navigation Optimization: A Deep Reinforcement Learning Approach [88.45509934702913]
  We design a navigation policy for multiple unmanned aerial vehicles (UAVs) where mobile base stations (BSs) are deployed. We incorporate different contextual information such as energy and age of information (AoI) constraints to ensure the data freshness at the ground BS. By applying the proposed trained model, an effective real-time trajectory policy for the UAV-BSs captures the observable network states over time.
  arXiv  Detail & Related papers  (2020-02-21T07:29:15Z)

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.