The Traveling Salesperson Problem with Hotel Selection (TSPHS) corresponds to a variant of the classic Traveling Salesman Problem (TSP) where the salesperson must establish a route in order to visit and attend all customers and return to the point of origin. At the end of each working day, if they had not attended all customers, the salesperson must go to a hotel (and stay there overnight). The objective of TSPHS is to first minimize the number of trips and then to minimize the total time spent. The present work proposes a new heuristic algorithm called BRKGA-LS, that combines characteristics and procedures of well-established metaheuristics and methods of vehicle routing problems. Based on computational experiments, carried out with 131 instances of the literature, the global optimum was achieved in about 90% of the cases where it is known (86 out of 95 instances), and the algorithm was able to improve the results of the literature in 11 of all 36 instances. Additionally, a hypothesis test was performed to validate the results and the good performance of the BRKGA-LS in comparison to other algorithms in the literature. Therefore, the proposed algorithm is a promising alternative for solving the problem addressed.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A new approach for the traveling salesperson problem with hotel selection




    Erscheinungsdatum :

    2021




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt




    Approximate Procedures for Probabilistic Traveling Salesperson Problem

    Tang, Hao / Miller-Hooks, Elise | Transportation Research Record | 2004


    Approximate Procedures for Probabilistic Traveling Salesperson Problem

    Tang, H. / Miller-Hooks, E. / Transportation Research Board | British Library Conference Proceedings | 2004



    The data-driven time-dependent traveling salesperson problem

    Avraham, Edison / Raviv, Tal | Elsevier | 2020


    A Control Theoretic Approach to the Dubins Travelling Salesperson Problem

    Isaiah, P. / Shima, T. / Tekhniyon, Makhon tekhnologi le-Yisra'el | British Library Conference Proceedings | 2014