Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention

• URL: http://arxiv.org/abs/2006.09100v1
• Date: Tue, 16 Jun 2020 12:08:10 GMT
• Title: Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• Authors: Jonas K. Falkner and Lars Schmidt-Thieme
• Abstract summary: 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.
• Score: 6.155158115218501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many real-world vehicle routing problems involve rich sets of constraints with respect to the capacities of the vehicles, time windows for customers etc. While in recent years first machine learning models have been developed to solve basic vehicle routing problems faster than optimization heuristics, complex constraints rarely are taken into consideration. Due to their general procedure to construct solutions sequentially route by route, these methods generalize unfavorably to such problems. In this paper, 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 that way the model is able to select routes and customers and thus learns to make difficult trade-offs between routes. 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. For two of the three variants it also creates significantly better solutions than a comparable meta-heuristic solver.

Related papers

• 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)
• Preference-Aware Delivery Planning for Last-Mile Logistics [3.04585143845864]
  We propose a novel hierarchical route with learnable parameters that combines the strength of both the optimization and machine learning approaches. By using a real-world delivery dataset provided by the Amazon Last Mile Research Challenge, we demonstrate the importance of having both the optimization and the machine learning components.
  arXiv  Detail & Related papers  (2023-03-08T02:10:59Z)
• 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)
• NeurIPS 2022 Competition: Driving SMARTS [60.948652154552136]
  Driving SMARTS is a regular competition designed to tackle problems caused by the distribution shift in dynamic interaction contexts. The proposed competition supports methodologically diverse solutions, such as reinforcement learning (RL) and offline learning methods.
  arXiv  Detail & Related papers  (2022-11-14T17:10:53Z)
• Supervised Permutation Invariant Networks for Solving the CVRP with Bounded Fleet Size [3.5235974685889397]
  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.
  arXiv  Detail & Related papers  (2022-01-05T10:32:18Z)
• End-to-End Intersection Handling using Multi-Agent Deep Reinforcement Learning [63.56464608571663]
  Navigating through intersections is one of the main challenging tasks for an autonomous vehicle. In this work, we focus on the implementation of a system able to navigate through intersections where only traffic signs are provided. We propose a multi-agent system using a continuous, model-free Deep Reinforcement Learning algorithm used to train a neural network for predicting both the acceleration and the steering angle at each time step.
  arXiv  Detail & Related papers  (2021-04-28T07:54:40Z)
• 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)
• SMARTS: Scalable Multi-Agent Reinforcement Learning Training School for Autonomous Driving [96.50297622371457]
  Multi-agent interaction is a fundamental aspect of autonomous driving in the real world. Despite more than a decade of research and development, the problem of how to interact with diverse road users in diverse scenarios remains largely unsolved. We develop a dedicated simulation platform called SMARTS that generates diverse and competent driving interactions.
  arXiv  Detail & Related papers  (2020-10-19T18:26:10Z)
• 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)
• 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)
• C. H. Robinson Uses Heuristics to Solve Rich Vehicle Routing Problems [0.4893345190925177]
  We propose a set partitioning framework with a number of route generation algorithms, which have shown to be effective in solving a variety of different problems. The proposed algorithms have outperformed the existing technologies at CHR on 10 benchmark instances and since, have been embedded into the company's transportation planning and execution technology platform.
  arXiv  Detail & Related papers  (2019-12-31T03:24:46Z)

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.