Neural Order-First Split-Second Algorithm for the Capacitated Vehicle Routing Problem - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

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

(1) , (1) , (1)
1
Ali Yaddaden
Michel Vasquez

Résumé

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.
Fichier non déposé

Dates et versions

hal-03899963 , version 1 (15-12-2022)

Identifiants

Citer

Ali Yaddaden, Sébastien Harispe, Michel Vasquez. Neural Order-First Split-Second Algorithm for the Capacitated Vehicle Routing Problem. OLA 2022 - International Conference on Optimization and Learning, Jul 2022, Syracuse, Italy. pp.168-185, ⟨10.1007/978-3-031-22039-5_14⟩. ⟨hal-03899963⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More