[pt] O Team Orienteering Problem é um problema de roteamento de veículos
sobre um grafo com durações associadas aos arcos e prêmios atribuídos à
visitação de cada vértice. Neste problema, considera-se que as visitas são
realizadas por uma frota com um número fixo de veículos idênticos e que
existe uma duração total máxima para as rotas serem finalizadas. Cada
vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade
de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo
de duração das rotas. O objetivo do problema é maximizar o prêmio total
ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens:
uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma
formulação baseada em arcos e uma formulação estendida na qual cada
arco tem um índice extra. Esse índice representa o tempo de partida de um
veículo ao percorrer o arco. Através de transformações sobre a formulação
estendida, foi obtida uma formulação, cuja relaxação, problema mestre
restrito, foi resolvida pela técnica de geração de colunas. O subproblema
de geração de colunas foi resolvido por programação dinâmica em tempo
pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas
nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos
das rotas não elementares, uma nova classe de desigualdades denominada
min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price
(BCP) foram obtidos alguns novos limites superiores. A abordagem exata
obteve resultados competitivos quando comparada ao melhor algoritmo
exato já proposto para esse problema. Na abordagem heurística, além de
uma vizinhança k-opt, foi explorada também uma busca elipsoidal que
adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse
novo corte reduz o espa¸co de busca a uma vizinhança em torno de um
conjunto de soluções conhecidas. Essa busca é utilizada como um operador
de crossover executado em todas as iterações de um algoritmo evolutivo.
Essa abordagem converge em um tempo computacional razoável e encontra
soluções ótimas ou próximas da ótima para algumas instâncias da literatura. / [en] Team Orienteering Problem is a vehicle routing problem on a graph with
durations associated to the arcs and profits assigned to visiting the vertices.
In this problem, a fleet with a fixed number of identical vehicles performs
the visitations and there is a limited total duration for the routes to be
ended up. Each vertex can be visited at most once and the solution does
not have the obligation to visit all vertices, due to the constraint that limits
the maximum duration of routes. The goal of the problem is to maximize
the total profit gathered by all routes. In this work, two approaches have
been proposed: an exact and a heuristic one. In the exact approach, we have
developed an arc based formulation and an extended formulation where each
arc has an extra index. This index represents the departure time of a vehicle
using an arc. Through transformations on the extended formulation, we have
obtained a formulation, whose relaxation - the restricted master problem -
is solved using the column generation technique. A dynamic programming
algorithm solves the column generation subproblem in pseudo-polynomial
time. This algorithm generates non-elementary routes that allow subcycles.
In order to cut off the subcycles, a new class of inequalities called min cut has
been proposed.We have applied a Branch-Cut-and-Price (BCP) algorithm.
This allowed finding some new upper bounds. The exact approach has
achieved competitive results compared to the best exact algorithm has
already proposed to this problem. In the heuristic approach, besides a kopt
neighborhood, we have also exploited an ellipsoidal search that adds a
new cut constraint to the formulation of Branch-Cut-and-Price algorithm.
This new cut reduces the space search to a neighborhood around a known
set of solutions. This search is used as a crossover operator that runs all
iterations of a evolutive algorithm. This approach converges in a reasonable
computational time and finds optimal or near optimal solutions for some
instances in the literature.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:19542 |
| Date | 18 May 2012 |
| Creators | FRANCISCO HENRIQUE DE FREITAS VIANA |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0029 seconds