Solving Multi-Agent Routing Problems Using Deep Attention Mechanisms
| Autor: | Jilles Steeve Dibangoye, Laëtitia Matignon, Guillaume Bono, Florian Pereyron, Olivier Simonin |
|---|---|
| Přispěvatelé: | Robots coopératifs et adaptés à la présence humaine en environnements dynamiques (CHROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria), Systèmes Cognitifs et Systèmes Multi-Agents (SyCoSMA), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Volvo Group, Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE23-0018,plasma,Planification et Apprentissage pour Agir dans des Systèmes Multi-Agents(2019) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
050210 logistics & transportation
deep reinforcement learning Artificial neural network Dynamic and stochastic vehicle routing problems Computer science Mechanical Engineering Distributed computing 05 social sciences Decision rule Computer Science Applications [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] attention mechanisms Robustness (computer science) 0502 economics and business Automotive Engineering Vehicle routing problem multi-agent systems Heuristics ComputingMilieux_MISCELLANEOUS |
| Zdroj: | IEEE Transactions on Intelligent Transportation Systems IEEE Transactions on Intelligent Transportation Systems, IEEE, 2020, pp.1-10. ⟨10.1109/TITS.2020.3009289⟩ IEEE Transactions on Intelligent Transportation Systems, 2021, 22 (12), pp.7804-7813. ⟨10.1109/TITS.2020.3009289⟩ |
| ISSN: | 1524-9050 |
| DOI: | 10.1109/TITS.2020.3009289⟩ |
| Popis: | International audience; Routing delivery vehicles to serve customers in dynamic and uncertain environments like dense city centers is a challenging task that requires robustness and flexibility. Most existing approaches to routing problems produce solutions offline in the form of plans, which only apply to the situation they have been optimized for. Instead, we propose to learn a policy that provides decision rules to build the routes from online measurements of the environment state, including the customers configuration itself. Doing so, we can generalize from past experiences and quickly provide decision rules for new instances of the problem without re-optimizing any parameters of our policy. The difficulty with this approach comes from the complexity to represent this state. In this paper, we introduce a sequential multi-agent decision-making model to formalize the description and the temporal evolution of a Dynamic and Stochastic Vehicle Routing Problem. We propose a variation of Deep Neural Network using Attention Mechanisms to learn generalizable representation of the state and output online decision rules adapted to dynamic and stochastic information. Using artificially-generated data, we show promising results in these dynamic and stochastic environments, while staying competitive in deterministic ones compared to offline classical heuristics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|