Scholarlink

<p>The capacitated vehicle routing problem (CVRP), as a core combinatorial optimization (CO) problem in modern logistics distribution systems, holds significant research value. In this work, a novel encoder-decoder framework called residual edge demand graph attention network encoder and multiple attention-based decoders (REDGAT-MA) is presented to address CVRP, trained end-to-end via REINFORCE algorithm with a high-quality baseline. On one hand, the encoder extracts and reconstructs node features and interconnections through a residual graph attention network, which produces powerful node representations by integrating node features, edge features, and node demands. And new feature embedding vectors for the decoder are generated at the same time. On the other hand, the attention-based decoders dynamically decode routing sequences by integrating real-time operational constraints–including residual vehicle capacity and customer demand on the basis of the new feature embedding vectors. Then the multiple decoders mechanism constructs multiple feasible solutions for each iteration for a single instance. REDGAT-MA narrows the gap to solver with 1.64%, 1.83%, and 3.33% for three different scales of random CVRP instances, and achieves average gaps of 3.49%, 3.80%, and 8.27% for the problems with same scales from CVRPLIB, which demonstrates the model’s efficiency and generalization capabilities. Furthermore, the results from real-world distribution tasks conducted by JD logistics (JDL) in Beijing further validate the algorithm’s effectiveness.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An improved graph attention network combined with reinforcement learning for capacitated vehicle routing problem

  • 期刊论文

  • 发表日期：

    2025年10月25日

查看全文
  • Yu Bai,
  • Xiaohan Xing,
  • Jian Wang

摘要

The capacitated vehicle routing problem (CVRP), as a core combinatorial optimization (CO) problem in modern logistics distribution systems, holds significant research value. In this work, a novel encoder-decoder framework called residual edge demand graph attention network encoder and multiple attention-based decoders (REDGAT-MA) is presented to address CVRP, trained end-to-end via REINFORCE algorithm with a high-quality baseline. On one hand, the encoder extracts and reconstructs node features and interconnections through a residual graph attention network, which produces powerful node representations by integrating node features, edge features, and node demands. And new feature embedding vectors for the decoder are generated at the same time. On the other hand, the attention-based decoders dynamically decode routing sequences by integrating real-time operational constraints–including residual vehicle capacity and customer demand on the basis of the new feature embedding vectors. Then the multiple decoders mechanism constructs multiple feasible solutions for each iteration for a single instance. REDGAT-MA narrows the gap to solver with 1.64%, 1.83%, and 3.33% for three different scales of random CVRP instances, and achieves average gaps of 3.49%, 3.80%, and 8.27% for the problems with same scales from CVRPLIB, which demonstrates the model’s efficiency and generalization capabilities. Furthermore, the results from real-world distribution tasks conducted by JD logistics (JDL) in Beijing further validate the algorithm’s effectiveness.