Problema do caixeiro viajante alugador com passageiro

This paper presents a new variant of the Traveling Salesman Problem not yet described in the literature, called the Traveling Car Renter with Passengers. This problem provides a set of cities, a set of vehicles and a set of potential passengers. The salesman's tour can be done using di erent...

ver descrição completa

Na minha lista:

Detalhes bibliográficos
Autor principal:	Sabry, Gustavo de Araújo
Outros Autores:	Goldbarg, Marco César
Formato:	doctoralThesis
Idioma:	pt_BR
Publicado em:	Universidade Federal do Rio Grande do Norte
Assuntos:	Problema do Caixeiro viajante alugador com passageiros Problema do caixeiro viajante Otimização combinatória
Endereço do item:	https://repositorio.ufrn.br/jspui/handle/123456789/30184
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	ri-123456789-30184
record_format	dspace
institution	Repositório Institucional
collection	RI - UFRN
language	pt_BR
topic	Problema do Caixeiro viajante alugador com passageiros Problema do caixeiro viajante Otimização combinatória
spellingShingle	Problema do Caixeiro viajante alugador com passageiros Problema do caixeiro viajante Otimização combinatória Sabry, Gustavo de Araújo Problema do caixeiro viajante alugador com passageiro
description	This paper presents a new variant of the Traveling Salesman Problem not yet described in the literature, called the Traveling Car Renter with Passengers. This problem provides a set of cities, a set of vehicles and a set of potential passengers. The salesman's tour can be done using di erent vehicles, i.e., the problem encompasses the process of car rental. The proposed model also includes elements related to the sharing of the seats of the used vehicle, i.e., in the cities there may be people interested in traveling to a certain destination and willing to share the costs with the salesman while they are aboard in the vehicle. The objective of the problem is to determine, in a graph, the Hamiltonian cycle with the lowest cost considering the vehicles' exchanges and the shipments along the tour. The problem is made up of several interlinked decisions: the sequence of visited cities, the order of used cars, the cities where the cars must be rented and/or delivered and the passengers' boarding scheme. The de nition of the proposed problem involves the combination of two important concepts that are currently being widely used in the eld of transportation: car rental and ride-sharing. Three formulations of mixed integer programming are proposed. These formulations are linearized using di erent techniques, resulting in six linearized models. These models are implemented in a solver and validated. In addition, three naive heuristics and three metaheuristics are presented to solve the problem. Comparative computational experiments and performance tests are performed on a set of 90 instances. The results obtained are compared and the conclusions are reported.
author2	Goldbarg, Marco César
author_facet	Goldbarg, Marco César Sabry, Gustavo de Araújo
format	doctoralThesis
author	Sabry, Gustavo de Araújo
author_sort	Sabry, Gustavo de Araújo
title	Problema do caixeiro viajante alugador com passageiro
title_short	Problema do caixeiro viajante alugador com passageiro
title_full	Problema do caixeiro viajante alugador com passageiro
title_fullStr	Problema do caixeiro viajante alugador com passageiro
title_full_unstemmed	Problema do caixeiro viajante alugador com passageiro
title_sort	problema do caixeiro viajante alugador com passageiro
publisher	Universidade Federal do Rio Grande do Norte
publishDate	2020
url	https://repositorio.ufrn.br/jspui/handle/123456789/30184
work_keys_str_mv	AT sabrygustavodearaujo problemadocaixeiroviajantealugadorcompassageiro AT sabrygustavodearaujo thetravelingcarrenterwithpassengers
_version_	1773967266015084544
spelling	ri-123456789-301842020-09-27T07:56:26Z Problema do caixeiro viajante alugador com passageiro The traveling car renter with passengers Sabry, Gustavo de Araújo Goldbarg, Marco César Goldbarg , Elizabeth Ferreira Gouveia Menezes, Matheus da Silva Silva, Paulo Henrique Asconavieta da Souza, Thatiana Cunha Navarro de Problema do Caixeiro viajante alugador com passageiros Problema do caixeiro viajante Otimização combinatória This paper presents a new variant of the Traveling Salesman Problem not yet described in the literature, called the Traveling Car Renter with Passengers. This problem provides a set of cities, a set of vehicles and a set of potential passengers. The salesman's tour can be done using di erent vehicles, i.e., the problem encompasses the process of car rental. The proposed model also includes elements related to the sharing of the seats of the used vehicle, i.e., in the cities there may be people interested in traveling to a certain destination and willing to share the costs with the salesman while they are aboard in the vehicle. The objective of the problem is to determine, in a graph, the Hamiltonian cycle with the lowest cost considering the vehicles' exchanges and the shipments along the tour. The problem is made up of several interlinked decisions: the sequence of visited cities, the order of used cars, the cities where the cars must be rented and/or delivered and the passengers' boarding scheme. The de nition of the proposed problem involves the combination of two important concepts that are currently being widely used in the eld of transportation: car rental and ride-sharing. Three formulations of mixed integer programming are proposed. These formulations are linearized using di erent techniques, resulting in six linearized models. These models are implemented in a solver and validated. In addition, three naive heuristics and three metaheuristics are presented to solve the problem. Comparative computational experiments and performance tests are performed on a set of 90 instances. The results obtained are compared and the conclusions are reported. Este trabalho apresenta uma nova variante do Problema do Caixeiro Viajante ainda não descrita na literatura, denominada de Problema do Caixeiro Viajante Alugador com Passageiros. Neste problema são disponibilizados um conjunto de cidades, um conjunto de veículos e um conjunto de passageiros em potencial. O tour do caixeiro pode ser realizado utilizando diferentes automóveis, ou seja, o problema engloba o processo de aluguel de veículos. O modelo proposto também inclui elementos relacionados ao compartilhamento dos assentos do veículos utilizado, ou seja, nas cidades podem haver pessoas interessadas em viajar para um determinado destino e dispostas a dividir os custos com o caixeiro enquanto estão embarcadas no veículo. O objetivo do problema é determinar, em um grafo, o ciclo Hamiltoniano de menor custo considerando as trocas de veículos e os embarques de passageiros durante o percurso. O problema é composto por várias decisões interligadas: a sequência das cidades visitadas, a ordem dos carros utilizados, as cidades onde os automó- veis devem ser alugados/devolvidos, bem como o esquema de embarque dos passageiros. A de nição do problema proposto neste trabalho envolve a combinação de dois conceitos importantes que estão sendo amplamente utilizados no setor de transportes: o aluguel e o compartilhamento de veículos. São propostas três formulações de programação inteira mista. Estas formulações são linearizadas utilizando técnicas diferentes, resultando em seis modelos lineares. Estes modelos são implementados em um solver e validados. Além disso, também são apresentadas três heurísticas ingênuas e três meta-heurísticas para solucionar o problema. Experimentos computacionais comparativos e testes de desempenho são realizados sobre uma amostra de 90 instâncias. Os resultados obtidos são comparados e as conclusões são reportadas. 2020-09-23T17:58:03Z 2020-09-23T17:58:03Z 2020-06-12 doctoralThesis SABRY, Gustavo de Araújo. Problema do caixeiro viajante alugador com passageiro. 2020. 137f. Tese (Doutorado 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/30184 pt_BR Attribution-NonCommercial-NoDerivs 3.0 Brazil http://creativecommons.org/licenses/by-nc-nd/3.0/br/ application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO

Problema do caixeiro viajante alugador com passageiro

Registros relacionados