Neural Order-First Split-Second Algorithm for the Capacitated Vehicle Routing Problem

Modern machine learning, including deep learning models and reinforcement learning techniques, have proven effective for solving difficult combinatorial optimization problems without relying on handcrafted heuristics. In this work, we present NOFSS, a Neural Order-First Split-Second deep reinforcement learning approach for the Capacity Constrained Vehicle Routing Problem (CVRP). NOFSS consists of a hybridization between a deep neural network model and a dynamic programming shortest path algorithm (Split). Our results, based on intensive experiments with several neural network model architectures, show that such a two-step hybridization enables learning of implicit algorithms (i.e. policies) producing competitive solutions for the CVRP.

Automated summary

This work presents a hybrid approach of deep neural network and dynamic programming for solving the Capacity Constrained Vehicle Routing Problem. Experimental results demonstrate the ability to learn an implicit algorithm that generates competitive solutions.