IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v339y2024i1d10.1007_s10479-022-04788-z.html
   My bibliography  Save this article

An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem

Author

Listed:
  • Yang Zou

    (Nanjing University of Aeronautics and Astronautics)

  • Hecheng Wu

    (Nanjing University of Aeronautics and Astronautics)

  • Yunqiang Yin

    (University of Electronic Science and Technology of China)

  • Lalitha Dhamotharan

    (University of Exeter)

  • Daqiang Chen

    (Zhejiang Gongshang University)

  • Aviral Kumar Tiwari

    (Rajagiri Business School (RBS))

Abstract

Low-carbon logistics is an emerging and sustainable development industry in the era of a low-carbon economy. The end-to-end deep reinforcement learning (DRL) method with an encoder-decoder framework has been proven effective for solving logistics problems. However, in most cases, the recurrent neural networks (RNN) and attention mechanisms are used in encoders and decoders, which may result in the long-distance dependence problem and the neglect of the correlation between query vectors. To surround this problem, we propose an improved transformer model (TAOA) with both multi-head attention mechanism (MHA) and attention to attention mechanism (AOA), and apply it to solve the low-carbon multi-depot vehicle routing problem (MDVRP). In this model, the MHA and AOA are implemented to solve the probability of route nodes in the encoder and decoder. The MHA is used to process different parts of the input sequence, which can be calculated in parallel, and the AOA is used to deal with the deficiency problem of correlation between query results and query vectors in the MHA. The actor-critic framework based on strategy gradient is constructed to train model parameters. The 2opt operator is further used to optimize the resulting routes. Finally, extensive numerical studies are carried out to verify the effectiveness and operation efficiency of the proposed TAOA, and the results show that the proposed TAOA performs better in solving the MDVRP than the traditional transformer model (Kools), genetic algorithm (GA), and Google OR-Tools (Ortools).

