Banca de DEFESA: RANMSÉS EMANUEL MARTINS BASTOS

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
STUDENT : RANMSÉS EMANUEL MARTINS BASTOS
DATE: 27/03/2023
TIME: 14:00
LOCAL: : https://meet.google.com/iyh-vwzt-pbw
TITLE:

Investigation of Models and Algorithms for the Traveling Salesman with Multiple Passengers and High Occupancy Problem

KEY WORDS:

Traveling Salesman Problem, Ridesharing Problem, Metaheuristics, High-Occupancy Toll, Reinforcement Learning, Lazy Constraints, Piecewise Functions

PAGES: 124
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Sistemas de Computação
SPECIALTY: Arquitetura de Sistemas de Computação
SUMMARY:

The Traveling Salesman with Multiple Passengers and High Occupancy Problem is a generalization of the Traveling Salesman Problem that incorporates real-world features, transforming it into a ridesharing problem with routing constraints. In this modality, the salesman offers rides to third parties along the route to share the cost of the trip. Links between cities may contain High-Occupancy tolls, in which the toll is waived if the vehicle is fully occupied. When tolls are charged, those expenses are entirely paid by the salesman. All other costs are shared equally between the salesman and all passengers occupying seats on their respective routes. The objective of the TSMPHOP is to find the Hamiltonian cycle with the lowest cost, calculated by the sum of expenses carried by the salesman. Such features promote efficiency in the use of urban space and the reduction of greenhouse gas emissions, given the incentive for sharing transportation with a larger number of people. This thesis presents the study of this new combinatorial optimization problem, beginning with an analysis of its relationship to other models in the literature. Subsequently, the mathematical formulation of the problem is addressed, with multiple variants for representing its constraints. Finally, algorithms are created to find good-quality solutions in a short amount of time. In order to conduct computational experiments, an artificial instance database is generated, and solution methods are implemented. Ten mathematical models are implemented in the Gurobi solver to establish a benchmark, determining optimal solutions for the instances, and comparing different formulation techniques, including lazy constraints and piecewise-linear functions. Procedures for manipulating solutions and ten heuristic algorithms are also proposed. The algorithms are developed based on the metaheuristics Genetic Algorithm, Memetic Algorithm, Transgenetic Algorithm, and Q-learning reinforcement learning technique. Three computational experiments are conducted: the first controlled by the maximum iteration parameter, the second with an absolute maximum count of objective function evaluations, and the third with a maximum count of objective function evaluations relative to the discovery of the last best solution. The parameter tuning is performed automatically by the irace tool. A statistical analysis based on the Friedman Aligned Ranks test indicated superior performance of the hybrid algorithm combining the Transgenetic Algorithm, Memetic Algorithm, and the Q-learning technique.

COMMITTEE MEMBERS:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Interna - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Externo à Instituição - LUCÍDIO DOS ANJOS FORMIGA CABRAL - UFPB
Externo à Instituição - MARCO CESAR GOLDBARG
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA