IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v611y2023ics0378437123000067.html
   My bibliography  Save this article

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

Author

Listed:
  • Zhang, Ke
  • Lin, Xi
  • Li, Meng

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.

Suggested Citation

  • Zhang, Ke & Lin, Xi & Li, Meng, 2023. "Graph attention reinforcement learning with flexible matching policies for multi-depot vehicle routing problems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 611(C).
    • Handle: RePEc:eee:phsmap:v:611:y:2023:i:c:s0378437123000067
    DOI: 10.1016/j.physa.2023.128451
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437123000067
    Download Restriction: 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
    File URL: https://libkey.io/10.1016/j.physa.2023.128451?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dong, Hanxuan & Ding, Fan & Tan, Huachun & Zhang, Hailong, 2022. "Laplacian integration of graph convolutional network with tensor completion for traffic prediction with missing data in inter-city highway network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 586(C).
    2. Li, Xue-yan & Li, Xue-mei & Yang, Lingrun & Li, Jing, 2018. "Dynamic route and departure time choice model based on self-adaptive reference point and reinforcement learning," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 502(C), pages 77-92.
    3. Zhang, Yihao & Chai, Zhaojie & Lykotrafitis, George, 2021. "Deep reinforcement learning with a particle dynamics environment applied to emergency evacuation of a room with obstacles," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 571(C).
    4. Wang, Jun & Wang, Wenjun & Liu, Xueli & Yu, Wei & Li, Xiaoming & Sun, Peiliang, 2022. "Traffic prediction based on auto spatiotemporal Multi-graph Adversarial Neural Network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    5. I D Giosa & I L Tansini & I O Viera, 2002. "New assignment algorithms for the multi-depot vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(9), pages 977-984, September.
    6. Zhang, Kunpeng & Feng, Xiaoliang & Jia, Ning & Zhao, Liang & He, Zhengbing, 2022. "TSR-GAN: Generative Adversarial Networks for Traffic State Reconstruction with Time Space Diagrams," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 591(C).
    7. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    8. Yang, Yun & Ma, Changxi & Ling, Gang, 2022. "Pre-location for temporary distribution station of urban emergency materials considering priority under COVID-19: A case study of Wuhan City, China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 597(C).
    9. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. L Tansini & O Viera, 2006. "New measures of proximity for the assignment algorithms in the MDVRPTW," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 241-249, March.
    2. Tian, Jing & Song, Xianmin & Tao, Pengfei & Liang, Jiahui, 2022. "Pattern-adaptive generative adversarial network with sparse data for traffic state estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    3. Ma, Changxi & Zhao, Mingxi, 2023. "Spatio-temporal multi-graph convolutional network based on wavelet analysis for vehicle speed prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 630(C).
    4. Tulika Saha & Sriparna Saha & Pushpak Bhattacharyya, 2020. "Towards sentiment aided dialogue policy learning for multi-intent conversations using hierarchical reinforcement learning," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-28, July.
    5. Mahmoud Mahfouz & Angelos Filos & Cyrine Chtourou & Joshua Lockhart & Samuel Assefa & Manuela Veloso & Danilo Mandic & Tucker Balch, 2019. "On the Importance of Opponent Modeling in Auction Markets," Papers 1911.12816, arXiv.org.
    6. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    7. Woo Jae Byun & Bumkyu Choi & Seongmin Kim & Joohyun Jo, 2023. "Practical Application of Deep Reinforcement Learning to Optimal Trade Execution," FinTech, MDPI, vol. 2(3), pages 1-16, June.
    8. Lu, Yu & Xiang, Yue & Huang, Yuan & Yu, Bin & Weng, Liguo & Liu, Junyong, 2023. "Deep reinforcement learning based optimal scheduling of active distribution system considering distributed generation, energy storage and flexible load," Energy, Elsevier, vol. 271(C).
    9. Yuhong Wang & Lei Chen & Hong Zhou & Xu Zhou & Zongsheng Zheng & Qi Zeng & Li Jiang & Liang Lu, 2021. "Flexible Transmission Network Expansion Planning Based on DQN Algorithm," Energies, MDPI, vol. 14(7), pages 1-21, April.
    10. Michelle M. LaMar, 2018. "Markov Decision Process Measurement Model," Psychometrika, Springer;The Psychometric Society, vol. 83(1), pages 67-88, March.
    11. Yang, Ting & Zhao, Liyuan & Li, Wei & Zomaya, Albert Y., 2021. "Dynamic energy dispatch strategy for integrated energy system based on improved deep reinforcement learning," Energy, Elsevier, vol. 235(C).
    12. Wang, Yi & Qiu, Dawei & Sun, Mingyang & Strbac, Goran & Gao, Zhiwei, 2023. "Secure energy management of multi-energy microgrid: A physical-informed safe reinforcement learning approach," Applied Energy, Elsevier, vol. 335(C).
    13. Neha Soni & Enakshi Khular Sharma & Narotam Singh & Amita Kapoor, 2019. "Impact of Artificial Intelligence on Businesses: from Research, Innovation, Market Deployment to Future Shifts in Business Models," Papers 1905.02092, arXiv.org.
    14. Sun, Hongchang & Niu, Yanlei & Li, Chengdong & Zhou, Changgeng & Zhai, Wenwen & Chen, Zhe & Wu, Hao & Niu, Lanqiang, 2022. "Energy consumption optimization of building air conditioning system via combining the parallel temporal convolutional neural network and adaptive opposition-learning chimp algorithm," Energy, Elsevier, vol. 259(C).
    15. Zhang, Yang & Yang, Qingyu & Li, Donghe & An, Dou, 2022. "A reinforcement and imitation learning method for pricing strategy of electricity retailer with customers’ flexibility," Applied Energy, Elsevier, vol. 323(C).
    16. He, Jing & Liu, Xinglu & Duan, Qiyao & Chan, Wai Kin (Victor) & Qi, Mingyao, 2023. "Reinforcement learning for multi-item retrieval in the puzzle-based storage system," European Journal of Operational Research, Elsevier, vol. 305(2), pages 820-837.
    17. Holger Mohr & Katharina Zwosta & Dimitrije Markovic & Sebastian Bitzer & Uta Wolfensteller & Hannes Ruge, 2018. "Deterministic response strategies in a trial-and-error learning task," PLOS Computational Biology, Public Library of Science, vol. 14(11), pages 1-19, November.
    18. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    19. Taejong Joo & Hyunyoung Jun & Dongmin Shin, 2022. "Task Allocation in Human–Machine Manufacturing Systems Using Deep Reinforcement Learning," Sustainability, MDPI, vol. 14(4), pages 1-18, February.
    20. Calvete, Herminia I. & Gale, Carmen & Oliveros, Maria-Jose & Sanchez-Valverde, Belen, 2007. "A goal programming approach to vehicle routing problems with soft time windows," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1720-1733, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:611:y:2023:i:c:s0378437123000067. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.