[pt] Problemas de multifluxos surgem como modelos básicos no
contexto de várias aplicações de fluxos em redes, tais
como redes de telecomunicações, redes de transporte e
logística. Em tais aplicações, os fluxos que atravessam a
rede compartilham simultaneamente os mesmos recursos
disponíveis e são definidos por suas próprias restrições.
A cada uma das arestas ligando os pontos da rede está
associado um custo, fixo ou proporcional à sua utilização.
Este trabalho trata problemas de projeto de redes
multifluxos, em que os custos estão associados às
capacidades instaladas nas arestas. Particularmente, será
estudado o caso em que a função de custo nas arestas
possui o comportamento de uma função escada crescente e
descontínua, para o qual métodos exatos de resolução são
ineficientes. Métodos heurísticos são propostos para a
resolução aproximada do problema e sintetizados em um
algoritmo de multi-partida com memória adaptativa. Um
mecanismo de intensificação, conhecido na literatura como
construção de vocabulário, é também explorado e aplicado.
Finalmente, experimentos computacionais são realizados e o
método de resolução proposto é analisado quanto aos seus
resultados e os resultados obtidos pelo método de
resolução proposto são analisados. O método obtém as
melhores soluções conhecidas para algumas instâncias da
literatura. / [en] Multicommodity flow problems arise widely as basic models
in the context of network flows applications such as
telecommunication networks, transportation problems, and
logistic. In these applicatons, the flows that cross the
networks share the same avaiable resources simultaneously
and are defined by their own constraints. Each edge
connecting two nodes in the network has an associated cost
that is either fixed or proportional to its use. This work
focuses on a network design problem in which the cost are
associated with the capacities installed in the edges.
Particularly, the network design problem studied has
discrete and step increasing cost functions on the edges,
for which exact methods are inefficient. Heuristics are
proposed for the approximate memory algorithm. An
intensification mechanism, known in the literature as
vocabulary building, is also explored and applied.
Finally, computational experiments are performed and the
results obtained with the proposed solution method are
evaluated. The method obtains the best known solutions for
some instances in the literature.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:6665 |
| Date | 28 June 2005 |
| Creators | DANIEL ALOISE |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0083 seconds