PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization
Authors: Federico Berto
Chuanbo Hua
Laurin Luttmann
Jiwoo Son
Junyoung Park
Kyuree Ahn
Changhyun Kwon
Lin Xie
Jinkyoo Park
Venue: NeurIPS 2025 poster ()
Keywords: Multi-agent Combinatorial Optimization; Multi-agent Reinforcement Learning; Neural Combinatorial Optimization
Primary area: reinforcement_learning
TL;DR: We propose a framework to that learns to construct high-quality solutions efficiently in parallel for multi-agent combinatorial optimization problems

Abstract: Combinatorial optimization problems involving multiple agents are notoriously challenging due to their NP-hard nature and the necessity for effective agent coordination. Despite advancements in learning-based methods, existing approaches often face critical limitations, including suboptimal agent coordination, poor generalization, and high computational latency. To address these issues, we propose PARCO (Parallel AutoRegressive Combinatorial Optimization), a general reinforcement learning framework designed to construct high-quality solutions for multi-agent combinatorial tasks efficiently. To this end, PARCO integrates three key novel components: (1) transformer-based communication layers to enable effective agent collaboration during parallel solution construction, (2) a multiple pointer mechanism for low-latency, parallel agent decision-making, and (3) priority-based conflict handlers to resolve decision conflicts via learned priorities. We evaluate PARCO in multi-agent vehicle routing and scheduling problems, where our approach outperforms state-of-the-art learning methods, demonstrating strong generalization ability and remarkable computational efficiency. We make our source code publicly available to foster future research: https://github.com/ai4co/parco.

