A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems

Maria Amélia Lopes Silva

doi:10.1016/j.eswa.2019.04.056

2019-10-01

PRE

Maria Amélia Lopes Silva

Sérgio Ricardo de Souza *

Marcone Jamilson Freitas Souza

Ana L. C. Bazzan

DOI：10.1016/j.eswa.2019.04.056

原文链接

原文求助

摘要

En 中文

This article presents a multi-agent framework for optimization using metaheuristics, called AMAM. In this proposal, each agent acts independently in the search space of a combinatorial optimization problem. Agents share information and collaborate with each other through the environment. The goal is to enable the agent to modify their actions based on experiences gained in interacting with the other agents and the environment using the concepts of Reinforcement Learning. For better introduction and validation of the AMAM framework, this article uses the instantiation of the Vehicle Routing Problem with Time Windows (VRPTW) and the Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSP-ST), i.e., two classic combinatorial optimization problems. The main objective of the experiments is to evaluate the performance of the proposed adaptive agents. The experiments confirm that the ability to learn attributed to the agent directly influences the quality of solutions, both from the individual point of view and from the point of view of teamwork. In this way, the framework presented here is a step forward in relation to the other frameworks of the literature regarding to the adaptation to the particular aspects of the problems. Additionally, the cooperation between agents and their ability to influence the quality of the solutions of the agents involved in the search of the solution is confirmed. The results also strengthen the issue of the scalability of the framework, since, with the addition of new agents, there is an improvement of the solutions obtained. (C) 2019 Elsevier Ltd. All rights reserved.

Keyword:

Multi-agent framework for optimization

Reinforcement learning

Metaheuristics

Multi-agent systems

Vehicle routing problem with time window

Unrelated parallel machine scheduling problem