Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size

• URL: http://arxiv.org/abs/2201.01529v1
• Date: Wed, 5 Jan 2022 10:32:18 GMT
• Title: Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size
• Authors: Daniela Thyssens, Jonas Falkner and Lars Schmidt-Thieme
• Abstract summary: Learning to solve optimization problems, such as the vehicle routing problem, offers great computational advantages. We propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles. In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also competitive results.
• Score: 3.5235974685889397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning to solve combinatorial optimization problems, such as the vehicle routing problem, offers great computational advantages over classical operations research solvers and heuristics. The recently developed deep reinforcement learning approaches either improve an initially given solution iteratively or sequentially construct a set of individual tours. However, most of the existing learning-based approaches are not able to work for a fixed number of vehicles and thus bypass the complex assignment problem of the customers onto an apriori given number of available vehicles. On the other hand, this makes them less suitable for real applications, as many logistic service providers rely on solutions provided for a specific bounded fleet size and cannot accommodate short term changes to the number of vehicles. In contrast we propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of available vehicles. In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also achieves competitive results that incorporate the practical aspect of vehicle costs. In thorough controlled experiments we compare our method to multiple state-of-the-art approaches where we demonstrate stable performance, while utilizing less vehicles and shed some light on existent inconsistencies in the experimentation protocols of the related work.

Related papers

• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• Towards Interactive and Learnable Cooperative Driving Automation: a Large Language Model-Driven Decision-Making Framework [79.088116316919]
  Connected Autonomous Vehicles (CAVs) have begun to open road testing around the world, but their safety and efficiency performance in complex scenarios is still not satisfactory. This paper proposes CoDrivingLLM, an interactive and learnable LLM-driven cooperative driving framework.
  arXiv  Detail & Related papers  (2024-09-19T14:36:00Z)
• 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)
• CLUTR: Curriculum Learning via Unsupervised Task Representation Learning [130.79246770546413]
  CLUTR is a novel curriculum learning algorithm that decouples task representation and curriculum learning into a two-stage optimization. We show CLUTR outperforms PAIRED, a principled and popular UED method, in terms of generalization and sample efficiency in the challenging CarRacing and navigation environments.
  arXiv  Detail & Related papers  (2022-10-19T01:45:29Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  Vehicle Re-Identification is one of the key elements in city-scale vehicle analytics systems. Many state-of-the-art solutions for vehicle re-id mostly focus on improving the accuracy on existing re-id benchmarks and often ignore computational complexity. We propose a simple yet effective hybrid solution empowered by self-supervised training which only uses a single network during inference time.
  arXiv  Detail & Related papers  (2022-05-16T12:14:42Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches. We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training.
  arXiv  Detail & Related papers  (2022-03-02T07:21:56Z)
• Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning [52.2663102239029]
  We present a new practical framework based on deep reinforcement learning and decision-time planning for real-world vehicle on idle-hailing platforms. Our approach learns ride-based state-value function using a batch training algorithm with deep value. We benchmark our algorithm with baselines in a ride-hailing simulation environment to demonstrate its superiority in improving income efficiency.
  arXiv  Detail & Related papers  (2021-03-08T05:34:05Z)
• 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)
• 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)
• 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)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.