HEURISTICS FOR THE TRAVELING SALESMAN PROBLEM WITH d-RELAXED PRIORITY RULE

• Grant number: 25/09548-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: October 01, 2025
• End date: September 30, 2026
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Silvio Alexandre de Araujo
• Grantee: Bruna Gonçalves Assumpção
• Host Institution: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

In its classical version, the Traveling Salesman Problem (TSP ) can be described as follows: givena set of cities and knowing the distance between each of these cities, it is necessary to find the shortest possible route such that each city is visited only once, including the city of origin, where the route also ends. In other words, the objective is to find the circuit with the shortest possible length. In the classical TSP, the order in which the vertices are visited has no restrictions. The only condition imposed is that each vertex is visited only once. In some real-world situations, this condition may not be sufficient to represent the problem, as there are cases where the order of visiting the verticesbecomes extremely important. In other words, it is also necessary to consider a priority among thevertices. To address these situations, some studies have been proposed in the literature, based on a rule called the d-relaxed priority rule, which captures the trade-off between total distance and vertex priorities. In this project, we aim to adapt classical TSP heuristics to the case where the d-relaxed priority rule is considered.