Banca de DEFESA: YURI KELVIN NASCIMENTO DA SILVA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
STUDENT : YURI KELVIN NASCIMENTO DA SILVA
DATE: 07/02/2020
TIME: 09:30
LOCAL: Auditório I - DIMAP
TITLE:

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

 


KEY WORDS:

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


PAGES: 90
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Teoria da Computação
SPECIALTY: Análise de Algoritmos e Complexidade de Computação
SUMMARY:

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


BANKING MEMBERS:
Presidente - 1149561 - MARCO CESAR GOLDBARG
Interna - 1201268 - ELIZABETH FERREIRA GOUVEA GOLDBARG
Externo à Instituição - MATHEUS DA SILVA MENEZES - UFERSA
Externa à Instituição - THATIANA CUNHA NAVARRO DE SOUZA - UFERSA
Notícia cadastrada em: 27/12/2019 09:12
SIGAA | Superintendência de Informática - | | Copyright © 2006-2020 - UFRN - sigaa11-producao.info.ufrn.br.sigaa11-producao