PARCO: Parallel AutoRegees Models for Multi-Agent Combinatorial Optimization
Federico Berto*. Chuanbo Hua*.1.2, Laurin Luttmann" ".4 JJiooo Son?, Junyoung Park',
Kyuree Ahnz, Changhyun Kwon Lin , Jinkyoo Park
KAIST 2Omelet *Radical Numerics 'Leuphana University
Brandenburg University of Technology AI4CO!
Abstract
Combinatorial optimization problems involving multiple agents notoriously challenging due to their NP-hard nature and the necessity for effective agent coordi- nation. Despite advancements learning-basee methods, existing approaches often face critical limitations, including suboptimal agent coordination, poor generaliza- tion, and high computational latency. To address these issues, we propose PARCO (Parallel Regesseee Combinatorial Optimization), a general reinforcement learning framework designed construct high-quality solutions for multi-agent combinatorial tasks efficiently. To this end, PARCO integrates three key novel components: (1) transformer- based communication layers to enable effective agent collaboration during parallel solution construction, (2) multiple pointer mecha- nism for low-latency, parallel agent peeision-makinge and (3) priority- based conflict handlers to resolve decision conflicts via learned priorities. We evaluate PARCO multi-agent vehicle routing and scheduling problems, where our approach out- performs hate-offthheart learning methods, demonstrating strong generalization ability and remarkable computational efficiency. We make our source code publicly available to foster future research: https //t//tttttt gith...... com/ ht///i444a ai4co/ /pacoo..
Introduction
Combinatorial optimization (CO) problems involve determining an optimal sequence of actions in dis- crete spaces with several crucial domains, including logistics and supply chain management
AutoRegresive Model
Action: (2)
Action: (b)
Solaion
[91]. Many practical CO problems require a solution to be con- structed by coordinating multiple distinct entities (i.c., agents), each with unique characteristics. We call such problems multi-agent CO. This class of prob- lems naturally arises in
Apuit
Num
Agric
Stop
Stop
Stop 9 [Done]
applications such as coordinated vehicle routing for disaster manage- ment [60], manufacturing [37] and ass- delivery optimization [1], where heterogeneous agents must operate under complex constraints.
Autofuegresion
Artions (1.
Artionn: (7.3.
Souttion
CO problems are notoriously hard to solve and cannot generally be solved optimally in polynomial time due to their NP-hardness [36, 79]. While traditional methods such as exact and heuristic methods have
Figure 1: PARCO generates better solutions with higher efficiency through parallel decision making.
EEqual contributions.
1 Authors are members the A14CO open research community.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

been developed to solve a variety of problems [51, 25], these approaches often concentrate on single-agent scenarios and require long execution times. Moreover, multi-agent CO poses additional challenges including additional constraints and different optimization objectives, such as minimizing lateness or the makespan among agents [82, 72].
Recently, Neural Combinatorial Optimization (NCO) has emerged as powerful alternative by learning efficient neural solvers [4]. In particular, Reinforcement Learning (RL) has shown promise due to its ability to learn directly from interactions with CO problems instead of relying on costly labeled datasets in the shape of optimal solutions, and could even outperform traditional approaches by automatically discovering better (neural) heuristics [3, 49, 40]. Among NCO methods, Autoregressive (AR) construcnnnt solutions step-by-step have garnered attention for their ability to generate solutions for a variety of problems with hard constraints [47, 50, 7]. This capability is crucial for addressing complex problems with multiple constraints, such as heterogeneous capacity [2] precedences in pickup and delivery [77] and machine scheduling problems [101].
However, despite their promising results single-agent settings, AR-CO methods pose two challenges that hinder their practical adoption in solving complex multi-agent CO problems, First, existing AR methods for multi-agent CO suffer from poor coordination, resulting in unsatisfactory solution quality and poor generalization across varying problem sizes and agent configurations [108, 84, 104, 63]. Moreover, AR sequence generation associated with high latency due each single action (or "token"") depending on each previous one, akin to large language models [52, 21J. This issue becomes increasingly pronounced when dealing with large problem instances involving numerous agents.
This paper introduces PARCO (Parallel AutoRegressive Combinatorial Optimization), a novel learn- ing framework to address multi- combinatorial problems effectively via parallel solution con- struction as illustrated in Fig. 1. We design specialized ransformer-baseee Communication Layers to enhance coordination among agents during -eeision-making, enabling collaborative behaviors. Our model leverages a Multiple Pointer Mechanism to efficiently generate actions for various agents simultaneously each solution construction step. Priority- -ased Conflict Handlers ensure feasibility and resolve potential conflicts among agents' decisions based on learned priorities.
We summarize PARCO's 's contributions follows:
We propose general Parallel Autoregressive framework for solution construction in multi- agent CO.
We introduce Communication Layers to enhance agent coordination at each parallel con- struction step.
We design a Multiple Pointer Mechanism that reduces latency by efficiently decoding solutions in parallel.
We enhance solution quality with Priority-based Conflict Handlers that tie break with learned priorities.
We evaluate PARCO on multi-agent vehicle routing and scheduling, where we outperform state-of-the art learning methods in solution quality, generalization, and efficiency.
2
Related Work
Neural Combinatorial Optimization Recent advancements in Neural Combinatorial Optimization
(NCO) have shown promising end-to-end solutions for combinatorial optimization problems [4,
94]. NCO has led to the development of a variety of methods for diverse problems, including the
incorporation of groblem-specific biases [35, 64, 44, 41, 83, 20, 311, bi-level solution pipelines [56,
96, 105], learning-guided search [95, 45, 85, 57, 58, 59, 42], improvement methods [26, 69, 70, 28), effective training algorithms [43, 23, 14, 13, 80, 65, 103], downstream applications [11, 106, 71, 66, 93], and the recent development of end-to-end foundation models [61, 107, 15, 6, 34, 53, 22].
Among such methods, RL-based end-to-end autoregressive (AR) models present several advantages, including climinating the need for labeled solutions, reducing reliance on handcrafted heuristics, and achieving high efficiency in generating high-quality solutions [47, 49, 50, 5, 8J.
Multi- Agent AR Methods for CO While the seminal works in AR-CO methods of Vinyals et al. [89], Kool et al. [47], Kwon et al. [49, 50] propose models that can be used in loose agent settings, such methods cannot be employed directly to model heterogencous agents with different

---

attributes and constraints. Building on Kool et al. [47], Son et al. [84] and Zheng et al. [104] introduce attention- policies for multi-agent min-mat max routing. These models adopt a sequential AR construction strategy, solving for one agent at time and switching agents only after completing single-agent solution. While this approach outperforms decentralized methods [10, 76] remains inherently sequential. In contrast, other multi-agent AR methods determine a location for every agent in each solution construction step, but the different agents select their actions sequentially in either random [102] or learned order [18, 55, 63], making these models still suffer from high generation latency as well as missing inter-agent communication and coordination. Zong et al. [108] propose a multi-agent pickup and delivery model with parallel decoding, using distinct decoders for each agent. However, this approach exhibits limited generalizability due to inflexible fixed decoders for specific agents, lacking powerful communication mechanism, and conflict resolution handled naively by assigning random precedence to agents, restricting the robustness of the model.
PARCO addresses the shortcomings of previous works by leveraging parallel solution construction for any number of agents efficiently with a Multiple Pointer Mechanism, enhancing coordination via Communication Layers, and solving conflicts in principled manner via Priority-based Conflict handlers. Finally, unlike previous works, PARCO is a general framework tackling multi-agent CO without restricting to single class of problems.
3 Preliminaries
3.1 Markov Decision Processes
Multi-agent CO problems can be formulated as Markov Decision Processes (MDPs) and solved autoregressively using RL [74]. In this framework, a solution a to a CO problem instance æ is represented as a sequence of actions. Actions ar selected sequentially from the action space A of size N based on the current state 8 E S, which encodes the problem's is configuration at step t. In multi-agent problems, each step agent E _M= {1..... M) selects an action a," according to a policy Ty. usually represented by a 6 p-arametrizee neural network, mapping states to actions. Agents are selected either by some predefined precedence rule in the sequential planning of Son et al. [84], where agent solutions are constructed one after another, or by the policy itself, in which case No S A MM. Given the agent and its corresponding action, the problem then transitions from state 8, to state 8t+1 according to a transition function т S x A x M - S. This process reaches the terminal state once it has generated feasible solution a (a1,..., ... aT) for the problem instance æ in 7' construction steps. The (sparse) reward Ri(a, x) is usually obtained only in the terminal state and takes the form of the negative of the cost function of the respective CO problem.
3.2 AR Models for CO
Given the sequential nature of MDPs, autoregressive (AR) models pose a natural choice for the policy Te. AR methods construct a viable solution by sequentially generating actions based on the current state and previously selected actions. Without loss of generality, the process can be represented in an encoder-decoder framework as:
po(a/ A II ga
(1)
where aet (a1...., -t-1) is the sequence of actions taken prior to t and h = fxx) is an encoding of the problem instance z obtained via the encoder network f. The decoder go then autoregressively generates the sequence of actions, conditioned on h and the previously generated actions. The parameters 0 encompass both the encoder and decoder components, which together define the policy as the mechanism for producing the joint distribution po pa(a/z)) Thus, the RL objective becomes finding the optimal set of parameters 0* that maximizes the reward function R [48, 49, 43).
4 Methodology
We now outline the general structure of PARCO shown in Fig. 2. First, we formally define parallel multi-agent MDPs for CO ($ 4.1,, which we use as a basis to derive our overall parallel autoregressive approach (5 4.2). We then describe in detail the components of our model: Multi-Agent Encoder
3

---

Graph Features
Encoder
Agent Fratures
Agent Embodiing
Fincdd Layos
Hoden State
Contec Embodiing
Probuiiliies
Agren
Norm
Agant
Enbeidingg
Agent
Node Embedding
Fectioes
Embediings
Norm
Node 2
Node hi
Agents States
MHA
Actions
Agent
L
reset
Vode
States
IR. M.
Agent it Murtiple Pointer Mechamam
Priortyy based Handler
States
Dysani:: Embeading
Communication 1pm
Environment
sLap() A
Actions
Figure 2: Overview of PARCO. Our model encodes multi-agent CO problems into separate agent and node embeddings. Communication Layers allow for coordination among agents during decoding, which enhances solution quality. Actions are decoded efficiently autoregressively parallel through a Multiple Pointer Mecha- nism enhanced by a Priority-based Conflict Handler.
($ 4.3), Communication Layers ( 4.4), Decoder with Multiple Pointer Mechanism ($ 4.5) and Conflict Handlers ($ 4.6). Finally, we outline the training scheme ($ 4.7).
4.1 Cooperative Multi-Agent MDPs
We reformulate the MDPs of $ 3.1 as cooperative multi-agent MDPs [9], often termed fully coopera- tive Markov games [73], by selecting multiple actions from joint action space simultaneously to en- hance efficiency and coordination [98, 68]. At each step t, M agents select actions a, = (a!.... a, according policy Ty
A1 X x AM, which maps the state space S to the joint action space of agents. A conflict handling function t (A1 X X AM) + (A1 x x AA)) ensures action compatibility by allowing only agent execute when multiple agents select mutually conflicting actions (e.g., the same customer location), and assigning a fallback action (e.g.. staying at current position) the others. Given the resolved agent actions a, (aa)), the state of the problem progresses to $t+1 according to the transition function T S (A1 X X Arr ) + S. The agents receive a shared reward R(a,20 x) with a (ā ..., @T) the sequence of joint agent actions.
In the following, we refer to the entities corresponding to actions in the MDP formulation a CO problem (e.g., customer locations in VRPs) nodes, following the convention of Kool et al. [47] and Kwon et al. [49].
4.2 Parallel AR Models for CO
Motivated by the nature of multi-agent MDPs, PARCO introduces Parallel AR model for the policy PARCO constructs feasible solutions by simultancously generating multiple agent actions based on the current state. We formulate the solution generation process an encoder-decoder framework similarly to Eq. (1):
(o (x)
II sb II go Jac,, (eethh)
where (ax) (e is the encoding of problem instance æ via encoder network fer and decoder go implements the policy to autoregressively generate actions efficiently for all agents in parallel. At each step f, the decoder outputs joint actions a; = (a ..., M) for all M agents with at" being the sampled action of agent m. The conflict resolution function ensures action compatibility by allowing only one agent to execute when multiple agents select mutually conflicting actions, resulting in resolved actions å; vaa)). Pa is thus solver that maps to solution (@i,..., är).
benefit of our parallel formulation is that the total number of construction steps T can be sub- stantially lower compared to purely AR methods. While the latter require ΣM= Tm, total actions to construct solution with Ti, being the number of steps required by agent to finish its task.

---

PARCO's Parallel AR needs only max Tm steps as agents effectively divide the solution space and act concurrently. This leads a faster solution construction illustrated in Figs. 1 and 6 and significantly reduced training times.
4.3 Multi-Agent Encoder
The multi-agent encoder fo transforms an input instance z into a hidden representation h. In PARCO, we explicitly model agents and employ separate agent and node embedding layers similar to Son et al. [84] to project agents and nodes into the same embedding space.
The agent embedding layer projects Ka agent features such as vehicle locations and capacities (routing) or machine characteristics (scheduling) into dd-dimensional space using linear projection W. a R Let h. a.e W denote the initial agent embeddings, where a E R.M xka denotes the matrix of agent features. Similarly, the node embedding layer projects k, node features such as customer demands in vehicle routing or job durations scheduling problems into the same d-dimensional space using linear projection Wn, E RR The initial embeddings of the nodes are defined as h F. Wn where En, E RNNx. represents the node feature matrix.
Depending on the problem structure, the initial agent and node embeddings might either be con- and passed through L transformer blocks, consisting of multi-head attentotentoon MHA(h (0), (0) and multi-layer perceptrons (MLPs) as defined in Vaswani al. [88]. Or, agent and node embeddings are used separately as query and keys/values, respectively, in cross-attention mechanism MHA (0) (0) h akin to MatNet [50]. The final
catenated as h (0) = Concat(h.. (0) .hn
embeddings h { h emitted by the last encoder layer contain processed representations of
both agents and nodes that capture their interactions as well as the overall problem structure.
4.4 Communication Layers
At each step of the decoding process of Eq. (2), given the encoded representations h. we construct dynamic agent queries that capture the current state of both agents and the environment. For each agent m, we form a context embedding dm = Concat(h.r h he) consisting of the following components: (1) the (static) embedding of the agent ham; (2) projection h55 8," W E IR of the agent's ' dynamics 6T"h like its current location and capacity (routing) or the time until the agent becomes idle (scheduling); (3) a projection h2 W, Rdd of the dynamic environment features e, that encode the current problem's 's state. These dynamic embeddings are then projected into query vectors qm = d,, W, where W, E [g3dxd is a learnable projection matrix.
The resulting queries q [91, 4M Rxd then processed through communication layers comprising multi-head self-attention followed by an MLP:
q' Norm(MHA() q. 4) + +
q Norm(MLP((g')) +
(4)
where Norm denotes normalization layer [33, 100]. These layers are inherently agent-count agnostic, allowing PARCO to handle arbitrary numbers of agents, making it more flexible and generalizable across different problems. Communication Layers allow agents coordinate their actions by attending to both the problem structure and other agents' states while maintaining efficiency through parallel processing.
4.5 Decoder with Multiple Pointer Mechanism
PARCO's decoder improves the AR pointer mechanism [89, 47] originally designed for single- agent scenarios and recently applied to sequential multi-agent planning with single agent at a time [84, 104] - to handle multiple agents operating in parallel via a Multiple Pointer Mechanism.
Starting with the processed agent queries q that underwent communication, we first compute agent- specific representations through masked cross MHA:
q' MHA(g, ho + & W E h + & W. M,)
(5)
5

---

where & E RN are dynamic node features which are projected via W w E IR xd for keys and values of the MHA, respectively. Further, M, RAxx is the current action mask step t,
avoiding agent representations to attend to infeasible actions.
We then obtain joint logit space across all agents:
q' W + W
B tanh
(6)
vd
with learnable parameters W E Rdxd W E xd and | is scale parameter, set to 10 following Bello et al. [3] to enhance exploration. The output logits u E RRMx are masked by setting infeasible actions given mask M; to -0.. The joint probability distribution over all agent actions becomes:
M
exp Um.
ala h) = II
exp(um..))
m=
where az (at (at....,, a represents the joint action across all agents step
4.6 Conflict Handlers
When sampling from the probability distribution p generated by the Multiple Pointer Mechanism, multiple agents may select the same action simultaneously, which can result in an infeasible solution in several CO problems- - for instance, in vehicle routing problems, usually only one agent is allowed to visit customer node and it becomes essential how to deal with such situation effectively. Conflict handling (i.e., tie- tie- breakkiak)g can be achieved by allowing a single agent among a number of agents that are in conflict to continue with its action while others revert to fallback actions, e.g.. staying in their current position. A simple approach introduced by Zong et al. [108] consists of randomly selecting an agent to perform the new action. However, this can be suboptimal since excludes inductive biases that can be leveraged, such as learned representations.
Algorithm Priority-based Conflict Handler
Require: Actions E NM, Priorities p RRM, Fallback actions R.M
Ensure: Resolved Actions a' E NM
1: argsort(p. descending True)
// Sort indices based priorities in descending order // Reorder actions according to priority // Initialize conflict mask // Check for conflicts in reordered actions
2: à + ala]
3: C' + 0
4: for i = 2 to M do
5: if à; {a
1 then
6:
C, 1
II C2 = indicates a conflict for index i
7: end if
8: end for
9: à (1- CC
Resolve conflicts by assigning fallback actions // Reorder resolved actions back to original order
10: a' + àlo
In PARCO, we propose Priority-based Conflict Handlers that leverage priorities as a tie-breaking rule. Such priorities can be based on heuristics such as giving priority to agents close to completion or whose action results in the smallest immediate cost or on learned priorities. In the latter case, the model output probability values the selected actions p(a:) serve as an indicator for prioritizing certain agents: the higher their value, the higher the priority learned by the model to have those agents win the bre-break.
Algorithm shows our efficient vectorized implementation of the Priority- -base Conflict Handler algorithm. In practice, we augment the conflict handler from 4.2 with priorities p == p(a.) and fallback actions r, i.e. (b(-)= = 2 a,, p. r). Fallback actions in PARCO correspond to "do nothing" operations maintaining an agent's current position (routing) or keeping a machine idle (scheduling) which may result in slightly more solution construction steps but do not affect the final solution This approach effectively handles conflicts by allowing the affected agents to reconsider their choices given the actions of (preceding) agents in the next decoding step.

---

4.7 Training Scheme
PARCO is centralized multi-agent decision making framework and can thus be trained by RL algo- rithms proposed in the single-agent NCO literature. We train PARCO by employing the REINFORCE gradient estimator [92] with a shared baseline as outlined by Kwon et al. [49] and Kim et al. [43]:
1 VoL
ΣΣ BS
Gig Vo pog
(8)
where B is the batch size, S the number of shared baseline samples, and Gyj R(aay, (.) -Iphard (mr)) the advantage of solution aij compared to the shared baseline b of problem instance æ;.
5 Experiments
We assess the effectiveness of PARCO on representative multi-agent CO problems, spanning both routing and scheduling domains. Specifically, we evaluate its performance on two challenging routing problems- - the min-max heterogeneous cupucitated vehicle routing problem (HCVRP) and the open multi-depot capacitated pickup and delivery problem (OMDCPDP) as well as a scheduling problem, the flexible flow shop problem (FFSP). Experimental details are available through Appendix B
5.1 Experimental Settings
HCVRP Problem. The min-max HCVRP involves M agents serving customer demands while adhering to heterogeneous vehicle capacity constraints. Each vehicle can replenish its load by returning to the depot. The objective is minimize the longest route taken by any agent main. ensuring balanced workload distribution. Traditional solvers. We include state-of-the-a art SISRs [12]. Genetic Algorithm (GA) [39] and Simulated Annealing (SA) [32]. Neural baselines. We evaluate the sequential planning baselines Attention Model (AM) [47], Equity Transformer (ET) [84] and Decoupling Partition and Navigation (DPN) [104], and autoregressive models with agent selection DRL,, [55] and state-of-the the-thean art learning method 2D-Ptr [63]. Additional problem and experimental
details are available in Appendix A. and Appendix B. respectively.
ONDCPDP Problem. The OMDCPDP challenging problem arising in last-mile delivery settings where M agents starting from different locations (i.c., multiple depots) must pick up and deliver parcels without returning to their starting point (i.e.. open). Agents have a capacity constraint for orders that can be carried out as stacking limit: tour can include more pickups than the constraint, but the agent must deliver corresponding orders so that carrying capacity is freed. The goal is to minimize the lateness, i.e., the sum of delivery arrival times. Traditional solvers. We include the popular and efficient optimization suite Google OR-Tools [19] as a classical baseline. Neural baselines. We evaluate models specializing in pickup and delivery problems, including the autoregressive Heterogeneous Attention Model (HAM) [54] for sequential planning and MAPDP [108] for parallel planning. Additional problem and experimental details are available in Appendix A.2 and Appendix B.2, respectively.
FFSP Problem. In FFSP, N jobs must be processed by M machines divided equally in S stages. Jobs follow a specified sequence through these stages. Within each, any available machine can process the job, with the key constraint that no machine can handle multiple jobs simultaneously. The goal is to schedule the jobs so that all jobs are finished in the shortest time possible. Traditional solvers. We incorporate the widely used and powerful Gurobi solver [24] as a baseline. Furthermore, we include dispatching rules Random and Shortest Job First (SJF), Particle Swarm Optimization (PSO) [81] I]] and Genetic Algorithm (GA) [25]. Neural baselines. Notable benchmarks include the Matrix Encoding Network (MatNet) [50] which demonstrates superior performance on FFSP. Additional problem and experimental details are available Appendix A.3 and Appendix B.3, respectively.
Source code is available https:://ght com/ a14o/parcc
7

---

Table 1: Main results on different problems with different configurations for problem size N and number of
agents M. For all metrics, the lower the better (L).
HCVRP
100
M
3
5
Metric
Obj.
Gap
Time
Ob)
Gap
Time
Ob)
Gap
Time
Obj
Gap
Time
Obj
Gap
Time
Obj.
Gap
Time
SISRs
6.57
0.00%
4.00
0.00%
274x
2.91
0.00%
276
10.29
0.008
615%
6.17
0.00%
623%
4.45
0.00%5
625c
GA
9.21
40.18%
2334
6.89
72.25%
320s
5.98
105
50%
405s
15,33
48.98%
47%
10.93
77.15%
6236
9.10
104,49%
7724
SA
7,04
7.15%
130s
1.39
9.75%
2894
3.30
13.40%
362s
11.13
8.16%
434k
6.80
10.21%
557s
5.01
12.58%
678s
AM (e)
29.22%
5.51
37.75%
0.08%
4.15
42.61%
23 23%
0.14s
8.10
31
0.13%
6.13
37.75%
0.136
ET (g-)
7.58
15.37%
0.15s
4.76
19.00%
0.17s
3.58
23.02%
0.16s
11.74
14.09%
0.25p
7.25
17.50%
0.25%
5.23
17.53%
0.26s
DPN (g.)
14.16%
0.18s
4.60
15.00%
0.19s
3.45
18.56%
11.54
12.15%
0.30s
6.94
12,48%
0,40s
4,98
11.91%
0.43s
DRL (8.)
7.43
13.09%
0.19:
4.71
17.75%
0.22s
3.60
23.71%
0.25s
11.44
11.18%
0.32s
7.06
14,42%
0.37%
5.38
20.90%
0.43s
2D-PI (R-)
7.30
9.59%
0.116
4.48
12.000%
0.11s
3,31
13.75%
0.1
11.12
0.7%
0.18
6.75
9.40%
0.18%
4,92
10.36%
0.17%
PARCO (g)
7.12
8.37%
0.04s
4,40
10.00%
0.05%
3.25
11.68%
0.05%
10,98
6.71%
0.06s
6.61
7.13%
0.05%
4.79
7.64%
0.05s
AM (x.)
7.62
15.98%
0.14s
1.82
20.50%
0.13s
3.63
24.74%
0.1
11.82
14.87%
0.29%
7.45
20.75%
0.28:
5.58
25.39%
0.28
(R.)
8.68%
4,46
11.50%
0.22s
3.33
14.43%
11.20
8.84%
0.43s
6.85
11,02%%
4.98
11.91%
0.40s
DPN (R)
7.08
7.76%
0.254
4.35
8.75%
0.28
3.20
9.97%
0.38%
11.04
7.29%
01.4%
6.66
7.94%
0.52:
4.79
7.64%
0.78%
DRL (A.)
6.97
6.09%
0.304
4.34
8.50%
0.36s
3:25
68.
0.43c
10.90
5.93%
0.60%
6.65
7.78%
0.76a
4.98
11.91%
0.92s
2D-Pu (c)
6.82
3.81%
0.136
4.20
5.00%
0.13s
3.09
6.19%
0.14g
10.71
4.08%
0.22%
6.46
4.70%
0.23%
4.68
5.17%
0.24s
PARCO (s.)
6.82
3.81%
0.05
4.17
4.25%
0.05g
3.06
5.15%
0.07%
10.61
3.11%
0.08g
6.36
3.08%
0.08g
4.58
2.92%
0.09s
OMDCPDP
N
50
100
M
5
10
10
15
20
Mitriic
Gap
Obi
Gap
Time
Obj
Gapp
Obj
Gap
Time
Gap
Time
Obj
Gap
Time
OR-Toool
37.61
4.61%
30s
30.18
3,38%
30s
24.48
1,79%
30s
66.78
4.99%
60%
51,49
3.15%
60x
43.90
1.53%
60s
HAM (g.)
39.67
10.30%
0.11s
31.49
7.85%
0.11s
29.24
21.23%
0.13%
71.12
11.60%
0.24g
54.31
8.69%
0.276
53.73
23.93%
0.29;
MAPDP (g.)
37.36
4.09%
0.024
30.36
4.08%
0.01s
24.88
3.46%
0.01s
66.54
4.71%
0.03s
52,08
4.34%
0.01s
44.71
3.40%
0.01s
PARCO (8)
37.27
3.84%
0.024
30.12
3.27%
0.01s
24.72
2.81%
0.01s
65.85
3.67%
0.02%
51.48
3.11%
0.01s
44.46
2.84%
0.01s
HAM DX)
36.26
1.17%
1.184
29.54
1.38%
1.31s
27.77
15.24%
1.37%
66.91
5.29
2.33
$1.60
3.42%
2.53%
52.24
20.32%
2.725
MAPDP (x.)
35.64
0.02%
0.024
29.03
0.23%
0.02g
23.97
0.35%
0.01s
63.64
0.65%
0.03g
50.07
0.75%
0.03g
43,57
1.13%
0.02s
PARCO (s.)
35.64
0.00%
0.03%
28.96
0.00%
0.02s
23.89
0.00%
0.02s
63.20
0.00%
0.04g
49.69
0.00%
0.03g
43.08
0.00%
0.03s
FTSP
N
20
50
100
50
M
12
18
24
30
Metric
Gap
Time
Ob)
Gap
Time
Obj.
Gap
Obj
Gap
Time
Gap
Time
Oby
Gap
Time
Gurohi (1m)
38.29
42.4%
60s
60s
60%
60%
60s
60s
Gurohi (10m)
31.61
27.6%
600s
600s
600s
600s
600s
600ss
Random
47.89 93.3%
0.18:
93.34
89.4%
0.37%
167.22
86.9%
0.72x
67.03
112.1%
0.33s
54,48
130.9%
0.33%
46.84
137.0%
0.375
SJF
31:27 26.2%
0.13:
56.94
15.6%
0.34s
99.27
11.0%
0.62s
38.01
20.3%
0.25
29.39
24.6%
0.25%
24.62
24.6%
0.29:
GA
31.15 25.7%
21s
56.92
15.5%
44s
99.25
10.9%
89s
38.26
21.1%
47%
29.05
16.7%
50s
24.52
24.1%
55s
PSO
29.10
17.4%
46s
55.
10
11.8%
82s
97.3
8.8%
184s
56.83
16.6%
85s
28.06
12.7%
89%
23.44
18.6%
95s
MatNet (g.)
27.26
10.0%
1.225
51.52
4.6%
2.17%
91.58
2.4%
4.97%
34,82
10.2%
2.42%
27.52
16.7%
2.65%
23.65
19.7%
3.09
PARCO (g.)
26.31
6.2%
0.26s
51.19
3.9%
0.52g
91.29
2.0%
0.89%
32,88
4.1%
0.50s
24.89
5.5%
0.44s
20.29
2.7%
0.41s
MatNet (X)
23.44
2.7%
3.885
49.68
0.8%
8.91s
89:72
0.3%
18s
33:45
5.9%
9.23%
26.00
10.2%
9.81s
22,31
13.9%
11s
PARCO (s.)
24.78
0.0%
49.27
1.97
89.46
4.04g
31.60
1.8%
23,59
0.0%
1.68%
0.0%
1.54s
5.2
Experimental Results
We report the main empirical results for HCVRP, OMDCPDP, and FFSP in Table 1, with average objective function values (Obj.), gaps to the best-known solutions, and inference times for solving each single problem instance. For neural baselines, we evaluate both greedy (g.) and sampling (s.) performance, using 1280 sampled solutions for routing problems and 128 for FFSP.
In HCVRP, PARCO outperforms all neural baselines in solution quality and speed while providing solutions at a fraction of the solving time required by traditional solvers. In OMDCPDP, our model surpasses all baselines, including OR-Tools. Notably, while the AR baseline HAM struggles with larger number of agents M. PARCO's parallel AR method maintains strong performance across all scales. In FFSP, PARCO outperforms traditional solvers (e.g.. Gurobi cannot find solutions in time for N > 20), dispatching rules, and MatNet in all tested scenarios while being more than 4x faster. Furthermore, similar our results in routing, PARCO's advantage becomes even more pronounced in instances with a larger number of agents where PARCO generates higher-quality schedules through effective agent coordination at a fraction of the cost of MatNet.
5.3 Analysis
Effect of Communication Layers We showcase the importance of Communication Layers in Fig. 3a. We benchmark different ways to obtain decoder queries (see 4.5) with 1) No communication (W/o Comm., i.e., with only context features), 2) MLP, 3) MHA, 4) our transformer-base based Com-
8

---

Table 2: Generalization for unseen numbers of nodes N and agents M (up to 10x those seen during training).
500
1000
Menie
Obj.
Gap
Time
Obj
Gop
Time
Obg.
Gap
1100
Obj
Gap
Time
Obj.
Gap
Time
Obj
Gap
Time
OR-Tools
290.79
7.81%
300s
223.72
4.68%
300s
192.59
1.51%
300s
780.89
33.93% 600s 642.54 36.47%
600s
584.27
56.81%
600s
HAM (e)
410.95
55.44%
1.03
310.17
48.72%
1.156
204.00
9.91%
1.23%
710.64
40.92% 2,43s (54.15
39.41%6
2,66s
368.56
8.88%
2.9%s
PARCO (x)
268.56
1.41%
0.02s
211.21
1.13%
0.024
187.37
0.83%
0.01s
510.61
0.81% 0.02s 401.46
0.61%
0.02s
389,98
0.19%
0.02s
HAM (6))
418.67
54,95%
1.19
805.16
16
46.
32%6
1.31s
203.50
9.64%
1.3%
708.55
40 50%
2.94s 552.76 390866
3.22%
384.10
7.63%
3.46s
PARCO
0.03%
208.56
0.00%
0.00%
504.30
0.0%%
0.79%
0.91s
356.87
1.26s
36
Ave aap Decoding Stage
1.0
I (
Tioe pcr Egosd
42-
(a) Effect of communication
(b) Dacoding stops and training time
(c) Efficct of conflict handleor
Figure 3: Analysis of PARCO components.
munication Layers (Comm.). Our Communication I Layers consistently outperform other methods. Fig. 3b shows decoding steps and training times the FFSP for N 50. PARCO greatly reduces the number of steps and training times, with Communication Layers further reducing them through better coordination, especially at a higher number of agents M.
Effect of Conflict Handlers In Fig. 3c, we compare 1) the random handler from MAPDP and our proposed Priority-based Conflict Handlers in different configurations, namely with priorities based on simple heuristics as 2) "smallest" prioritizing the agent with the lowest cost so far, and 3) "closest", prioritizing agents closer the corresponding node, and finally 4) "learned" based on model output probabilities. The latter consistently outperforms other methods, which also enjoy a relative reduction the number of steps for constructing a solution, e.g., with a 4% reduction conflict rates.
Large-Scale Generalization We study the zero-shot large-scale generalization performance of PARCO in the OMDCPDP and report the results in Table 2 for nodes N and agents M, both up to 10x those seen in training. We find that the AR HAM baseline cannot generalize well such scales due the lack of communication and robust parallel construc- tion, while MAPDP cannot be applied to an unseen M because of its inflexible decoder structure. Conversely, our method outperforms all baselines, cluding Oo-lo with a 10-minute solving time per instance for N 1000, making PARCO strong can- didate for real-time deployment.
numbers of
Method (M Agents)
2.00
PAIC D (10)
1.75
ARR (50)
PARCO (S0)
1.50
Inference Time
1.25
PARCO AR Models Scalability Finally, we showcase PARCO's speedups against autoregressive methods in Fig. 4. Notably, compared AR mod- els (c.g., DPN, HAM), PARCO achieves significant speedups of 3.3x up 24.7x, with inference time de- creasing as the number of agents M increases: thanks to parallel decoding, fewer solution construction steps for larger M lead to substantially lower latency.
Speedup (20): 6.5x
Specdup (50): 21.7x
0.70
0.26
0.00
Problem Size IV
Figure 4: PARCO AR inference time. PARCO constructs solutions faster with more agents M.
6 Conclusion
We introduced PARCO, learning model to tackle multi-agent combinatorial optimization problems efficiently via parallel autoregressive solution construction. By integrating transformer-basee Com- munication Layers, a Multiple Pointer Mechanism, and Priority-baseed Conflict Resolution, PARCO enables effective agent coordination and significantly reduces computational latency. Our extensive experiments on multi-agent vehicle routing and scheduling demonstrate that PARCO consistently outperforms state-of-the- the learning-base solvers with better solution quality and higher efficiency.

---

Limitations & Future Work Although PARCO can efficiently solve multi agent CO problems with a defined number of agents M, it cannot be directly applied to CO tasks where solutions are constructed via an unspecified M. In future work, we plan to explore multi-agent CO problems with an unspecified number of agents, which could be achieved by either rolling out a batch of several values of M until an optimal solution is reached or by employing prediction module to predict an optimal agent number. We defer additional discussions to Appendix C.I.
Acknowledgements We deeply grateful to the members of the AI4CO open research community for their invaluable contributions to PARCO and related projects, including RI4CO. We also thank the anonymous reviewers who greatly helped improve our paper with their constructive feedback. This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant, funded by the Korean government (MSIT) [Grant No. 2022-0-01032. Devel- opment of Collective Collaboration Intelligence Framework for Internet of Autonomous Things]; National Research Foundation of Korea(NRF)) grants funded by the Korea government (No. and No. RS-2025-005637633, and by the InnoCORE program of the Ministry of Science and I0255102)
References
[1] C. Arehetii and L. Bertazzi. Recent challenges in routing and inventory routing: E-commerce and last-mile delivery. Networks, 77(2):255-266 2021.
[2] R. Baldacci, M. Battarra, and D. Vigo. Routing a heterogeneous fleet of vehicles. The vehicle routing problem: latest advances and new challenges, pages 3-27, 2008.
[3] I. Bello, H. Pham, Q. V. Lc, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arX:v:1661.009:
2016.
[4] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: methodological tour d' horizon. European Journal of Operational Research, 290(2):405 421, 2021.
[5] F. Berto, C. Hua, J. Park, L. Luttmann, Y. Ma, F. Bu, J. Wang, H. Ye, M. Kim, S. Choi, N. G. Zepeda, A. Hottung, J. Zhou, J. Bi, Y. Hu, F. Liu, H. Kim, Son, H. Kim, D. Angioni, W. Kool, Z. Cao, J. Zhang, K. Shin, C. Wu, S. Ahn, G. Song, C. Kwon, L. Xie, and J. Park. RLACO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
[6] F. Berto, C. Hua, N. G. Zepeda, A. Hottung, N. Wouda, L. Lan, J. Park, K. Tierney, and J. Park. RouteFinder: Towards Foundation Models for Vehicle Routing Problems. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https: //tp///veeeeeeeeee/eeeeeeeeeeeee net/ forum?id-Q2GLoapPP:
[7] J. Bi, Y. Ma, Zhou, W. Song, Z. Cao, Wu, and Zhang. Learning handle complex constraints for vehicle routing problems. arXiv preprint arXiv:2410.2 1066, 2024.
[8] C. Bonnet, D. Luo, D. Byrne S. Surana, S. Abramowitz, P. Duckworth, V. Coyette, L. I. Midgley, E. Tegegn, Kalloniatis, et Jumanji: diverse suite of scalable reinforcement learning environments in jax. ICLR, 2024.
[9] C. Boutilier. Planning, learning and coordination in multiagent decision processes. In TARK, volume 96, pages 195-210, 1996.
[10] Y. Cao, Z. Sun, and Sartoretti. Dan: Decentralized attention-basee neural network for the minmax multiple traveling salesman problem. In International Symposium on Distributed Autonomous Robotic Systems, pages 202-215. Springer, 2022.
[11] J. Chen, Wang, Z. Zhang, Z. Cao, Ye, and S. Chen. Efficient meta neural heuristic for multi-objective combinatorial optimization. arXiv preprint arXiv:23 20.i::2330..1/10 2023.
[12] J. Christiaens and G. Vanden Berghe. Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2):417-45 2020.
[13] Corsini, A. Porrello, S. Calderara, and M. Dell' Amico. Self-labeling the job shop scheduling problem. arXiv preprint arXiv:2401.11849, 2024.
10

