Exact and Heuristic Approaches for the Restricted Steiner Multicycle Problem

• Grant number: 25/19181-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: February 01, 2026
• End date: January 31, 2027
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Gustavo Cesar Bento Laurindo
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

Abstract

Vehicle Routing Problems involve finding one or more routes for vehicles to meet demands, whether for transporting customers or delivering products. The objective is to minimize the total operational cost, which may include time, fuel, etc. This family of problems is highly relevant to industry, as it models various logistical challenges.This project focuses on the Restricted Steiner Multicycle Problem, a variant of Vehicle Routing Problems in which the goal is to find a set of minimum-cost cycles. It is important to note that the demands correspond to pairs of terminals that must belong to the same cycle. Being an NP-hard problem, it is not possible to obtain an optimal solution for all instances in polynomial time.In this regard, the project proposes the use of both exact and heuristic approaches, aiming to compare their solutions in terms of computational cost and solution quality.As a Scientific Initiation, this project also aims to introduce the candidate to scientific research and to complement his education in Computer Engineering. (AU)