Suggested Citation

  • Yang Zou & Hecheng Wu & Yunqiang Yin & Lalitha Dhamotharan & Daqiang Chen & Aviral Kumar Tiwari, 2024. "An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem," Annals of Operations Research, Springer, vol. 339(1), pages 517-536, August.
  • Handle: RePEc:spr:annopr:v:339:y:2024:i:1:d:10.1007_s10479-022-04788-z
    DOI: 10.1007/s10479-022-04788-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-022-04788-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10479-022-04788-z?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. Mustafa Şaylı & Enes Yılmaz, 2017. "Anti-periodic solutions for state-dependent impulsive recurrent neural networks with time-varying and continuously distributed delays," Annals of Operations Research, Springer, vol. 258(1), pages 159-185, November.
    2. Sahin, Bahri & Yilmaz, Huseyin & Ust, Yasin & Guneri, Ali Fuat & Gulsun, BahadIr, 2009. "An approach for analysing transportation costs and a case study," European Journal of Operational Research, Elsevier, vol. 193(1), pages 1-11, February.
    3. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    4. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    5. Jagannath Roy & Dragan Pamučar & Samarjit Kar, 2020. "Evaluation and selection of third party logistics provider under sustainability perspectives: an interval valued fuzzy-rough approach," Annals of Operations Research, Springer, vol. 293(2), pages 669-714, October.
    6. Humberto Brandão de Oliveira & Germano Vasconcelos, 2010. "A hybrid search method for the vehicle routing problem with time windows," Annals of Operations Research, Springer, vol. 180(1), pages 125-144, November.
    7. Warren B. Powell, 2016. "Perspectives of approximate dynamic programming," Annals of Operations Research, Springer, vol. 241(1), pages 319-356, June.
    8. Emna Marrekchi & Walid Besbes & Diala Dhouib & Emrah Demir, 2021. "A review of recent advances in the operations research literature on the green routing problem and its variants," Annals of Operations Research, Springer, vol. 304(1), pages 529-574, September.
    9. Gillett, Billy E & Johnson, Jerry G, 1976. "Multi-terminal vehicle-dispatch algorithm," Omega, Elsevier, vol. 4(6), pages 711-718.
    10. Eiji Mizutani & Stuart Dreyfus, 2017. "Totally model-free actor-critic recurrent neural-network reinforcement learning in non-Markovian domains," Annals of Operations Research, Springer, vol. 258(1), pages 107-131, November.
    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. Garside, Annisa Kesy & Ahmad, Robiah & Muhtazaruddin, Mohd Nabil Bin, 2024. "A recent review of solution approaches for green vehicle routing problem and its variants," Operations Research Perspectives, Elsevier, vol. 12(C).
    2. Sun, Lijun & Zhang, Yuankai & Hu, Xiangpei, 2021. "Economical-traveling-distance-based fleet composition with fuel costs: An application in petrol distribution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    3. Battini, Daria & Persona, Alessandro & Sgarbossa, Fabio, 2014. "A sustainable EOQ model: Theoretical formulation and applications," International Journal of Production Economics, Elsevier, vol. 149(C), pages 145-153.
    4. Voelkel, Michael A. & Sachs, Anna-Lena & Thonemann, Ulrich W., 2020. "An aggregation-based approximate dynamic programming approach for the periodic review model with random yield," European Journal of Operational Research, Elsevier, vol. 281(2), pages 286-298.
    5. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    6. Mladen Krstić & Giulio Paolo Agnusdei & Snežana Tadić & Pier Paolo Miglietta, 2023. "Prioritization of e-traceability drivers in the agri-food supply chains," Agricultural and Food Economics, Springer;Italian Society of Agricultural Economics (SIDEA), vol. 11(1), pages 1-26, December.
    7. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.
    8. Suzanne, Elodie & Absi, Nabil & Borodin, Valeria, 2020. "Towards circular economy in production planning: Challenges and opportunities," European Journal of Operational Research, Elsevier, vol. 287(1), pages 168-190.
    9. Victor F. Araman & René A. Caldentey, 2022. "Diffusion Approximations for a Class of Sequential Experimentation Problems," Management Science, INFORMS, vol. 68(8), pages 5958-5979, August.
    10. Liu, Xinbao & Yang, Tianji & Pei, Jun & Liao, Haitao & Pohl, Edward A., 2019. "Replacement and inventory control for a multi-customer product service system with decreasing replacement costs," European Journal of Operational Research, Elsevier, vol. 273(2), pages 561-574.
    11. H. Asefi & S. Lim & M. Maghrebi & S. Shahparvari, 2019. "Mathematical modelling and heuristic approaches to the location-routing problem of a cost-effective integrated solid waste management," Annals of Operations Research, Springer, vol. 273(1), pages 75-110, February.
    12. Chan, Chi Kin & Lee, Y.C.E. & Campbell, J.F., 2013. "Environmental performance—Impacts of vendor–buyer coordination," International Journal of Production Economics, Elsevier, vol. 145(2), pages 683-695.
    13. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    14. Makboul, Salma & Kharraja, Said & Abbassi, Abderrahman & El Hilali Alaoui, Ahmed, 2024. "A multiobjective approach for weekly Green Home Health Care routing and scheduling problem with care continuity and synchronized services," Operations Research Perspectives, Elsevier, vol. 12(C).
    15. De Rosa, Vincenzo & Gebhard, Marina & Hartmann, Evi & Wollenweber, Jens, 2013. "Robust sustainable bi-directional logistics network design under uncertainty," International Journal of Production Economics, Elsevier, vol. 145(1), pages 184-198.
    16. Hamed Farrokhi-Asl & Ahmad Makui & Armin Jabbarzadeh & Farnaz Barzinpour, 2020. "Solving a multi-objective sustainable waste collection problem considering a new collection network," Operational Research, Springer, vol. 20(4), pages 1977-2015, December.
    17. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    18. Rui Ren & Wanjie Hu & Jianjun Dong & Bo Sun & Yicun Chen & Zhilong Chen, 2019. "A Systematic Literature Review of Green and Sustainable Logistics: Bibliometric Analysis, Research Trend and Knowledge Taxonomy," IJERPH, MDPI, vol. 17(1), pages 1-25, December.
    19. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    20. Dekker, Rommert & Bloemhof, Jacqueline & Mallidis, Ioannis, 2012. "Operations Research for green logistics – An overview of aspects, issues, contributions and challenges," European Journal of Operational Research, Elsevier, vol. 219(3), pages 671-679.

    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:spr:annopr:v:339:y:2024:i:1:d:10.1007_s10479-022-04788-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.