Recent works using deep learning to solve routing problems such as the traveling salesman problem (TSP) have focused on learning construction heuristics. Such approaches find good quality solutions but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which can be easily extended to more general k-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions faster than previous state-of-the-art deep learning methods for the TSP. We also show we can adapt the proposed method to two extensions of the TSP: the multiple TSP and the Vehicle Routing Problem, achieving results on par with classical heuristics and learned methods.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Learning 2-Opt Heuristics for Routing Problems via Deep Reinforcement Learning


    Beteiligte:

    Erscheinungsdatum :

    2021-07-23


    Anmerkungen:

    de O. da Costa , P R , Rhuggenaath , J , Zhang , Y , Akcay , A & Kaymak , U 2021 , ' Learning 2-Opt Heuristics for Routing Problems via Deep Reinforcement Learning ' , SN Computer Science , vol. 2 , 388 . https://doi.org/10.1007/s42979-021-00779-2



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Reinforcement Learning Heuristics for Aerospace Control Systems

    Robinette, Preston K. / Heiner, Benjamin K. / Ravaioli, Umberto et al. | IEEE | 2022


    Using Cases as Heuristics in Reinforcement Learning: A Transfer Learning Application

    Celiberto, Luiz A. / Matsuura, Jackson P. / López de Mántaras, Ramón et al. | BASE | 2011

    Freier Zugriff

    Deep Reinforcement Learning-Based Routing for Space-Terrestrial Networks

    Tsai, Kai-Chu / Yao, Ting-Jui / Huang, Pin-Hao et al. | IEEE | 2022



    Routing using Safe Reinforcement Learning

    Nayak Seetanadi, Gautham / Årzén, Karl-Erik | BASE | 2020

    Freier Zugriff