Neural Combinatorial Optimization on Heterogeneous Graphs. An Application to the Picker Routing Problem in Mixed-shelves Warehouses

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 20:01:00

Abstract: In recent years, machine learning (ML) models capable of solving combinatorial optimization (CO) problems have received a surge of attention. While early approaches failed to outperform traditional CO solvers, the gap between handcrafted and learned heuristics has been steadily closing. However, most work in this area has focused on simple CO problems to benchmark new models and algorithms, leaving a gap in the development of methods specifically designed to handle more involved problems. Therefore, this work considers the problem of picker routing in the context of mixed-shelves warehouses, which involves not only a heterogeneous graph representation, but also a combinatorial action space resulting from the integrated selection and routing decisions to be made. We propose both a novel encoder to effectively learn representations of the heterogeneous graph and a hierarchical decoding scheme that exploits the combinatorial structure of the action space. The efficacy of the developed methods is demonstrated through a comprehensive comparison with established architectures as well as exact and heuristic solvers.

Main paper: 
 introduction 20: 
 In recent years, there has been a remarkable surge in the adoption of end-to-end ML methods for solving NP-hard CO problems, which offers an appealing alternative to the tedious task of manually crafting heuristics. Typically, neural combinatorial optimization (NCO) integrates deep neural networks as feature extractors in the reinforcement learning (RL) framework to enable a neural agent to learn optimal decisions based on the extracted information. Significant progress has been made in both of these domains, particularly with the Attention Model (AM) proposed by Kool, van Hoof, and Welling (2019) and improved training algorithms like POMO (Kwon et al. 2020) , which led to substantial performance improvements. Nevertheless, most of these advances are designed for and applicable to only a limited number of simple CO problems, with the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP) being the most frequently used problems (Mazyavkina et al. 2021) . To foster its practical relevance, NCO also has to demonstrate its effectiveness in dealing with more complex real-world problems, which necessitates the design of novel models and algorithms. Therefore, in this work, we will focus on the Mixed-shelves Picker Routing Problem (MSPRP) as an example application to develop new methods within the NCO framework that are capable of addressing more complicated CO problems.In a warehouse context, picker routing is concerned with generating efficient sequences of storage locations to be visited by a picker to collect items requested by customer orders and deliver them to a central packing station. Recent research has focused on picker routing in mixed-shelves warehouses, where items of the same stock keeping unit (SKU) are spread across multiple shelves, allowing pickers to choose between alternative storage locations and thus reduce the travel distances (Xie, Li, and Luttmann 2023) . The integration of selection and routing decisions in MSPRP results in a complex combinatorial action space when formulating the problem as a sequential decision problem. Thus, we utilize the MSPRP as an example of a more complex CO problem to pioneer the development of neural architectures capable of addressing a broader spectrum of CO problems than those currently covered in existing NCO literature.While Cals et al. (2021) are the first to apply RL to improve warehouse operations, they focus on the problem of order batching. To the best of our knowledge, no work has yet used this framework to generate solutions for the picker routing problem. Therefore, we first formulate the MSPRP as a Markov Decision Process (MDP), where we represent the state of the problem instance as a heterogeneous graph. Further, we develop a novel encoder-decoder architecture, where the encoder is specifically designed to effectively learn representations over the heterogeneous graph structure. The decoder then uses these representations to select actions from a factorized action space in a hierarchical manner. To the best of our knowledge, this work is the first in the NCO field to perform an action space factorization using a hierarchical decoding strategy. Other work dealing with multidimensional action spaces either flatten it by including every possible combination of the distinct action space dimensions or solve only parts of the decision problem using a neural agent and others by handcrafted heuristics. We will demonstrate that both our encoder and decoder models perform better than the other methods currently employed in the literature. Therefore, this work not only contributes to the field of NCO by demonstrating its effectiveness on a novel problem class, but also by developing new models that hopefully allow more CO problems with similar problem structure to be effectively solved using NCO.Mixed-shelves Picker Routing. The picking process is known to be a very labor-intensive and time-consuming task, representing an estimated 50-65% of the total operating cost for a warehouse (De Koster, Le-Duc, and Roodbergen 2007) . Within conventional picker-to-parts warehouses, the majority of a pickers' working time is dedicated to traveling between shelves (Tompkins 2010) . Minimizing the travel distance of order pickers has consequently been extensively studied in the operations research community and a vast body of literature on the picker routing problem has emerged over the years. We refer to the literature review of De Koster, Le-Duc, and Roodbergen (2007) for a comprehensive overview on picker routing and related warehousing decision problems. Here we focus in particular on picker routing in mixed-shelves warehouses which can be regarded a combined problem of selecting the storage positions to visit and the actual picker routing. The first to treat this kind of problem were Daniels, Rummel, and Schantz (1998) who considered a TSP variant of the MSPRP, where the set of orders to be collected during a tour is assumed to be determined by a preceding order batching step. The authors define a mathematical model for the problem and propose a tabu search algorithm to solve it. Later, Weidinger (2018) solve the same problem under the assumption of a rectangular warehouse using a more efficient heuristic based on the dynamic programming algorithm of Ratliff and Rosenthal (1983) . More recently, Weidinger, Boysen, and Schneider (2019) and Xie, Li, and Luttmann (2023) extend the MSPRP by integrating the decision which orders to pick during a tour into the problem. Their problem can be regarded a variant of the capacitated VRP due to the construction of multiple tours with limited capacity. While Weidinger, Boysen, and Schneider (2019) propose different construction heuristics and an iterative improvement procedure based on destroy and repair operators, Xie, Li, and Luttmann (2023) develop a Variable Neighborhood Search (VNS) to solve this problem.Neural Combinatorial Optimization. The Ptr-Net proposed by Vinyals, Fortunato, and Jaitly (2015) was the first architecture that was specifically designed to solve CO problems. The authors used supervised learning to train the network to solve the TSP using optimal solutions as training data. Their architecture follows an encoder-decoder structure, where the encoder maps customer locations from the feature space to learned embeddings, which in turn are used by the decoder to iteratively select the next location to visit. Later, Bello et al. (2017) proposed a Deep Reinforcement Learning (DRL) approach to train Ptr-Nets without the need for a database of optimal solutions. Network architectures other than the Recurrent Neural Networks used in the Ptr-Net were proposed by Nazari et al. (2018) and Kool, van Hoof, and Welling (2019) . The latter introduced the AM which incorporates the multi-head attention mechanism of Vaswani et al. (2017) in both encoder and decoder of the Ptr-Net and is still the state-of-the-art NCO architecture.Recently, Mazyavkina et al. (2021) provided a structured literature analysis of RL for CO problems. The authors found that the majority of the literature proposes methods for simple CO problems, with the TSP and capacitated VRP being covered the most. A notable exception is the work of Kwon et al. (2021) , who propose a novel encoder based on the AM that is applicable to a wider range of CO problems that can be expressed as bipartite graphs.On the other hand, new decoder models for more complex CO problems have hardly been investigated, as also Hildebrandt, Thomas, and Ulmer (2022) note. They identified that most research applying RL to more complex VRP variants uses either an action space restriction or a simplifi-155 cation thereof. In the former case, the RL agent is only used to generate solutions for a sub-problem, and everything else is solved using established heuristics. An example is Chen, Ulmer, and Thomas (2022), who also face a combined selection and routing problem where they use a neural agent to 160 select a vehicle from a heterogeneous fleet, but rely on handcrafted heuristics for route generation. An example of action space simplification can be found in Song et al. (2022) , who propose a heterogeneous graph attention network as a feature extractor for the job-shop scheduling problem, where 165 jobs and machines pose different node types to be represented by the encoder. In the end, they propose to concatenate the learned embeddings of jobs and machines and consider a combinatorial actions space with all job-machine combinations in the decoding stage. Although this flatten-170 ing of the action space is straightforward to implement, an obvious drawback is the size of the action space growing quadratically with the number of jobs and machines.This work considers an MSPRP similar to the one outlined 175 by Weidinger, Boysen, and Schneider (2019) . However, Xie et al. (2021) proposed the concept of split orders, which allows items of an order to be picked within different tours, resulting in significantly shorter picker routes. Inspired by their findings, we relax the constraint that items of the same 180 order must be collected in one picker tour. This adjustment is further justified by our focus on single-depot instances, ensuring that items from a single order reach the same packing stations for consolidation and packaging, regardless of the tour in which they were picked.1 185 The goal of our MSPRP is then to pick all d p demanded units of all requested SKUs p ∈ P while minimizing the travel distance of the various picker tours b ∈ B. A tour is defined by the storage locations visited between two successive visits to the packing station h, where picked items are 190 unloaded and commissioned. During a tour, no more than κ units can be picked. We assume that the demand for an SKU must not be satisfied by a single picker tour, but can be split over multiple tours and collected from different shelves (split deliveries). Each SKU may be retrieved from multi-195 ple shelves / racks i ∈ V R of the warehouse. However, for the formulation of the mathematical model, we follow the approach of Weidinger, Boysen, and Schneider (2019) and consider storage locations i ∈ V S instead of shelves. Accordingly, each shelf consists of multiple storage locations 200 or compartments, each of which can store units of only a single SKU. The distance D ij between storage locations of the same shelf is zero. To collect an SKU p during a tour, a picker can choose between the different storage locations i ∈ V S p storing n i > 0 units of this SKU. Further, to formulate the mathematical model, we need to determine the number of tours required to fully satisfy the demand. Due to the assumption of split orders and split deliveries, this is simply the ceiling of the total demand divided by the picker capacity: |B| = p dp κ. Table 1 summarizes the notation 210 used to define the mathematical model.EQUATIONEQUATION)EQUATIONThe objective function (1) minimizes the total distance travelled by the picker. Every storage location that is visited during a picker tour must also be left, which is ensured by constraints (2). Moreover, constraints (3) ensure that a storage location is visited only once during a tour. Although a storage location may be visited multiple times if the remaining capacity of the picker does not suffice to satisfy the respective demand in one go, it does not make sense to visit the same storage location twice within one tour.Through the Big-M formulation in (4) we make sure that only items are taken from a storage location if this location is also included in the respective tour. As no more than κ items may be picked in a single tour, it is sufficient to set M = κ. Since every tour must start and end at the depot, 225 equations ( 5) require that the depot is left exactly once in P Set of SKUs for picking V L Set of storage locations and depot(V L = V S ∪ {h}) E Set of edges {(i, j) | i, j ∈ V L , i ̸ = j} V S pSet of required tours {1, 2, ..., |B|} D ij Distance between two nodes (i, j) ∈ E κ Maximum picking capacity per tour d p Total demand for item p ∈ P n i Available supply at storage location i ∈ V S x ijt Binaray variable, indicating whether Node j ∈ V L has been visited after node i ∈ V L in tour b ∈ B y it Units picked up at location i ∈ V S in tour b ∈ B Table 1 : Notation used in the MIP-Model every tour. In combination with the network flow constraints (2) this also ensures that each tour goes back to the depot. And the subtour elimination constraints ( 6) ensure that all storage locations visited in between are also connected to the tour. Constraints (7) ensure that the picker capacity is not exceeded. Furthermore, constraints (8) make sure that customer orders are satisfied and inequalities (9) take care that the available stock of items in a shelf is not exceeded during order picking. Lastly, constraints ( 10) and ( 11) delineate the domains of the decision variables x and y.Similar to other CO problems, a solution to the MSPRP can be obtained via a sequence of decisions, which can naturally be constructed using RL. In each iteration t = 0, . . . , t max , the RL agent decides the next location to visit and which items to pick until the demand for all SKUs is met. We model the solution construction as an MDP with the policy being a θ-parameterized neural network π θ which takes the state representation as input and outputs a probability distribution over the action space. In this chapter, we will first define the state, action space, transition rule and reward function of the MSPRP. Then, our policy network based on the encoder-decoder framework will be described in detail.State. Typically, the state of a CO problem is represented by a graph. For the MSPRP we found two possible graph representations. First, one could consider each available shelf and SKU combination as a unique storage location, similar to our mathematical model. However, a challenge arises in finding a size-agnostic feature representation for storage locations, which needs to include the supply and demand of the SKU contained in the storage location. Given that an SKU can exist in multiple locations, a representation ensuring unique identification of the stored SKU is necessary. The mathematical model addresses this by defining a subset V S p of locations containing SKU p. However, the encoder requires a vectorized representation, for instance, using a one-hot representation. Yet, this approach violates the requirement of the model being agnostic to the instance size, an important generalization property of NCO models.Thus, a more natural way of representing the state of an MSPRP instance is by using a heterogeneous graph with different node types, namely shelves and SKUs. Let at each decision step t, the state s t ∈ S be a graph G = (V, P, E t , c t ) representing the current status of the problem. The set of location nodes V is the union between the packing station h and the shelves V R . We follow the common practice in the NCO field and represent the location nodes by their Cartesian coordinates x V i ∈ R 2 . The set of SKUs P poses the second type of nodes in the heterogeneous graph. We use x P p to denote the feature representation of an SKU p, which consists only of its demand d p,t at time t. Moreover, edges with weights E t connect shelf and SKU nodes, specifying the storage quantity e ip,t of an item p in the respective shelf i at time t. Lastly, the graph is augmented by the context node c t , containing dynamic context information relevant for the decoding stage. It consists of the current location i t of the picker as well as the remaining picker capacity κ t .Action. An action a t ∈ A(s t ) corresponds to a feasible shelf-SKU combination (i, p) specifying the next picking job. Given s t , visiting shelf i is a feasible action if it can satisfy the demand of at least one SKU currently in demand. Furthermore, given the next picking location i, an SKU p may only be selected if it is available in the respective shelf.The depot can always be visited to replenish the picker's capacity, but consecutive visits to the depot are prohibited. When the picker's capacity is exhausted, visiting the depot is the only possible action. We introduce a dummy SKU |P|+1 that is selected when the depot is visited. Furthermore, we assume that the picker always starts and ends the tour at the depot, i.e. a 0 = a tmax = (h, |P| + 1).Transition. Once, a feasible shelf-SKU pair (i, p) has been selected, the transition function Γ • (s t , a t ) deterministically determines the next state s t+1 . To this end, the picking quantity y t is determined in a first step. Here, we choose to always pick the maximum feasible quantity, that is the minimum of the shelf's supply for the SKU, the SKU's demand and the remaining picker capacity. Given a t and y t , the environment deterministically transits to a new state s t+1 . It consists of the new location i t ∈ V, the updated demand d p,t+1 = d p,t -y t , the updated supply e ip,t+1 = e ip,t -y t and the remaining picker load κ t+1 = κ t -y t . When the agent chooses to return to the depot, the picker capacity will be set to the initial payload κ and supply and demand remain unchanged. The problem instance is solved once the demand for every SKU is met and the picker has returned to the depot. We use τ to denote the complete solution starting and ending at the depot, i.e. τ = {a t , t = 0, ..., t max }.Reward. To minimize the total travel distance of the picker, we define the reward R(τ ) as the negative of the objective value defined in equation (1), i.e. the summation of distances between locations visited in τ .Encoder. In this work we are facing a CO problem which is defined over a heterogeneous graph with different node types, namely shelves and SKUs. Heterogeneous nodes have different properties, manifested in distinct feature spaces. This requires specialized architectures specifically designed for handling heterogeneous inputs and relationships between 325 them. Several models have been proposed in the literature for learning representations over heterogeneous graphs. The Heterogeneous Graph Attention (HAN) architecture, introduced by Wang et al. (2019) , adapts the Graph Attention Network (GAT) to handle graphs with diverse node types. 330 To this end, the authors propose type-specific transformations to project the different node-types from their distinct feature spaces into a mutual embedding space of dimensionality d h . The mutual embedding space is then used to calculate attention scores α between the different nodes:335 α l ij = exp(ϵ l ij ) q∈Ni exp(ϵ l iq ) , ϵ l ij = σ w l ⊤ [h l-1 i ||h l-1 j ] (12)where, w l ∈ R 2d h is a learnable weight vector, [•||•] denotes vertical concatenation, σ represents a non-linear activation function, and N i is the neighborhood of node i, including node i itself. Moreover, h l i denotes the embedding of node i after the lth layer, where h 0 i is the initial embed-340 ding obtained via the type-specific transformations W ϕi for a node of type ϕ i . The attention scores are then used to compute the node embeddings h l i as a weighted sum over all embeddings h l-1 j of nodes j in the neighborhood of i, along with the embedding h l-1 i itself. One drawback of this archi-345 tecture is that no edge weights are utilized when computing the attention score. Therefore, the HGCN proposed by Yang et al. (2021) adapts the Graph Convolution Network (Kipf and Welling 2017) to aggregate the node embeddings from the neighborhood of a node using the adjacency matrix di-350 rectly. HGCN then uses an attention mechanism similar to HAN to compute a weighted sum of the target node embedding and the aggregation of the neighborhood embeddings.For CO problems formulated over homogeneous graphs like the TSP, the AM has been shown to outperform other 355 graph neural networks such as the GNN proposed by Khalil et al. (2017) by a large margin. Therefore, Kwon et al. (2021) adapt the attention model to solve CO problems defined over bipartite graphs with node types I and J as well as weights E ∈ R |I|×|J | of the edges connecting nodes from 360 the two sets. The encoder of their MatNet architecture also uses type-specific transformations to generate initial embeddings h 0 i of size d h for all nodes. Then, for each of the node types the authors apply distinct update functions F I and F J . The update functions perform L layers of multi-head 365 cross-attention to calculate attention scores between a target node i and all nodes j from the respective other set. To this end, let Z be the set of all nodes i ∈ I ∪ J , Z ϕi the subset of nodes of the same type as i and Z ∁ ϕi the set of nodes of the respective other type. Then, cross-attention is defined as:EQUATION)whereq i = W Q ϕi h l-1 i k j = W K ϕi h l-1 j (14)and weight matrices W Q ϕi and W K ϕi ∈ R d k ×d h being learned by the update function corresponding to nodes of type ϕ i . After that, Kwon et al. (2021) propose to concatenate α ′ ij with the corresponding edge weight e ij and map it through a feed-forward neural network FF : R 2 → R to a scalar score, which is then normalized using the softmax function:EQUATIONThe resulting weights are used to compute a weighted average of the embeddings v j = W V ϕi h l-1 j of the nodes in Z ∁ ϕi . In the end, skip connections, layer normalization (LN) and feed-forward layers are used as in Vaswani et al. (2017) :EQUATION)h l i = LN ĥl i + FF l ( ĥl i ) , ∀i ∈ Z (17)Although MatNet poses a viable extension of the AM, we consider the limitation to bipartite graphs as a shortcoming. In bipartite graphs, relations exist only between nodes of different types, yet many real-world problems formulated over heterogeneous graphs also involve intra-type relationships.For instance, in the MSPRP shelf nodes strongly influence each other due to the potential availability of the same SKU in multiple shelves. By exclusively focusing on inter-type relationships through the application of cross-attention, the MatNet encoder may not fully encompass such relationships in the node embeddings.Motivated by the identified weaknesses of existing approaches, we propose the Heterogeneous Attention Model (HAM), which is an extension of the MatNet encoder for the more general case of a heterogeneous graph. As usual, our HAM encoder first projects the feature vectors into a mutual embedding space using type-specific transformations. Then, multi-head self-attention (MHSA), followed by skip-connection and layer normalization, as described by Vaswani et al. (2017) , is performed for each node type:hl i = LN(h l-1 i + MHSA l ϕi ({h l-1 j | j ∈ Z ϕi }), ∀i ∈ ZUsing self-attention allows the network to learn relationships between nodes of the same type, like the substitutability of shelves containing the same SKUs.Next, we apply the operations described in equations (13-17) to capture inter-type relationships, but we replace h l-1 in equations ( 14) and ( 16) with hl . Moreover, we remove the feed-forward layer and the concatenation in equation ( 15) and simply multiply α ′ ij and e ij , which yielded better results in our experiments while being much faster. Figure 1 depicts the architecture of our HAM encoder. Decoder. This work uses a hierarchical decoder to sample actions specifying the next location i t to visit and the SKU p t to pick. To this end, we decompose the action space of composite actions A into the sub-action spaces A V ≡ V and A P ≡ P, where A = A V × A P . Similar to Sharma et al. (2017) , our hierarchical decoding strategy uses a separate policy network for each sub-action space. However, in contrast to Sharma et al. (2017) , we do not sample from the shelf-and SKU-policy independently, but in a hierarchical manner. Therefore, let Γ • : S × A V → S ′ be a partial transition function generating an intermediate state s ′ t with updated location information i t . Moreover, let π θ V : S → A V be the shelf-policy and π θ P : S ′ → A P the SKU-policy, then sampling a composite action a from π θ (a t | s t ) is equivalent to sampling shelves and SKUs successively from π θ V and π θ P , respectively, according to the chain rule of probability:EQUATIONWhile the sub-policies share the same encoder they have their own decoder networks. We use the decoder architecture from the AM for both the shelf-and the SKU-policy. The attention decoder for sub-action space A d performs multi-395 head attention by using the embeddings h L i of the respective node type from the encoder to compute keys and values. Moreover, the context node c t is used by each decoder to compute the query (again omitting head enumeration):q c = W Q d h c k i = W K d h L i v i = W V d h L i ∀i ∈ A dwhere h c is the concatenation of the encoder embedding of 400 the current picker location h L it and the remaining picker capacity κ t . Again, W Q d , W K d and W V d are weight matrices learned per head and sub-action space A d . The MHSA operation generates a glimpse, similar to Bello et al. (2017) . The glimpse is multiplied with a single-head transformation 405 of h L i to obtain the logit for action i in the respective subspace. Lastly, softmax-normalization of the logits over all actions in the sub-space yields their sampling probabilities. Training. To learn the parameters θ of the policy network, we adapt the POMO training algorithm proposed by Kwon et al. (2020) . POMO is based on the well-known REIN-FORCE gradient estimator (Williams 1992) :EQUATION)whereπ θ (τ i |s i ) = tmax t=2 π θ (a i,t |s i,t), b is a baseline function, used to reduce the variance of the estimated gradients and B is the size of the mini-batch. In POMO, the baseline for a training instance is computed as the average reward of W sampled solutions for that instance. To generate diverse sampled solutions, POMO employs W distinct initial actions, from which the policy network constructs trajectories through Monte-Carlo rollouts. For the MSPRP this means using W different shelf-SKU combinations for the first picking task a 1 . However, unlike TSP or CVRP where all locations need to be visited anyway, the MSPRP does not require all shelves to be visited. Consequently, selecting a random shelf at the start of the picker tour can drastically deteriorate the solution quality, when this shelf is at the other end of the warehouse. Consequently, selecting the initial actions randomly may result in a high variance of the baseline, especially for small W . Therefore, instead of selecting W random actions, we sample them from the policy π θ (a|s) without replacement (wor). To ensure predominantly favorable initial moves right from the start of the training process, we warm the policy network up for one epoch using an exponential moving average over the mini-batch rewards as baseline, similar to Kool, van Hoof, and Welling (2019) . Given the baseline b(s i ), gradients are computed using equation (19) and we use the Adam optimizer (Kingma and Ba 2015) with a learning rate of 2e-4 to obtain the parameter updates. Algorithm 1 summarizes this procedure which we will refer to as Policy-aware POMO (Pa-POMO). Empirically, we found that, using the Pa-POMO training algorithm, the variance of the baseline value is reduced by 20% compared to POMO. Figure 3 shows how the variance of the gradient updates for POMO and Pa-POMO evolve during training, demonstrating the effectiveness of our Pa-POMO method for the MSPRP. {a 1 i,1 , a 2 i,1 , . . . , a W i,1 } wor ∼ π(a i | s i ) ∀ i = 1, ..., B5:s j i ← Γ • (s i , a j i,1 ) ∀ i = 1, ..., B, j = 1, ..., W 6: τ j i ← π θ τ j i |s j i ∀ i = 1, ..., B, j = 1, ..., W 7: b i = 1 W W j=1 R(τ j i ) ∀ i = 1, ...8:A j i ← R(τ j i ) -b i ∀ i = 1, ..., B, j = 1, ..., W 9: ∇ θ L ← 1 B•W B i=1 W j=1 A j i ∇ θ log π θ (τ j i |s j i ) 10: θ ← Adam(θ, ∇ θ L) 11: end for Experiments 450Experimental Setup and Instance Generation Dataset. For training and evaluating the proposed policies, we generate instances for three warehouse types that differ in the number of available storage locations and shelves. In conformity with other NCO literature, that typically tests 455 models on TSP and VRP instances with 20, 50 and 100 nodes, we consider instances with 20, 50 and 100 storage locations V S referred to as PRP20, PRP50 and PRP100, respectively. While the number of shelves is fixed to 10, 25 and 40 for the respective instances, we alter the number of 460 demanded SKUs for each warehouse type.We follow the standard procedure in NCO literature and sample the |V R | shelf locations uniformly at random in the unit square and assume Euclidean distances between them. We choose this approach over a realistic rectangular ware-465 house layout with parallel racks and non-Euclidean distance as described for example in Weidinger (2018) , as this would introduce additional complexity through the requirement of a distance matrix. Since we are more interested in demonstrating the ability of the proposed methods to solve CO 470 problems over heterogeneous graphs, we sacrifice some realism here to facilitate model development.We randomly select the |V S | storage locations from all |P| × |V R | possible SKU-shelf combinations and sample the supply from a discrete uniform distribution with mean 475 ni . Likewise, the demand for each SKU is sampled from a discrete uniform distribution with mean dp . Lastly, we clip the demand of an SKU by the warehouse's total supply for it in order to ensure feasibility of all generated instances. Table 2 summarizes the parameters of the different instances.PRP20 PRP50 PRP100 |V R | --10 ----25 -- -40 - |V S | --20 ----50 -- -100 - dp --2.5 ----2.5 -- -2.Setup. We empirically validate the effectiveness of the proposed encoder-decoder architecture for solving the MSPRP in two steps. First, we evaluate the encoder as well as the hierarchical decoder of our HAM by comparing them with other approaches that we found in the literature. Then, we compare our DRL model with the solutions obtained by a heuristic and an exact solver.For the first part, we use the HAN, HGCN and MatNet encoders we introduced earlier alongside our HAM encoder. Moreover, we use a homogeneous graph formulation of the MSPRP, using storage locations as sole node types, to solve it using the AM. For all encoder architectures, we are using our hierarchical decoder. One exception from this is the homogeneous graph formulation, which naturally has a flat action space and thus uses a single AM decoder. On the contrary, we validate the effectiveness of the hierarchical decoder by comparing it with a single AM decoder operating on the combinatorial action space similar to Song et al. (2022) as well as a hybrid policy, combining a neural agent and a handcrafted heuristic, like Chen, Ulmer, and Thomas (2022) . This policy uses the AM decoder only to determine the next location to visit and, given a shelf, selects the SKU for which the most demand can be satisfied. Each of these decoders uses the HAM encoder as a feature extractor.All policy networks are trained for 50 epochs on 350,000 training instances that are randomly generated on the fly, and evaluated on 30,000 test instances for each of the six instance types corresponding to layouts PRP20 and PRP50. We refrain from comparing all models on the PRP100 instances due to the immense computational training effort.These instances are only used in the second part of the experiments, where we compare our DRL model with a heuristic and the solutions obtained by the Gurobi solver, for which we set a time limit of 1 hour. Heuristic for comparison. In order to validate the solu-530 tion quality of our DRL method on instances where Gurobi cannot find the optimal solution within the time limit, we include the VNS of Xie, Li, and Luttmann (2023) into the comparison, where we can make some simplifications due to our split-order and single-depot assumptions. The VNS 535 starts by constructing a solution using a greedy nearestneighbor algorithm, determining for each SKU in random order the shelf and sequence-position that adds the least distance to the current tour. After that, the VNS iteratively tries to improve the solution by using a Shaking operation, de-540 stroying parts of the current solution and repairing them in random order, followed by a local search, altering shelves to visit and swapping items between tours. The Python implementation can be found in our GitHub codebase and a detailed description is found in Xie, Li, and Luttmann (2023) . 545The results of our experiments comparing different encoder architectures and decoding strategies can be found in Tables 3 and 4 , respectively. The HAM encoder clearly outperforms the other tested architectures. While the performance of the 550 MatNet encoder comes close to that of HAM, the other models performed significantly worse with the HAN architecture producing the most inferior results. But also the HGCN is (2022) , who also report large optimality gaps of up to 16%. Furthermore, the performance discrepancy compared to the 565 other methods increases with problem size, suggesting that the exponential growth of the action space leads to problems such as sample inefficiency on larger instances. While the hybrid approach achieves much better results than the composite policy network, the disparity with the hierarchi-570 cal approach becomes as large as 2.5% for PRP50 instances with 15 SKUs, which clearly outweighs the computational cost of the additional neural decoder.The comparison of HAM with Gurobi and the heuristic can be found in Table 5 . The Gurobi solver can only find op-575 timal solutions for all test instances on PRP20 instances. Remarkably, even on these instances, our HAM combined with beam search achieves on par solution quality with Gurobi. On the larger instances, where Gurobi could not find optimal solutions within the time limit, HAM consistently outperforms both the heuristic and Gurobi. Further, the short inference time allows for fast adaptation of current plans to the dynamics of the warehouse environment. In this work we have introduced an encoder-decoder model to solve CO problems that are defined over heterogeneous graphs and exhibit a combinatorial action space. We believe that our proposed methods can leverage the adoption of NCO for more complex CO problems and pose a serious competitor for handcrafted heuristics. Not only has the handcrafted heuristic been beaten on the majority of instances, but also the hybrid approach, combining a neural agent with a heuristic, has been proven to be less effective than the endto-end ML model. Not only is the development of an additional heuristic an extra-burden that NCO tries to eliminate, also is the use of heuristics limited due to the extraordinary efficiency requirement during model training. This usually requires the use of local and greedy search algorithms using only local information, since more sophisticated heuristics would introduce an unaffordable bottleneck during training. Conversely, the neural agent is not only capable to incorporate local information (such as determining which SKU of a given shelf can satisfy the most demand) but also the broader global context (e.g. identifying alternative sources for a particular SKU) in its decision-making. This alone motivates deeper research into DRL-based CO solvers. The notable achievement of our model, surpassing both exact and heuristic solvers on the majority of tested MSPRP instances, further underscores their substantial potential.One limitation of our work is that the HAM encoder is limited to heterogeneous graphs with only two node types and a single edge type between them. In future work, we will therefore adapt the proposed methods to CO problems with more complex heterogeneous graph representations, e.g. by relaxing the split-order assumption of our MSPRP, which would add another order dimension to the problem. Another important direction for future research is the scalability of ML models to larger instances. Here, our hierarchical decoding strategy makes an important contribution, since it offers the possibility to factorize the action space. Through the factorization, the number of possible actions in our MSPRP grows only linearly with the problem size as opposed to the exponential growth seen in the case of the combinatorial space. In future research we will further investigate means to make the model generalize to larger instances, for instance by training a foundation model on instances of different sizes and then fine-tune it to a specific instance type. Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations. Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations.The MSPRP covered here can be considered a special case of the problem described byWeidinger, Boysen, and Schneider (2019), where each order consists of only a single SKU. The authors provide a proof for the NP-hardness of the MSPRP.https://github.com/ellelsd/rl4msprp 
 
 Appendix:  


