Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems

Ke Zhang, Xi Lin and Meng Li

Physica A: Statistical Mechanics and its Applications, 2023, vol. 611, issue C

Abstract: Multi-depot vehicle routing problem with soft time windows (MD-VRPSTW) is a valuable practical issue in urban logistics. However, heuristic methods may fail to generate high-quality solutions for massive problems instantly. Thus, this paper presents a novel reinforcement learning algorithm integrated with graph attention network (GAT-RL) to efficiently solve the problem. This method utilizes the encoder–decoder architecture to produce routes for vehicles starting from different depots iteratively. The encoder architecture employs graph attention network to mine the complex spatial–temporal correlations within time windows. Then, the decoder architecture designs fixed-order and full-pair matching policies to generate solutions. After off-line training, experiments show that this approach consistently outperforms Google OR-Tools with negligible computational time. Particularly, the robustness of the pre-trained model is validated under multiple sources of variations and uncertainties, including customer/depot numbers, vehicle capacities, and en-route traffic conditions.

Keywords: Multi-depot; Reinforcement learning; Graph attention; Soft time window; Multi-agent (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437123000067
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:611:y:2023:i:c:s0378437123000067

DOI: 10.1016/j.physa.2023.128451

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().