---

[14] D. Drakulic, S. Michel, F. Mai, A. Sors, and J.-M. Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[15] D. Drakulic, S. Michel, and J.-M. Andreoli. Goal: A generalist combinatorial optimization agent learning. In International Conference Learning Representations, 2025.
[16] L. Duan, Y. Zhan, H. Hu, Y. Gong, J. Wei, X. Zhang, and Y. Xu. Efficiently solving the practical vehicle routing problem: novel joint learning approach. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 3054-3063, 2020.
[17] W. Falcon and The PyTorch Lightning team. PyTorch Lightning, 3 2019. URL https:
[18] J. K. Falkner and L. Schmidt-Thieme.. Learning solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006. 09 100, 2020.
[19] V. Furnon and L. Perron. Or-tools routing library, 2024. URL https://developers.
google. wtt.coooooo/// http///ptiizzaioo/rrttttto
[20] C. Gao, H. Shang, K. Xue, D. Li, and C. Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv preprint arXiv:2308. 14104, 2023.
[21] X. Gao, W. Xie, Y. Xiang, and F. Ji. Falcon: Faster and parallel inference of large language models through enhanced semi-autoregressiv drafting and custom- dessonddesigned decoding tree. arXiv preprint arXiv:2412.12639 2024.
[22] L. Goh, Y. Ma, J. Zhou, Z. Cao, M. H. Dupty, and W. S. Lee. Shield: Multi-task multi- distribution vehicle routing solver with sparsity hierarchy in efficiently layered decoder. In ICML, 2025.
[23] N. Grinsztajn, D. Furelos-Blanco, S. Surana, C. Bonnet, and T. Barrett, Winner takes it all: Training performant populations for combinatorial optimization. Advances in Neural Information Processing Systems, 01448485-45500 2023.
[24] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL httpp://ww/tt gurobi. com.
[25] S. R. Hejazi and S. Saghafian. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, 43(14))2895-292) 29299, 2005.
[26] A. Hottung, Y.-D. Kwon, and K. Tiemney Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106.00 05 126, 2021.
[27] A. Hottung, F. Berto, C. Hua, N. G. Zepeda, D. Wetzel, M. Römer, H. Ye, D. Zago, M. Poli,
S. Massaroli, J. Park, and K. Tiemney. Vrpagent: LIm-driven discovery of heuristic operators for vehicle routing problems, 2025. URL btttps://arsiei org abs/2510.......//////////// /ttob//000077333....
[28] A. Hottung, P. Wong-Chung and K. Tierney. Neural deconstruction search for vehicle routing problems. Transactions on Machine Learning Research, 2025.
[29] C. Hua, F. Berto, J. Son, S. Kang, C. Kwon, and J. Park. CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems. In Proceedings of the 2025 International Conference
Autonomous Agents and Multiagent Systems (AAMAS), 2025. https://
github. com/ ai ai4co/ camp.
[30] C. Hua, F. Berto, Z. Zhao, J. Son, C. Kwon, and J. Park. Uspr: Learning unified solver for profiled routing, 2025. URL https : //arxiaa.vvv////////// org/ abs//505.. 05119.
[31] Z. Huang, Zhou, Z. Cao, and Y. Xu. Rethinking light decoder-based solvers for vehicle routing problems. In International Conference on Learning Representations, 2025.
[32] i. ilhan. An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem. Swarm and Evolutionary Computation, 64: 64:100911, 2021.
[33] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Intermational conference on machine learning, pages 448-456. pmlr, 2015.
[34] X. Jiang, Y. Wu, Y. Wang, and Y. Zhang. Unco: Towards unifying neural combinatorial
optimization through large language model. arXiv preprint arXiv:2408. 2024.
11

---

[35] Y. Jin, Y. Ding, X. Pan, K. He, L. Zhao, T. Qin, L. Song, and J. Bian. Pointerformer: Deep reinforeed multi-pointer transformer for the traveling salesman problem. arXiv preprint arXiv:2304.0940 2023.
[36] M. Jünger, G. Reinelt, and G. Rinaldi. The traveling salesman problem. Handbooks in operations research and management science, 7:225-330, 1995.
[37] J. Jungwattanakit, M. Reodecha, P. Chaovalitwongse, and Werner. Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. The International Journal of Advanced Manufacturing Technology, 37:354-370, 2008
[38] C. Kahraman, O. Engin, I. Kaya, and M. K. Yilmaz. An application of effective genetic algorithms for solving hybrid flow shop scheduling problems. International Journal of Computational Intelligence Systems, 1(2):134-147 1473,,44,,4 2008.
[39] S. Karakatič and V. Podgorelec. A survey genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27:519-523 2015.
[40] H. Kim, M. Kim, S. Ahn, and J. Park. Symmetric exploration in combinatorial optimization is free! arXiv preprini arXiv:2306.012760 2023.
[41] H. Kim, M. Kim, F. Berto, J. Kim, and J. Park. Devformer: A symmetric transformer for context-aware device placement. In International Conference Machine Learning, pages 16541-16566. PMLR, 2023.
[42] H. Kim, S. Choi, J. Son. J. Park, and C. Kwon. Neural genetic search in discrete spaces, In International Conference on Machine Learning, 2025.
[43] M. Kim, J. Park, and Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2022.
[44] M. Kim, T. Yun, E. Bengio, D. Zhang, Y. Bengio, S. Ahn, and J. Park. Local search gflownets. arXiv preprint ar.iv:2310.027 10, 2023.
[45] M. Kim, S. Choi, H. Kim, J. Son, J. Park, and Y. Bengio. Ant colony sampling with gflownets for combinatorial optimization. In AISTATS, 2025.
[46] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6940 2014.
[47] W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019, URL https://openrrrvei Bttp//ormmmii--yyBBaee
[48] W. Kool, H. van Hoof, and M. Welling. Buy reinforce samples, get baseline for free! 2019.
[49] Y.-D. Kwon, J. Choo. B. Kim, I. Yoon, Y. Gwon, and Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 18888881999 198, 2020.
[50] Y.D. Kwon, J. Choo, I. Yoon, M. Park, D. Park, and Y. Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 34, pages 5138-5149, 2021.
[51] G. Laporte and H. Osman, Routing problems: A bibliography. Annals of operations research, 61:227-262, 1995.
[52] Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[53] H. Li, F. Liu, Z. Zheng, Zhang, and Z. Wang. Cada: Cross-problem routing solver with constraint constrain--wware dual-attention. arXiv preprint arXiv:2412.003466, 2024.
[54] J. Li, L. Xin, Z. Cao, A. Lim, W. Song, and J. Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. JEEE Transactions on Intelligent Transportation Systems, 23(3):2306-23 2021.
[55] J. Li, Y. Ma, R. Gao, Z. Cao, L. Andrew, W. Song, and J. Zhang. Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. IEFE Trunsactions on Cybernetics,
2022. doi: 00.1109/CCYB.2221311100
12

---

