Caixeiro viajante com coleta de prêmios e passageiros

The Prize Collect Traveling Salesman Problem with Ridesharing is a model that merge elements of the classic problem PCTSP with ridesharing. The costs of the driver journey are reduced through the apportionment of expenses due to the sharing of accents in the vehicle used in the task of collecting...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Medeiros, Ygor Alcântara de
Outros Autores: Goldbarg, Marco Cesar
Formato: Dissertação
Idioma:pt_BR
Publicado em: Brasil
Assuntos:
Caixeiro viajante
Passageiros
Ridesharing
Meta-heurísticas
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/27640
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-27640
record_format dspace
spelling ri-123456789-276402019-09-08T05:15:18Z Caixeiro viajante com coleta de prêmios e passageiros Prize collecting traveling salesman problem with ridesharing Medeiros, Ygor Alcântara de Goldbarg, Marco Cesar Goldbarg, Elizabeth Ferreira Gouvea Maia, Silvia Maria Diniz Monteiro Souza, Thatiana Cunha Navarro de Caixeiro viajante Passageiros Ridesharing Meta-heurísticas CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO The Prize Collect Traveling Salesman Problem with Ridesharing is a model that merge elements of the classic problem PCTSP with ridesharing. The costs of the driver journey are reduced through the apportionment of expenses due to the sharing of accents in the vehicle used in the task of collecting prizes. The tasks in the route are selected according to the routing model with collection of prizes, therefore considering penalties for the non-attendance of existing task and additionally determining the fulfillment of a minimum demand of tasks. The demand for collaborative transport is protected by restrictions that ensure passengers are transported to their destination. Likewise, the apportionment costs will be less than or equal to the tariff limits established by the passengers. The present work presents the mathematical formulation for the problem, validates the model in an exact solution process and examines the performance of two algorithms that execute construction steps with exact criteria and six with heuristic criteria. Accurate step-by-step algorithms aim to create anchoring results to evaluate algorithm performance with heuristic decisions. Three instance groups are also proposed for the problem in order to allow future experimentation of new algorithms. Finally, it is concluded that the algorithms of heuristic steps achieve promising performance for the problem examined. O Problema do Caixeiro Viajante com Coleta de Prêmios e Passageiros é um modelo que mescla elementos do clássico PCVCP, com características dos problemas de ridesharing. Os custos do trajeto do motorista são reduzidos através do rateio de despesas em virtude do compartilhamento de assentos no veículo usado na tarefa de coleta de prêmios. As tarefas na rota são selecionadas segundo o modelo de roteamento com coleta de prêmios, portanto se considerando penalidades pelo eventual não atendimento de tarefas existentes e, adicionalmente, determinando o cumprimento de uma demanda mínima de tarefas. A demanda do transporte colaborativo é protegida por restrições que garantem aos passageiros seu transporte até o destino. Igualmente, os custos de rateio serão menores ou iguais aos limites de tarifa estabelecidos pelos passageiros. O presente trabalho apresenta a formulação matemática para o problema, valida o modelo em um processo de solução exata e examina o desempenho de dois algoritmos que executam passos de construção com critérios exatos e seis com critérios heurísticos. Os algoritmos construtivos com passos exatos visam principalmente criar resultados de ancoragem para a avalição do desempenho dos algoritmos com decisões heurísticas. São também propostos três grupos de instâncias de teste para o problema, visando permitir futuras experimentações de novos algoritmos. Por fim, conclui-se que os algoritmos de passos heurísticos alcançam desempenho promissor para o problema examinado. 2019-09-04T23:23:17Z 2019-09-04T23:23:17Z 2019-07-01 masterThesis MEDEIROS, Ygor Alcântara de. Caixeiro viajante com coleta de prêmios e passageiros. 2019. 93f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2019. https://repositorio.ufrn.br/jspui/handle/123456789/27640 pt_BR Acesso Aberto application/pdf Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
institution Repositório Institucional
collection RI - UFRN
language pt_BR
topic Caixeiro viajante
Passageiros
Ridesharing
Meta-heurísticas
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
spellingShingle Caixeiro viajante
Passageiros
Ridesharing
Meta-heurísticas
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Medeiros, Ygor Alcântara de
Caixeiro viajante com coleta de prêmios e passageiros
description The Prize Collect Traveling Salesman Problem with Ridesharing is a model that merge elements of the classic problem PCTSP with ridesharing. The costs of the driver journey are reduced through the apportionment of expenses due to the sharing of accents in the vehicle used in the task of collecting prizes. The tasks in the route are selected according to the routing model with collection of prizes, therefore considering penalties for the non-attendance of existing task and additionally determining the fulfillment of a minimum demand of tasks. The demand for collaborative transport is protected by restrictions that ensure passengers are transported to their destination. Likewise, the apportionment costs will be less than or equal to the tariff limits established by the passengers. The present work presents the mathematical formulation for the problem, validates the model in an exact solution process and examines the performance of two algorithms that execute construction steps with exact criteria and six with heuristic criteria. Accurate step-by-step algorithms aim to create anchoring results to evaluate algorithm performance with heuristic decisions. Three instance groups are also proposed for the problem in order to allow future experimentation of new algorithms. Finally, it is concluded that the algorithms of heuristic steps achieve promising performance for the problem examined.
author2 Goldbarg, Marco Cesar
author_facet Goldbarg, Marco Cesar
Medeiros, Ygor Alcântara de
format masterThesis
author Medeiros, Ygor Alcântara de
author_sort Medeiros, Ygor Alcântara de
title Caixeiro viajante com coleta de prêmios e passageiros
title_short Caixeiro viajante com coleta de prêmios e passageiros
title_full Caixeiro viajante com coleta de prêmios e passageiros
title_fullStr Caixeiro viajante com coleta de prêmios e passageiros
title_full_unstemmed Caixeiro viajante com coleta de prêmios e passageiros
title_sort caixeiro viajante com coleta de prêmios e passageiros
publisher Brasil
publishDate 2019
url https://repositorio.ufrn.br/jspui/handle/123456789/27640
work_keys_str_mv AT medeirosygoralcantarade caixeiroviajantecomcoletadepremiosepassageiros
AT medeirosygoralcantarade prizecollectingtravelingsalesmanproblemwithridesharing
_version_ 1773964250782367744

Registros relacionados