Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems
Zengyu Zou, Jingyuan Wang, Yixuan Huang, Junjie Wu · 2025
Read Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems by Zengyu Zou, Jingyuan Wang, Yixuan Huang, Junjie Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17435.txt.
Introduction
Zengyu Zou and three co-authors design a learning system for fleets of vehicles handling pickup and delivery requests that arrive on the fly. The problem generalizes vehicle routing: several vehicles cooperate while new stochastic requests appear, and classical optimization methods buckle under the scale and pace. Earlier reinforcement learning approaches decoded each vehicle's actions on their own, missing how the choices interact, and struggled with the huge joint action space.
Their framework, the Multi-Agent Pointer Transformer, reads the scene with a transformer encoder, then generates the fleet's joint actions one step at a time with a decoder joined to a pointer network. A relation-aware attention module captures interactions between entities, and informative priors guide exploration. Across eight datasets, the system clearly outperformed existing learning baselines and answered far faster than classical operations research methods.
Catalog record
| CREATOR | Zengyu Zou, Jingyuan Wang, Yixuan Huang, Junjie Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-17435
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Agent Pointer Transformer: Seq-to-Seq Reinforcement Learning for Multi-Vehicle Dynamic Pickup-Delivery Problems Zengyu Zou, Jingyuan Wang, Yixuan Huang, Junjie Wu Abstract This paper addresses the cooperative Multi-Vehicle Dynamic Pickup and Delivery Problem with Stochastic Requests (MVDPDPSR) and proposes an end-to-end centralized decision-making framework based on sequence-to-sequence, named Multi-Agent Pointer Transformer (MAPT). MVDPDPSR is an extension of the vehicle routing problem and a spatio-temporal system optimization problem, widely applied in scenarios such as on-demand delivery. Classical operations research methods face bottlenecks in computational complexity and time efficiency when handling large-scale dynamic problems. Although existing reinforcement learning methods have achieved some progress, they still encounter several challenges: 1) Independent decoding across multiple vehicles fails to model joint action distributions; 2) The feature extraction network struggles to capture inter-entity relationships; 3) The joint action space is exponentially large. To address these issues, we designed the MAPT framework, which employs a Transformer Encoder to extract entity representations, combines a Transformer Decoder with a Pointer Network to generate joint action sequences in an AutoRegressive manner, and introduces a Relation-Aware Attention module to capture inter-entity relationships. Additionally, we guide the model’s decision-making using informative priors to facilitate effective exploration. Experiments on 8 datasets demonstrate that MAPT significantly outperforms existing baseline methods in terms of performance and exhibits substantial computational time advantages compared to classical operations research methods. Code — https://github.com/wszzyer/MAPT 1 Introduction The Pickup and Delivery Problem is a type of vehicle routing problem that has demonstrated its importance in many real-world applications, such as online food delivery. In real-world scenarios, the arrival time, origin, and destination of requests are often unpredictable, and there are strict requirements for service response times. Therefore, efficiently planning vehicle routes based on real-time updated information is particularly important in solving this problem. This work focuses on solving the cooperative Multi-Vehicle Dynamic Pickup and Delivery Problem with Stochastic Requests (MVDPDPSR). Unlike the traditional Pickup and Delivery Problem, in this problem, we need to route multiple vehicles, and the occurrence times of all requests are unknown in advance. Moreover, the origin and destination of each request are only revealed after the request emerges. Existing methods for addressing dynamic vehicle routing problems fall into three categories: heuristic methods , classical operations research methods , and reinforcement learning-based algorithms . Heuristic methods have shown some success ( 31 ; 11 ; 1 ) by routing vehicles through manually designed heuristic rules, such as the nearest-distance rule. Their strengths are simplicity and efficiency, fitting real-time decision scenarios, but they have clear limits as they depend heavily on manually designed rules and struggle to ensure optimality. Classical operations research methods typically adopt the Rolling-Horizon paradigm, which transforms dynamic problems into static ones. These static subproblems are then solved using either exact algorithms ( 24 ; 23 ; 27 ) or metaheuristics ( 28 ; 12 ; 6 ) . This paradigm requires accumulating a sufficient number of requests before initiating planning, which fails to meet the needs of real-time dynamic decision-making. Also, both exact and metaheuristic algorithms have high computational complexity, greatly affecting their time efficiency in practice. With technology development, reinforcement learning-based algorithms have been used for multi-vehicle routing. Multi-agent reinforcement learning methods have been proposed for the static multi-vehicle pickup and delivery problem ( 48 ; 5 ) . They encode the current state with an Encoder, decode independently for each vehicle with a Decoder, and use a conflict handler in post-processing to solve vehicle conflicts. However, these multi-agent methods still face the following issues: (1) Existing multi-agent reinforcement learning methods decode each agent independently, failing to model the joint probability distribution of agents’ actions. Furthermore, the decisions generated by these methods may conflict among agents (e.g., competing for the same request). (2) Existing feature extraction networks fail to capture relationships between entities (e.g., stations, vehicles, requests), which are key components of the MVDPDPSR. (3) The joint action space is often exponentially large, which prevents reinforcement learning from exploring useful actions. To tackle these remaining issues, we propose the Multi-Agent Pointer Transformer (MAPT), an end-to-end centralized decision-making framework based on sequence-to-sequence to solve MVDPDPSR. Specifically, we model the MVDPDPSR problem as a Markov Decision Process, use a Transformer Encoder to extract entity representations, and then combine a Transformer Decoder with a Pointer Network to convert the embedding sequence into a joint action sequence in an AutoRegressive manner. To extract relationships between entities, we propose a Relation-Aware Attention module that embeds entity relationships and adds them to the attention matrix. To address the challenge of reinforcement learning exploring a vast joint action space, we design informative priors based on load balancing and station distance, and fuse these priors with the action distribution decoded by the Decoder, enabling the model to select actions with higher potential rewards. In summary, the main contributions of our work are as follows: • We formalize the MVDPDPSR problem as a Markov Decision Process and design the Multi-Agent Pointer Transformer (MAPT) framework to decode joint actions and model the joint probability. • We design a Relation-Aware Attention module to capture various relationships between entities. • We design informative priors and integrate them into the model’s decision distribution to facilitate effective exploration. • We validate the effectiveness of MAPT on 8 datasets, and experiments show that MAPT outperforms various baselines and demonstrates significant computational time advantages over classical operations research methods. 2 Preliminaries 2.1 Problem Formulation In this section, we formally define the Multi-Vehicle Dynamic Pickup and Delivery Problem with Stochastic Requests(MVDPDPSR). A typical MVDPDPSR scenario involves a fleet of vehicles (Multi-Vehicle) tasked with picking up and delivering cargos among a set of stations. The pickup and delivery requests arise dynamically over time, reflecting the “Dynamic” nature of the problem. Accordingly, stations, vehicles, and requests constitute the three fundamental components of a MVDPDPSR. We provide their formal definitions below. Definition 1 (Stations) . The stations in MVDPDPSR are represented as a fully connected weighted graph \mathcal{G}=\{N,\bm{E}\} . Here, N=\{n_{1}, \ldots, n_{i}, \ldots, n_{I}\} denotes the set of stations, where n_{i} represents the i -th station. \bm{E}\in\mathbb{R}^{|N|\times|N|} is the distance matrix, where each element e_{n_{i},n_{j}} indicates the travel time from station n_{i} to station n_{j} . In the station graph \mathcal{G} , each station can serve as either an origin (pickup station) or a destination (delivery station) for cargos. Definition 2 (Vehicles) . A MVDPDPSR scenario involves K vehicles, where each vehicle v_{k} is represented by a tuple of four state variables: v_{k}=\left\langle\;{cap}_{k},\;{spa}_{k},\;{to}_{k},\;{dist}_{k}\;\right\rangle. (1) The meanings of these variables are as follows: • {cap}_{k} (capacity): the total capacity of vehicle v_{k} . • {spa}^{t}_{k} (space): the remaining available space of vehicle v_{k} at time t . For notational brevity, we omit the superscript time index t when unambiguous (e.g. spa_{k} ). • {to}_{k} (destination): the current destination station of the vehicle. • {dist}_{k} (distance): the remaining distance (travel time) to reach the current destination. If {dist}_{k}\neq 0 , the vehicle is en route; otherwise, it is located at a station. Notably, the destination of a vehicle cannot be changed while it is en route. Definition 3 (Requests) . The objective of MVDPDPSR is to fulfill M cargo delivery requests, where each request r_{m} is represented by a tuple of six state variables: r_{m}=\left\langle\;{from}_{m},\;{to}_{m},\;{val}_{m},\;{vol}_{m},\;{time}_{m},\;{state}_{m}\;\right\rangle. (2)