Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação

O Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação constitui uma generalização do Problema do Caixeiro Viajante que lhe adiciona características do mundo real, transformando-o em um problema de ridesharing com restrições de roteamento. Nessa modalidade, o caixeiro oferece caronas a...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Bastos, Ranmsés Emanuel Martins
Outros Autores: Goldbarg, Elizabeth Ferreira Gouvêa
Formato: doctoralThesis
Idioma:pt_BR
Publicado em: Universidade Federal do Rio Grande do Norte
Assuntos:
Computação
Problema do caixeiro viajante
Problema ridesharing
Meta-heurísticas
Aprendizado por reforço
Pedágios high-occupancy
Restrições lazy
Funções piecewise
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Endereço do item:https://repositorio.ufrn.br/handle/123456789/53356
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-53356
record_format dspace
spelling ri-123456789-533562023-07-13T21:28:51Z Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação Investigation of models and algorithms for the traveling salesman with multiple passengers and high occupancy problem Bastos, Ranmsés Emanuel Martins Goldbarg, Elizabeth Ferreira Gouvêa http://lattes.cnpq.br/2569092352488218 http://lattes.cnpq.br/2888641121265608 Menezes, Matheus da Silva Cabral, Lucídio dos Anjos Formiga Goldbarg, Marco César http://lattes.cnpq.br/1371199678541174 Maia, Silvia Maria Diniz Monteiro Computação Problema do caixeiro viajante Problema ridesharing Meta-heurísticas Aprendizado por reforço Pedágios high-occupancy Restrições lazy Funções piecewise CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO O Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação constitui uma generalização do Problema do Caixeiro Viajante que lhe adiciona características do mundo real, transformando-o em um problema de ridesharing com restrições de roteamento. Nessa modalidade, o caixeiro oferece caronas a terceiros ao longo da rota visando compartilhar os custos da viagem. As ligações entre cidades podem conter pedágios do tipo High-Occupancy, no qual há isenção da tarifa caso o veículo esteja com todos os assentos ocupados. Quando cobradas, as despesas de pedágio são inteiramente pagas pelo caixeiro. Os demais custos são divididos igualmente entre o caixeiro e todos os passageiros que ocupam assentos em seus respectivos percursos. O objetivo do PCV-MPL é encontrar o ciclo Hamiltoniano com o menor custo, calculado pela soma das despesas arcadas pelo caixeiro. Tais características promovem a eficiência no uso do espaço urbano e a redução das emissões de gases de efeito estufa, dado o incentivo para compartilhamento do meio de transporte com um número maior de pessoas. Esta tese apresenta o estudo deste novo problema de otimização combinatória, iniciando pela análise da relação existente com outros modelos na literatura. Em seguida, é abordada a formulação matemática do problema com diversas variantes para representação de suas restrições. Por fim, são criados algoritmos para encontrar soluções de boa qualidade em curto espaço de tempo. Com o intuito de realizar experimentos computacionais, é realizada a geração de um banco de instâncias artificiais e a implementação dos métodos de solução. Dez modelos matemáticos são implementados no solver Gurobi para estabelecer um padrão de referência, determinando soluções ótimas para as instâncias e comparando diferentes técnicas de formulação, incluindo restrições lazy e funções lineares piecewise. São propostos também procedimentos para manipular soluções e dez algoritmos heurísticos desenvolvidos com base nas meta-heurísticas Algoritmo Genético, Memético e Transgenética Computacional e na técnica de aprendizado por reforço Q-learning. Três experimentos computacionais são conduzidos: o primeiro controlado pelos parâmetros de iteração máxima, o segundo com limite absoluto de avaliações da função objetivo e o terceiro com limite de avaliações da função objetivo relativo à descoberta da última melhor solução. O ajuste de parâmetros é executado de modo automático pela ferramenta irace. Uma análise estatística baseada no teste Friedman Aligned Ranks indicou um desempenho superior do algoritmo híbrido unindo a Transgenética Computacional, o Algoritmo Memético e a técnica Q-learning. 2023-07-13T21:28:05Z 2023-07-13T21:28:05Z 2023-03-27 doctoralThesis BASTOS, Ranmsés Emanuel Martins. Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação. Orientador: Elizabeth Ferreira Gouvêa Goldbarg. 2023. 284f. Tese (Doutorado em Ciência da Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2023. https://repositorio.ufrn.br/handle/123456789/53356 pt_BR Acesso Aberto application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
institution Repositório Institucional
collection RI - UFRN
language pt_BR
topic Computação
Problema do caixeiro viajante
Problema ridesharing
Meta-heurísticas
Aprendizado por reforço
Pedágios high-occupancy
Restrições lazy
Funções piecewise
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
spellingShingle Computação
Problema do caixeiro viajante
Problema ridesharing
Meta-heurísticas
Aprendizado por reforço
Pedágios high-occupancy
Restrições lazy
Funções piecewise
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Bastos, Ranmsés Emanuel Martins
Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
description O Problema do Caixeiro Viajante com Múltiplos Passageiros e Lotação constitui uma generalização do Problema do Caixeiro Viajante que lhe adiciona características do mundo real, transformando-o em um problema de ridesharing com restrições de roteamento. Nessa modalidade, o caixeiro oferece caronas a terceiros ao longo da rota visando compartilhar os custos da viagem. As ligações entre cidades podem conter pedágios do tipo High-Occupancy, no qual há isenção da tarifa caso o veículo esteja com todos os assentos ocupados. Quando cobradas, as despesas de pedágio são inteiramente pagas pelo caixeiro. Os demais custos são divididos igualmente entre o caixeiro e todos os passageiros que ocupam assentos em seus respectivos percursos. O objetivo do PCV-MPL é encontrar o ciclo Hamiltoniano com o menor custo, calculado pela soma das despesas arcadas pelo caixeiro. Tais características promovem a eficiência no uso do espaço urbano e a redução das emissões de gases de efeito estufa, dado o incentivo para compartilhamento do meio de transporte com um número maior de pessoas. Esta tese apresenta o estudo deste novo problema de otimização combinatória, iniciando pela análise da relação existente com outros modelos na literatura. Em seguida, é abordada a formulação matemática do problema com diversas variantes para representação de suas restrições. Por fim, são criados algoritmos para encontrar soluções de boa qualidade em curto espaço de tempo. Com o intuito de realizar experimentos computacionais, é realizada a geração de um banco de instâncias artificiais e a implementação dos métodos de solução. Dez modelos matemáticos são implementados no solver Gurobi para estabelecer um padrão de referência, determinando soluções ótimas para as instâncias e comparando diferentes técnicas de formulação, incluindo restrições lazy e funções lineares piecewise. São propostos também procedimentos para manipular soluções e dez algoritmos heurísticos desenvolvidos com base nas meta-heurísticas Algoritmo Genético, Memético e Transgenética Computacional e na técnica de aprendizado por reforço Q-learning. Três experimentos computacionais são conduzidos: o primeiro controlado pelos parâmetros de iteração máxima, o segundo com limite absoluto de avaliações da função objetivo e o terceiro com limite de avaliações da função objetivo relativo à descoberta da última melhor solução. O ajuste de parâmetros é executado de modo automático pela ferramenta irace. Uma análise estatística baseada no teste Friedman Aligned Ranks indicou um desempenho superior do algoritmo híbrido unindo a Transgenética Computacional, o Algoritmo Memético e a técnica Q-learning.
author2 Goldbarg, Elizabeth Ferreira Gouvêa
author_facet Goldbarg, Elizabeth Ferreira Gouvêa
Bastos, Ranmsés Emanuel Martins
format doctoralThesis
author Bastos, Ranmsés Emanuel Martins
author_sort Bastos, Ranmsés Emanuel Martins
title Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
title_short Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
title_full Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
title_fullStr Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
title_full_unstemmed Investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
title_sort investigação de modelos e algoritmos para o problema do caixeiro viajante com múltiplos passageiros e lotação
publisher Universidade Federal do Rio Grande do Norte
publishDate 2023
url https://repositorio.ufrn.br/handle/123456789/53356
work_keys_str_mv AT bastosranmsesemanuelmartins investigacaodemodelosealgoritmosparaoproblemadocaixeiroviajantecommultiplospassageiroselotacao
AT bastosranmsesemanuelmartins investigationofmodelsandalgorithmsforthetravelingsalesmanwithmultiplepassengersandhighoccupancyproblem
_version_ 1773959785495920640

Registros relacionados