O problema do caixeiro viajante com passageiros

This thesis presents a vehicle seat sharing model in order to reduce travel costs for drivers and passengers, contributing significantly to the environment and society. The problem is also described by a linear programming model and it is discussed in some variants of an important subproblem for...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Calheiros, Zailton Sachas Amorim
Outros Autores: Goldbarg, Marco César
Formato: Dissertação
Idioma:por
Publicado em: Brasil
Assuntos:
Caixeiro viajante
Passageiros
Algoritmos evolucionários
Genético
Memético
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/24203
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-24203
record_format dspace
spelling ri-123456789-242032017-11-08T04:16:17Z O problema do caixeiro viajante com passageiros Traveling salesman with passengers problem Calheiros, Zailton Sachas Amorim Goldbarg, Marco César Gouvea, Elizabeth Ferreira Maia, Silvia Maria Diniz Monteiro Menezes, Matheus da Silva Caixeiro viajante Passageiros Algoritmos evolucionários Genético Memético CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO This thesis presents a vehicle seat sharing model in order to reduce travel costs for drivers and passengers, contributing significantly to the environment and society. The problem is also described by a linear programming model and it is discussed in some variants of an important subproblem for solving the main problem. Besides, some computational approaches are implemented, composed by evolutionary (genetic and memetic) e constructive (ant optimization) algorithms. In addition to the adaptation of already existing algorithms for the travaling salesman problem as the Lin-Kernighan algorithm. After performing experiments, ant-based algorithms prove itself promising for asymmetric instances while the Lin-Kernighan algorithm takes advantage of its robustness through the implementation of Helsgaun and has a good performance for symmetric instances. Este trabalho apresenta um modelo de compartilhamento de assentos veicular de modo a reduzir os custos de viagem de motoristas e passageiros, contribuindo de maneira significativa ao meio ambiente e à sociedade. O problema também é descrito através de um modelo de programação linear e são discutidas algumas variantes de um subproblema importante para resolução do modelo proposto. Além disso, algumas abordagens computacionais são implementadas, compostas de algoritmos evolucionários (genético e memético) e construtivos (formigas e GRASP). Além da adaptação de algoritmos já existes para o problema do caixeiro viajante tradicional como o algoritmo de Lin-Kernighan. Após a realização de experimentos, o algoritmo baseado em formiga revela-se promissor para instâncias assimétricas enquanto que o algoritmo de Lin-Kernighan leva vantagem pela sua robustez através da implementação de Helsgaun que desempenha bons resultados para instâncias simétricas. 2017-11-07T21:20:44Z 2017-11-07T21:20:44Z 2017-07-31 masterThesis CALHEIROS, Zailton Sachas Amorim. O problema do caixeiro viajante com passageiros. 2017. 90f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2017. https://repositorio.ufrn.br/jspui/handle/123456789/24203 por 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 por
topic Caixeiro viajante
Passageiros
Algoritmos evolucionários
Genético
Memético
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
spellingShingle Caixeiro viajante
Passageiros
Algoritmos evolucionários
Genético
Memético
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Calheiros, Zailton Sachas Amorim
O problema do caixeiro viajante com passageiros
description This thesis presents a vehicle seat sharing model in order to reduce travel costs for drivers and passengers, contributing significantly to the environment and society. The problem is also described by a linear programming model and it is discussed in some variants of an important subproblem for solving the main problem. Besides, some computational approaches are implemented, composed by evolutionary (genetic and memetic) e constructive (ant optimization) algorithms. In addition to the adaptation of already existing algorithms for the travaling salesman problem as the Lin-Kernighan algorithm. After performing experiments, ant-based algorithms prove itself promising for asymmetric instances while the Lin-Kernighan algorithm takes advantage of its robustness through the implementation of Helsgaun and has a good performance for symmetric instances.
author2 Goldbarg, Marco César
author_facet Goldbarg, Marco César
Calheiros, Zailton Sachas Amorim
format masterThesis
author Calheiros, Zailton Sachas Amorim
author_sort Calheiros, Zailton Sachas Amorim
title O problema do caixeiro viajante com passageiros
title_short O problema do caixeiro viajante com passageiros
title_full O problema do caixeiro viajante com passageiros
title_fullStr O problema do caixeiro viajante com passageiros
title_full_unstemmed O problema do caixeiro viajante com passageiros
title_sort o problema do caixeiro viajante com passageiros
publisher Brasil
publishDate 2017
url https://repositorio.ufrn.br/jspui/handle/123456789/24203
work_keys_str_mv AT calheiroszailtonsachasamorim oproblemadocaixeiroviajantecompassageiros
AT calheiroszailtonsachasamorim travelingsalesmanwithpassengersproblem
_version_ 1773958686890262528

Registros relacionados