[56] S. Li. Z. Yan, and C. Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pages 26198-26211, 2021.
[57] Y. Li, J. Guo, R. Wang, and J. Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
[58] Y. Li, J. Guo, R. Wang, H. Zha, and J. Yan. Fast 12t:
Optimization consistency speeds up diffusion-base training-too to-testing solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37, 2025.
[59] Li, J. Ma, W. Pan, R. Wang, methodological principles for tsp and beyond from streamlined design space of learning and search. In The Thirteenth International Conference on Learning Representations, 2025.
Geng, N. Yang, and J. Yan. Unify ml4tsp: Drawing
[60] F. Liberatore, M. T. Ortuño, G. Tirado, B. Vitoriano, and M. P. Scaparra. A hierarchical compromise model for the joint optimization of recovery operations and distribution of emergency goods in humanitarian logistics. Computers & Operations Research, 42:3-13, 2014.
[61] F. Liu, X. Lin, Z. Wang, Q. Zhang, Xialiang, and M. Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1898-1908, 2024.
[62] F. Liu, T. Xialiang, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, and Q. Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the s International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 32201-32223, PMLR, 21-27 Jul 2024. URL https: http:////oceeeeigss//ee mlr press/v235/ 1iu24bs..... html.
[63] Q. Liu, C. Liu, S. Niu, C. Long, J. Zhang, and M. Xu. 2d-ptr: 2d array pointer network for solving the heterogeneous capacitated vehicle routing problem. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 1238-1246, 2024.
[64] F. Luo, X. Lin, F. Liu, Q. Zhang, and Z. Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. arXiv preprint arXiv:23 2023.
[65] F. Luo, X. Lin, Z. Wang, X. Tong, M. Yuan, and Q. Zhang. Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561, 2024.
[66] L. Luttmann and L. Xic. Neural combinatorial optimization on heterogeneous graphs: An application to the picker routing problem in mixed-shelves warchouses. In Proceedings of the International Conference Automated Planning and Scheduling, volume 34, pages 351-359, 2024.
[67] L. Luttmann and L. Xic. Learning to solve the min-max mixed-shelves picker-routing problem via hierarchical and parallel decoding, 2025. URL https:
/a0.ab////22222532222 10233. [68] I.. Luttmann and Xie. Multi-action self eef--imtrveement neural combinatorial optimization, 2025. URI. /esttss//arssee orgg /2100 12273.
[69] Y. Ma, Li, Z. Cao, W. Song, L. Zhang, Z. Chen, and J. Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-11109) 2021.
[70] Y. Ma, Z. Cao, and Y. M. Chee. Learning search feasible and infeasible regions of routing problems with flexible neural k-opt. Advances in Neural Information Processing Systems, 36, 2024.
[71] Z. Ma. H. Guo, J. Chen, Z. Li, G. Peng, Y.J. Gong, Y. Ma. and Z. Cao. Metabox: A benchmark platform for meta- siluu-lack-brr optimization with reinforeement lcarning. arXiv preprint urXiv:2310.08255 2023.
[72] S. Mahmoudinazlou and C. Kwon. A hybrid genetic algorithm for the min- multiple traveling salesman problem. Computers Operations Research, 162:106455, 2024.
[73] L. Matignon, G. J. Laurent, and N. Le Fort-Piat. Independent reinforcement learners in cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
13

---

[74] N. Mazyavkina. S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combina- torial optimization: A survey, Computers & Operations Research, 134: 105400, 2021.
[75] J. Park, C. Kwon, and Park. Learn to solve the min-max max multiple traveling salesmen problem with reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 878-886, 2023.
[76] J. Park, Kwon, and J. Park. Learn solve the min- max multiple traveling salesmen problem with reinforcement learning. In AAMAS, pages 878-886, 2023.
[77] S. N. Parragh, K. F. Doerner, and R. F. Hartl. A survey on pickup and delivery problems: Part i: Transportation between eustomers and depot. Journal für Betriebswirtschaf,, 58:21-51, 2008.
[78] A. Paszke, S. Gross, F. Massa, A. Lever, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in neural information processing systems, 2019.
[79] F. Peres and M. Castelli. Combinatorial optimization problems and metaheuristics: Review, challenges, design, and development. Applied Sciences, 11(14):6449, 2021.
[80] J. Pirnay and D. G. Grimm. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. arXiv preprint arXiv:2403.15746 2024.
[81] M. R. Singh and S. Mahapatra. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. The International Journal of Advanced Manufacturing Technology, 62:267-277, 2012.
[82] J. T. Soman and R. J. Patil. A scatter search method for heterogeneous fleet vehicle routing problem with release dates under lateness dependent tardiness costs. Expert Systems with Applications, 150:1 13302, 2020.
[83] J. Son, M. Kim, H. Kim, and J. Park. Meta-sage: Scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. arXiv preprint arXiv:2306. 02688, 2023.
[84] J. Son, M. Kim, S. Choi, H. Kim, and J. Park. trunty-transformer. Solving np-hard min max routing problems as sequential generation with equity context. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 10265-20273 2024.
[85] Z. Sun and Y. Yang. Difusco: Graph- based diffusion solvers for combinatorial optimization. arXiv preprint arXiv:2302.08 08224,, 2023.
[86] C. D. Tran, Q. Nguyen-Tri -rii H. T. T. Binh, and H. Thanh-Tung. Large language models powered neural solvers for generalized vehicle routing problems. In Towards Agentic Al for Science: Hypothesis Generation, Comprehension, Quantification, and Validation, 2025. URL https://openreva
net /tte///rrmmiddd//jiiie.e
[87] D. Ulyanov, A. Vedaldi, and V. Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv:1607.08022 2016.
[88] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, E.. Kaiser, and
1. Polosukhin. Attention is all you need. In Advances in neural information processing systems, 2017.
[89] O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[90] Y. Wang, Y.-H. Jia, W.-N. Chen, and Y. Mei. Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems, Jan. 2024. URL attp://arxxx
org/ abs/ 06979. (XXi:22401.06977 [cs].
[91] J. M. Weinand, K. Sörensen, P. San Segundo, M. Kleinebrahm, and R. McKenna. Research trends in combinatorial optimization. International Transactions in Operational Research, 29 (2):667-705, 2022.
[92] J. Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-25 226,, May 1992. ISSN 0885-6125, 1573-0565. doi: 10. F0.0000/0F0099666.
[93] Z. Yan and C. Wu. Neural neighborhood search for multi-agent path finding. In The Twelfth International Conference on Learning Representations, 2024.
14

---

[94] Y. Yang and A. Whinston. A survey on reinforcement learning for combinatorial optimization. In 2023 IEEE World Conference on Applied Intelligence and Computing (AIC), pages 131-136. IEFE, 2023.
[95] H. Ye, J. Wang, Z. Cao, H. Liang, and Y. Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[96] H. Ye, J. Wang, H. Liang, Z. Cao, Y. Li, and F. Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. arXiv preprint arXiv:2312.08222 2023.
[97] H. Ye, J. Wang. Z. Cao, F. Berto, C. Hua, H. Kim, J. Park, and G. Song. Reevo: Large language models as hyper-heuristies with reflective evolution. Advances in Neural Information Processing Systems, 2024. https: //gi thub. com/ai4co/
[98] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu. The surprising effectiveness of ppo in cooperative multi-agent games. In Advances in Neural Information Processing Systems, volume 35, pages 24611-24624, 2022.
[99] N. G. Zepeda, A. Hottung, and K. Tiemmyy Learning to solve the skill vehicle routing problem with deep reinforcement learning. In THE 19TH LEARNING AND INTELLIGENT OPTIMIZA- TION CONFERENCE, 2025. URL
[100] B. Zhang and R. Sennrich. Root mean square layer normalization. In Advances in Neural Information Processing Systems, 2019.
[101] C. Zhang, W. Song, Z. Cao. J. Zhang, S. Tan, and X. Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances neural information processing systems, 122166211633 2020.
[102] K. Zhang, F. He, Z. Zhang, X. Lin, and M. Li. Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach. Transportation Research Part C: Emerging Technologies, 121:102861, 2020.
[103] N. Zhang, J. Yang, Z. Cao, and X. Chi. Adversarial generative flow network for solving vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025.
[104] Z. Zheng. Yao, Z. Wang. X. Tong. M. Yuan, and K. Tang. Dpn: Decoupling partition and navigation for neural solvers of min-max vehicle routing problems. arXiv preprint urXiv:2405. 17272, 2024.
[105] Z. Zheng, C. Zhou, T. Xialiang, M. Yuan, and Z. Wang. Ude: A unified neural divide- and-conquer framework for large-scale combinatorial optimization problems. arXiv preprint arXiv:2407.0033
2024.
[106] J. Zhou, Y. Wu, Z. Cao, W. Song, J. Zhang, and Z. Chen. Learning large neighborhood search for vehicle routing in airport ground handling. IEEE Trunsactions on Knowledge and Data Engineering, 2023.
[107] J. Zhou, Z. Cao, Y. Wu, W. Song. Y. Ma, J. Zhang, and C. Xu. Mvmoe: Multi-task vehicle routing solver with mixture-of-eeperts. arXiv preprint arXiv:2405.01029, 2024.
[108] Z. Zong, M. Zheng, Y. Li, and D. Jin. Mapdp: Cooperative multi-agent reinforcement learning to solve pickup and delivery problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9980-9988 2022.
15

---

PARCO:
Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization Supplementary Material
A Problem Definitions
A.1 HCVRP
The min-max HCVRP (Heterogeneous Capacitated Vehicle Routing Problem) consists of M agents sequentially visiting customers to satisfy their demands, with constraints including each customer can be visited exactly once and the amount of demand satisfied by single vehicle in trip cannot exceed its capacity, which can be reloaded by going back to the depot. The goal is to minimize the makespan, i.e., the worst route.
Consider a problem with N + nodes (including customers and a depot) and M vehicles. The depot is indexed as O, and customers are indexed from to N.
Indices
Node indices, where i,j 0, N (0 represents the depot) Vehicle index, where k = 1,...,M M
Parameters
N
Number of customer nodes (excluding depot)
M
Number of vehicles
X;
Location of node
d,
Demand of node i (do = 0 for the depot)
Qs
Capacity of vehicle &
Speed of vehicle k
Gj
Distance between nodes and j
Decision
Variables
1 if vehicle & travels directly from node node
Tijk
0 otherwise
ligk
Remaining load of vehicle & before travelling from node to node j
Objective Function:
N N
min max
ΣΣ
zigh
fr
i=0 ==
16

---

Subject to:
N
Tijk =
I,,..
(10)
1=
1=0
Tijk
Jjhk 0
O, ,,,..,,,,, k , m
(11)
N
Lisk
jhk = d3
= I,...,N N
(12)
R=1
t=
R=1 h=0
dyzigk S Ligk 2 (Qs- d.) Zigh
1, = 0, N, h ,,..., m
(13)
Tijk {0,
1. = 0. N, k
(14)
4isk 2 0, d 2 0
1, = 0 N, h = 172
(15)
Constraint Explanations: The formulation subject to several constraints that define feasible solution space. Eq. (10) ensures that each customer is visited exactly once by one vehicle. The flow conservation constraint (11) guarantees that each vehicle that enters node also leaves that node, maintaining route continuity. Demand satisfaction is enforeed by constraint (12), which ensures that the difference in load before and after serving a customer equals the customer's 's demand. The vehicle capacity constraint (13) ensures that the load carried by vehicle does not exceed its capacity and is sufficient to meet the next customer's demand.
A.2 OMDCPDP
The OMDCPDP (Open Multi-Depot Capacitated Pickup and Delivery Problem) is practical variant of the pickup and delivery problem in which agents have stacking limit of orders that can be carried at any given time. Pickup and delivery locations are paired, and pickups must be visited before deliveries. Multiple agents start from different depots without returning (open). The goal is minimize the sum of arrival times to delivery locations, i.c., minimizing the cumulative lateness.
Indices
i.j
Node indices, where i,j = 1......2... Vehicle index, where k = I,...,M M
2N .2N
k
Sets
P
Set of pickup nodes, P (1..... N) Set of delivery nodes, D = (N 2N}
D
Parameters
N
Number of pickup-delivery pairs
M
Number of vehicles
Cyj
Travel time between nodes and j
Q
Capacity (stacking limit) vehicle
ok
Initial location (depot) of vehicle
Decision Variables
1
if vehicle A: travels directly from node i to node otherwise
Tisk
0
1 if vehicle visits node
Yik
0 otherwise
t;
Arrival time at node
lik
Load of vehicle & after visiting node
Objective Function:
min
Σ
(16)
N+1
17

---

Subject to:
Vlik
i 1,... 2N
(17)
2N
I Fog.j.k =
h 1,...,m m
(18)
j=1
2N
Tiyk
Σ Jyhk-
j L, 1,...,,,........... ......,,,,..... k= -.1, I....,
(19)
2N
Vik =
Σ
Bisk
i 1-.,,,,,,,,,. d: = 1,...,
(20)
j=1
4 + Cij M(1 Tijk) $ 1
i 1 2N, k = 1, iEP
(21)
1, 5 1
(22)
4k + 1 - -M - zijk) / 1μK
iEP N 1
(23)
4i M(1 Tisk) 2 15k
iED, N, ..... 1
(24)
0 S Lı < Q
i= 2N, A == -1, 1,...,
(25)
Figk: Vik {0, 1}
i.j =1 1.j=1..... 2N, -1..... m
(26)
4 2 0
i == 1, 2N
(27)
Constraints Explanations: Eq. (17) ensures that each node is visited exactly once. Constraint (18)
guarantees that each vehicle starts from its designated depot. The flow conservation constraint (19) ensures route continuity for each vehicle. Eq. (20) defines the relationship between x and y variables. Time consistency is enforced by constraint (21). while (22) ensures that pickups are visited before
their corresponding deliveries. Constraints (23) and (24) manage the load changes during pickup and delivery operations. Finally, the vehicle capacity constraint (25) ensures that the load never exceeds the vehicle's s stacking limit.
Visualization
We provide a visualization of a large-scale instance in Fig. 5.
Figure 5: Real-world instance for the OMDCPDP problem in Seoul City, South Korea, with N 1000 locations and 100 agents showing relations (-) pickups and their respective deliveries (x).
18

---

A.3 FFSP
The flexible flow shop problem (FFSP) is challenging and extensively studied optimization problem in production scheduling, involving N jobs that must be processed by total of M machines divided into i 1.... S stages, each with multiple machines (m; 1). Jobs follow a specified sequence through these stages, but within each stage, any available machine can process the job, with the key constraint that no machine can handle more than one job simultaneously. The FFSP can naturally be viewed multi-agent CO problem by considering each machine an agent that constructs its own schedule. Adhering to autoregressive CO, agents construct the schedule sequentially, selecting one job (or no job) at time. The job selected by machine (agent) at specific stage in the decoding process is scheduled at the earliest possible time, that is, the maximum of the time the job becomes available in the respective stage (i.e., the time the job finished on prior stages) and the machine becoming idle. The process repeats until all jobs for each stage have been scheduled, and the ultimate goal is to minimize the makespan, i.e., the total time required to complete all jobs.
Mathematical Model FFSP:
We use the mathematical model outlined in Kwon et al. [50] to define the
Indices
i
Stage index
j.1
Job index
k
Machine index in each stage
Parameters
N
Number of jobs
S
Number of stages
my
Number of machines in stage
M
A very large number
Pijk
Processing time of job j in stage on machine
Decision variables
Cj
Completion time of job j in stage i
1 if job is assigned to machine k in stage i
Xizk
0 otherwise
1 if job is processed earlier than job j in stage i
Yaj
0 otherwise
Objective:
max f= {Css}
min
(28)
Subject to:
Xijk
i i= 1, 8; 1,
1,..,,N N (29)
Yús 0
i i= 1 8;
N
(30)
N
Yu
max Σ (Xir)) - 1,0
i i= 1 L,..,, S
(31)
1=1
1=1
J=1
19

---

