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.
A new approach for the traveling salesperson problem with hotel selection
2021
Article (Journal)
Electronic Resource
Unknown
Metadata by DOAJ is licensed under CC BY-SA 1.0
Approximate Procedures for Probabilistic Traveling Salesperson Problem
British Library Conference Proceedings | 2004
|Approximate Procedures for Probabilistic Traveling Salesperson Problem
Online Contents | 2004
|Approximate Procedures for Probabilistic Traveling Salesperson Problem
Transportation Research Record | 2004
|The data-driven time-dependent traveling salesperson problem
Elsevier | 2020
|A Control Theoretic Approach to the Dubins Travelling Salesperson Problem
British Library Conference Proceedings | 2014
|