Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent
  Reinforcement Learning Approach
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an
indispensable constituent in urban logistics distribution systems. Over the
past decade, numerous methods for MVRPSTW have been proposed, but most are
based on heuristic rules that require a large amount of computation time. With
the current rapid increase of logistics demands, traditional methods incur the
dilemma between computational efficiency and solution quality. To efficiently
solve the problem, we propose a novel reinforcement learning algorithm called
the Multi-Agent Attention Model that can solve routing problem instantly
benefit from lengthy offline training. Specifically, the vehicle routing
problem is regarded as a vehicle tour generation process, and an
encoder-decoder framework with attention layers is proposed to generate tours
of multiple vehicles iteratively. Furthermore, a multi-agent reinforcement
learning method with an unsupervised auxiliary network is developed for the
model training. By evaluated on four synthetic networks with different scales,
the results demonstrate that the proposed method consistently outperforms
Google OR-Tools and traditional methods with little computation time. In
addition, we validate the robustness of the well-trained model by varying the
number of customers and the capacities of vehicles.
