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...
Na minha lista:
Autor principal: | |
---|---|
Outros Autores: | |
Formato: | doctoralThesis |
Idioma: | pt_BR |
Publicado em: |
Universidade Federal do Rio Grande do Norte
|
Assuntos: | |
Endereço do item: | https://repositorio.ufrn.br/jspui/handle/123456789/30184 |
Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
Resumo: | 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. |
---|