EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Reinforcement Learning Framework for Scalable Partitioning and Optimization of Large-Scale Capacitated Vehicle Routing Problems

Chaima Ayachi Amar, Khadra Bouanane, Oussama Aiadi

Electronics · 29.09.2025 · 14 (19) · 3879

DOI: 10.3390/electronics14193879 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronics, online erschienen am 29.09.2025. Verfasst von Chaima Ayachi Amar und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Capacitated Vehicle Routing Problem (CVRP) is a central challenge in combinatorial optimization, with critical applications in logistics and transportation. Traditional methods struggle with large-scale instances, due to the computational demands, while learned construction models often suffer from degraded solution quality and constraint violations. This work proposes SPORL, a Scalable Partitioning and Optimization via Reinforcement Learning framework for large-scale CVRPs. SPORL decomposes the problem using a learned partitioning strategy, followed by parallel subproblem solving, and employs a greedy decoding scheme at inference to ensure scalability for instances with up to 1000 customers. A key innovation is a context-based attention mechanism that incorporates sub-route embeddings, enabling more informed and constraint-aware partitioning decisions. Extensive experiments on benchmark datasets with up to 1000 customers demonstrated that SPORL consistently outperformed state-of-the-art learning-based baselines (e.g., AM, POMO) and achieved competitive performance relative to strong heuristics such as LKH3, while reducing inference time from hours to seconds. Ablation studies confirmed the critical role of the proposed context embedding and decoding strategy in achieving high solution quality.

Zitieren

APA

Amar, C. A., Bouanane, K., & Aiadi, O. (2025). A Reinforcement Learning Framework for Scalable Partitioning and Optimization of Large-Scale Capacitated Vehicle Routing Problems. Electronics, 14(19), 3879. https://doi.org/10.3390/electronics14193879

Vancouver

Amar CA, Bouanane K, Aiadi O. A Reinforcement Learning Framework for Scalable Partitioning and Optimization of Large-Scale Capacitated Vehicle Routing Problems. Electronics. 2025;14(19):3879. doi:10.3390/electronics14193879

BibTeX
@article{Amar2025,
  author = {Amar, Chaima Ayachi and Bouanane, Khadra and Aiadi, Oussama},
  title = {A Reinforcement Learning Framework for Scalable Partitioning and Optimization of Large-Scale Capacitated Vehicle Routing Problems},
  journal = {Electronics},
  year = {2025},
  volume = {14},
  number = {19},
  pages = {3879},
  doi = {10.3390/electronics14193879}
}
Kostenlos starten →