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. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    5. 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.
    6. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    7. 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.
    8. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    9. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    10. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    11. 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).
    12. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.
    13. 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.
    14. Kusum Deep & Hadush Mebrahtu & Atulya K. Nagar, 2018. "Novel GA for metropolitan stations of Indian railways when modelled as a TSP," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(3), pages 639-645, June.
    15. Y H Lee & J I Kim & K H Kang & K H Kim, 2008. "A heuristic for vehicle fleet mix problem using tabu search and set partitioning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 833-841, June.
    16. 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.
    17. 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).
    18. 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.
    19. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
    20. 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.

    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.