Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs
This addresses routing optimization for logistics and transportation systems with privacy constraints, but it is incremental as it builds on existing single-agent methods and shows results only on small scales.
The paper tackles the multi-vehicle routing problem by modeling it as a team Markov game with partially observable costs, where agents observe only their own costs, and proposes a multi-agent Neural Rewriter approach that achieves performance close to an OR-Tools benchmark with perfect cost information on small problem sizes.
We interpret solving the multi-vehicle routing problem as a team Markov game with partially observable costs. For a given set of customers to serve, the playing agents (vehicles) have the common goal to determine the team-optimal agent routes with minimal total cost. Each agent thereby observes only its own cost. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions. Parallel agent action execution and partial observability require new rewriting rules for the game. We propose the introduction of a so-called pool in the system which serves as a collection point for unvisited nodes. It enables agents to act simultaneously and exchange nodes in a conflict-free manner. We realize limited disclosure of agent-specific costs by only sharing them during learning. During inference, each agents acts decentrally, solely based on its own cost. First empirical results on small problem sizes demonstrate that we reach a performance close to the employed OR-Tools benchmark which operates in the perfect cost information setting.