Banca de QUALIFICAÇÃO: YURI KELVIN NASCIMENTO DA SILVA

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE : YURI KELVIN NASCIMENTO DA SILVA
DATA : 14/06/2019
HORA: 11:00
LOCAL: Auditório I - DIMAP
TÍTULO:

Traveling Salesman Problem with Prize Collecting, Passengers and Penalties for Delays

 

PALAVRAS-CHAVES:

Traveling Salesman Problem with Prize Collecting, Passagens and Penalties for Delays; Metaheursitics, Combinatorial Optimization. 

PÁGINAS: 50
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:

This work introduces a new Traveling Salesman Problem variant called Traveling Salesman Problem with Prize Collecting, Passengers and Penalties for Delays. In this problem, the salesman has, along the graph, potential passengers who need to move between localities. Each boarded passenger will contribute a portion to the division of the travel costs between all the occupants of the vehicle in a certain stretch. In addition, each vertex has an aggregate prize value that may or may not be collected by the salesman during his journey. The prizes have a time for the collection and an estimated minimum time to be collected without a reduction in its value, characterizing the penalty. Thus, the goal is to find a route that maximizes the amount of collected prizes minus the travel costs divided with passengers and any penalties imposed on the prizes. As an instrument of formalization and validation of the problem, a Mathematical Programming model is proposed and solved through a mathematical solver for test instances generated for the problem in question. A coupling analysis of the instances is reported through experiments with ad hoc heuristic methods and exact methods that consider particular cases of the model. Moreover, three evolutionary metaheuristics are proposed aiming the efficiency in obtaining quality solutions

MEMBROS DA BANCA:
Presidente - 1149561 - MARCO CESAR GOLDBARG
Interna - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA