A deep reinforcement learning approach to multistage stochastic network flows for distribution problems

Abstract

Distribution networks are a crucial part of supply chains that often entail highly complex optimization problems. An NP-hard example is minimizing the longterm transportation cost of multiple kinds of goods over a time horizon from suppliers to customers, considering order consolidation restrictions for shipments and demand uncertainty. This work presents a novel instance of such a distribution problem called the Shipping Point Assignment (SPA) problem, formulated as a multistage stochastic multicommodity network flows problem with additional nonlinear constraints, where the decision is to which warehouse to assign to the delivery of incoming orders to minimize inventory movements. Inspired by recent advances in combinatorial optimization using reinforcement learning and graph neural networks, we propose a deep Q learning agent with a GCN-based Value Function Approximator. We compare this agent with MLP-based, deterministic and greedy approaches over different simulations scenarios of the SPA problem. While the results do not suggest that the deep Q learning agent finds better policies than the reference agents, interesting avenues of future research were identified to enable reinforcement learning agents to learn from stochastic optimization problems with a graph structure.

Las redes de distribuci´on son una parte crucial de las cadenas de suministro que frecuentemente implican problemas de optimizaci´on altamente complejos. Un ejemplo NP-duro es minimizar el costo de transporte al largo plazo de multiples tipos de bienes en un horizonte de tiempo, de proveedores a clientes, considerando restricciones de consolidaci´on de embarques para las ´ordenes y la incertidumbre de la demanda. Este trabajo presenta una instancia novedosa de este problema de distribuci´on, llamado el problema Shipping Point Assignment (SPA), formulado como un problema de flujos de redes multimercanc´ıa estoc´astico multietapa con restricciones no lineales adicionales, donde la decisi ´on es a qu´e almac´en asignar la entrega de ´ordenes entrantes para minimizar movimientos de inventario. Inspirados por avances en optimizaci´on combinatoria con aprendizaje por refuerzo y redes neuronales de grafos, proponemos un agente de deep Q learning con una funci´on de aproximaci´on de valor basada en GCN. Comparamos este agente con alternativas basadas en MLP, deterministicas y greedy en diferences escenarios de simulaci´on del problema SPA. A pesar de que los resultados no sugieren que el agente de deep Q learning encontrara mejores pol´ıticas que los agentes de referencia, interesantes avenidas de investigaci ´on futuras fueron identificadas para abilitar que agentes de aprendizaje por refuerzo aprendan de problemas de optimizaci´on estoc´astica con estructura de grafo.