Banca de DEFESA: RANMSES EMANUEL MARTINS BASTOS

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : RANMSES EMANUEL MARTINS BASTOS
DATA : 17/02/2017
HORA: 08:00
LOCAL: Sala de Reunião do DIMAp
TÍTULO:

The Traveling Salesman with Passengers and High Occupancy Problem

PALAVRAS-CHAVES:

Ridesharing Problem, Carpool, Metaheuristics.

PÁGINAS: 140
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

The Traveling Salesman with Passengers and High Occupancy Problem is a version of the classic TSP where the salesman is the driver of a vehicle who shares travels’ expenses with passengers. Besides shared expenses, the driver also benefits from discounts of the high-occupancy vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from tolls. This  paper presents a succinct mathematical model for this problem and an algorithm based on Simulated Annealing and Variable Neighborhood Search metaheuristics. The results of the heuristic algorithm are compared with the optimal solutions obtained by an exact algorithm.This work addresses the study of this novel combinatorial optimization problem, going from the relationship it draws with other ones widely covered by the literature, by the means of a revision of related work, until the conception of artificial test cases to fulfill the purpose of serving as comparison subjects to the experimental algorithms developed to solve it.

MEMBROS DA BANCA:
Presidente - 1149561 - MARCO CESAR GOLDBARG
Interno - 1201268 - ELIZABETH FERREIRA GOUVEA
Externo ao Programa - 2859606 - SILVIA MARIA DINIZ MONTEIRO MAIA
Externo à Instituição - LUCÍDIO DOS ANJOS FORMIGA CABRAL - UFPB
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA