Banca de QUALIFICAÇÃO: RANMSÉS EMANUEL MARTINS BASTOS

Uma banca de QUALIFICAÇÃO de DOUTORADO foi cadastrada pelo programa.
STUDENT : RANMSÉS EMANUEL MARTINS BASTOS
DATE: 19/08/2022
TIME: 14:00
LOCAL: https://meet.google.com/xmj-rzoe-qgw
TITLE:

Model and Algorithms for The Travelling Salesman with Multiple Passengers and High Occupancy Problem

KEY WORDS:

Traveling Salesman Problem, Ridesharing, Metaheuristics, High-Occupancy Toll

PAGES: 120
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 an extension of the TSP that transforms it, from a pure routing problem, into a ridesharing problem with routing restrictions determined by real-world characteristics. In this new scenario, the salesman offers rides to passengers along the TSP route to share expenses. In between roads that connect cities, some of them are toll roads, and those are of the High-Occupancy type, since vehicles are exempt from paying the fare if they have no seats available. When charged, toll’s expenses are entirely paid by the salesman, but besides that, all other costs are shared, being equally divided between the salesman and all riding passengers on their respective paths. TSMPHOP’s objective is to find the Hamiltonian cycle with the lowest cost, which is defined by the sum of expenses paid by the salesman along the route. Those features promote the efficient use of urban space and the reduction of greenhouse gas emissions, since there’s a clear incentive to move more people using the same transportation means. This work presents the study of this novel combinatorial optimization problem, going from the conception of a mathematical model to represent all of its restrictions, the analysis of the existent relationship with other problems in the literature, and the creation of experimental algorithms to find good quality solutions for it. To further support computational experiments and put the proposed methods to test, a set of resources is also presented, including the generation of artificial test cases and the implementation of the solution methods. Four experimental algorithms based on the Genetic, Memetic, and Transgenetic metaheuristics are introduced. Auxiliary procedures for generating and manipulating solutions are revealed as well. The instances are submitted to the Gurobi solver to establish a benchmark. Heuristics’ parameters are tuned using the iRace tool and later compared through two computational experiments, one without additional stop criteria and another with a maximum number of evaluations of the objective function. A statistical analysis based on Friedman tests pointed to a superior performance of the algorithm using the Transgenetic approach with Local Search procedures.

COMMITTEE MEMBERS:
Presidente - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Interna - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA