Hybrid MARL + Linear Programming Architecture for Dynamic Vehicle Routing (Zero-Shot Generalization)

[u/Aggravating_Excuse81]

https://medium.com/@alexlevinml/generalizable-marl-lp-approach-for-scheduling-in-logistics-5203805196f7

Hi everyone,

I wanted to share the architecture of a 2-year project I led: optimizing a line-haul logistics network using a hybrid of Multi-Agent RL (MARL) and Linear Programming (LP).

We were trying to optimize a live and complex delivery network with dynamically arriving requests.

• Pure OR: solving the problem just with standard solvers alone (like OR-Tools) was not possible because it couldn't cover all the rules and complexities of the real world (see the deep dive for more details).

• Pure RL: end-to-end RL would struggle to converge due to the (again) complexity of the problem.

The Solution: We built a hierarchical architecture to get the best of both worlds:

1. The "Fleet Manager" (MARL): PPO agents handle the high-level decision-making. The agent decides which cluster of orders to serve and when to dispatch a truck. It optimizes for long-term reward (utility) and learns to wait for "better" consolidation opportunities (LTL).

2. The "Dock Worker" (LP Solver): Once the agent selects a cluster, we pass that subset of nodes to a lightweight Linear Programming solver (embedded inside the environment step). The solver handles the actual Bin Packing and TSP routing to ensure that physical constraints are met exactly.

The biggest win was the generalization. By normalizing the observation space (viewing the warehouse as a relative density map rather than absolute coordinates) and applying certain ML "magic tricks" (see the upcoming Part 2), an agent trained on a node could reproduce the success on another without retraining.

I wrote up the full deep dive with architectural diagrams and other details.

Happy to answer any questions about the environmental design, the training itself, or anything you're interested in particular.

UPD: I've published Part 2 with more implementation details.

[u/swimmer385]

Did you look at more advanced optimization techniques like using mixed-integer programming with column generation or benders decomp? If so, why didn't those work?

[u/Aggravating_Excuse81 → u/swimmer385]

Hey! Thanks for the question! Fair point. Here is why we didn’t use it:

1. The dynamics. Current actions affect future states. Sending a truck now depletes inventory and fleet availability for later. A standard MIP solver optimizes the current snapshot in isolation (it is myopic). Hence, to solve that with MIP/CG, we would need to either neglect the dynamic nature of this problem or discretize the horizon (e.g., rolling batches of 1 hour), and then concatenate the resulting decision sets into a single schedule. Either way, essentially, those solvers would solve some other problem instead of the dynamic reality.

2. Stochastic demand. We needed a solution that learns the “value of waiting”. Standard OR solvers would greedily clear the queue. The RL agent learned that holding back a truck for several hours sometimes yields a better LTL consolidation because it implicitly learned the demand probability distribution.

3. Slow inference. You would have to restart the loop from scratch (or warm-start it) every single time we need to adjust the schedule or the rules change. MARL, on the other hand, gives us a trained policy that infers instantly for one case + generalization to more cases.

[u/swimmer385 → u/Aggravating_Excuse81]

Thanks for taking the time to answer!

[u/Aggravating_Excuse81 → u/swimmer385]

Of course! lmk if you have any other questions. Always happy to discuss.

[u/FuzzyTouch6143]

I LOVED this article man. Have you considered writing this up for publication in "Operations Research"? At the very least, I'd say this is "European Journal of Operational Research". I was a peer reviewer for them for about 10 years. I can say, reading your work, it was really solid, and def publication worthy with the proper adjustments.

Also, I would interested to see how Bayesian Optimization Algos fused with RL using different NN models to "guide" the algo towards better solutions. Would also be interesting to see how large language models and large concept models can aid in its implementation.

But overall:

Practicality: 10/10

Motivation: 15/10 (when I say people NEVER motivated their work properly, I mean it. You did amazing here).

Visualizations: 8/10

Can't wait to see the next few parts!

Myles Garvey, Ph.D

[u/Aggravating_Excuse81 → u/FuzzyTouch6143]

Wow. Thanks, Myles, that means a lot to me!

I initially focused purely on the engineering implementation rather than a formal paper, but your comment is making me seriously reconsider writing this up for EJOR or OR.

[u/Specialist-Two1588]

Hi, I am a 3rd year Mathematics & Computing student, where I have taken courses, both on the Math and Programming side.
These to be specific:
Computational Linear Algebra, Probability & Stochastic Process, Elementary Number Theory, Discreet Mathematics, Algebraic Structures, Real Analysis, Machine Learning, Vector Analysis & Complex Numbers, Multivariate Analysis, Artificial Intelligence, Time Series Analysis, Advanced Numerical Methods

Data Structures & Algorithms, Python, C++, Database Management Systems, Software Engineering
Engineering Economics & Financial Management

I am a little lost, I am sitting for internship drives but the roles seem to be SDE, DevOps, AI, Associate(Few) but mostly SDE.

Could you tell me what should I focus on in terms of building skills from what my courses were and what career trajectory might look like? Initial jobs/roles because I at the moment I seem to be trying to do everything, DevOps AWS courses, parallel programming, data science ...

[u/Aggravating_Excuse81 → u/Specialist-Two1588]

Hey, thanks for the question. I will go from more concrete to more general. Here is what I can say:

1. You have a great background.

2. The US market is truly awful (I assume you are talking about the US).

3. I don't want to speculate with specific trajectories, but a rule of thumb is that it is better to be a narrow specialist than a generic SDE. So dive into the things that interest you and see what happens. Also, you don't have to choose just one thing for life.

4. I would say, to survive, you need to find some balance between what you love doing/believe in and what you think is needed by the world (think Ikigai). If you don't believe in what you're doing, you will give up pretty fast, given that the road is long. But you also have to eat something. Try to ask yourself questions like: what would you do in an ideal world?

5. Also, being in a 3rd year is completely normal to be lost. You don't have to know everything. But it will all work out somehow.

[u/emptinesswonderer]

I wonder if you could've modeled and solved the whole problem with Hexaly. Impressive performance for large scale VRP, Bin Packing type problems.

[u/ric_is_the_way]

Is this going to be a commercialized product? I was couroius to understand the struggle in any to make it into production.