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. 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.
    2. 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.
    3. Gillett, Billy E & Johnson, Jerry G, 1976. "Multi-terminal vehicle-dispatch algorithm," Omega, Elsevier, vol. 4(6), pages 711-718.
    4. 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.
    5. 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.
    6. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    7. Warren B. Powell, 2016. "Perspectives of approximate dynamic programming," Annals of Operations Research, Springer, vol. 241(1), pages 319-356, June.
    8. 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.
    9. 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.
    10. 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.
    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. Alexandre Forel & Martin Grunow, 2023. "Dynamic stochastic lot sizing with forecast evolution in rolling‐horizon planning," Production and Operations Management, Production and Operations Management Society, vol. 32(2), pages 449-468, February.
    6. 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.
    7. 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.
    8. Oscar Dominguez & Angel A. Juan & Barry Barrios & Javier Faulin & Alba Agustin, 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet," Annals of Operations Research, Springer, vol. 236(2), pages 383-404, January.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    15. Gharehgozli, A.H. & Roy, D. & de Koster, M.B.M., 2014. "Sea Container Terminals," ERIM Report Series Research in Management ERS-2014-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    16. van der Plas, C. & Tervonen, T. & Dekker, R., 2012. "Evaluation of scalarization methods and NSGA-II/SPEA2 genetic algorithms for multi-objective optimization of green supply chain design," Econometric Institute Research Papers EI2012-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. 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.
    18. 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.
    19. Tahir Ekin & Stephen Walker & Paul Damien, 2023. "Augmented simulation methods for discrete stochastic optimization with recourse," Annals of Operations Research, Springer, vol. 320(2), pages 771-793, January.
    20. 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).

    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.