EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1436. A Tale of Middle-Mile Logistics, Graph Neural Networks, and Reinforcement Learning

Invited abstract in session MC-3: (Deep) Reinforcement Learning for Combinatorial Optimization 1, stream Data Science Meets Optimization.

Monday, 12:30-14:00
Room: 1005 (building: 202)

Authors (first author is the speaker)

1. Thibaut Cuvelier
Operations Research, Google Research
2. Onno Eberhard
Max Planck Institute for Intelligent Systems / University of Tübingen
3. Bruno De Backer
Operations Research, Google Research

Abstract

Middle-mile logistics describes the problem of routing shipments through a network of hubs while respecting deadlines upon arrival. We consider that the hubs are linked by predefined lines, to which we have to assign vehicles. A very challenging aspect of the problem comes from the finite capacity of the vehicles: allocating a shipment to a given vehicle might block another one from using the same vehicle.

Typical exact solution methods, based on a multicommodity-flow formulation, scale poorly with the problem size and real-world instances become quickly intractable. Instead, we turn to reinforcement learning (RL) by rephrasing the middle-mile problem as a multi-objective Markov decision process, where the state is a graph: the lines (edges) between the hubs and the parcels (nodes). At each round, we assign one shipment to a vehicle or decide that it stays in the same hub. The key ingredients of our proposed method are the extraction of small feature graphs from the state and the combination of graph neural networks (GNN) with model-free RL.

We use the PPO (proximal policy optimization) algorithm, which maintains both an actor and a critic, while being able to cope with a varying number of actions depending on the state. We compare linear functions and GraphNet (a particular kind of GNN) to approximate the policy and value functions. GNNs can deliver up to 40% more shipments than a linear function and both approaches scale well with the number of shipments per truck.

Keywords

Status: accepted

Back to the list of papers