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

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.

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.