i 1= - 1.0)
Yuy- S max
max (X + xunk kml...m
5,,.,,,,
(32)
N E
Yuj S
i i=
1=1
(33)
N Σ
Yug 1
i= 1.2,...... 1= .., .V
1=1
(34)
Ci 2
Pijk X1jk
1 == 1.2...., N
(35)
1=1
Ci 2 Ci-1j +
Pijk Xish
2 S; = 1.2,...,
1=1
(36)
m2
C₁ + M(1 Yay)= 2 Ca Σ
Pisk Xisk
i= 1..,...,, S. 1,2,=112..
k=1
(37)
Constraint Explanations: Here, the objective function Eq. (28) minimizes the makespan of the resulting schedule, that is, the completion time of the job that finishes last. The schedule has to adhere to several constraints: First, constraint set (29) ensures that each job is assigned to exactly one machine at each stage. Constraint sets (30) through (34) define the precedence relationships between jobs within a stage. Specifically, constraint set (30) ensures that a job has no precedence relationship with itself. Constraint set (3 ensures that the total number of precedence relationships in a stage equals N that precedence relationships can only exist among jobs assigned the same machine. Additionally, constraint sets (33) and (34) restrict job to having at most one preceding job and one following job.
minus the number of machines with no jobs assigned. Constraint set (32) dictates
Moving on, constraint set (35) specifies that the completion time of job in the first stage must be least as long as its processing time in that stage. The relationship between the completion times of a job in consecutive stages is described by constraint set (36). Finally, constraint set (37) ensures that no more than one job can be processed on the same machine simultaneously.
B Experimental Details
B.1 HCVRP
B.1.1
Baselines
We follow the experimental setup of Liu al. [63] for baselines, with additional baselines hyperpa- rameter details reported in their respective papers.
The Slack Induction by String Removals (SISR) approach [12] offers a heuristic method for addressing vehicle routing problems (VRPs), focusing on simplifying the optimization process. It combines techniques for route dismantling and reconstruction, along with vehicle fleet minimization strategies. SISR is applied across various VRP scenarios, including those with specific pickup and delivery tasks. In our experiments, we adhere to the hyperparameters provided in the original paper
SISR
with ō 10, L max_ 10, a 10-3, B- 2 To 100, Ty 1, iter = 3 10 x N.
20

---

GA The Genetic Algorithm (GA) [39] is used to address vehicle routing problems (VRPs) and other NP-hard challenges by simulating natural evolutionary processes. GA generates adequate solutions with reasonable computational resources. Our experiment follows the same carefully tuned hyperparameters from [63] with n 200, iter = 40 x N, P. = 0.8, Pa 1
SA The Simulated Amnealing (SA) method [32] targets the capacitated vehicle routing problem (CVRP) using a population-baser approach combined with crossover operators. It incorporates local search and the improved 2-opt algorithm to refine routes alongside crossover techniques to speed up convergence. In our experiment, we follow the same carefully tuned hyperparameters from [63] with To = 100, T = 10 ? L = 20 x N, a 0.98.
AM The Attention Model (AM) [47] applies the attention mechanism to tackle combinatorial optimization problems like the Traveling Salesman and Vehicle Routing Problems. It utilizes attention layers for model improvement and trains using REINFORCE with deterministic rollouts. In our studies, we adopt adjustments from the DRL framework, which involves selecting vehicles sequentially and then choosing the next node for each. Additionally, vehicle-specific features are incorporated into the context vector generation to distinguish between different vehicles.
ET The employing sequential planning approach with sequence generators like the Transformer. It focuses on equitable workload distribution among multiple agents, applying this strategy to challenges like the min-max multi-agen traveling salesman and pickup and delivery problems. In our experiments, we modify the decoder mask in ET to generate feasible solutions for HCVRP and integrate vehicle features into both the input layer and the context encoder, similarly to the setting of Liu et al. [63].
(ET) approach [84] addresses large-scale min-max routing problems by
DPN The Decoupling Paiiinng-Paatttin-Naa Naviiainna (DPN) approach [104] a SOTA sequential planning AR baseline that tackles min-max vehicle routing problems (min-max VRPs) by explicitly separating the tasks of customer partitioning and route navigation. introduces a pariition-and-Naviilll (P&N) Encoder to learn distinct embeddings for these tasks, an Dreent-errmtation-SS (APS) loss to leverage routing symmetries, and a Rotation- -ased Positional Encoding to enhance generalization across different depot locations. We employ similar setting ET.
DRL The DRL approach for solving HCVRP by Li et al. [55] employs a transformer architecture similar to Kool et al. [47] in which the vehicle and node selection happens in two steps via a two selection decoder, thus requiring two actions. We employ their original model with additional context of variable vehicle speeds, noting that in the original setting each model was trained single distribution number of agents M, each with always the same characteristics.
2D-Ptr The 2D Array Pointer network (2D-Ptr) [63] addresses the heterogeneous capacitated vehicle routing problem (HCVRP) by using a dual-encoder setup to map vehicles and customer nodes effectively. This approach facilitates dynamic, real-time decision-making for route optimization. Its decoder employs a 2D array pointer for action selection, prioritizing actions over vehicles. The model is designed to adapt to vehicle and customer numbers changes, ensuring robust performance across different scenarios.
B.1.2 Datasets
Train data generation Neural baselines were trained with the specific number of nodes N and number of agents AM they were tested on. In PARCO, we select a varying size and number of customer training schemes: each training step, we sample N (60, 100) and m U(3, 7). As we show in Table I, single PARCO model can outperform baseline models even when they were fitted on specific distribution. The coordinates of each customer location (I;, Vi),, where i 1, 1..... N, are sampled from uniform distribution 2/ (0.0,, 1.0) within a voo-dimensional space. The depot location similarly sampled using the same uniform distribution. The demand d, for each customer i is also drawn from uniform distribution (111, 10), with the depot having no demand, i.e., do = O. Each vehicle m, where m = I,..., M, assigned a capacity Q.. sampled from a uniform distribution (20, 41). The speed fm of each vehicle is uniformly distributed within the range U(0.5, 1.0).
21

---

Testing Testing is performed on the 1280 instances per (N.M) test setting from Liu et al. [63]. In Table 1, (g.) refers to the greedy performance of the model, i.e., taking a single trajectory by taking the maximum action probability; (s.) refers to sampling 1280 solutions in the latent space and selecting the one with the lowest cost (i.e., highest reward).
B.1.3 PARCO Network Hyperparameters
Encoder Initial Embedding. This layer projects initial raw features hidden space. For the depot, the initial embedding is the positional encoding of the depot's location Xo- For agents, the initial embedding is the encoding for the initial location, capacity, and speed. Main Encoder. we employ L = 3 attention layers in the encoder, with hidden dimension da 128, 8 attention heads in the MHA, MLP hidden dimension set to 512, with RMSNorm [100] as normalization before the MHA and the MLP.
Decoder Context Embedding. This layer projects dynamic raw features to hidden space. The context is the embedding for the depot states, current node states, current time, remaining capacities, time of backing to the depot, and number of visited nodes. Multiple Pointer Mechanism. Similarly to the encoder, we employ the same hidden dimension and number of attention heads for the Multiple Pointer Mechanism.
Communication Layer We employ single transformer layer with hidden dimension da 128, 8 attention heads in the MHA, MLP hidden dimension set to 512, with RMSNNrm [100] as normalization before the MHA and the MLP. Unlike the encoder layer, which acts between all M +N problem tokens, communication layers are lighter because they communicate between M agents.
Agent Handler We use the Priority- Conflict Handler guided by the model output probability for managing conflicts: priority is given to the agent whose probability of selecting the conflicting action is the highest (see $ 4.6).
B.1.4 PARCO Training Hy perpararrets
Unlike baselines, which are trained and tested the same distribution, we train single PARCO model that can effectively generalize over multiple size and agent distributions thanks to our flexible structure. We train PARCO with RL via SymNCO [43] with K = 10 symmetric augmentations as shared REINFORCE baseline for 100 epochs using the Adam optimizer [46] with total batch size 512 (using 4 GPUs in Distributed Data Parallel configuration) and an initial learning rate of 10-1 with a step decay factor of 0.1 after the 80th and 95th epochs. For each epoch, we sample 4 x 1 randomly generated data. Training takes around 15 hours in our configuration.
B.2 OMDCPDP
The setting introduced in OMDCPDP is more general and realistic setting than the one introduced in Zong et al. [108], particularly due to the multiple depots and the global lateness objective function which is harder to optimize than vanilla min-sum.
B.2.1 Baselines
OR-Tools Google OR-Tools [19] is an open-source software suite designed to address various combinatorial optimization problems. This toolkit offers comprehensive selection of solvers suitable for linear programming, mixed-integer programming, constraint programming, and routing and scheduling challenges. Specifically for routing problems like the OMDCPDP, OR-Tools can integrate additional constraints to enhance solution accuracy. For our experiments, we maintained consistent parameters across various problem sizes and numbers of agents. We configured the global span cost coefficient to 10, 000, selected SETTH_CCEAPESSSAAE ARC as the initial solution strategy, followed by GUIDED SEIDED_LOCAL_SAAAE SEARCH for local optimization. The solving time was set {30, 60, 300, 600) seconds for N = (50, 100, 500, 1000), respectively.
HAM The Heterogeneous Attention Model (HAM) [54] utilizes a neural network-integrated with heterogeneous attention mechanism that distinguishes between the roles of nodes and enforces
22

---

precedence constraints, ensuring the correct sequence of pickup and delivery nodes. This approach helps the deep reinforcement learning model to make informed node selections during route planning. We adapt the original model to handle OMDCPDP with multiple agents akin to the sequential planning of Son et al. [84].
MAPDP
The Multi-Agent Reinforcement Learning- based Framework for Cooperative Pickup and Delivery Problem (MAPDP) [108] introduces cooperative PDP with multiple vehicle agents. This framework is trained via a centralized (MA)RL architecture to generate cooperative decisions among agents, incorporating a paired context embedding to capture the inter-dependennc of heterogeneous nodes. We adapted the MAPDP to fit our OMDCPDP task, utilizing the same encoder as PARCO ensure fair comparison. For the decoder and training phases, we kept the same random conflict handler, and we retained the hyperparameters detailed in the original study overall.
B.2.2 Datasets
Train data generation Neural baselines were trained with the specific number of nodes N and number of agents M they were tested on. In PARCO, we select a varying size and number of customer training schemes: at each training step, we sample N (50, 100) and m U(, 20). As we show in the Table I, a single PARCO model can outperform baseline models even when they were fitted
specific distribution. The coordinates of each customer location (1), Vs), where i i= 1...., N, are sampled from a uniform distribution (0.00, 1.0) within a two-dimensional space. Similarly, we sample M initial vehicle locations from the same distribution. We set the demand d; for each customer to 1 and the capacity of each vehicle to 3. This emulates realistic settings in which single package per customer will be picked up and delivered.
Testing Testing performed on 1000 new instances for each setting of in-distribution N and M in Table I with the distributions from the training settings. For large-scale generalization in Table 2, we generate 100 new instances.
B.2.3 PARCO Network Hyperparameters
Most hyperparameters are kept similar to Appendix 1.1.3.
Encoder Initial Embedding. This layer projects initial raw features to hidden space. For depots, the initial embeddings encode the location Om and the respective vehicle's capacity Qm- For pickup nodes, the initial embeddings encode the location and paired delivery nodes' location. For delivery nodes, the initial embeddings encode the location and paired pickup nodes' location. Main Encoder. We employ 1 = 3 attention layers in the encoder, with hidden dimension da 128, 8 attention heads in the MHA, MI.P hidden dimension set to 512, with RMSNorm [100] as normalization before the MHA and the MLP.
Decoder Context Embedding. This layer projects dynamic raw features to hidden space. The context is the embedding for the depot states Om, current node states, current length, remaining capacity, and number of visited nodes. These features are then employed to update multiple queries Qm, m = I,..., M simultaneously. Main Decoder. Similarly to the encoder, we employ the same hidden dimension and number of attention heads for the Multiple Pointer Mechanism.
We employ a single transformer layer with hidden dimension da 128, 8 attention heads in the MHA. MLP hidden dimension set to 512, with RMSNorm [100] as normalization before the MHA and the MLP. Note that unlike the encoder layer, which acts between all M + N tokens, communication layers are lighter because they communicate between M agents.
Communication Layer
Agent Handler We employ the Prisrity-based Conflict Handler guided by the model output probability for managing conflicts with priority given to the agent whose probability of selecting the conflicting action is the highest (see 4.6).
B.2.4 PARCO Training Hyperparameters
For each problem size, we train a single PARCO model that can effectively generalize over multiple size and agent distributions. We train PARCO with RL via SymNCO [43] with K = 8 symmetric
23

---

augmentations as shared REINFORCE baseline for 100 epochs using the Adam optimizer [46] with total batch size 128 on single GPU and an initial learning rate of 10 with step decay factor of 0.1 after the 80th and 95th epochs. For each epoch, we sample 10 randomly generated data. Training takes less than hours in our configuration.
B.3 FESP
B.3.1
Baselines
Gurobi We implement the mathematical model described above in the exact solver Gurobi [24] with time budget of 60 and 600 seconds per instance. However, with both time budgets, Gurobi is only capable of generating solutions to the FFSP20 instances, similar to the findings made by Kwon et al. [50] for the CPLEX solver.
Random and Shortest Job First (SJF) The Random and Shortest Job First (SJF) heuristics are simple construction strategies that build valid schedules in iterative manner. Starting from an empty schedule, the Random construction heuristic iterates through time steps / = 0,... . and stages i i= 1...S S and randomly assigns jobs available the given time idle machine of the respective stage until all jobs are scheduled, Likewise, the SJF proceeds by assigning job- machine pairs with the shortest processing time first.*
Genetic Algorithm (GA) Genetic Algorithms metaheuristics widely used by the OR com- munity to tackle the FFSP [38]. The GA iteratively improves multiple candidate solutions called chromosomes. Each chromosome consists of 5 x N real numbers, where S is the number of stages and N the number of jobs. For each job at each stage, the integer part of the corresponding numher indicates the assigned machine index, while the fractional part determines job priority when multiple jobs are available simultaneously. Child chromosomes are created through crossover, inheriting integer and fractional parts independently from two parents. Mutations, applied with a 30% chance, use one of four randomly selected methods: exchange, inverse, insert, or change. The implementation uses 25 chromosomes. One initial chromosome is set the Shortest Job First (SJF) heuristic solution and the best-performing chromosome is preserved across iterations. Each instance runs for 1,000 iterations.
Particle Swarm Optimization (PSO) Finally, Particle Swarm Optimization iteratively updates multiple candidate solutions called particles, which are updated by the weighted sum of the inertial value, the local best, and the global best at each iteration [81]. In this implementation, particles use the same representation as GA chromosomes. The algorithm employs 25 particles, with an inertial weight of 0.7 and cognitive and social constants heuristic solution. Like GA, PSO runs for 1,000 iterations per instance.
1.5. One initial particle represents the SUF
MatNet We benchmark PARCO mainly against MatNet [50], a state-of-the-ar NCO architecture for the FFSP. MatNet is encoder-decoder architecture, which is inspired by the attention model [47]. It extends the encoder the attention model with dual graph attention layer, horizontal stack of two transformer blocks, capable of encoding nodes of different types in bipartite graph-like machines and jobs in the FFSP. Kwon et al. [50] train MatNet using POMO [49].
B.3.2 Datasets
Train data generation We follow the instance generation scheme outlined in Kwon et [50] sample processing times for job-machine pairs independently from uniform distribution within the bounds [2, 10). For the first three FFSP instance types shown in Table we also use the same instance sizes Kwon et al. [50] with N = 20, 50 and 100 jobs and M = 12 machines which are spread evenly over S stages. To test for agent sensitivity in the FFSP, we fix the number of jobs to N = 50 but alter the number of agents for the last three instance types shown in Table 1. Still, we use S for this experiment, but alter the number of machines per stage to M, = 6, and 10, yielding total of 18, 24 and 30 agents, respectively:
'To obtain results for the heuristics and metaheuristics. we used the implementation of Kwon et al. [50]. provided in the official GitHub repository of the paper: bttps://gite http//gtttttttttt/e/////tt com/yd- /dn//dd-u hts//yd-kkoodd kwon/MatNet
24

---

Testing Testing is performed on 100 separate test instances generated randomly according to the above generation scheme.
B.3.3 PARCO Network Hyperparameters
Encoder To solve the FFSP with our PARCO method, we use a similar encoder as Kwon et al. [50]. The MatNet encoder generates embeddings for all machines of all stages and the jobs they need to process, plus an additional dummy job embedding, which can be selected by any machine in each decoding step skip the next step. To compare PARCO with MatNet, we use similar hyperparameters for both models. We use L = 3 encoder layers, generating embeddings of dimen- sionality d₁ 256, which split over 16 attention heads the MHA layers. Further, employ Instance Normalization [87] and a feed-forward network with 512 neurons in the transformer blocks of the encoder.
Decoder The machines are regarded as the agents in our PARCO framework. As such, their embeddings used queries the Multiple Pointer Mechanism Eq. (6), while job embeddings are used as the keys and values. In each decoding step, the machine embeddings are fused with a projection of the time the respective machine becomes idle. Similarly, job embeddings augmented with linear transformation of the time they become available the respective stage before entering the attention head in Eq. (5).
Communication Layer We employ single transformer block with hidden dimension d₁ 256 and h = 16 attention heads in the MHA, MLP with 512 hidden units and Instance Normalization.
Agent Handler We use the High Probability Handler for managing conflicts: priority is given the agent whose (log-) probability of selecting the conflicting action is the highest. Formally, priorities Pm log po (p((m())) for m
1, ,,,..,M M.
B.3.4 PARCO Training Hyperparameters
Regarding the training setup, each training instance i augmented by a factor of 24, and the average makespan the augmented instances is used as shared baseline 0ehared for the REINFORCE gradient estimator of Eq. (8). We use the Adam optimizer [46] with a learning rate of x 10 10-4, which alter during training using cosine annealing scheme. We train separate models for the environment configurations used in Table 1. We train models corresponding to environments with 20 jobs for 100, with 50 jobs for 155 and with 100 jobs for 200 epochs. In each epoch, we train the models using 1,000 randomly generated instances split into batches size 50.5
B.3.5 Diagram for MatNet Decoding vs. PARCO Decoding for the FFSP
The following figures visualize the decoding for the machines of given stage using MatNet and PARCO. As one can see in Fig. 6a, MatNet requires a decoder forward pass for each machine to schedule job each of them. In contrast, as detailed in Fig. 6b, PARCO can schedule jobs all machines simultaneously through its Multiple Pointer Mechanism and Agent Handler, leading to significant efficiency gains.
B.4 Hardware and Software
B.4.1 Hardware
We experiment on a workstation equipped with INTEL(R) XEON(R) GOLD 6338 CPUs and NVIDIA RTX 4090 graphic cards with 24 GB of VRAM each. Training runs of PARCO take less than 24 hours each. During inference, we employ only one CPU and single GPU.
B.4.2 Software
We used Python 3.12, PyTorch 2.5 [78] coupled with Py Torch Lightning [17] with most code based on the RL4CO library [5]. The operating system is Ubuntu 24.04 LTS.
NNoe: to avoid OOMs, for FFSP100 instances, batches are further split into mini batchea of size 25 whose gradients accumulated.
25

---

1-4
Pyu. Pyo. the Plw, Pin-i
Prtu Pya Pijk
Ppt. Paces
Pyu, in P/n.
Encoder
Decoder
Decoder
Dacoder
Decodler
embaa embue embba embbys
embr amina emdrs
embpa
embys embys embis
embea
emdy emilyy embyy : embjy embbyee
embua
embyy embba emb
embee
emay emby embj.
emby embyuet
emb pk emoo
embbyx em emb
emb ju embdyse
1-
(a) An FFSP Decading Step with MatNet
1
10
PM
Agjent Aggent Handler
Mi
J22
PA
M12
Mines
J3
Encoder
Dezoder
embga embea
emaiy emiby embba
emb f embss emb6e
emmiys ammiyy emn6y
embaa embbe
embie emb
embyy
en
K.Y
maak
(b) An FTSP Decoding Step with PARCO
Figure Comparison decoding steps for FFSP with MatNet and PARCO.
B.5
Source Code
We value open reproducibility and release our source code at https:://// cestps://githti www/aiaco//pppecccccootooo. parco. We also provide the summary of licenses in Table 3.
C Additional Materials
C.1 Further Discussions
Follow-ups We acknowledge there are works based on or inspired by PARCO already out in the wild at the time of publication. These include extending to profiled VRP [29, 30], mixed-shelves picker-routing [67], and self-improvement for better performance [68]. We hope to see even more in the future from diverse research groups, and we remain available for discussions, including through the AI4CO Slack.
Possible future directions In this paragraph, we will share short list of possible additional future directions for PARCO. One promising direction NCO to employ Large Language Models (LLMs) for automating the design of algorithms and particularly heuristics [62, 97, 27J. Several
26

---

Table 3: Summary of licenses for used assets.
Resource
Type
License
OR-Tools [19]
Code
Apache License, Version 2.0
AM [47]
Code
MIT License
ET [84]
Code
Available on Github
DPN [104]
Code
MIT License
DRL [55]
Code
Available on Github
2D-Ptr [63]
Code/Dataset
Available on Github
HAM [54]
Code
MIT License
Gurobi [24]
Code
Commercial license (free for academic use)
MatNet [50]
Code/Dataset MIT License
RL4CO [5]
Library
MIT License
components of PARCO could be designed by LLMs, including the conflict handling mechanism or
attention biases dependent on specific problems [31, 90] as done by Tran al. [86]. Of interest would
also be extensions to other problem variants [99]. Integrating parallel decoding into search methods, as NDS [28], may also yield much more efficient models and enable them capture different agents.
C.2 Comparison with Decentralized and Graph-Based Communication Methods
We additionally compare PARCO with decentralized methods and alternative communication models like Graph Neural Networks (GNNs). We experiment on the min-max traveling salesman problem (mTSP). benchmarking PARCO against notable decentralized methods like GNN-DisPN [16], DAN [10] and GNN-based communication models like ScheduleNet [75].
The results, shown Table 4 with instances from Park et al. [75] as well as the mTSPLib in Table additionally adding the HGA solver for further comparison from Mahmoudinazlou and Kwon [72] demonstrate that PARCO consistently outperforms these methods in solution quality. Centralized training with parallel decoding, used in PARCO, offers distinct advantages by enabling global coordination and highly efficient solution construction. For example, GNN-based communication in models like ScheduleNer incurs significantly higher computational overhead, making our approach much faster than those methods.
Table 4: Cost comparison on the m TSP with different numbers of salesmen M and number of nodes N.
N
50
100
200
Gap
M
5
7
10
5
10
15
10
15
20
LKH3 (solver)
2.00
1.95
1.91
2.20
1.97
1.98
2.04
2.00
1.97
OR-Tools (solver)
2.04
1.96
1.96
2.36
2.29
2.25
2.57
2.59
2.59
14.42
GNN-DisPN (g.)
2.14
2.10
1.99
2.56
2.22
2.04
2.97
2.30
2.15
13.45
DAN (g.)
2.29
2.11
2.03
2.72
2.17
2.09
2.40
2.20
2.15
11.75
SchedNet (g.)
2.17
2.07
1.98
2.59
2.13
2.07
2.45
2.24
2.17
10.16
PARCO (g.)
2.12
2.00
1.92
2.47
2.02
1.98
2.28
2.06
1.99
4.43
DAN (s.)
2.12
1.99
1.95
2.55
2.05
2.00
2.29
2.13
2.07
6.13
SchedNet (s.)
2.07
1.99
1.92
2.43
2.03
1.99
2.25
2.08
2.05
4.29
PARCO (s.)
2.07
1.98
1.91
2.38
1.99
1.98
2.22
2.03
1.98
2.80
We note that these experiments refer to previous version of PARCO in which the conflict handler was not properly working and was similar the random handler - we would expect retraining PARCO on the newest implementation would perform even better. As the scope of this comparison to compare against decentralized methods, we not include more recent approaches as ET [84] or DPN [104] which would outperform this old PARCO version albeit with slower decoding, We expect that recent follow-ups our work, which allow for stopping actions by adding special tokens
'nttps://profs. info. waic. www..ro/mihaell. http://bbbbbbbattpp//////ttaa/aa
27

---

Table 5: Results for the mTSPLib. CPLEX results with optimal solutions. Otherwise, the best-known upper hound of CPLEX results reported.
instance N
ei151
berlin52
c1176
rat39
Gap (%)
M
3
5
7
3
CPLEX
222.7"
159.6
124.0
112.1
41.0.2
3244.4
2441.4
2440.9
280.9"
197.3
150.3
139.6
728.8
587.2
469.3
443.9
3.40%
LKH3
221.7
159.6
124.0
112.1
4110.2
3244.4
2441.4 2440.9
280.9
197.3
150.3
139.6
728.8
587.2
469.3 443.9
3.40%
OR-Tools
243.3 170.5
127.5 112.1
4665.5
3311.3
2482.6 2440.9
318.0
212.4
143.4
128.3
762.2
552.1
473.7 442.5
6.05%
HGA
222.7 159.6
118.1 112.1
4110.2
3009.6 2440.9 2440.9
196.7 142.9
127.6
666.0
517.7
450.3 436.7
0.00%
DAN (x.)
178.9
114.3
5097.7
3455.7 2677.1
336.7
228.1
462.0
14.51%
SchedNet (x.)
173.5
112.2
4591.6
3276.1
2517.3
317.7
8.55%
PARCO (s.)
170.8
123.6 112.5
4429.2
33316 2519.3 2444.8
295.7
450.7
5.22%
to the embedding, as MACSIM [68], would outperform ET and DPN, perhaps considerably. We leave this as an interesting direction for future work.
C.3 Convergence Rates
Table 6: Convergence rates in different problems: cost as a percentage of training budget.
10%
25%
50%
75%
100%
HCVRP
5.13 + 0.09 5,00 + 0.06 4.90 + 0.05 4.88 + 0.03 4.79 0.03
OMDCPDP
46.23 + 0.21
45.57
0.15 45.34 + 0.11
44.87 + 0.10
44.48 0.09
FFSP
95.45 + 0.52 94.32 0.31 92.88 0.20 92.15 = 0.12 91.48 = 0.08
Table shows the convergence rate of PARCO across different problems on validation datasets at different training budgets (in percentage). PARCO is robust during training and converges stably.
C.4 XXL Instances
To further strengthen our results, we have tested PARCO for even larger scales in both the number of nodes and the number of agents. We generated 16 new instances for N = 5000 nodes and 3 different values of M agents (a total of 48 instances) of OMDCPDP. We evaluated OR-Tools with hour of runtime and greedy performance for HAM and PARCO.
Table 7: Large- scale generalization results for OMDCPDP with N 5000.
M
500
M
750
M
1, 000
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
OR-Tools
5575.73
134.06%
3600s 5127.46
115.24%
3600s
4974.81
188.10%
3600s
HAM
4813.99
102.08%
17.4s 3732.06
97.33%
19.5s 3258.26
88.69%
22.3s
PARCO
2382.22
0.0%
0.21s 1891.28
0.0%
0.21s 1726.78
0.0%
0.22s
As shown in Table 7, PARCO excels at generalization XXL scales with 50x the number of nodes and agents seen during training and up to 000 agents. Thanks to its massively parallel structure, PARCO can solve such instances in fraction of second with better results than OR-Tools at 10, x00x speedup. This makes PARCO ideal for real-world, real-time, targe-scale complex problems.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims on the abstract and introduction accurately reflect the paper's contribution and scope (see methodology of $ and experimental results $ 5).
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We include paragraph in $ 6 discussing limitations and future works.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: This paper does not include theoretical results.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We give detailed description of our method in & 4 and discuss the experimental settings in 5 with further information in the Appendix. The source code of PARCO is also publicly available.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code of PARCO available https://github com/ ai 4co/o/ 414co/parco. We provide detailed instructions on how to reproduce the main experimental results.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the settings of the training and test details 5, supplemented by further details for each experiment in Appendix B. The original configurations additionally available in the publicly available code to foster reproducibility and openness.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the standard deviation in Fig. with experiments run on 3 different seeds. For the main results including Table we adhere to the established standard in
machine learning for combinatorial optimization papers, which involves reporting averaged results for several dataset instances each to ensure statistical significance: 1,280, 1,000, and 100 for HCVRP, OMDCPDP, and FFSP, respectively.
29

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We report resources in $ 5.
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //terrip///.ip....////
Answer: [Yes]
Justification: Our research conforms to the NeurlPS Code of Ethics
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The adoption of PARCO is not expected to have any negative societal impact. On the contrary, we envision machine learning approaches as PARCO may become more prevalent in solving CO problems and thus lead to positive societal benefits, including reduced resource consumption, better management logistics such as disaster relief efforts, and democratization of optimization solvers.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no high risk of misuse for our released assets.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Creators of assets (e.g., code, data, models) used in the paper are properly credited Table
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All introduced assets are well documented. We provide clear instructions, including checkpoints release through HuggingFace.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. Institutional review board (IRB) approvals or equivalent for research with human subjects
30

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs are used only for writing, editing, or formatting purposes and do not impact the core methodology, scientific rigor, or originality of the research.
31


Reviews:
[{"review_id": "zrOgqtC3zQ", "reviewer": "Reviewer_ycp1", "summary": "PARCO is a reinforcement learning framework designed to efficiently solve complex multi-agent combinatorial optimization problems. It introduces three key innovations: (1) a transformer-based communication layer for agent coordination, (2) a multiple-pointer mechanism for parallel decision-making, and (3) a priority-based conflict resolution system. Evaluated on tasks like multi-agent vehicle routing and scheduling, PARCO outperforms state-of-the-art learning-based methods in both solution quality and generalization.", "questions": "No particular question, I think this is a well written paper and can be accepted.", "limitations": "yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. the empirical improvement is clear, including the performance and the efficiency.\n2. the architecture design seems reasonable, including multi-agent encoder, communication layer, and multi-pointer decode.\n\nWeakness:\n1. no particular weakness, probably lack of guarantee on optimality.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and for providing a positive and encouraging review, acknowledging the design choices of our PARCO method, our empirical results, as well as the clear writing. We will answer your concern below:\n\n\n**W1: About guarantee on optimality**\n\nRegarding the lack of an optimality guarantee, we agree with the reviewer's observation. This is a common and accepted trade-off for heuristic and learning-based methods designed to tackle NP-hard problems. Our primary objective is to produce high-quality solutions in the shortest possible time, which is a critical requirement for many real-world applications where exact methods are computationally infeasible. In this sense, PARCO can produce a high-quality solution at a fraction of the cost of traditional methods while outperforming all learning-based ones. This is validated across numerous benchmarks and ablation studies in the paper. While PARCO does not offer an optimality guarantee, it successfully provides a state-of-the-art, scalable, and efficient solver for practical use."}, {"review_id": "M0pD604MVR", "reviewer": "Reviewer_HMqs", "summary": "The authors propose a general reinforcement learning framework to handle multi-agent combinatorial optimization problems. The proposed framework mainly contains three components: (1) communication layers for multi-agent collaboration; (2) multi-pointer mechanism for low-latency multi-agent action generation; (3) priority-based conflict handler to deal with action conflicts based on learned priorities with allowance of fallback actions. Extensive experiments show that these designs effectively help the proposed approach achieve superior performance and efficiency in several challenging routing and scheduling problems.", "questions": "1. It is said in L196 that the communication layers are agent-count agnostic, but the self-attention layer in transformer may lead to fluctuated effect in multi-agent communication when the agent count becomes huge.\n2. It seems like there are two stages of communication for multi-agent coordination, not only in the communication layers? The encoder module actually involves agent-agent interaction through self-attention MHA or even agent-node interactions through cross-attention MHA.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The designs including the communication layers, multi-pointer mechanism, and the conflict handlers are compact in formulation and efficient to deal with multiple agents in parallel, clearly echoing the name \"Parallel AutoRegressive Models\".  \n2. The proposed communication layers are scalable in agent count, and it can generalized to out-of-distribution numbers of agents M according to the ablation results in table 2. \n3. The whole framework is general to various combinatorial optimization problems including routing and scheduling tasks. It demonstrate extraordinary scalability and efficiency in solving time and speedups against related works, as shown in Table 1 and figure 4.\n\nWeaknesses:\n1. Lack of comparison with decentralized approaches in performance and efficiency, and any disadvantages against decentralized methods? \n2. Lack of experiments comparing with related works modeling the multi-agent collaboration/communication other than MHA and MLP, for example, graph-based models? \n3. Inconsistent depiction between figure and text body. As for the Multiple Pointer Mechanism, only context embeddings are fed in as key and value in Figure 2, but $\\mathbf{h}_n$ plus dynamic node features are playing as keys and values in Eq. (5).", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and for highlighting the strengths of our paper. We appreciate the insightful feedback, which has helped us further improve our work. Below, we address each of your concerns and questions.\n\n\n**W1 & W2: Comparison with Decentralized and Graph-Based Communication Methods**\n\nThank you for this valuable suggestion. We agree that comparing PARCO with decentralized methods and alternative communication models like Graph Neural Networks (GNNs) provides a more complete picture. During the rebuttal period, we conducted new experiments on the min-max traveling salesman problem (mTSP), benchmarking PARCO against notable decentralized methods like GNN-DisPN [1], DAN [2], and GNN-based communication models like ScheduleNet [3].\n\nThe results, shown in the table below (where g. stands for greedy and s. for sampling), demonstrate that PARCO consistently outperforms these methods in solution quality.\n\n\n| Method | N=50 |  |  | N=100 |  |  | N=200 |  |  | Gap(%) |\n|--------|------|------|------|-------|------|------|-------|------|------|--------|\n| **M** | **5** | **7** | **10** | **5** | **10** | **15** | **10** | **15** | **20** |  |\n| LKH3 (solver) | 2.00 | 1.95 | 1.91 | 2.20 | 1.97 | 1.98 | 2.04 | 2.00 | 1.97 | - |\n| OR-Tools (solver) | 2.04 | 1.96 | 1.96 | 2.36 | 2.29 | 2.25 | 2.57 | 2.59 | 2.59 | 14.42 |\n| GNN-DisPN (g.) | 2.14 | 2.10 | 1.99 | 2.56 | 2.22 | 2.04 | 2.97 | 2.30 | 2.15 | 13.45 |\n| DAN (g.) | 2.29 | 2.11 | 2.03 | 2.72 | 2.17 | 2.09 | 2.40 | 2.20 | 2.15 | 11.75 |\n| SchedNet (g.) | 2.17 | 2.07 | 1.98 | 2.59 | 2.13 | 2.07 | 2.45 | 2.24 | 2.17 | 10.16 |\n| **PARCO (g.)** | **2.12** | **2.00** | **1.92** | **2.47** | **2.02** | **1.98** | **2.28** | **2.06** | **1.99** | **4.43** |\n| DAN (*s.*) | 2.12 | 1.99 | 1.95 | 2.55 | 2.05 | 2.00 | 2.29 | 2.13 | 2.07 | 6.13 |\n| SchedNet (*s.*) | 2.07 | 1.99 | 1.92 | 2.43 | 2.03 | 1.99 | 2.25 | 2.08 | 2.05 | 4.29 |\n| **PARCO (s.)** | **2.07** | **1.98** | **1.91** | **2.38** | **1.99** | **1.98** | **2.22** | **2.03** | **1.98** | **2.80** |\n\n\nCentralized training with parallel decoding, as used in PARCO, offers distinct advantages by enabling global coordination and highly efficient solution construction. For example, GNN-based communication in models like ScheduleNet incurs significantly higher computational overhead, making our approach much faster.\n\n**W3: Clarification on Figure 2 and Dynamic Node Features**\n\nThank you for pointing out this inconsistency. Figure 2 was simplified for visual clarity, but your interpretation of Equation (5) is correct. Dynamic node features ($\\xi_t$) are indeed a part of our model. While these features are not used in the routing problems (where $\\xi_t$ is zero), they are critical for the Flexible Flow Shop Problem (FFSP). In FFSP, $\\xi_t$ encodes the time a job becomes available at a new stage, which is essential dynamic information for the machines (agents) to make correct scheduling decisions. We will update Figure 2 in the final version to fully reflect Equation (5).\n\n\n**Q1: Scalability**\n\nThis is a valid concern. While self-attention complexity is quadratic with the number of agents, our experiments show that PARCO's performance remains robust and stable even at extreme scales. During the rebuttal, we stress-tested PARCO on the OMDCPDP with up to 5000 nodes and 1000 agents, 50 times larger than the training distributions.\n\n\n|        | $M=500$ |  |  | $M=750$ |  |  | $M=1,000$ |  |  |\n|--------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|\n|        | Obj. | Gap | Time | Obj. | Gap | Time | Obj. | Gap | Time |\n| OR-Tools | 5575.73 | 134.06% | 3600s | 5127.46 | 115.24% | 3600s | 4974.81 | 188.10% | 3600s |\n| HAM | 4813.99 | 102.08% | 17.4s | 3732.06 |97.33%| 19.5s | 3258.26 | 88.69% | 22.3s |\n| PARCO | **2382.22** | **0.0%** | **0.21s** | **1891.28** | **0.0%** | **0.21s** | **1726.78** | **0.0%** | **0.22s** |\n\nAs we can see from the results, PARCO excels at generalization in extremely large scales with $50\\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools at a $10,000\\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications.\n\n\n**Q2: Two Stages of Communication**\n\nThis is an excellent observation. You are correct that one can view the model as having two stages of \"communication\":\n- Static Communication (Encoder): The encoder processes the initial agent and node features, establishing a baseline understanding of the problem structure and static agent-node relationships.\n- Dynamic Communication (Decoder): The Communication Layers provide a second, crucial stage of coordination that happens at every step of the decoding process. This allows agents to react to the dynamically changing state of the problem and each other's actions.\n\nOur ablation study in Figure 3a, which removes the explicit Communication Layers but keeps the same encoder, confirms that this second stage of dynamic collaboration is essential for achieving high-quality solutions.\n\n---\n\n**References**\n\n[1] Hu, Yujiao, Yuan Yao, and Wee Sun Lee. \"A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs.\" Knowledge-Based Systems 204 (2020): 106244.\n\n[2] Cao, Yuhong, Zhanhong Sun, and Guillaume Sartoretti. \"Dan: Decentralized attention-based neural network for the minmax multiple traveling salesman problem.\" International Symposium on Distributed Autonomous Robotic Systems. Cham: Springer Nature Switzerland, 2022.\n\n[3] Park, Junyoung, Changhyun Kwon, and Jinkyoo Park. \"Learn to Solve the Min-Max Multiple Traveling Salesmen Problem with Reinforcement Learning.\" AAMAS. Vol. 22. 2023."}, {"review_id": "5ceRClB5Kn", "reviewer": "Reviewer_NRcw", "summary": "The authors address two major limitations of the existing autoregressive paradigm for multi-agent combinatorial optimization problems, namely inefficiency and lack of coordination. By introducing a communication layer to enhance coordination, a multiple-point mechanism to improve inference speed, and a conflict handler to ensure constraint satisfaction, the proposed method achieves certain improvements. However, there remain several aspects that require further clarification, including the motivation, problem definition, effectiveness of the conflict handler, and the presentation of experimental results.", "questions": "1. Could the authors provide more precise mathematical definitions for key concepts such as \"agent,\" \"node,\" decision variables, and optimization objectives? How do these definitions clarify the differences and relationships among multi-agent CO, single-agent CO, and conventional CO problems?\n\n2. The conflict handler is implemented as a fixed, non-adaptive fallback mechanism. Have the authors considered or experimented with adaptive or learnable conflict resolution methods? Additionally, could the authors provide more detailed analysis and experimental results on the selection of the fallback action, its optimality, and its role during different training phases?\n\n3. The paper currently does not include training curve plots. Could the authors provide these curves to help assess the convergence behavior, stability, and training efficiency of the proposed method?\n\n4. Given that the performance improvements reported are relatively marginal, could the authors further discuss the practical significance of their approach and clarify whether the addressed motivation reflects a critical challenge in combinatorial optimization?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "**Strength**\n\nThe overall quality of this paper is commendable. It presents a motivation, targeted model design, and extensive experimental comparisons. The writing in most parts of the paper is quite clear and easy-to-understand.\n\n**Weakness**\n1. The paper lacks clear and precise definitions regarding the multi-agent CO problem. Specifically, the concepts of \"agent,\" the justification for modeling the problem as multi-agent, as well as definitions for \"node,\" the relationships between nodes, decision variables, and optimization objectives are not rigorously formulated. This makes it difficult for readers to quickly grasp the differences, connections, and levels of complexity among multi-agent CO, single-agent CO, and conventional CO problems.\n2. The literature review is not sufficiently comprehensive, which undermines the persuasiveness of the motivation. Additionally, the definition of the CO problem under study may be overly broad, making the proposed motivation less convincing in many scenarios. For example, in applications such as urban ride-hailing and task assignment, drivers, passengers, and workers are heterogeneous; however, many existing works adopt a single-agent RL paradigm and, combined with algorithms such as the KM algorithm, can guarantee conflict-free assignments and make decisions within hundreds of milliseconds even at large urban scale. These findings contradict the premises of the authors’ motivation.\n3. The effectiveness of the proposed conflict handler appears to be very limited. In my experience, it is extremely challenging for neural networks to consistently satisfy nested, diverse, large-scale, and overlapping constraints. The handler adopted by the authors relies on a fixed, non-adaptive, and non-learnable fallback mechanism, which makes it difficult to guarantee constraint satisfaction unless every action fall backs to r. Therefore, more explicit experimental results and discussion are needed regarding the choice of r, its optimality, its role during training, the specific phases in which it is necessary or unnecessary, and when constraints can be satisfied without its assistance. Such analysis is essential to justify the necessity and effectiveness of the proposed handler.\n4. The experimental results lack training curve plots, making it difficult to assess the convergence, stability, training speed, and computational time of the proposed approach. Additionally, the reported performance improvements appear to be quite marginal. This raises the question of whether the motivation addressed by the authors truly targets a critical or fundamental challenge in combinatorial optimization.", "was_revised": true, "final_justification": "After the rebuttal, the authors have addressed my concerns regarding the Conflict Handler and some aspects of the problem definition, and have also stated that they will include training curves. However, I still have some reservations about the clarity of the writing.", "rebuttal": "We sincerely thank the reviewer for their valuable and detailed feedback. We are happy to provide below extensive answers to highlight the significance and originality of our approach.\n\n\n**W1 & Q1: about the formulation of multi-agent CO**\n\nWe appreciate the opportunity to clarify these important concepts.\n\nIn conventional CO, \"agents\" are indeed mathematical entities without the interactive properties we model. Our approach differs fundamentally in how we conceptualize and solve these problems.\n\nIn our formulation, we model problems where multiple distinct entities must coordinate to construct a complete solution as multi-agent systems. Each \"agent\" corresponds to a physical entity (e.g., vehicle, machine, robot) that can independently take actions to build parts of the overall solution. This is formalized through our parallel multi-agent MDP in Section 4.1, where agents operate in a joint action space $A_1 \\times ... × A_M$ rather than a single action space.\n\nThe key distinctions are:\n- Multi-agent CO (PARCO): Multiple coordinating entities construct solution parts simultaneously with communication and conflict resolution.\n- Single-agent CO: One entity constructs the entire solution sequentially.\n- Conventional CO: Mathematical optimization without explicit agent modeling or coordination mechanisms.\n\nRegarding nodes, these represent the discrete decision points or locations in the problem space (customers in VRP, jobs in scheduling). The relationships between nodes are problem-specific (distances in routing, precedence in scheduling) and captured in our encoder representations and through masking in the decoder.\n\nOur decision variables are the actions taken by each agent at each time step, forming joint actions $\\mathbf{a}_t = (a^1_t, ..., a^M_t)$. The optimization objective remains minimizing the original CO cost function, but achieved through coordinated parallel construction rather than centralized sequential planning.\n\nThis formulation enables the communication layers and conflict resolution mechanisms that are central to our contribution, allowing agents to coordinate during solution construction rather than operating independently.\n\n\n\n**W2: About literature review**\n\n\nThank you for raising this important point about our literature review and motivation. We appreciate your feedback and would be happy to expand our literature review in specific directions if you could suggest particular areas you would like us to focus on. Regarding the definition of multi-agent CO, we intentionally keep it broad because our approach is general-purpose and does not restrict to any single problem class; we view this generality as a key advantage of PARCO, allowing it to tackle diverse optimization scenarios with a unified framework.\n\nYour example of ride-hailing with polynomial-time algorithms like the KM algorithm is well-taken for certain task assignment problems. However, this does not apply to the significantly more complex problems we address. The combinatorial optimization problems we consider - particularly OMDCPDP and FFSP - are much harder computational challenges where traditional methods struggle considerably. Our experimental results demonstrate that PARCO not only finds substantially better solutions than existing approaches but does so more efficiently and with superior scalability. For instance, in FFSP, traditional solvers like Gurobi cannot even find feasible solutions for problems with $N > 20$ within reasonable time limits, while PARCO consistently outperforms all baselines across all tested scales. This highlights that while polynomial-time solutions may exist for some specific assignment problems, the broader class of multi-agent CO problems we target requires the sophisticated coordination and parallel decision-making capabilities that PARCO provides.\n\n**W3 & Q2: About the effectiveness of the conflict handler**\n\nThank you for your detailed question about the conflict handler. We appreciate your concern about the fallback mechanism and would like to clarify several key points about its design and effectiveness.\n\nFirst, we want to emphasize that the fallback mechanism is only applied to actions that are in conflict and not selected as priority and not to every action. This selective application guarantees feasibility of construction while maintaining the parallel decision-making benefits. The priority-based selection uses learned probabilities from the model output (as shown in Fig. 3c, where \"learned\" priorities consistently outperform heuristic alternatives), making it an adaptive mechanism that leverages the neural network's learned representations rather than being purely fixed. The fallback actions (staying at current position for routing, keeping machine idle for scheduling) are domain-appropriate \"do nothing\" operations that maintain feasibility without disrupting solution quality, as agents can reconsider their choices in subsequent decoding steps.\n\nRegarding your question about more sophisticated conflict resolution methods, we acknowledge this as an interesting direction for future work. However, our empirical results demonstrate that the current approach already works quite well in practice: PARCO achieves state-of-the-art performance across all tested problems while maintaining computational efficiency. The simplicity of the fallback mechanism is actually a strength, as it provides reliable constraint satisfaction without adding computational overhead or training complexity. We chose this approach following the principle of using the simplest effective solution, similar to how masking is used in neural combinatorial optimization to guarantee feasible solution construction. The learned priority mechanism already provides the adaptive component you mentioned, while the fallback ensures robustness.\n\n\n**W4 & Q3: About lack of training curve plots**\n\nThank you for pointing this out. While we cannot add figures or any other media due to the rebuttal policy, we will provide the below table with PARCO's convergence evaluated on the validation dataset  (training budgets refer to the percentage of the total training epochs):\n\n| Training budget  | 10% | 25% | 50% | 75% | 100% |\n|------|-----|-----|-----|-----|------|\n| HCVRP ($N=100$, $M=7$) | 5.13 ± 0.09 | 5.00 ± 0.06 | 4.90 ± 0.05 | 4.88 ± 0.03 | 4.79 ± 0.03 |\n| OMDCPDP ($N=100$, $M=20$) | 46.23 ± 0.21 | 45.57 ± 0.15 | 45.34 ± 0.11 | 44.87 ± 0.10 | 44.48 ± 0.09 |\n| FFSP ($N=100$, $M=12$) | 95.45 ± 0.52 | 94.32 ± 0.31 | 92.88 ± 0.20 | 92.15 ± 0.12 | 91.48 ± 0.08 |\n\nWe can observe that PARCO is robust and yields consistent improvements.\n\n**Q4: What is the practical significance of the approach?**\n\nThanks for asking this question, as it gives us an opportunity to further emphasize the strength of our approach. PARCO yields substantial imporvements over multiple problems, scales, and number of agents. In most problems we tested, it yields SOTA results even against heuristic approaches and a fraction of the cost. \n\nTo further strengthen our results, we have tested PARCO for even larger scales in both number of nodes and number of agents during the rebuttal. We generated 16 new instances for $N=5000$ nodes and 3 different values of $M$ agents total of 48 instances of OMDCPDP and evaluate OR-Tools with 1 hour of runtime and greedy performance for HAM and PARCO. The results are in the table below:\n\n\n\n|        | $M=500$ |  |  | $M=750$ |  |  | $M=1,000$ |  |  |\n|--------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|\n|        | Obj. | Gap | Time | Obj. | Gap | Time | Obj. | Gap | Time |\n| OR-Tools | 5575.73 | 134.06% | 3600s | 5127.46 | 115.24% | 3600s | 4974.81 | 188.10% | 3600s |\n| HAM | 4813.99 | 102.08% | 17.4s | 3732.06 |97.33%| 19.5s | 3258.26 | 88.69% | 22.3s |\n| PARCO | **2382.22** | **0.0%** | **0.21s** | **1891.28** | **0.0%** | **0.21s** | **1726.78** | **0.0%** | **0.22s** |\n\nAs we can see from the results, PARCO excels at generalization in extremely large scales with $50\\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools -- at a $10,000\\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications."}, {"review_id": "ZOpJcRYU0w", "reviewer": "Reviewer_GvYn", "summary": "The paper introduces **PARCO**, a reinforcement learning framework for multi-agent combinatorial optimization that integrates transformer-based communication, parallel decision-making, and conflict resolution. The approach achieves improved coordination, generalization, and computational efficiency on tasks such as vehicle routing and scheduling.", "questions": "1. Since the joint action space grows with the number of agents, how does this affect learning stability and computational complexity?\n2. Is the agent embedding hah_aha also used in the decoding process (Equations 5, 6, and 7)?\n3. The agent priority is derived from the policy π\\piπ, which may introduce an overestimation bias. Could this cause high-priority agents to be reinforced more strongly, and how is this mitigated?\n4. For the generalization results, how is PARCO used in an untrained number of agents?  Is there a training-testing mismatch?", "limitations": "See Question 1.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The reformulation of the multi-agent decision-making problem is theoretically sound and enables more efficient parallel execution.\n- The experimental evaluation is thorough, comparing against a broad set of baselines, including both classical optimization methods and neural-based approaches.\n\n**Weaknesses:**\n\n- The proposed formulation allows multiple agents to act simultaneously, whereas the original problem restricts movement to one agent at a time. It is unclear whether efficiency comparisons across these settings are entirely fair, given this difference in assumptions.\n- The training curves are missing from the main paper. It would be helpful to include them to evaluate convergence behavior. Additionally, it is unclear whether Figure 3b represents wall-clock training time or another metric — this should be clarified.", "was_revised": true, "final_justification": "The paper proposes a multi-agent method to solve a realistic robotic task. The initial submission missed details on training performances, which were added in the rebuttal. I have raised the score to 4.", "rebuttal": "Thank you for your constructive feedback and for your time reviewing our paper. We greatly appreciate your acknowledgment of PARCO's strengths, including our model's efficacy across multiple settings and the thorough experimental design.\n\nWe will address your concerns and questions in the following.\n\n**W1: About fair efficiency comparison**\n\nThis is a crucial point that highlights a core contribution of our work. The reformulation from a sequential to a parallel decision-making process is an intentional innovation designed to find higher-quality solutions more efficiently.\n\nThe comparison is fair for two key reasons:\n\n- Shared Objective: All models are ultimately judged on the quality of the final, complete solution (e.g., the total makespan or the longest route) for the same underlying optimization problem. The method of constructing that solution is what differs.\n\n- Efficiency as a Contribution: PARCO's ability to construct this solution in parallel is precisely the source of its efficiency advantage. It drastically reduces the number of sequential decoding steps required to build a valid solution (see figure 3b), leading to significant speedups in both training and inference without sacrificing - and often improving - the final solution quality.\n\nTherefore, the efficiency gain isn't an artifact of an unfair comparison; it's the direct result of a more advanced and arguably more realistic solution construction methodology.\n\n**W2: About training curves and clarification of figure 3b**\n\nThanks for pointing us to missing information and training details. Regarding the convergence analysis, while note that we cannot add figures or any other media due to the rebuttal policy, we will provide the below table with PARCO's convergence evaluated on the validation datasets of the respective problems  (Training budgets refer to the percentage of the total training epochs):\n\n| Training budget  | 10% | 25% | 50% | 75% | 100% |\n|------|-----|-----|-----|-----|------|\n| HCVRP ($N=100$, $M=7$) | 5.13 ± 0.09 | 5.00 ± 0.06 | 4.90 ± 0.05 | 4.88 ± 0.03 | 4.79 ± 0.03 |\n| OMDCPDP ($N=100$, $M=20$) | 46.23 ± 0.21 | 45.57 ± 0.15 | 45.34 ± 0.11 | 44.87 ± 0.10 | 44.48 ± 0.09 |\n| FFSP ($N=100$, $M=12$) | 95.45 ± 0.52 | 94.32 ± 0.31 | 92.88 ± 0.20 | 92.15 ± 0.12 | 91.48 ± 0.08 |\n\nWe can observe that PARCO is robust and yields consistent improvements.\n\nTo clarify, the \"Time per Epoch (s)\" metric on the right y-axis of Figure 3b represents the wall-clock training time in seconds. This is a standard measure of computational throughput, indicating how long it takes to complete one full training epoch on the FFSP dataset. The figure illustrates that PARCO's parallel architecture allows it to process an entire epoch of training data significantly faster than the sequential MatNet baseline, demonstrating its superior training efficiency. \n\n\n**Q1: Learning stability and computational complexity**\n \nThe learning stability and computational complexity with growing number of agents is one of the greatest strengths of PARCO. PARCO's design directly confronts the challenge of a large joint action space via: \n- Factorization of joint action space: PARCO does not compute a probability distribution over the entire joint action space of size $N^M$. Instead, PARCO leverages the fact that all agents share the same action space, generating a joint logit space of dimension $N \\times M$. In addition, our method generates this joint logit space in parallel (one forward pass) via our multiple-pointer mechanism enabling efficient scaling to multi-agent settings without combinatorial explosion.\n- Coordination through communication layers: The attention-based coordination layer effectively helps to coordinate even a large (and as we show in the result table below also an unseen) number of agents\n- Intelligently resolving decision conflicts (e.g., two agents selecting the same customer) using learned priorities\n\n\nThe effectiveness of these components is also demonstrated in Figure 3a, 3b, and 3c of the paper. While 3a and 3c show the effectiveness of our communication layer and conflict handler respectively, figure 3b demonstrates that PARCO requires fewer forward passed of the neural policy to construct a solution, when the number of agents increases, leading to much shorter training and inference times.  \n\n\n**Q2: Is the agent embedding also used in the decoding process?**\n\nYes, after the communication layer, which sends the agent embeddings as well as context information (like remaining workload) through a transformer layer, the resulting query vectors q are used in the decoding process in order to generate the score matrix $\\mathbf{u} \\in \\mathbb{R}^{M \\times N}$ (i.e. one score for each agent-node pair). \n\n\n**Q3: About the overestimation bias**\n\nThank you for the insightful question. While priority is derived from the policy, our method does not introduce overestimation bias, due to the structure of the REINFORCE + POMO update and our deterministic fallback mechanism.\n\n#### Gradient-Based Analysis:\n\nIn case of conflict (i.e., multiple agents selecting the same node), only the agent with the highest action probability $g_{\\theta} (a_t^m | a_{<t}, \\mathbf{h})$ is allowed to proceed; the others fall back to a deterministic \"do-nothing\" action (with $\\log p_\\theta (a_t^m) = 0$ and zero gradient).\nWe apply REINFORCE with a POMO-style baseline. The policy gradient for solution $\\tau_i$ is:\n\n$$\n\\nabla_\\theta J(\\theta) \\propto \\nabla_\\theta \\log \\pi_\\theta(\\tau_i|x) \\cdot (R(\\tau_i) - \\bar{R})\n$$\n\nwhere $R$ is the return the $i$-th POMO rollout and $\\bar{R}$ is the mean return across multiple POMO rollouts.\n\n##### Case 1: Agent $m$ wins in a conflict and executes $a_t^m$ in solution $\\tau_i$:\n\n- If $R_i > \\bar{R}$: the update is positive &#8594; the action is reinforced and the chances of agent $m$ winning increase.\n- If $R_i < \\bar{R}$: the update is negative &#8594; the action is penalized and the chances of agent $m$ winning decrease.\nThus, high-priority agents are not blindly reinforced; they are only updated in proportion to actual performance.\n\n##### Case 2: The agent looses and is forced into a deterministic fallback action with probability 1:\n\n- $\\log \\pi(\\text{fallback}) = 0$\n- $\\nabla_\\theta \\log \\pi = 0$\n\nHence, the gradient update is zero, and no reinforcement occurs, even if the original action had high $\\pi$. Therefore, no overestimation bias is introduced. The priority mechanism acts only as a selection filter and the gradient remains aligned with actual performance outcomes.\n\n\n**Q4: Is PARCO used in an untrained number of agents?**\n\nYes! We also tested PARCO in not only a new number of agents $M$ , but also new number of nodes $N$. This is the result of Table 2.\n\n\nMoreover, we have further tested PARCO for even larger scales in both number of nodes and number of agents during the rebuttal. We generated 16 new instances for $N=5000$ nodes and 3 different values of $M$ agents total of 48 instances of OMDCPDP and evaluate OR-Tools with 1 hour of runtime and greedy performance for HAM and PARCO. The results are in the table below:\n\n\n|        | $M=500$ |  |  | $M=750$ |  |  | $M=1,000$ |  |  |\n|--------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|\n|        | Obj. | Gap | Time | Obj. | Gap | Time | Obj. | Gap | Time |\n| OR-Tools | 5575.73 | 134.06% | 3600s | 5127.46 | 115.24% | 3600s | 4974.81 | 188.10% | 3600s |\n| HAM | 4813.99 | 102.08% | 17.4s | 3732.06 |97.33%| 19.5s | 3258.26 | 88.69% | 22.3s |\n| PARCO | **2382.22** | **0.0%** | **0.21s** | **1891.28** | **0.0%** | **0.21s** | **1726.78** | **0.0%** | **0.22s** |\n\nAs we can see from the results, PARCO excels at generalization in extremely large scales with $50\\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools at a $10,000\\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications."}]

Author rebuttal:

Meta-review: Summary:

This paper introduces PARCO (Parallel AutoRegressive Combinatorial Optimization), a novel reinforcement learning framework designed to solve multi-agent combinatorial optimization (MACO) problems. The core contribution is a parallel solution construction method that addresses the high latency and poor coordination of traditional sequential autoregressive models. PARCO integrates three key components: (1) transformer-based Communication Layers to facilitate effective coordination among agents during decoding; (2) a Multiple Pointer Mechanism that enables simultaneous, low-latency decision-making for all agents; and (3) a Priority-based Conflict Handler that uses learned priorities to resolve action conflicts and ensure solution feasibility. The authors evaluate PARCO on several challenging multi-agent routing (HCVRP, OMDCPDP) and scheduling (FFSP) problems, demonstrating that their approach outperforms state-of-the-art learning-based methods and traditional solvers in terms of solution quality, computational efficiency, and generalization.

Strengths:
- Strong Empirical Performance and Efficiency: PARCO consistently achieves state-of-the-art results, outperforming strong learning-based and traditional baselines (e.g., OR-Tools) across multiple complex MACO domains. Its parallel construction method leads to remarkable computational speedups, making it suitable for real-time applications.
- Novel and Sound Methodology: The proposed parallel autoregressive framework is a significant and well-motivated departure from prior sequential methods. The architectural components, particularly the Communication Layers and Multiple Pointer Mechanism, are considered well-designed and theoretically sound for enhancing agent coordination and efficiency.
- Excellent Generalization and Scalability: The framework demonstrates impressive zero-shot generalization to problem instances with significantly more nodes and agents (up to 50x larger than seen in training). The authors substantiated this during the rebuttal with new large-scale experiments, showcasing robust performance with up to 1,000 agents.

Weaknesses:
- Clarity and Terminology: The most consistent remaining critique, raised by Reviewer NRcw, pertains to the clarity of the writing and the use of non-standard terminology. Specifically, framing the multi-agent problem as a Markov Decision Process (MDP) was noted as potentially confusing, with "Markov Game" being the more appropriate term from literature. The authors have acknowledged this and committed to revising the text for the camera-ready version.

The Most Important Reason for Decision:

The decision to recommend acceptance is based on the fact that the paper's significant strengths and contributions convincingly outweigh its remaining, and largely addressable, weaknesses. The authors propose a novel, efficient, and high-performing framework for a challenging and practical class of problems. The quality and thoroughness of the author rebuttal were exceptional; they provided substantial new experiments (including a new mTSP benchmark and very large-scale tests) that successfully addressed the vast majority of the initial, more critical concerns raised by the reviewers. The paper makes a solid contribution to the field of neural combinatorial optimization.

Summary of Rebuttal and Changes

The discussion period was highly productive and pivotal. Initially, the paper received mixed reviews, with significant concerns from Reviewer NRcw. Key points raised and addressed were:

Concern 1: Lack of Comparison with Other Methods

Points Raised: Reviewer HMqs noted that the paper lacked a comparison with decentralized approaches and alternative communication models, such as those based on Graph Neural Networks (GNNs).

Authors' Response: During the rebuttal, the authors conducted new experiments on the min-max traveling salesman problem (mTSP). They benchmarked PARCO against notable decentralized methods (GNN-DisPN, DAN) and a GNN-based communication model (ScheduleNet), with results showing PARCO consistently outperforming these baselines in solution quality.

Final Decision Weight: This was a significant addition that addressed a clear gap in the original submission. By providing new, targeted experiments, the authors substantially strengthened the paper's empirical claims and demonstrated the superiority of their approach. This weighed heavily in favor of acceptance.

Concern 2: Effectiveness and Design of the Conflict Handler

Points Raised: Reviewer NRcw raised major concerns about the conflict handler, describing it as a "fixed, non-adaptive, and non-learnable fallback mechanism". Reviewer GvYn also questioned whether using the policy's output for priority could introduce overestimation bias.

Authors' Response: The authors provided a detailed clarification, explaining that the mechanism is adaptive because it uses learned priorities from the model's output to select a single "winner" in a conflict. To address the bias concern, they provided a gradient-based analysis showing that the deterministic fallback has a zero gradient, thus preventing reinforcement and overestimation.

Final Decision Weight: This was a critical point of discussion. The authors' thorough response corrected a key misunderstanding of their method and successfully addressed the concerns about adaptiveness and bias. This was significant in mitigating what was initially a significant reason for potential rejection.

Concern 3: Lack of Training Analysis and Perceived Marginal Improvement

Points Raised: Reviewers NRcw and GvYn noted the absence of training curves to evaluate convergence and stability. Reviewer NRcw also initially felt the reported performance improvements were "quite marginal".

Authors' Response: The authors provided tables with convergence data and committed to including full training curve plots in the final version. To counter the claim of marginal improvement and demonstrate practical significance, they conducted new, very-large-scale experiments (up to 5000 nodes and 1000 agents), showing that PARCO finds superior solutions up to 10,000x faster than strong traditional solvers like OR-Tools.

Final Decision Weight: The new large-scale results were particularly compelling, highlighting the method's strengths in scalability and efficiency, which significantly boosted the paper's perceived impact and weighed strongly in favor of acceptance.

Concern 4: Problem Formulation and Terminology

Points Raised: Reviewer NRcw found the terminology inconsistent with standard multi-agent literature, specifically the use of "Markov Decision Process (MDP)" for a multi-agent setting, which could be confusing for readers.

Authors' Response: The authors acknowledged the reviewer's point, explaining that their formulation is functionally equivalent to a fully cooperative Markov Game. They agreed to add a reference to relevant literature (e.g., Boutilier) and clarify their terminology in the camera-ready version to better align with standard conventions.

Final Decision Weight: While a presentation issue, resolving it was important for ensuring the paper's correctness and accessibility. This cooperative engagement was viewed positively in the final recommendation.
Decision: Accept (poster)