Decision: The paper introduces an NCO method for the Mixed-shelves Picker Routing Problem. Compared to existing NCO methods, this paper addresses a novel and compelling application domain and proposes a new NCO architecture. The rebuttal has effectively addressed most concerns raised by the reviewers. We recommend that the authors improve the final version based on the comments from the reviewers if the paper gets accepted.

Reviews: review: strength_weakness: strength_weakness: 1. The presented mathematical programming formulations are not optimized. Comparing HAM against them is thus not the most informative.

2. While the running time of the HAM approach looks fast, the training times are very long and do not seem to scale well in response to the problem size. 

3. The largest instance size is with 100 storage locations. For a realistic warehouse, the storage locations might be several orders of magnitude larger. With the reported training times, will this NCO approach be applicable to real-world instances?

4. As the HAM models are pre-trained, what if there are minor changes to the problem instance configuration (e.g., in terms of the number of storage locations, and SKU-related information); could the trained models be used to handle instances that are slightly different in sizes/state dimensions?
questions: questions: If possible, please provide responses to the comments made in the "Weaknesses" box.
strength_weakness: strength_weakness: •	The work only considers routing of one picker while, in real warehouses, multiple pickers need to be coordinated, which is usually more complicated than optimizing their routes individually.
•	The description of how routing instances are generated is not very clear.
questions: questions: 1. It is unclear how difficult the problem is. In Table 5, Gurobi is run up to 1 hour, and produces quite large average gap for PRP100. I understand it is not feasible to run Gurobi longer for so many instances. However, it would be interesting to let it run 20 hours for a few instances, and to get some idea on the difficulty of the problem. 
2. Is the dummy node connected to all the other nodes? And what are the edge features, if there are any?
strength_weakness: strength_weakness: (1) The authors promise to provide a solution suitable for more complex real-world problems, but do not provide any proof regarding the transferability of their approach.
(2) The description of the transition is not in correspondence to the state description
(3) Reward definition seems to be incomplete
questions: questions: (1) Why did you select MSPRP? What are the benefits regarding the field of NCO?
(2) There are several contributions in the field of NCO that deal with similar complex optimization problems (e.g. JSSP derivates). Why are these problems neglected / not mentioned?
(3) What are other complex optimization problems that benefit from your work? Why?
(4) The reward is defined in a sparse way? How do you deal with invalid sequences? Have you tried different reward designs?