# Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem

Source: https://www.youtube.com/watch?v=He0FY9EXRSo
Recap page: https://rapidrecap.app/video/He0FY9EXRSo
Generated: 2026-01-05T19:03:23.853+00:00

---
## Quick Overview

The Deep Reinforcement Learning (DRL) method, specifically using the FRIPN network, significantly outperforms traditional heuristic methods like CPA L-X and ALNS for solving the Vehicle Routing Problem with Fleet Size and Mix (VR-FSM), achieving an 8.8% cost reduction on a 100-node problem instance.

**Key Points:**
- The FRIPN DRL method reduced total cost by 8.8% compared to the best traditional heuristic (ALNS) on a 100-node logistics problem.
- The core challenge solved is the Vehicle Routing Problem with Fleet Size and Mix (VR-FSM), which involves deciding both the route and the vehicle type for each delivery.
- Traditional heuristic methods like CPA L-X and ALNS failed to solve the 100-node problem optimally within the 1800-second time limit.
- The DRL approach frames the problem as a dual decision process (fleet size/mix and route) integrated into a single sequence, providing a holistic solution.
- The fixed cost of deploying a new vehicle type is factored in, contrasting with variable costs per kilometer traveled.
- The DRL model's success stems from incorporating the fleet/route trade-off directly into the sequential decision-making process, utilizing a specialized graph embedding structure.

![Screenshot at 00:21: The visual explicitly highlights the core problem being addressed: Deep Reinforcement Learning for solving the fleet size and mix vehicle routing problem, contrasting it with traditional methods.](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-00-21.jpg)

**Context:** This AI Papers Podcast daily segment dives into a research paper that applies Deep Reinforcement Learning (DRL) to the complex Vehicle Routing Problem with Fleet Size and Mix (VR-FSM). This problem requires optimizing not only the sequence of customer visits but also selecting the appropriate vehicle type (small, medium, large) for each route, which involves balancing fixed vehicle acquisition/leasing costs against variable travel costs.

## Detailed Analysis

The discussion centers on a Deep Reinforcement Learning (DRL) solution, utilizing the FRIPN (Fleet Routing and Inventory Planning Network) structure, designed to solve the Fleet Size and Mix Vehicle Routing Problem (VR-FSM). This problem is notoriously complex because it forces a dual decision: which vehicle to use (fleet sizing/mixing) and which route to take, which affects both fixed costs (vehicle leasing/purchase) and variable costs (mileage). The speakers note that traditional heuristics, like CPA L-X and ALNS, struggle with this complexity, often failing to solve large instances (like 100 nodes) within time constraints. The DRL approach, however, integrates these two decisions—fleet selection and routing—into a single sequential decision-making framework. The key innovation is framing the problem such that the model learns the trade-off between fixed and variable costs simultaneously. When tested on a 100-node problem, the DRL method achieved an 8.8% cost reduction compared to the best heuristic (ALNS), proving its superior ability to handle the inherent complexity and generalize across different fleet compositions and customer demands.

### Problem Introduction

- Deep dive into the Fleet Size and Mix Vehicle Routing Problem (VR-FSM)
- VR-FSM requires optimizing routes and vehicle mix simultaneously
- Traditional heuristics struggle with the dual decision complexity

### DRL Solution

- Utilizes the FRIPN network (a Transformer-based encoder-decoder structure)
- Integrates fixed vehicle costs and variable travel costs into a single sequence
- Outperforms heuristics by learning the optimal trade-off

### Performance Results

- DRL achieved an 8.8% cost reduction over the best heuristic (ALNS) on a 100-node problem
- Heuristics failed to solve the 100-node problem optimally within 1800 seconds
- DRL generalized well across different fleet sizes and customer locations

![Screenshot at 00:09: The hosts introduce the deep dive into DRL for solving the fleet size and mix vehicle routing problem.](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-00-09.jpg)
![Screenshot at 00:26: The speaker introduces the two main cost components: variable costs \(per kilometer\) and fixed costs.](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-00-26.jpg)
![Screenshot at 00:56: The speakers contrast the heuristic approach \(spatial, location-driven routing\) with the DRL's financial-driven approach.](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-00-56.jpg)
![Screenshot at 01:45: A comparison is drawn between the complexity of the DRL approach and the slowness of traditional exact solvers.](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-01-45.jpg)
![Screenshot at 02:28: The speaker highlights the two cost components: variable costs \(easy\) and fixed costs \(harder\).](https://ss.rapidrecap.app/screens/He0FY9EXRSo/00-02-28.jpg)