Goldbarg, Marco CésarSilva, Yuri Kelvin Nascimento da2020-06-042020-06-042020-02-07SILVA, Yuri Kelvin Nascimento da. Problema do passeio lucrativo com passageiros e penalidades por atrasos. 2020. 160f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2020.https://repositorio.ufrn.br/jspui/handle/123456789/29157This work introduces a new Traveling Salesman Problem variant called Profitable Tour Problem with 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 as a result of delays. 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.Acesso AbertoOtimização combinatóriaMeta-heurísticasAlgoritmos evolucionáriosProblema do passeio lucrativo com passageirosmasterThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO