IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i14p3221-d1199888.html
   My bibliography  Save this article

A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem

Author

Listed:
  • Jun Xu

    (School of Systems Science, Beijing Jiaotong University, Beijing 100044, China)

  • Wei Hu

    (School of Systems Science, Beijing Jiaotong University, Beijing 100044, China)

  • Wenjuan Gu

    (School of Modern Post, Beijing University of Posts and Telecommunications, Beijing 100876, China)

  • Yongguang Yu

    (School of Mathematics and Statistics, Beijing Jiaotong University, Beijing 100044, China)

Abstract

The JAYA algorithm is a population-based meta-heuristic algorithm proposed in recent years which has been proved to be suitable for solving global optimization and engineering optimization problems because of its simplicity, easy implementation, and guiding characteristic of striving for the best and avoiding the worst. In this study, an improved discrete JAYA algorithm based on reinforcement learning and simulated annealing (QSA-DJAYA) is proposed to solve the well-known traveling salesman problem in combinatorial optimization. More specially, firstly, the basic Q-learning algorithm in reinforcement learning is embedded into the proposed algorithm such that it can choose the most promising transformation operator for the current state to update the solution. Secondly, in order to balance the exploration and exploitation capabilities of the QSA-DJAYA algorithm, the Metropolis acceptance criterion of the simulated annealing algorithm is introduced to determine whether to accept candidate solutions. Thirdly, 3-opt is applied to the best solution of the current iteration at a certain frequency to improve the efficiency of the algorithm. Finally, to evaluate the performance of the QSA-DJAYA algorithm, it has been tested on 21 benchmark datasets taken from TSPLIB and compared with other competitive algorithms in two groups of comparative experiments. The experimental and the statistical significance test results show that the QSA-DJAYA algorithm achieves significantly better results in most instances.

Suggested Citation

  • Jun Xu & Wei Hu & Wenjuan Gu & Yongguang Yu, 2023. "A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem," Mathematics, MDPI, vol. 11(14), pages 1-23, July.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:14:p:3221-:d:1199888
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/14/3221/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/14/3221/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Yang, Zhao & Xiao, Ming-Qing & Ge, Ya-Wei & Feng, De-Long & Zhang, Lei & Song, Hai-Fang & Tang, Xi-Lang, 2018. "A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods," European Journal of Operational Research, Elsevier, vol. 265(1), pages 65-80.
    3. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    4. Zhaojun Zhang & Zhaoxiong Xu & Shengyang Luan & Xuanyu Li & Yifei Sun, 2020. "Opposition-Based Ant Colony Optimization Algorithm for the Traveling Salesman Problem," Mathematics, MDPI, vol. 8(10), pages 1-16, September.
    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. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    2. Arroyo, Federico, 2024. "Cost Allocation in Vehicle Routing Problems with Time Windows," Junior Management Science (JUMS), Junior Management Science e. V., vol. 9(1), pages 1241-1268.
    3. Jumbo, Olga & Moghaddass, Ramin, 2022. "Resource optimization and image processing for vegetation management programs in power distribution networks," Applied Energy, Elsevier, vol. 319(C).
    4. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    5. Tianlu Zhao & Yongjian Yang & En Wang, 2020. "Minimizing the average arriving distance in carpooling," International Journal of Distributed Sensor Networks, , vol. 16(1), pages 15501477198, January.
    6. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    7. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    8. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    9. Yimei Chang & Jiaqi Yu & Yang Wang & Xiaoling Xie, 2025. "An Improved Salp Swarm Algorithm for Solving a Multi-Temperature Joint Distribution Route Optimization Problem," Mathematics, MDPI, vol. 13(4), pages 1-24, February.
    10. Sivanandham, S. & Srivatsa Srinivas, S., 2025. "Enhancing food security at the last-mile: A light-weight and scalable decision support system for the public distribution system in India," Socio-Economic Planning Sciences, Elsevier, vol. 98(C).
    11. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    12. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    13. Tibor Holczinger & Olivér Ősz & Máté Hegyháti, 2020. "Scheduling approach for on-site jobs of service providers," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 913-948, December.
    14. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    15. Narjes MASHHADI BANDANI & Alireza NADERI & Mohsen AKBARPOUR SHIRZAEI, 2017. "Cement Transportation Limited-Fleet Modeling And Assigning To Rated Demands," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 12(1), pages 111-123, March.
    16. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex," European Journal of Operational Research, Elsevier, vol. 124(2), pages 267-282, July.
    17. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    18. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    19. Castellano, Davide & Gallo, Mosè & Grassi, Andrea & Santillo, Liberatina C., 2019. "The effect of GHG emissions on production, inventory replenishment and routing decisions in a single vendor-multiple buyers supply chain," International Journal of Production Economics, Elsevier, vol. 218(C), pages 30-42.
    20. Yeo, Lip Siang & Teng, Sin Yong & Ng, Wendy Pei Qin & Lim, Chun Hsion & Leong, Wei Dong & Lam, Hon Loong & Wong, Yat Choy & Sunarso, Jaka & How, Bing Shen, 2022. "Sequential optimization of process and supply chains considering re-refineries for oil and gas circularity," Applied Energy, Elsevier, vol. 322(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:gam:jmathe:v:11:y:2023:i:14:p:3221-:d:1199888. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.