Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem.

Area of Science:

• Operations Research
• Artificial Intelligence

Background:

• Current deep reinforcement learning (DRL) methods for capacitated vehicle routing problems (CVRP) assume homogeneous fleets, limiting their real-world applicability.
• Heterogeneous fleets, with vehicles possessing varying capacities or speeds, present a significant challenge for existing DRL algorithms.

Purpose of the Study:

• To address the heterogeneous capacitated vehicle routing problem (HCVRP) by developing a DRL method capable of handling fleets with diverse vehicle characteristics.
• To optimize both min-max (minimize longest travel time) and min-sum (minimize total travel time) objectives for HCVRP.

Main Methods:

• Propose a DRL method utilizing an attention mechanism with specialized decoders for vehicle selection and node selection.
• The model learns to simultaneously select an appropriate vehicle and the next customer node for that vehicle at each step.
• The vehicle selection decoder specifically accounts for the heterogeneous fleet constraints.

Main Results:

• The proposed DRL method demonstrates superior performance compared to state-of-the-art DRL methods and most conventional heuristics on randomly generated instances.
• The approach exhibits strong generalization capabilities across various problem sizes.
• Competitive performance is achieved against the highly effective 'slack induction by string removal' heuristic.
• Satisfactory results are obtained on standard CVRPLib instances.

Conclusions:

• The developed DRL method effectively solves the HCVRP by dynamically selecting vehicles and routes.
• This approach offers a significant advancement for DRL applications in logistics and transportation optimization with heterogeneous fleets.