CENTRO FEDERAL DE EDUCAÇÃO
TECNOLÓGICA DE MINAS GERAIS
Diretoria de Pesquisa e Pós-Graduação
Curso de Mestrado em Modelagem
Matemática e Computacional
UMA ABORDAGEM DE
PROBLEMAS DE FLUXO
MULTIPRODUTO VIA
MÉTODOS HEURÍSTICOS
Dissertação de Mestrado, submetida ao Curso de
Mestrado em Modelagem Matemática e Computacional, como parte dos requisitos exigidos para
a obtenção do título de Mestre em Modelagem
Matemática e Computacional.
Aluno: Carlos Alexandre Silva
Bacharel em Matemática Computacional (UFMG)
Orientador: Prof. Dr. Sérgio Ricardo de Souza (CEFET-MG)
Belo Horizonte, dezembro de 2007.
S586a SILVA, Carlos Alexandre
2007
Uma abordagem de problemas de fluxo multiproduto via métodos heurísticos.
Belo Horizonte: CEFET-MG, 2007.
83p.
Dissertação (Mestrado) Centro Federal de Educação
Tecnológica de Minas Gerais
CEFET/MG.
1. Otimização combinatória. 2. Fluxo multiproduto.
3. Métodos heurísticos. 4. Pesquisa operacional.
I. Título.
CDD 001.424
Aos meus pais,
Terezinha e Pedro.
ii
Agradecimentos
Agradeço a meus pais, Terezinha e Pedro, principais incentivadores presentes
em todas as etapas de minha vida e responsáveis pela formação de meu caráter e
educação, os quais jamais se deteriorarão com o tempo.
Às minhas irmãs Fernanda e Sheila, pelo apoio despendido a mim incondicionalmente.
Ao meu orientador Sérgio, por ter acreditado no meu pontencial e pelo suporte
prestado em todas as adversidades que surgiram durante esses dois anos.
Agradeço a todos meus amigos, que de formas diferentes contribuiram para este
novo passo de minha vida e a Deus.
Agradeço a Deus, por existir essas pessoas a quem agradeci anteriormente e por
tudo que tem feito por mim até o presente momento.
À CAPES e ao CEFET-MG pelo apoio financeiro despendido a esta pesquisa.
iii
“O sucesso é ir de fracasso em fracasso sem perder o entusiasmo.”
Sir Winston Churchill
iv
Resumo
Neste trabalho, é proposta uma análise e comparação entre metaheurísticas que
fazem uso de busca local (Iterated Local Search e Simulated Annealing) e um modelamento matemático computacional referente à busca populacional (Algoritmo Genético) para resolver o Problema de Fluxo Multiproduto. No intuito de solucionar o problema, a formulação matemática sofre uma relaxação quanto à restrição de fluxo,
penalizando o excesso de fluxo pelos nós da rede. Os resultados obtidos quanto à
utilização destas técnicas heurísticas mostram soluções de boa qualidade e em tempo
computacional razoável, porém, sem garantir a otimalidade global. Para o caso da
formulação em que cada produto especificado possui uma única origem e um único
destino, é apresentada uma técnica de pré-otimização cuja propriedade advém das
características de sua própria formulação, que se baseia na resolução de sistemas
lineares homogêneos e que apresenta bons resultados, dependendo da densidade da
rede utilizada. Além disso, é feita uma análise da dimensão do espaço solução do
problema tratado, sendo este espaço considerado como uma região de vizinhança
e/ou espaço de busca para as heurísticas utilizadas. Essa análise reflete a grande
dificuldade de solucionar o tipo de problema abordado neste presente trabalho.
Palavras-Chave: Otimização em Rede; Fluxo Multiproduto; Métodos Heurísticos.
v
Abstract
In this work it is considered an analysis and comparison between metaheuristics
that make use of local search (Iterated Local Search and Simulated Annealing) and
a computational mathematical modeling referring to the population search (Genetic
Algorithm) to solve the Multicommodity Flow Problem. To solve the problem, the
mathematical formulation suffers to a relaxation on the flow restriction, penalizing
the excess of flow for nodes of the net. The obtained results in relation the use of
these heuristics techniques show solutions of good quality and in reasonable computational time, however, without guaranteeing the global otimality. For the case
of the formulation where each specified commodity has an only origin node and an
only destination node, one technique of pre-optimization will be presented whose
property come of the characteristics of its proper formulation, that if bases on the
resolution of homogeneous linear systems and that it presents good results depending
on the density of the used network. Moreover an analysis of the dimension of the
space will be made solution of the treated problem, being this space considered as a
neighborhood region and/or used search space for the heuristics ones. This analysis
reflects the great difficulty to solve the type of boarded problem in this present work.
Keywords: Network Optimization; Multicommodity Flow; Metaheuristic.
vi
Sumário
1 Introdução
1.1 Preliminares . . . . . . . . . .
1.2 Motivação . . . . . . . . . . .
1.3 Caracterização do problema .
1.4 Objetivos . . . . . . . . . . .
1.5 Proposta de desenvolvimento .
1.6 Organização do trabalho . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
3
3
4
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Problemas de Fluxo Multiproduto
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . .
2.2 Definição do problema . . . . . . . . . . . . . . .
2.3 Formulações do Problema de Fluxo Multiproduto
2.3.1 Formulação nó-arco . . . . . . . . . . . . .
2.3.2 Formulação arco-rota . . . . . . . . . . . .
2.4 Problema multiproduto inteiro . . . . . . . . . . .
2.5 Conclusão . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
. 6
. 7
. 9
. 9
. 11
. 12
. 14
3 Modelagem do Problema
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Modelagem matemática . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Modelagem computacional . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Modelagem computacional sem uso da Pré-Otimização . . .
3.3.2 Modelagem computacional com o uso da Pré-Otimização . .
3.4 Modelagem matemática computacional de algoritmo genético para
PFMI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Uma revisão bibliográfica da aplicação de algoritmos genéticos
à solução de PFM . . . . . . . . . . . . . . . . . . . . . . . .
3.4.3 Representação de uma solução . . . . . . . . . . . . . . . . .
3.4.4 População inicial . . . . . . . . . . . . . . . . . . . . . . . .
3.4.5 Função de avaliação . . . . . . . . . . . . . . . . . . . . . . .
3.4.6 Aplicação de Algoritmo Genético ao Problema de Fluxo Multiproduto . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
.
.
.
.
.
15
15
15
18
19
21
. 22
. 22
.
.
.
.
23
24
25
25
. 26
. 28
4 Pré-Otimização Aplicada ao Problema de Fluxo Multiproduto
teiro
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Revisão bibliográfica . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Propriedade das restrições . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Modelagem dos sistemas lineares homogêneos . . . . . . .
4.4 Aplicação do método de pré-otimização . . . . . . . . . . . . . . .
4.5 Resultados computacionais . . . . . . . . . . . . . . . . . . . . . .
4.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
In.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Análise do Espaço Solução de um Problema de Fluxo Multiproduto
Inteiro
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Análise matemática do dimensionamento . . . . . . . . . . . . . . . .
5.3 Enumeração do espaço solução . . . . . . . . . . . . . . . . . . . . . .
5.4 Validação do dimensionamento . . . . . . . . . . . . . . . . . . . . . .
5.5 Análise para variação de parâmetros . . . . . . . . . . . . . . . . . .
5.6 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 Métodos Heurísticos
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Iterated Local Search aplicada ao Problema de Fluxo Multiproduto
Inteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Representação de uma solução . . . . . . . . . . . . . . . . .
6.2.2 Determinação da solução inicial . . . . . . . . . . . . . . . .
6.2.3 Função de avaliação . . . . . . . . . . . . . . . . . . . . . . .
6.2.4 Estruturas de vizinhança . . . . . . . . . . . . . . . . . . . .
6.2.5 Aplicação ILS ao PFM . . . . . . . . . . . . . . . . . . . . .
6.2.6 Análise dos resultados computacionais . . . . . . . . . . . .
6.3 Simulated Annealing aplicada ao Problema de Fluxo Multiproduto
Inteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Aplicação da metaheurística híbrida SA-ILS ao PFMI . . . .
6.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 Conclusão Geral e Trabalhos Futuros
29
29
29
30
32
32
35
37
38
38
38
40
44
45
48
49
. 49
.
.
.
.
.
.
.
50
51
52
52
53
54
54
. 57
. 59
. 60
61
A Algoritmo Recursivo para Determinação da Dimensão do EspaçoSolução
63
B Algoritmos de Pré-otimização
65
Referências
67
viii
Lista de Tabelas
3.1
Tabela de dimensionamento de operações. . . . . . . . . . . . . . . . 18
4.1
4.2
4.3
4.4
Complexidade de pré-condicionadores envolvendo laplacianos.
Resultados computacionais (% soluções). . . . . . . . . . . . .
Resultados computacionais (% soluções). . . . . . . . . . . . .
Resultados computacionais (Soluções prévias). . . . . . . . . .
5.1
Análise da dimensão do espaço solução do PFMI. . . . . . . . . . . . 47
6.1
6.2
Parâmetros presentes no algoritmo ILS. . . . . . . . . . . . . . . . .
Resultados computacionais para redes de alta densidade. ILS1: algoritmo ILS-Adaptado; ILS2: algoritmo ILS clássico. . . . . . . . . . .
Resultados computacionais para redes de baixa densidade. ILS1: algoritmo ILS-Adaptado; ILS2: algoritmo ILS clássico. . . . . . . . .
Resultados computacionais da aplicação da metaheurística híbrida
SA-ILS ao PFMI. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3
6.4
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
36
36
37
. 55
. 56
. 57
. 60
Lista de Figuras
2.1
2.2
Exemplo de rede de fluxo multiproduto. . . . . . . . . . . . . . . . . 7
Rede de fluxo multiproduto. . . . . . . . . . . . . . . . . . . . . . . . 10
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
Representação dos vetores de custo e de fluxo.
Representação do vetor de capacidade. . . . .
Registro para variável de fluxo. . . . . . . . .
Representação da lista de fluxo. . . . . . . . .
Representação da lista de fluxo. . . . . . . . .
Pseudocódigo do Algoritmo Genético. . . . . .
Matriz populacional. . . . . . . . . . . . . . .
Operação de crossover. . . . . . . . . . . . . .
Operação de mutação. . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16
18
19
20
21
23
25
27
28
4.1
4.2
4.3
4.4
Pseudocódigo para o procedimento de pré-otimização. . . .
Determinação das variáveis para a aplicação do Lema 4.1. .
Determinar fluxo infactível. . . . . . . . . . . . . . . . . .
Atualização da matriz. . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
34
34
34
5.1
5.2
5.3
5.4
Diagrama do espaço solução de um PFMI.
Variação do número de arcos. . . . . . . .
Variação de número de produtos. . . . . .
Variação da capacidade nos arcos. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
46
46
47
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
Estruturas de busca de algoritmos (Coelho, 2006). . . . . . . . . . . .
Perturbação sobre uma solução s em problemas de otimização contínua.
Pseudocódigo da metaheurística Iterated Local Search. . . . . . . . . .
Estruturação de uma solução s. . . . . . . . . . . . . . . . . . . . . .
Pseudocódigo do procedimento GeraSolucaoInicial. . . . . . . . . . .
Trajetória das soluções sob o espaço de restrições. . . . . . . . . . . .
Pseudocódigo da metaheurística ILS-Adaptado. . . . . . . . . . . . .
Pseudocódigo para algoritmo Simulated Annealing. . . . . . . . . . .
Pseudocódigo da metaheurística híbrida SA-ILS. . . . . . . . . . . . .
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
50
51
51
52
52
54
55
58
59
Lista de Siglas
AG - Algoritmo Genético.
GenMCF - Generator Multicommodity Flow.
GRASP - Greedy Randomized Adaptive Search Procedure.
ILS - Iterated Local Search.
MRD - Movimento Randômico de Descida.
ODE - Origem Destino Específico.
OX - Order Crossover.
PFM - Problema de Fluxo Multiproduto.
PFMI - Problema de Fluxo Multiproduto Inteiro.
PMX - Partially Matched Crossover.
POC - Problema de Otimização Combinatorial.
PSO - Particle Swarm Optimization.
RAM - Random Access Memory.
SA - Simulated Annealing.
xi
Lista de Símbolos
|X | - cardinalidade de um conjunto X .
|a| - valor absoluto de um elemento a.
A - conjunto de arestas de um grafo.
k mod |P| - resto da divisão inteira de k por |P|.
k div |P| - quociente da divisão inteira de k por |P|.
fi - fluxo na aresta i.
F - representação do fluxo em uma rede.
G - representação de um grafo.
N - conjunto de nós de um grafo.
N - conjunto dos números naturais.
P - conjunto de produtos inseridos num grafo.
R - representação de uma rede.
< - conjunto dos números reais.
Z - conjunto dos números inteiros.
xii
Capítulo 1
Introdução
1.1
Preliminares
Os primeiros trabalhos relatados na literatura sobre o Problema de Fluxo Multiproduto (PFM) datam do início dos anos 60, com as contribuições de Ford e
Fulkerson (1962) e Hu (1963). Há uma larga variedade de aplicações em relação a
esse tema, sobretudo nas áreas de telecomunicação e transportes. A determinação de
compostos para refinaria de petróleo (Lasdon, 1970), produção de bens de consumo
(Hax e Candea, 1984) e alocação de estudantes em escolas (Clark e Surkis, 1968)
são exemplos de aplicações do PFM.
A modelagem do problema tratado neste trabalho incide sobre um grafo direcionado, estrutura composta por pontos (nós) ligados por retas (arestas) orientadas.
Muitos problemas envolvendo situações reais podem ser representados por grafos.
Por exemplo, na modelagem de um problema aplicado à área de transporte, os nós
representariam cidades de uma região; as arestas representariam as rotas ligando as
cidades; e cada rota teria um determinado peso, o qual corresponderia à distância
entre uma cidade a outra. O objetivo seria transportar alguma mercadoria visando a
menor trajetória. O problema multiproduto surge quando vários produtos compartilham os arcos em uma rede e competem pela capacidade dos mesmos. O objetivo
é determinar, ao menor custo possível, o fluxo dos produtos pelos arcos da rede, de
maneira a atender um determinado conjunto de restrições.
Os problemas de fluxo multiproduto figuram entre os mais difíceis problemas de
programação linear, afirmativa justificada pela sua alta complexidade combinatorial,
caracterizando-o como um problema NP-difícil. Motivado por este fato, técnicas
heurísticas apresentam uma boa aceitação na tentativa de solucionar o problema.
Existem dois tipos de casos no que se refere à distribuição dos produtos pela
rede. No primeiro caso, existe uma única origem e um único destino para cada
produto. No segundo caso, as origens e destinos relacionados aos produtos não são
únicos. O produto pode sair de um único nó-origem e ter como destino um conjunto de nós; ou sair de vários nós-origens e ter como destino um único nó; além de
vários nós origens para vários nós destinos. Neste trabalho, inicialmente é tratado o
primeiro caso, no qual, para cada produto, existe um par de nós origem-destino especificado. Essa restrição fornece uma das principais características exploradas pelo
algoritmo de pré-otimização proposto. A bijeção existente entre o conjunto de nós
origem/destino implica no surgimento de sistemas lineares homogêneos na formu1
1.2
Motivação
2
lação matemática do problema, facilitando a determinação de variáveis, antes mesmo
de aplicar qualquer método para solucionar o problema em questão. O número de
soluções previstas pelo algoritmo de pré-otimização depende da densidade da rede
utilizada e alguns resultados obtidos tornam-se bem significativos, qualificando o
algoritmo como uma boa ferramenta de otimização.
Uma outra restrição importante que é considerada é a integralidade, que refere-se
às variáveis de interesse, ou seja, os fluxos dos produtos que trafegam pela rede são
valores inteiros positivos. Utilizando-se dessa restrição, é feita uma análise do espaço
solução do problema, em especial de um subespaço explorado pelas heurísticas. Ele
se configura como possível região de vizinhança ou espaço de busca para as soluções
correntes implicadas na heurística utilizada.
Há uma extensa bibliografia a respeito de problemas de fluxo multiproduto. Conseqüentemente, há várias estratégias no intuito de solucioná-los. Pode-se encontrar
algumas dessas estratégias em Ahuja et al. (1993). Existem basicamente quatro
classes de métodos para a resolução de um PFM, segundo Castro (2003): baseados
no método simplex, na decomposição, em aproximação e método de ponto interior.
Motivado pela complexidade dos problemas de fluxo multiproduto, os quais apresentam, em geral, uma elevada dimensão em relação ao número de variáveis envolvidas
no problema, o método de resolução aplicado a este trabalho é um método baseado
em heurísticas computacionais, buscando soluções sub-ótimas, já que os métodos
exatos apresentam dificuldades na determinação de soluções ótimas para essa classe
de problemas combinatoriais.
1.2
Motivação
O Problema de Fluxo Multiproduto Inteiro (PFMI), especificamente com variáveis inteiras, é, em geral, um problema NP-difícil. Sua complexidade aumenta
exponencialmente com a adição de novos produtos ao problema (vide capítulo 5).
Em virtude da dimensão do problema tratado, os métodos exatos encontram dificuldade na determinação de soluções ótimas. A grande quantidade de variáveis
envolvidas, bem como a utilização de procedimentos de inversão de matrizes, despendem uma enorme quantidade de memória, tornando inviáveis a utilização desses
métodos. Já as técnicas heurísticas apresentam boa aceitação na busca de soluções,
porém, sem a garantia de otimalidade.
É observada, na literatura, a utilização de métodos heurísticos em sub-problemas
menores, como a determinação de solução inicial, para posterior aplicação de um
método de resolução. Algumas metaheurísticas são bem recentes, como é o caso
do Iterated Local Search (ILS), apresentada em 2002. Neste trabalho, é apresentada uma abordagem para a solução do PFMI baseada no uso de metaheurísticas
como ILS, Simulated Annealing e Algoritmo Genético. A justificativa para a utilização destas está nos bons resultados obtidos em problemas diversos encontrados
na literatura, como é o caso da aplicação ILS ao problema de logística de uma
rede (Cordeau et al., 2006), tendo as soluções sido comparadas aos limites inferiores
gerados pela relaxação lagrangeana do problema. Em Yang et al. (2000) a metaheurística Simulated Annealing é utilizada para resolver um PFM binário, a fim
de encontrar soluções aproximadas que reflitam a um custo mínimo. Os resultados
1.4
Caracterização do problema
3
foram comparados com os resultados obtidos por alguns algoritmos exatos. Por fim,
em Tu et al. (2005) é desenvolvido um modelo de PFM híbrido para otimizar a distribuição e qualidade de água aplicado ao sistema regional de distribuição de água
da Califórnia do Sul. Os resultados obtidos, conforme Tu et al. (2005), indicam que
o algoritmo genético utilizado, junto ao algoritmo baseado no método gradiente,
conseguem resolver eficientemente o problema.
A restrição de conservação de fluxo do problema tratado fornece uma interessante
propriedade, útil para determinação prévia de algumas variáveis de interesse. Ela
se baseia na existência de um número definido de sistemas lineares homogêneos,
motivando a criação de um algoritmo de pré-otimização. Este conceito, aplicado
ao problema em questão, com as devidas particularidades de suas restrições, figura
como um bom método de pré-condicionamento.
A terceira abordagem presente nesta proposta refere-se ao espaço explorado pelas
heurísticas. É apresentada a real dimensão deste espaço, refletindo a alta complexidade do problema.
1.3
Caracterização do problema
O problema de fluxo multiproduto inteiro é modelado via grafo, o qual representa
a rede em questão. Cada nó do grafo diz respeito a um ponto de oferta ou demanda
de um determinado produto ou simplesmente representa um ponto de transbordo.
As arestas do grafo representam os meios pelos quais trafegam os produtos pela rede,
sendo que cada aresta possui uma certa capacidade, limitando o fluxo de produtos
que transitam por ela. Há um custo associado a cada produto em cada aresta,
sendo o somatório desses custos a função objetivo a ser minimizada. As variáveis
de interesse representam o fluxo dos produtos pelos arcos da rede e pertencem ao
conjunto dos inteiros positivos.
Existem quatro restrições de interesse: restrição de conservação de fluxo, a qual é
responsável pelo gerenciamento do fluxo dos produtos pelos nós da rede, conseqüentemente pelos arcos; restrição de capacidade, segundo a qual o fluxo dos produtos
em cada arco não deve exceder sua capacidade; restrição de integralidade, proibindo
o fracionamento dos produtos em partes não-inteiras; e, por fim, a restrição de
positividade, sendo o fluxo mínimo representado pelo fluxo nulo.
Em suma, o problema fica caracterizado pela determinação do fluxo dos produtos
pelos arcos da rede, mediante um conjunto de restrições, visando a obtenção de um
custo mínimo. Este problema pode ser modelado como uma problema de otimização
linear, considerando a matriz de incidência da rede pela formulação nó-arco ou pela
formulação arco-rota.
1.4
Objetivos
Este trabalho tem como objetivo geral realizar um estudo sobre métodos de
otimização combinatorial para resolver problemas de fluxo multiproduto inteiro.
Especificamente, é feita uma análise do comportamento de algumas técnicas
heurísticas aplicadas à resolução de um PFMI, juntamente a um espaço solução
provindo das restrições do problema. Em particular, são objetos de estudo as
1.6
Proposta de desenvolvimento
4
seguintes metaheurísticas: ILS, Simulated Annealing e Algoritmo Genético. As
duas primeiras são representantes de heurísticas que fazem uso da busca local. A
última, uma heurística bio-inspirada, que faz uso de busca populacional. Espera-se
determinar uma solução sub-ótima para o problema em tempo aceitável para o caso
das heurísticas locais, e propor um modelo matemático computacional bem definido,
no caso da heurística populacional.
Como trata-se de um problema de otimização combinatorial (POC), é interessante ressaltar esforços quanto a um possível pré-condicionamento aplicado a
ele. Isso leva a uma meta abordada neste trabalho, o que se pode chamar de uma
tentativa de pré-otimização motivada pela formulação matemática do problema. Tal
procedimento visa diminuir o espaço de busca de soluções do problema abordado.
1.5
Proposta de desenvolvimento
Para a realização dos testes computacionais referentes aos procedimentos heurísticos, foram utilizadas instâncias produzidas por um gerador aleatório (GenMCF),
desenvolvido por Alvelos (2005). Os resultados computacionais são comparados entre si, visando determinar o melhor procedimento quanto a resolução do problema
em tela. A formulação matemática sofre uma relaxação, de modo a agregar a restrição de conservação de fluxo. O problema é resolvido na totalidade pelos métodos
heurísticos propostos, de modo que a preocupação com a solução inicial está inserida
no espaço solução adotado, proveniente das restrições do problema.
Além da utilização das metaheurísticas para resolver o PFM, é proposto um
conceito de pré-otimização aplicada ao problema, no caso de haver bijeção entre
o conjunto de origens e destinos de cada produto, tendo como base a resolução
de sistemas lineares homogêneos, advindos das restrições inerentes ao problema. A
justificativa para a abordagem deste conceito está na dimensão do problema tratado,
o que torna interessante a tentativa de redução desta dimensão, a fim de otimizar
previamente o processo de resolução adotado.
Uma última proposta, não cronologicamente apresentada nesta seção, incide sobre a análise do espaço solução do PFM. O espaço em questão é construído a partir da
restrição de capacidade, possibilitando a não-violação dos arcos. Como na literatura
não se encontra algo muito detalhado a respeito da dimensão deste espaço analisado,
espera-se contribuir com informações relevantes para futuros pesquisadores deste
tema.
1.6
Organização do trabalho
Este trabalho está organizado da seguinte maneira: no capítulo 2, é apresentada uma revisão bibliográfica a respeito dos problemas multiproduto, bem como a
natureza de suas formulações e suas aplicabilidades.
No capítulo 3, é apresentado o modelamento do problema, tanto a modelagem
matemática como a modelagem computacional. Na modelagem matemática, são
detalhadas as estruturas algébricas presentes, assim como as variáveis envolvidas e
o dimensionamento do problema. Já na modelagem computacional, vale ressaltar a
conversão de estruturas presentes na formulação do PFMI, em virtude da aplicação
1.6
Organização do trabalho
5
das técnicas heurísticas. Ainda neste capítulo, o problema é modelado segundo uma
visão evolutiva, para futuramente prover a aplicação do algoritmo genético.
No capítulo 4, é apresentado um conceito de pré-condicionamento aplicado a
um PFMI, baseado na resolução iterada de sistemas lineares homeogêneos, tendo
resultados dependentes da densidade da rede utilizada. No capítulo 5, é analisado o
espaço solução das heurísticas computacionais aqui utilizadas, a fim de obter informações sobre o comportamento das mesmas quanto a sua eficiência na resolução do
problema. No capítulo 6, é apresentada a aplicação das heurísticas ILS e Simulated
Annealing ao PFMI, assim como os resultados obtidos. Por fim, no capítulo 7, são
discutidas as conclusões gerais do trabalho, além de serem apresentadas propostas
de perspectivas de trabalhos futuros.
Capítulo 2
Problemas de Fluxo Multiproduto
2.1
Introdução
Os problemas de fluxo multiproduto foram propostos inicialmente no início da
década de 60, através dos trabalhos de Ford e Fulkerson (1962) e de (Hu, 1963). Em
geral, envolvem um grande número de variáveis e restrições, além de possuírem uma
extensa variedade de aplicações, incluindo:
• Seqüenciamento de carga (Shan, 1985);
• Roteamento de mensagens em redes de comunicação (Hu, 1969; Naniwada,
1969);
• Roteamento/seqüenciamento de suprimentos militares (Kennington e Helgason, 1980; Schultz e Meyer, 1991; Staniec, 1987);
• Localização de depósitos (Geoffrion e Graves, 1974);
• Planejamento de sistemas de tráfego urbano (Bradley, 1965; Potts e Oliver,
1972);
• Planejamento de produção de bens de consumo (Hax e Candea, 1984);
• Seqüenciamento de operações em refinarias de petróleo (Lasdon, 1970);
• Alocação de estudantes em escolas por composição étnica (Clark e Surkis,
1968).
A maior parte das aplicações está concentrada nas áreas de telecomunicação e
de transporte.
Os problemas de fluxo, segundo Goldbarg e Luna (2005), abordam o processo
de otimização de distribuição de produtos originados em pontos de ofertas e consumidos em pontos de demanda, dentro de uma rede de interligações possíveis, as
quais podem possuir restrições de capacidade de tráfego e custos variados. Esses
elementos, presentes numa rede, podem gerar uma enorme quantidade de variáveis
e de restrições, tornando inviável a utilização de programação matemática genérica
para resolver o problema.
6
2.2
Definição do problema
7
Neste capítulo é apresentada uma definição do problema de fluxo multiproduto.
Em seguida, é feita uma abordagem às formulações matemáticas, considerando a
natureza da matriz que gere o fluxo da rede. Depois disso, é apresentada uma visão
geral sobre o caso envolvendo variáveis inteiras, ao qual este trabalho se dedica.
2.2
Definição do problema
Seja R = (N , A, F) uma rede representada por um grafo G = (N , A), pelo qual
passa um fluxo F = {f1 , f2 , . . . , f|A| } por suas |A| arestas, as quais interligam seus
|N | nós, e seja P um conjunto de produtos inseridos em R. Alguns elementos do
conjunto N são denominados de nó fonte e outros são denominados de nó sumidouro, representando, respectivamente, pontos de oferta e pontos de demanda para
os produtos envolvidos na rede. O processo de distribuição dos produtos não é realizado diretamente de um ponto de oferta a um ponto de demanda, e isso faz com
que os demais elementos de N sejam também utilizados como pontos de passagem.
Existe um custo associado à passagem de cada produto em cada aresta, além de se
ter uma limitação quanto à capacidade das mesmas. O problema de fluxo multiproduto (PFM) é caracterizado quando vários produtos compartilham os arcos de R e
competem por suas capacidades, sendo o objetivo determinar F, de maneira que o
custo seja o menor possível.
Na Figura 2.1, é apresentada uma rede de fluxo multiproduto, na qual 3 tipos de
produtos (PA , PB , PC ), utilizando 6 unidades de cada tipo, devem ser distribuídos
pela rede, saindo de seus respectivos nós-origens e chegando em seus nós-destinos.
Cada aresta apresenta uma certa capacidade, limitando o fluxo dos produtos que
transitam por ela, além de um custo associado, neste caso, independente do produto.
Figura 2.1: Exemplo de rede de fluxo multiproduto.
2.2
Definição do problema
8
Essa classe de problemas é modelada através de um grafo e pode ser representada
por um modelo de otimização linear. Seja G = (N , A) um grafo direcionado representando uma rede de fluxo e P um conjunto de produtos inseridos nessa rede. O
modelo de programação linear objetivando um custo mínimo é apresentado abaixo:
min
X X
k∈P
suj. a
X
ckij xkij
(2.1a)
i,j∈A
xkij ≤ uij , ∀ (i, j) ∈ A
(2.1b)
k∈P





B 0 ··· 0
0 B ··· 0
.. .. . .
.
. ..
. .
0 0 ··· B





x1
x2
..
.
x|P|


 
 
=
 
xkij ≥ 0, ∀(i, j) ∈ A, ∀k ∈ P.
b1
b2
..
.
b|P|



,

(2.1c)
(2.1d)
sendo:
ckij = custo do transporte do produto k pelo arco (i, j);
xkij = fluxo do produto k no arco (i, j);
xk = vetor coluna representando o fluxo do produto k em cada arco da rede;
uij = capacidade do arco (i, j);
B = matriz de incidência nó-arco;
bk = vetor de oferta/demanda do produto k.
Há duas importantes restrições neste problema, no que se refere à capacidade dos
arcos da rede e à conservação do fluxo envolvendo os produtos. A restrição (2.1b)
é denominada restrição de aglutinação ou simplesmente de capacidade. Por ela, é
garantido que o fluxo dos produtos que trafegam pelos arcos da rede não ultrapassa
a capacidade dos mesmos. Essa limitação costuma ser representada por um número
real ou por um intervalo. Neste último caso, é necessário que o fluxo seja maior que
um limite mínimo e menor que um limite máximo. Em situações que não existam
essa limitação, dizemos que o arco possui capacidade infinita.
A restrição (2.1c) diz respeito à conservação de fluxo. A matriz B é responsável
pela regra de comunicação entres os pontos da rede, lhe conferindo a gerência sobre o
tráfego dos produtos. Essa matriz pode ser construída utilizando-se de duas relações:
nó-arco ou arco-rota. Ambas são detalhadas na seção 2.3. Os elementos da matriz
pertencem ao conjunto {−1, 0, 1}. Logo, se (i, j) = 1, então a atribuição de i
pertence à atribuição de j, assumindo um papel de fonte; caso (i, j) = −1, então a
atribuição de i pertence à atribuição de j, assumindo um papel de sumidouro; e
se (i, j) = 0, então a atribuição de i não pertence à atribuição de j.
Além disso, a matriz de incidência B nessa formulação apresenta a propriedade
de unimodularidade total. Isto quer dizer que o determinante de qualquer submatriz
quadrada da matriz original pertence ao conjunto {−1, 0, 1}. Mesmo adicionando
2.3
Formulações
9
variáveis de folgas ou artificiais e sendo o conjunto de oferta/demanda composto
por valores inteiros, a matriz preserva a unimodularidade total, garantindo solução
inteira nos vértices do poliedro convexo gerado pelas restrições. Uma demonstração
dessa propriedade pode ser vista em Bazaraa et al. (1990).
O vetor bk indica o fluxo gerado nos nós, em relação ao produto k, ou seja,
identifica o nó como ponto de oferta, demanda ou transbordo, de modo que cada
elemento i ∈ bk , i = 1, . . . , |N |, seja dado por:
 k
 bi > 0, se o nó i é um nó de fornecimento do produto k;
k
bk < 0, se o nó i é um nó de demanda para o produto k;
bi =
 ki
bi = 0, se o nó i é um nó de transbordo em relação ao produto k.
2.3
Formulações do Problema de Fluxo Multiproduto
Existem, basicamente, dois tipos de formulações para o PFM: a formulação nóarco e a formulação arco-rota. São diferenciadas quanto à identificação ou representação do fluxo da rede. Isso se reflete sobre a matriz de incidência de cada
formulação, ambas apresentando vantagens e desvantagens quanto à sua utilização.
Na identificação do fluxo pelo par nó-arco, não é necessária a determinação prévia
de rotas. Porém, sua modelagem é mais complexa. Por outro lado, na formulação
arco-rota, apesar de apresentar uma menor quantidade de restrições, é necessário
um conjunto pré-definido de caminhos. Isso pode levar a uma divergência em relação
à solução ótima (ou sub-ótima) do problema original, uma vez que rotas ótimas (ou
sub-ótimas) podem estar fora do conjunto de caminhos escolhidos. Para o problema
tratado neste trabalho, é adotada a formulação nó-arco.
2.3.1
Formulação nó-arco
A formulação mostrada em (2.1) é um exemplo de formulação guiada por nó-arco.
Considere a rede apresentada pela Figura 2.2. Nesta rede, o ponto 1 representa um
nó de transbordo, os pontos 3 e 4 representam nós de oferta e o ponto 2 um nó
de demanda. São produzidas 2 unidades do produto P1 no nó 3 e 3 unidades do
produto P2 no nó 4, todas com destino ao nó 2. Em cada arco há uma representação
do tipo [arco, capacidade, custo]. Neste exemplo, o custo não varia com o produto
e, sim, com o arco. Em algumas instâncias utilizadas neste trabalho, o custo varia
em função do produto e do arco. A matriz de incidência nó-arco para este exemplo
de rede é dada por:


1
1
0
0 −1
0
 −1
0
1
0
0 −1 

B=
 0 −1 −1
1
0
0 
0
0
0 −1
1
1
As regras de conservação de fluxo da rede estão subentendidas nessa matriz,
como o fato do primeiro nó (primeira linha da matriz) gerar fluxo de saída pelos
arcos 1 e 2 (colunas 1 e 2 da matriz) e captar fluxo do arco 5 (coluna 5 da matriz). A
Formulações
10
1
[1, 3, 2]
]
,3
,3
[5
2
P2
[6
,4
,8
]
[3, 4, 5]
P1
2
[4, 5, 7]
2.3
3
P1
[2, 5, 4]
4
P2
Figura 2.2: Rede de fluxo multiproduto.
dimensão da matriz de incidência é dada por |N |×|A|, ou seja, cada linha representa
um nó e cada coluna um arco.
O vetor de capacidade é representado pelo vetor u e os vetores de oferta/demanda
por b1 e b2 . A dimensão do vetor de capacidade u é dada por |A| × 1, sendo que
cada linha representa a capacidade de um arco. A dimensão de cada vetor de
oferta/demanda referente a um determinado produto é equivalente à |N | × 1, de
modo que cada linha representa um nó, na forma:
 
3




 5 
0
0
 

 4 



 , b1 =  −2  , b2 =  −3 
u=
 5 
 0 
 2 
 
 3 
3
0
4
A formulação nó-arco ainda pode ser subdividida quanto à identificação dos
produtos na rede. Em Jones et al. (1992), é apresentada uma aplicação do método
de decomposição de Dantzig-Wolfe a três formulações nó-arco de um PFM:
• Origem-Destino Específico: os produtos são identificados pelos seus índices e
pelos pares origem-destino;
• Destino Específico: a identificação do produto é feita pelo seu índice e ele pode
partir de qualquer nó-origem, porém, seu destino é especificado;
• Produto Específico: cada produto é identificado pelo seu índice e pode ser
transmitido de qualquer nó-origem a qualquer nó-destino.
No capítulo 4 é utilizada a formulação do tipo Origem-Destino Específico. Cada
produto sai de um determinado nó, denominado de nó-origem, e deve se deslocar até
chegar a um nó-destino. Para cada produto, identificado pelo par origem-destino,
2.3
Formulações
11
a quantidade que sai do nó-origem deve ser necessariamente igual à quantidade
que chega ao nó-destino. Já no capítulo 6 é utilizada uma forma mais restrita da
formulação Produto Específico. Neste tipo de formulação, os produtos saem de um
nó-origem especificado e podem se deslocar a mais de um nó-destino, caso haja
necessidade. Isso se deve à relaxação sobre uma das restrições do problema.
Segundo Rardin e Wolsey (1993), a relaxação na formulação origem-destino costuma tornar o problema mais fácil de ser resolvido, apesar de apresentar maior
número de variáveis e restrições.
Em geral, a escolha de como definir a identificação do produto depende da análise
do conjunto de restrições e do método empregado para resolver o problema.
2.3.2
Formulação arco-rota
Existem vários trabalhos publicados utilizando-se dessa formulação, sobretudo
envolvendo PFM (Problema de fluxo multiproduto), como em Barnhart et al. (1995),
e Farvolden et al. (1993) e PFMI (Problema de fluxo multiproduto inteiro), presente
em Barnhart et al. (1996). Em Rardin e Choe (1979), é apresentada uma comparação
entre as formulações nó-arco e arco-rota para um problema de fluxo multiproduto
capacitado. Mostra-se que, relaxando o problema, nenhuma formulação se sobressai
em relação à outra. Porém, no caso de não haver capacidades nos arcos, a formulação
baseada nas rotas demonstra ser menos eficiente do que a formulação baseada nos
arcos.
Nesta formulação, é necessário definir um conjunto de caminhos ou rotas para o
atendimento dos serviços. Um exemplo de formulação arco-rota pode ser vista em
Mccallum (1977), aplicada a um problema de rede de comunicação, o qual é exibido
a seguir:
X X
min
ckr xkr
(2.2a)
suj. a
k∈P
r∈R(k)
X
X
k∈P
X
arij xkr ≤ uij , ∀ i, j ∈ A,
(2.2b)
r∈R(k)
xkr = dk , ∀k ∈ P,
(2.2c)
r∈R(k)
xkr ≥ 0, ∀r ∈ R(k), ∀k ∈ P.
sendo:
ckr = soma dos custos de tráfego do produto k pela rota r;
xkr = quantidade do produto k que passa pela rota r;
uij = capacidade do arco (i, j);
R(k) = conjunto de caminhos ou rotas para o produto k;
arij = elemento da matriz de incidência arco-rota, de modo que:
1, se o arco (i, j) está contido na rota r ∈ R(k);
r
aij =
0, se o arco (i, j) não está contido na rota r ∈ R(k).
(2.2d)
2.4
Problema multiproduto inteiro
12
dk = demanda do produto k que deve ser transportada de um nó-origem a um
nó-destino especificado.
A restrição (2.2b) corresponde à restrição de aglutinação, ou seja, o fluxo de
todos os produtos nas rotas que fazem uso do arco (i, j) é limitado pela capacidade
do mesmo. A restrição (2.2c) é responsável pela distribuição dos produtos, conforme
suas demandas.
A matriz de incidência para o caso da formulação arco-rota, tendo dimensão
|A| × |R|, é composta por elementos do conjunto {0, 1}, sendo 1 se um determinado
arco pertence a uma determinada rota especificada, e 0 se o arco em questão não
pertence à rota associada. Em termos de estruturas algébricas, a matriz de incidência
é a principal diferença entre as formulações nó-arco e arco-rota. No caso do exemplo
apresentado na Figura 2.2, a matriz de incidência do tipo arco-rota é formada a
partir da definição do conjunto de rotas R = {r1 , r2 , r3 }, correspondendo ao conjunto
formado por três rotas pré-estabelecidas, para ri = {(k, l)}, representando a rota
i, composta pelo arco formado pelos nós k e l. Assim, r1 = {(1, 2); (2, 3)}, r2 =
{(3, 4); (4, 1); (1, 2)} e r3 = {(4, 2)}. A matriz de incidência é, então, dada por:


1 1 0
 0 0 0 


 1 0 0 

B=
 0 1 0 


 0 1 0 
0 0 1
Existem outros tipos de formulações, como a baseada em cortes, empregadas em
problemas de fluxo sem custo. Para esses problemas, alguns autores usam modelos
baseados em cortes junto a algoritmos de plano de corte. Em Grötschel et al. (1995),
são tratados problemas que levam a essa formulação. Outras formulações são citadas
em Gendron et al. (1998).
2.4
Problema multiproduto inteiro
No problema de fluxo multiproduto inteiro (PFMI), o fluxo de cada produto
pode ser distribuído por diferentes caminhos. Porém, a quantidade desses produtos
em cada arco deve ser um valor inteiro. As demais características são comuns às
citadas anteriormente para um PFM guiado por uma formulação do tipo nó-arco ou
arco-rota.
Não diferente do caso geral, o caso inteiro também apresenta várias aplicações,
incluindo:
• Problema de designação de comprimentos de ondas (Ozdaglar e Bertsekas,
2003);
• Problema de alocação de equipes de enfermeiros (Moz e Pato, 2003);
• Problema de roteamento de aviões (Verweij et al., 1997).
2.5
Problema multiproduto inteiro
13
Essa classe de problemas é tratada no presente trabalho e sua formulação matemática é semelhante à expressão (2.1), porém, agregando a condição de integralidade. Existem variações do PFMI, como é o caso do modelo binário, conforme a
formulação a seguir:
X X
min
ckij dk xkij
(2.3a)
k∈P
suj. a
(i,j)∈A
X
dk xkij ≤ uij
(2.3b)
∀(i, j) ∈ A,
k∈P
X
xkij −
(i,j)∈A
xkij
X
xkij = bki ,
∀k ∈ P, ∀i, j ∈ N ,
(2.3c)
(j,i)∈A
∈ {0, 1},
∀(i, j) ∈ A, ∀k ∈ P.
(2.3d)
sendo:
ckij = custo do produto k no arco (i, j);
1, se o fluxo do produto k faz uso do arco (i, j);
k
xij =
0, caso contrário.
uij = capacidade do arco (i, j);
dk = demanda do produto k;

 1, se o nó i é um nó de fornecimento;
k
0, se o nó i é um nó de transbordo;
bi =

−1, se o nó i é um nó de demanda.
Em Barnhart et al. (2000), o PFMI foi modelado utilizando-se o modelo de
otimização linear apresentado na expressão (2.3), nas formulações guiadas por nóarco e arco-rota. No problema binário, cada produto deve fazer uso de um único
caminho.
Na literatura, encontram-se vários métodos para solucionar um problema de
programação linear inteira. Devido à particularidade desses problemas, em geral,
pertencerem à classe NP-difícil, alguns métodos se tornam ineficientes na tentativa
de solucioná-los, como é o caso da aplicação do método simplex, o qual requer uma
grande quantidade de memória, além de despender muito tempo de execução. No
próximo capítulo, são abordadas algumas técnicas aplicadas ao problema de fluxo
multiproduto.
Na formulação do problema tratado neste trabalho, algumas estruturas algébricas
sofrem alterações, a fim de favorecer a aplicação das heurísticas utilizadas para
solucionar o problema. Uma análise sobre essas estruturas e as variáveis envolvidas
no modelo são detalhadas no capítulo 3, além do modelamento do problema segundo
perspectivas de uma heurística populacional, em específico, o Algoritmo Genético.
A restrição de conservação de fluxo e a condição de integralidade presentes na
formulação do PFMI contribuem para a técnica de pré-otimização e análise do espaço
solução descritas respectivamente nos capítulos 4 e 5. Uma aplicação das heurísticas
ILS e Simulated Annealing, bem como a análise de seus comportamentos para a
solução do PFMI de acordo com a formulação proposta, é mostrada no capítulo 6.
2.5
2.5
Conclusão
14
Conclusão
O problema foi modelado por um grafo representando uma rede, pela qual
trafegam vários produtos, os quais devem sair de um ponto origem (ou conjunto
de pontos) e chegar a um ponto destino (ou conjunto de pontos). Os meios por onde
transitam esses produtos podem apresentar uma certa limitação quanto ao fluxo
dos mesmos. A formulação matemática do problema pode ser do tipo nó-arco ou
arco-rota, além de poder ser caracterizada quanto a identificação dos produtos na
rede.
Foi feita uma abordagem a problemas de fluxo multiproduto inteiro, classe de
problemas tratada neste trabalho, e apresentado um modelo de otimização linear.
Modelos não-lineares não foram apresentados especificamente, porém, existe uma
grande aplicação e trabalhos publicados em torno desse tipo de modelo envolvendo
problemas de fluxo multiproduto.
Capítulo 3
Modelagem do Problema
3.1
Introdução
Neste capítulo é apresentada a modelagem matemática e computacional utilizada
neste trabalho, no intuito de resolver o Problema de Fluxo Multiproduto Inteiro
(PFMI) abordado. Na seção 3.2 são detalhadas as estruturas algébricas presentes
na formulação matemática do problema, bem como suas restrições e função objetivo
de minimização. Na seção 3.3, são exibidas as estruturas de dados utilizadas para
a implementação computacional das heurísticas e o algoritmo de pré-otimização.
Finalizando, na seção 3.4, é abordada a modelagem matemática computacional segundo o algoritmo genético, descrevendo a representação de soluções e operadores
genéticos envolvidos.
3.2
Modelagem matemática
Considere um grafo G = (N , A) direcionado, com |N | nós, |A| arcos e seja P um
conjunto de produtos. O problema abordado neste trabalho fornece uma caracterização geral, possibilitando a aplicação a várias classes de problemas. O conjunto
N de nós representa pontos de oferta, demanda e transbordo de um determinado
produto. Esses produtos podem representar pacotes de dados de telecomunicação,
frotas de caminhões, conjunto de aeronaves ou navios, compostos químicos, suprimentos militares, dentre outros exemplos. Os elementos deste conjunto indicam os
pontos ou locais de saída de um determinado produto e de chegada do mesmo, além
dos pontos de transbordo, em que simplesmente os produtos trafegam, visando o
seu local de destino. O conjunto A de arcos pode representar rotas aéreas ou terrestres, seqüenciamento de procedimentos, dentre outros significados. No problema
em questão, o conjunto de arcos representa os meios pelos quais trafegam os produtos, sendo que, em cada arco, há um custo associado ao produto, além de apresentar
uma certa limitação quanto ao fluxo nas mesmas.
O PFMI de interesse neste capítulo é caracterizado pela expressão (3.1), mostrada
15
3.2
Modelagem matemática
16
a seguir:
min
suj. a
cx
Dx = b
X
xkl ≤ ul ,
(3.1a)
(3.1b)
(3.1c)
l∈A
k∈P
(3.1d)
x ∈ Z+
Observe que esta expressão é uma adaptação da expressão (2.1), de modo que:
c = parâmetro de custo;
xkl = fluxo do produto k no arco l;
x = variável de fluxo dos produtos pelos arcos, dada por:
 1
|P| 
x1 x21 . . . x1
 .
..
.. 
x =  ..
.
. 
|P|
1
2
x|A| x|A| . . . x|A|
de modo que cada coluna representa o fluxo do produto k nos arcos da rede G
e cada linha representa o fluxo dos produtos pelo arco l;
u = vetor de capacidade dos arcos, tal que u ∈ <|A| ;
D = matriz de incidência nó-arco;
b = matriz de oferta/demanda.
A expressão (3.1a) representa a minimização da função objetivo do problema,
associada aos custos dos |P| produtos atravessarem os |A| arcos da rede; a expressão
(3.1b) indica a restrição de conservação de fluxo; em (3.1c), está representada a restrição de capacidade dos arcos, e por fim, em (3.1d), a condição de não negatividade
e integralidade das variáveis. Note que, diferentemente da representação apresentada em (2.1), no presente caso adota-se a notação que o arco l ∈ A, em lugar de
representá-lo na forma (i, j) ∈ A.
A modelagem computacional dessa expressão é discutida em seqüência. A representação da variável de fluxo x é mostrada na Figura 3.1.
p1
p|P|
p2
···
a1
p1
p|P|
p2
···
a2
p1
···
p|P|
p2
···
a|A|
Figura 3.1: Representação dos vetores de custo e de fluxo.
Para esta modelagem, é utilizada uma transformação da estrutura matricial da
variável de fluxo x para uma estrutura vetorial, de modo que:
3.2
Modelagem matemática
17

x11
x21
..
.







x1







 x|P|
1


. . . .
..

1

x2 


2 


x
2

x2
..

. 




x=
 x|P|
2


......

..


.


......
 1 
 x|A| 
 2 

 x|A| 

x|A|
..


. 


|P| 
x|A|
































(3.2)
sendo xl o fluxo total através do arco l ∈ A.
Uma estrutura semelhante é adotada para o modelamento computacional do
parâmetro de custo c. Tanto o parâmetro de custo c como a variável de fluxo x
são compostos por |A| vetores, cada um deles de tamanho |P|. Cada posição desses
vetores está associada a um produto e a um arco, sendo que, no parâmetro de custo,
esta posição indica o custo de um dado produto em um dado arco, e, na variável de
fluxo, a posição representa a quantidade de um determinado produto em um dado
arco.
A matriz de incidência D segue a orientação do tipo nó-arco, ou seja, cada
linha representa um nó e cada coluna representa um arco. A matriz de incidência,
responsável pelo gerenciamento do fluxo pelos nós da rede, é dada por:


d11 · · · d1|A|


..
...
(3.3)
D =  ...

.
d|N |1 · · · d|N ||A|
Os elementos de D são constituídos pelos elementos do conjunto {−1, 0, 1}. Cada
elemento dij da matriz corresponde ao tipo de ligação que um nó tem a outro, ou
seja, se um dado nó pertence a um determinado arco. Cada linha i, i = 1, . . . , |N |,
representa, assim, um nó da rede G, enquanto que cada coluna j, j = 1, . . . , |A|,
representa um arco da mesma rede
A matriz de oferta/demanda, representada por b em (3.1b), indica quais são
os nós de oferta, de demanda ou de transbordo. Nesta matriz, cada coluna está
associada a um produto k; cada linha representa a oferta/demanda dos |P| produtos.
A representação computacional desta estrutura assemelha-se à mostrada na Figura
3.1 e na expressão (3.2). Porém, cada partição bm tem dimensão igual a |P|, e
existem |N | partições. Cada posição do vetor, no modelamento computacional,
refere-se à quantidade final de um determinado produto em um dado nó.
3.3
Modelagem computacional
18
A formulação inicial do problema (considerando a restrição de conservação de
fluxo) é do tipo ODE (origem-destino-específico), ou seja, cada produto possui um
único nó de origem e um único nó de destino. De acordo com esta formulação,
cada sub-vetor do vetor de oferta/demanda (representando um certo produto k)
tem apenas duas posições não-nulas. Estas posições, que devem ter o mesmo valor
absoluto, indicam os nós de origem e de destino do produto associado, sendo o valor
positivo designado para o nó de oferta e o valor negativo para o nó de demanda.
Dentre as estruturas apresentadas no modelamento matemático dado pela expressão (3.1), resta analisar o vetor de capacidade. Este vetor indica o fluxo máximo
permitido em cada arco. A representação dessa estrutura é exibida pela Figura 3.2,
na qual ul representa a capacidade máxima do arco l.
u1
u2
ul
···
u|A|
···
Figura 3.2: Representação do vetor de capacidade.
A utilização de matrizes como vetores, ou vice-versa, é totalmente flexível, pois a
transformação de uma estrutura para outra é bem simples. Isto torna o modelamento
matemático apresentado bem definido, segundo a Tabela 3.1.
Tabela 3.1: Tabela de dimensionamento de
Expressão Estruturas
Operações
função
- custo
c1×|A||P| x|A||P|×1
objetivo
- fluxo
conservação - matriz de incidência D|N |×|A| x|A|×|P|
de fluxo
- matriz de fluxo
- matriz de
b|N |×|P|
oferta/demanda
P k
restrição de - vetor de fluxo
xl , k ∈ P
capacidade
3.3
- vetor de capacidade
l∈A
ul , l ∈ A
operações.
Resultante
(cx)1×1
(Dx)|N |×|P| = b|N |×|P|
P
k∈P
xkl ≤ ul , l ∈ A
Modelagem computacional
Nesta seção, são apresentadas as estruturas utilizadas para o modelamento computacional do problema. É enfatizada a estrutura correspondente à variável de interesse, ou seja, o fluxo dos produtos pela rede. As demais estruturas matemáticas
são transformadas em listas, que seguem a configuração da variável de fluxo, porém,
com os campos e índices correspondentes à suas formulações matemáticas descritas
na seção anterior. A modelagem abordada nesta seção incide fortemente sobre os
capítulos 4 e 6. O detalhamento da modelagem para a utilização das heurísticas
3.3
Modelagem computacional
19
computacionais é abordado no capítulo 6, onde é apresentada a estruturação da
solução do problema. Para esta seção, é feita a análise da manipulação dos índices
da lista, referente às variável de interesse, sob o ponto de vista da não-utilização do
algoritmo de pré-otimização ou no caso de sua utilização.
Para a implementação computacional foi utilizada a estrutura de listas lineares.
Existem algumas vantagens e desvantagens na utilização das listas. A vantagem
é que se pode tratar todas as estruturas como se fossem vetores, sendo mais fácil
realizar as operações inerentes ao problema, como a multiplicação de valores contidos
nas listas. Por outro lado, a manipulação dos índices se torna mais difícil, pois não há
referência quanto à mudança de arco ou de produto tão óbvia quanto numa matriz,
sobretudo quando se utiliza o método de pré-otimização, em que há um grande fator
de aleatoriedade (o qual depende fortemente da instância utilizada) em relação ao
tamanho da lista. Por exemplo, se numa instância tem-se |A| arcos e |P| produtos,
não-utilizando a pré-otimização pode-se afirmar que a sub-lista que contém a linha
i (arco i) certamente terá tamanho igual a |P|. Já com o uso da pré-otimização, a
sub-lista que contém a linha i (arco i) terá tamanho ti , sendo 0 ≤ ti ≤ |P|.
A seguir, é apresentada a estrutura da variável de fluxo, assim como a manipulação de seus elementos, considerando o caso da aplicação do algoritmo de préotimização e o caso da não aplicação do mesmo.
3.3.1
Modelagem computacional sem uso da Pré-Otimização
Suponha que, numa determinada instância, tenha-se |A| arcos e |P| produtos. A
lista que representa o fluxo dos produtos pelos arcos da rede é formada por registros
compostos por três campos: linha, coluna e valor. O campo linha representa o
arco; o campo coluna representa o produto; e o campo valor representa o fluxo do
produto no arco associado.
O fluxo dos produtos é representado por uma lista linear de registros. A única
dificuldade em relação a essa estrutura está associada à manipulação sobre os índices,
ou seja, à tarefa de determinar registros a partir do arco ou do produto. Na Figura
3.3, é descrito o registro que compõe a lista de fluxo x.
Figura 3.3: Registro para variável de fluxo.
A lista de fluxo x é composta por vários registros, como descrito anteriormente.
Para o caso de não se usar a pré-otimização, o tamanho da lista é definido por:
T amanho_lista = (quantidade_de_arcos) ∗ (quantidade_de_produtos)
3.3
Modelagem computacional
20
Na Figura 3.4, é mostrado o diagrama da lista de fluxo x, no qual o campo vazio
representa o fluxo (a ser determinado) do produto no arco associado.
1
1
1
···
p
1
p
p+1
2
1
···
2p
2
p
···
(i-1)p
i-1
p
(i-1)p+1
i
1
···
ip
i
p
···
(a-1)p
a-1
p
(a-1)p+1
a
1
···
ap
a
p
Figura 3.4: Representação da lista de fluxo.
A motivação para o uso destas estruturas está nas movimentações e nas trocas
produzidas pelos passos das heurísticas, pois esses procedimentos atingem um único
índice associado a um registro. A seguir, é analisada a busca de registros por arco
ou por produto. A relevância dessas análises está nas operações necessárias para a
resolução do problema, como, por exemplo, a multiplicação da matriz de incidência
pela matriz (ou vetor) de fluxo, resultando na matriz (ou vetor) de oferta/demanda,
a essa altura todas essas estruturas transformadas em listas.
Obtendo registro a partir do arco
São necessários três parâmetros para obter a sub-lista que contém os registros
nos quais o arco está presente. São eles: o arco em questão; a lista de fluxo; e a
quantidade de produtos.
Para obter informações como o fluxo do produto no arco i, o índice do primeiro
registro da sub-lista a ser encontrada é dado por (linha − 1) ∗ |P| + 1, no qual linha
representa o arco a ser pesquisado e |P| a quantidade de produtos da instância. O
índice do último registro da sub-lista é dado por linha∗|P|. Pela construção da lista
de fluxo x, neste caso, o próximo elemento é obtido acrescentando-se uma unidade
no índice atual.
Obtendo registro a partir do produto
Desta análise, obtém-se as informações sobre o fluxo do produto em todos os
arcos. Os parâmetros são semelhantes ao primeiro caso, porém, a linha (que representa o arco) é substituída por coluna (arco), além de ser informada a quantidade
de arcos.
Observando-se a configuração da lista, percebe-se que o primeiro elemento da
sub-lista, ou seja, o índice do primeiro registro da sub-lista, é dado pelo produto
em questão (coluna), e o próximo elemento seria |P| + coluna, no qual |P| representa
a quantidade de produtos, e coluna representa o produto passado como argumento.
− 3.3
Modelagem computacional
1
1
1
···
1
t1
t1
i−1
i−1
P
ti
a−1
P
ti
t1 − 1
1
a−1
p
21
t1 + 1
i−1
P
ti + 1
a−1
P
ti + 1
1
1
1
2
1
···
i
1
···
a
1
···
t1 + t2
2
t2
···
···
i
P
ti
i
ti
a
P
ti
a
t|A|
1
1
Figura 3.5: Representação da lista de fluxo.
Generalizando, as posições a serem encontradas são (i − 1)|P| + coluna, com i =
1, . . . , |A|, para |A| a quantidade de arcos.
3.3.2
Modelagem computacional com o uso da Pré-Otimização
O procedimento de pré-otimização (vide capítulo 4) oferece bons resultados na
determinação prévia de soluções de um PFMI, dependendo, no entanto, da densidade
da rede utilizada.
A configuração da lista de fluxo difere-se da configuração da lista sem o uso
da pré-otimização, no que diz respeito ao tamanho das sub-listas. Enquanto no
primeiro caso o tamanho é o mesmo, aqui isso não ocorre, em virtude da eliminação
de algumas variáveis inerentes ao procedimento da pré-otimização.
Seja ti o tamanho da sub-lista associada ao arco i, ou seja, a quantidade de
produtos no arco i. Na Figura 3.5 é mostrado o diagrama da lista de fluxo x,
no qual o campo vazio representa o fluxo a ser determinado do produto no arco
associado. A lista completa apresenta tamanho igual a
T amanho_lista =
|A|
X
ti
i=1
A análise para obtenção dos registros que compõem as sub-listas procuradas é
feita de maneira análoga à análise do procedimento sem uso da pré-otimização. Um
devido cuidado deve ser tomado nessa etapa, qual seja, a ausência de elementos
associados em virtude da eliminação de variáveis produzidas pelo método. Como a
lista é linear, essa preocupação se reflete na busca por produto, já que a busca por
arco também é linear, em virtude da construção da lista. A seguir é feita a busca
de registro por arco.
Obtendo registro a partir do arco
Pela configuração da lista, o índice do primeiro registro que compõe a sub-lista
i−1
P
tj + 1. Como a busca neste
procurada, dado um arco i, é obtido pela expressão
j=1
3.4
Modelagem matemática computacional de AG para PFMI
caso é linear, o índice do último registro é dado por
i
P
22
tj . Na construção do al-
j=1
goritmo, é necessário mais um parâmetro em relação ao tamanho das sub-listas
que foram otimizadas, ou seja, que sofreram alterações devido ao procedimento de
pré-otimização. Esse parâmetro reflete sobre a variável t.
Obtendo registro a partir do produto
A única preocupação aqui refere-se à existência do registro. Para isso, basta
verificar se a variável responsável pelo tamanho da sub-lista é não nula. Novamente,
analisando a configuração da lista de fluxo, pode-se construir o algoritmo, no qual
estarão embutidas as informações necessárias para obtenção dos registros envolvidos.
j−1
P
ti + coluna, para j o primeiro índice, sendo
O início da sub-lista é dado por
i=1
ti > 0. O próximo termo será
j
P
ti , caso tj+1 > 0.
i=1
As análises descritas anteriormente podem ser melhor entendidas de posse dos
algoritmos implementados em linguagem C, apresentados no Anexo B. O modelamento matemático e computacional apresentado, em específico para metodologias
heurísticas de busca local, é descrito em Silva e Souza (2007c).
3.4
Modelagem matemática computacional de algoritmo genético para PFMI
Esta seção se dedica à modelagem do problema de fluxo multiproduto inteiro
utilizando algoritmo genético (AG). Na sub-seção 3.4.1 é feita uma introdução a
algoritmos genéticos. Na sub-seção 3.4.2 são relatados trabalhos científicos abordando problemas de fluxo multiproduto (PFM). Nas sub-seções 3.4.3, 3.4.4 e 3.4.5,
são descritas as representações de soluções e a função de avaliação utilizada. Na
sub-seção 3.4.6, é descrita a aplicação do AG ao PFM, apresentando os operadores
evolutivos propostos. A modelagem descrita a seguir está conforme a apresentada
em Silva e Souza (2007b).
3.4.1
Algoritmo Genético
As primeiras pesquisas em simulações computacionais de sistemas genéticos
foram efetuadas por Holland (1975), representando o ponto inicial para desenvolvimento dos atualmente denominados Algoritmos Genéticos (AGs). A partir
da década de 80, os AGs começaram a ser utilizados para solucionar problemas de
otimização, motivado sobretudo pelo trabalho de Goldberg (1989).
O AG mantém uma população (soluções) que, durante cada geração, passa a ser
qualificada por sua efetividade como solução predominante, e uma nova população
candidata é formada por operadores genéticos como o operador de reprodução (seleção), o operador de cruzamento (recombinação) e o operador de mutação. Um fato
importante para a eficácia do método incide sobre a escolha dos operadores de cruzamento e mutação, já que, segundo Carrano et al. (2004), para determinados tipos
3.4
Revisão bibliográfica da aplicação de AG à solução de PFM
23
de problemas, os operadores tradicionais se mostram completamente ineficientes.
Os Algoritmos Genéticos reproduzem um modelo simplificado de evolução das
espécies através de iterações. Partindo de uma população inicial, é associado, a
cada indivíduo desta população, um valor de aptidão, que determina o quanto um
indivíduo está adaptado ao ambiente em que vive, determinando suas chances de sobrevivência. Após um processo de seleção, os indivíduos escolhidos para permanecer
na população são, então, recombinados, através de cruzamentos (ou recombinações)
e mutações. A partir daí, o processo se repete, sendo que, a cada iteração, deseja-se
obter um melhor valor de aptidão médio para a população. O pseudocódigo de um
AG básico é descrito na Figura 3.6.
procedimento AG
1) t ← 0;
2) Gere a população inicial P (t);
3) Avalie P (t);
4) enquanto (os critérios de parada não estiverem satisfeitos) faça
5)
t ← t + 1;
6)
Gere P (t) a partir de P (t − 1);
7)
Avalie P (t);
8)
Defina a população sobrevivente;
9) fim-enquanto;
fim AG
Figura 3.6: Pseudocódigo do Algoritmo Genético.
Na operação de recombinação, os genes de dois pais são combinados de forma
a gerar filhos, sendo que, em cada filho, há um conjunto de genes de cada um dos
pais. A operação de mutação altera aleatoriamente uma parte dos genes de cada
indivíduo-pai.
A escolha dos parâmetros de um AG tem um impacto direto sobre o desempenho
do mesmo. Os parâmetros são:
• Tamanho da população inicial (nind);
• Probabilidade de cruzamento (pc );
• Probabilidade de mutação (pm ).
A probabilidade de cruzamento é realizada normalmente por um fator mais elevado, em torno de 80%; já a probabilidade de mutação possui, normalmente, um
fator mais baixo, em geral de 1 a 2%.
3.4.2
Uma revisão bibliográfica da aplicação de algoritmos
genéticos à solução de PFM
Nesta sub-seção, são discutidos trabalhos que fizeram uso de algoritmos genéticos
para a solução de Problemas de Fluxo Multiproduto.
3.4
Representação de uma solução
24
Em Pioró e Gajowniczek (1997), é utilizado o método Simulated Allocation em
problemas de fluxo multiproduto inteiro capacitado e não-capacitado. Os testes incidem em um problema da mochila múltipla e em uma rede de telecomunicação.
Um algoritmo genético é comparado à heurística estocástica. A conclusão apresentada mostra que, apesar de não superar os resultados do Simulated Allocation, o
algoritmo genético proposto produz soluções bem próximas e de boa qualidade, em
um tempo computacional razoável.
Gorman (1998) aborda um problema de fluxo de demanda referente ao sistema
ferroviário americano. Um algoritmo genético é usado para encontrar soluções factíveis e, em conjunto com a metaheurística Busca Tabu, é aplicado para resolver o
problema. Os resultados mostram uma economia de custo na rede ferroviária em
torno de 4% e uma redução de 6% em relação ao tempo de serviço despendido.
Em Erickson et al. (2002) é descrito um problema de otimização de roteamento
do tráfego na internet, dado um conjunto de demandas (pacotes de dados), com o
objetivo de minimizar o congestionamento na rede. É apresentado um algoritmo
genético para resolver o problema, sendo os resultados comparados àqueles mais
conhecidos obtidos por heurísticas desenvolvidas especificamente para este tipo de
problema. O algoritmo proposto, de acordo com Erickson et al. (2002), foi capaz
de produzir soluções de boa qualidade para a maioria das instâncias. Os autores
propõem, além disso, a introdução de mecanismo de hibridismo heurístico com uma
busca local, como feito em Moscato (2001).
Em Przewozniczek e Walkowiak (2005) é apresentado um algoritmo evolucionário
aplicado ao problema de congestionamento em redes orientadas a conexão. O fluxo
de rede é modelado como um problema de fluxo multiproduto não-bifurcado. O
algoritmo genético proposto consiste em dois níveis, sendo o primeiro nível baseado
nos operadores típicos, como crossover e mutação e, o segundo, baseado na idéia
hierárquica do algoritmo.
Sheng et al. (2006) propõem um algoritmo genético para resolver um problema
de transporte. O ponto de corte do operador de cruzamento (crossover ) e o pivot
randômico do operador de mutação são desenvolvidos para uma evolução eficiente.
O algoritmo proposto produz soluções de melhor qualidade, segundo os autores, que
os algoritmos genéticos baseados na matriz de códigos (Michalewicz et al., 1991)
Em Alminana et al. (2007) é apresentado um novo problema de fluxo multiproduto, baseado na incerteza das informações de fluxo quanto a origem e ao destino
dos produtos envolvidos. O modelo determinístico equivalente foi proposto para um
problema estocástico de dois estágios. Foi utilizado um algoritmo híbrido, baseado
na geração de colunas e algoritmo genético, para determinação do roteamento dos
protocolos da rede. Os resultados mostram que, para instâncias de larga escala,
somente o algoritmo proposto foi capaz de gerar soluções quando comparado ao
método exato. Em outros casos, as soluções obtidas equivaleram às soluções ótimas.
3.4.3
Representação de uma solução
Nos Algoritmos Genéticos, cada cromossomo, ou seja, cada indivíduo da população, está associado a uma solução do problema. Cada gene corresponde a um
componente da solução. Na sub-seção 3.4.6, é discutido o mecanismo de reprodução
baseado em processos evolutivos, sendo aplicado sobre a populção, com o intuito de
3.4
Representação de uma solução
25
explorar o espaço de busca e encontrar soluções para o PFM.
A estrutura de uma solução sji , a qual compõe o conjunto denominado de população, é semelhante à apresentada pela Figura 3.1. Uma população é um conjunto
de soluções, ou cromossomos.
Uma população inicial de tamanho n, ou dita população no tempo 0, é representada pelo conjunto {s01 , s02 , . . . , s0n }. Na Figura 3.7 é exibida a matriz populacional
D com n indivíduos, na qual cada linha representa uma solução sji associada a um
cromossomo, e cada vetor de fluxo associado a um dado arco representa um gene.
Figura 3.7: Matriz populacional.
3.4.4
População inicial
A população inicial é gerada de forma aleatória, porém, atendendo à restrição
de capacidade, representada pela expressão (3.1c). Deste modo, a solução inicial
comporta-se exatamente como as soluções obtidas em Silva e Souza (2007g) e Silva
e Souza (2007f). A restrição (3.1b), que representa a conservação de fluxo, sofre uma
relaxação, de modo que a condição de igualdade é substituída pela condição de desigualdade, na forma de menor ou igual. Isso permite que se obtenha a factibilidade
em relação ao fluxo pelos arcos, diminuindo-se os pontos de oferta do problema e
tendendo à uma bijeção entre os pontos de oferta e de demanda de produtos.
Na abordagem clássica de AG, é usual a geração da população inicial de modo puramente aleatório. Porém, utilizando-se este procedimento para problemas combinatoriais como o abordado nesta dissertação, pode-se gerar uma população composta,
quase em sua totalidade, por soluções infactíveis, pois há uma grande probabilidade
das soluções produzidas violarem a capacidade dos arcos, além de não constituírem
uma configuração que conserve o fluxo da rede. Uma alternativa para a geração da
solução inicial é, então, aplicar a proposta apresentada em Silva e Souza (2007f),
atribuindo a responsabilidade da geração da população inicial a uma metaheurística.
3.4.5
Função de avaliação
A associação de cada solução ao valor de avaliação é dada por meio da função
de aptidão. Esta função tem, por objetivo, fornecer uma medida de adequação de
cada indivíduo da população ao seu habitat.
A função de aptidão utilizada na presente dissertação agrega penalizações referentes às restrições (3.1b) e (3.1c), uma vez que os movimentos gerados pelos
operadores genéticos podem causar infactibilidade nas populações sobreviventes em
cada etapa evolutiva. A função de aptidão é dada pela expressão (3.4):
3.4
Aplicação AG ao PFM
f (s) =
X
26
ckl xkl + α max{0, (Dx − b)} + β max{0, (x − u)}
(3.4)
k ∈ P
l ∈ A
Nesta expressão, o primeiro termo representa a função de custo do PFMI, conforme apresentada em (2.1a) e em (3.1a). O segundo termo está associado à relaxação sobre a restrição de conservação de fluxo, dada pela expressão (3.1b). O
terceiro e último termo representa a relaxação sobre a capacidade dos arcos, dada
por (3.1c). Estes dois últimos termos representam, assim, termos de penalização,
que têm sua influência ponderada pelo uso dos parâmetros α e β, gerados a partir
de experimentos computacionais. Um possível valor para esses parâmetros incide
sob o somatório dos custos dos produtos pelos arcos da rede.
Pode-se também utilizar a técnica de ranking, que gera uma função de ajuste
linear e provoca uma redução da pressão seletiva, diminuindo a probabilidade de
convergência prematura do algoritmo. Esta função é representada por:
F R(j) =
nind − pj
nind
X
(3.5)
(nind − i)
i=1
para:
• F R(j): função rank do indivíduo j;
• nind: número de indivíduos da população;
• pj : posição do indivíduo j na população.
3.4.6
Aplicação de Algoritmo Genético ao Problema de Fluxo
Multiproduto
Nesta sub-seção é discutida a utilização dos operadores genéticos à solução do
PFM, segundo as estruturas definidas anteriormente.
Antes de se aplicar os operadores de cruzamento (crossover ) e de mutação, faz-se
necessário estabelecer um critério de seleção em relação aos novos indivíduos que
serão gerados pelo processo evolutivo. Segundo Blickle (1996), a probabilidade de
sobrevivência do indivíduo durante o processo iterativo é dada pela expressão (3.6):
Φi
pi = Xnind
j=1
para
(3.6)
Φi
• Φi : representa a avaliação do indivíduo i na população;
• nind: número de indivíduos da população.
A seleção é feita através do elitismo, que é um operador presente em quase todas
as implementações de AG. Por ele, os melhores vetores de fluxo estarão presentes
na geração de novos indivíduos.
3.4
Aplicação AG ao PFM
27
Depois de escolhidos os indivíduos, a população é dividida em três classes, conforme Erickson et al. (2002). A classe de elite (classe A) constitui η × 100%. A
classe mediana (classe B) compõe-se de µ × 100%. O restante da população (classe
C) constitui a classe baixa. Usando os parâmetros de controle de tamanhos de
famílias η e µ, pode-se controlar a propriedade de elitismo e balancear a convergência e a diversidade da população gerada. A seguir, serão apresentados os processos
de cruzamento e mutação.
3.4.6.1
Cruzamento
Para cada par formado, verifica-se se irá ou não ocorrer cruzamento, com probabilidade de ocorrência pc . No cruzamento, os genes (arcos da rede) de dois cromossomos (vetores de fluxo) pais são combinados, gerando cromossomos-filhos. O
operador utilizado é o crossover ordenado (OX), o qual possui uma implementação
mais simplificada quando comparado ao PMX (Partially Matched Crossover ). A
aplicação deste operador (OX) pode provocar a violação tanto da capacidade dos
arcos como da conservação do fluxo pelos nós, sendo responsabilidade da função de
avaliação penalizar tais infactibilidades. A Figura 3.8 representa um esquema geral
do operador de crossover com um ponto de corte.
Figura 3.8: Operação de crossover.
3.4.6.2
Mutação
A mutação procura buscar regiões ainda não exploradas pelo AG, inserindo, na
população, genes que ainda não foram incluídos na mesma. A mutação pode ocorrer
por gene ou por alelos, que são partes integrantes dos genes.
Inicialmente, determina-se o número de mutações que deverão ocorrer, sendo
essa escolha proporcional à probabilidade de mutação e ao número de indivíduos.
Em seguida, é feita a escolha aleatória de um indivíduo e de parte dele, e realiza-se
a mutação. A mutação ocorre entre os vetores de fluxos dos arcos, ou então entre o
3.5
Conclusão
28
fluxo individual de determinados produtos em um determinado arco. Fazendo uso
da segunda opção, garante-se a factibilidade em relação à limitação do fluxo pelos
arcos da rede. Na Figura 3.9, é representada a mutação entre genes (i) e entre alelos
(ii).
Figura 3.9: Operação de mutação.
3.5
Conclusão
Neste capítulo foi apresentado o modelamento do problema de fluxo multiproduto
inteiro abordado nesta dissertação. O modelo está presente em Silva e Souza (2007c)
e é utilizado nos capítulos posteriores, tendo um maior enfoque matemático no
capítulo 5 e maior enfoque computacional no capítulo 6. A modelagem matemáticacomputacional também é utilizada no capítulo 4, onde foi apresentado um algoritmo
para otimizar o processo de solução do problema, e este modelamento é detalhado
neste presente capítulo. Foi discutido o significado de cada estrutura matemática do
problema na seção 3.2, além da transformação destas estruturas em listas lineares
na seção 3.3, aproveitando a facilidade nas operações advindas dos procedimentos
heurísticos. Foram implementadas algumas funções em linguagem C para a obtenção
de informações a respeito da variável de interesse, tendo como parâmetros o produto ou o arco especificado. Essas implementações estão disponíveis no Anexo B.
Além disso, foi feita uma abordagem a uma metaheurística que faz uso de busca
populacional, especificamente o algoritmo genético, sendo base do modelamento
matemático e computacional apresentado na seção 3.4.
Capítulo 4
Pré-Otimização Aplicada ao
Problema de Fluxo Multiproduto
Inteiro
4.1
Introdução
Como visto no capítulo 2, há uma grande variedade de aplicações envolvendo problemas de fluxo multiproduto, implicando em questões de forte impacto econômico
e social. Dependendo da rede utilizada, a dimensão do problema pode gerar dificuldades nos procedimentos empregados na solução. Problemas que retratam uma
aplicação real, em geral, apresentam grandes dimensões, em virtude da quantidade
de variáveis e restrições apresentadas. Tal fato motiva a utilização de técnicas de
pré-otimização ou pré-condicionamento, a fim de reduzir a dimensão do problema.
Neste capítulo, é apresentada uma análise de pré-otimização aplicada a problemas de fluxo multiproduto inteiro, motivada pela existência de sistemas lineares homogêneos, provindos da restrição de conservação de fluxo junto à formulação origemdestino específico do problema, com o objetivo de garantir previamente soluções, de
modo a beneficiar posteriormente o método de resolução empregado.
Os resultados, apresentados na seção 4.5, mostram a possibilidade de uma redução significativa do número de variáveis tratadas pelo problema. Na seção 4.2,
é apresentada uma revisão bibliográfica sobre pré-condicionadores aplicados a problemas modelados via grafos; já na seção 4.3 são analisadas as restrições do PFMI
remetendo às matrizes de conservação de fluxo e de oferta/demanda; além disso, é
apresentada a modelagem dos sistemas lineares homogêneos. Na seção 4.4 é apresentada uma rotina computacional que ilustra o conceito de pré-otimização aplicada
ao PFMI, com as devidas restrições especificadas anteriormente.
4.2
Revisão bibliográfica
Na literatura encontram-se técnicas de pré-otimização ou pré-condicionamento,
aplicadas a problemas modelados via grafos. Em Maggs et al. (2002), é apresentado
um pré-condicionador aplicado a uma rede, incidindo sobre um sistema linear do
tipo Ax = b, no qual A é uma matriz quadrada n × n; b é um vetor n × 1; e x é
29
4.3
Propriedade das restrições
30
um vetor n × 1, a ser determinado. Essas matrizes, em geral, descrevem sistemas
físicos e apresentam, em suas estruturas, propriedades que podem ser exploradas.
É o caso dos laplacianos, descritos em Golub e Loan (1996), no qual desenvolvese pré-condicionadores para acelerar a convergência de métodos iterativos, como o
gradiente conjugado, para a resolução de sistemas envolvendo laplacianos.
A Tabela 4.1 mostra resultados em termos de pré-condicionadores para laplacianos, aplicados em grafos com n nós e m arcos, obtidos para sub-classes de sistemas
simétricos.
Tabela 4.1: Complexidade de pré-condicionadores envolvendo laplacianos.
Autor
Descrição
Complexidade
• sub-grafos esparsos
(Vaidya, 1991)
O (n1.75 )
• grafo não-planar
• grafo-planar
(Vaidya, 1991)
O (n1.2 )
• sub-grafo com adição
de nós
q
1
(Gremban et al., 1994)
O m dn n log (n)
• rede d-dimensional
(Boman e Hendrickson, 2004)
(Spielman e Teng, 2003)
• peso uniforme
• peso não-uniforme
O (m1.5 pol log (n))
• particionamento
recursivo do grafo
O (m1.31 )
Em Resende e Veiga (2003), pode-se encontrar uma extensa bibliografia sobre
pré-condicionadores, usados em implementações do método gradiente conjugado
para resolver sistemas de equações aplicadas a algoritmos de fluxo em rede, em
particular para o método de ponto interior. O algoritmo do gradiente conjugado
pré-condicionado é usado para resolver o sistema:
M −1 ADk AT ∆y = M −1 b
sendo ∆y ∈ <m , A ∈ <m×n a matriz de incidência nó-arco e M ∈ <m×m uma matriz
positiva definida. O vetor b ∈ <m e a matriz diagonal Dk ∈ <n×n dependem do
algoritmo de ponto interior usado. O método gradiente conjugado, em conjunto à
fatoração Cholesky, e aproveitando a esparsidade da matriz de incidência, constitui
a estratégia de pré-condicionamento aplicada a problemas de fluxo multiproduto
utilizada em Castro (2003).
4.3
Propriedade das restrições
Considere a matriz de incidência B nó-arco de uma rede R = (N , A, F), tendo
um fluxo F e um conjunto P de produtos, definida por:
4.3
Propriedade das restrições
31

(4.1)

a11 · · · a1|A|


..
...
B =  ...

.
a|N |1 · · · a|N ||A|
sendo:

 1, se o nó i pertence ao arco j como fonte;
-1, se o nó i pertence ao arco j como sumidouro;
aij =

0, se o nó i não pertence ao arco j.
O grau de esparsidade dessa matriz depende fortemente da densidade da rede.
Considere também a matriz de oferta/demanda, definida por:


b11 · · · b1|P|


..
...
(4.2)
N =  ...

.
b|N |1 · · · b|N ||P|
na qual bij representa a quantidade do produto j no nó i, de modo que:

 bij > 0, se o nó i é um nó de fornecimento;
bij < 0, se o nó i é um nó de demanda;
bij =

bij = 0, se o nó i é um nó de transbordo.
e cada coluna representa o vetor bi de oferta-demanda de um produto i.
Usando o fato da formulação do problema ser do tipo ODE (origem-destino específico), pode-se afirmar que, em cada coluna da matriz de oferta/demanda dada
em (4.2), existem |N | − 2 valores iguais a zero, gerando um total de |P| (|N | − 2)
valores nulos. O produto da matriz de incidência pelo vetor de fluxo gera a matriz de
oferta/demanda, caracterizando a restrição de conservação de fluxo. Pode-se notar,
então, a existência de |P| |N | sistemas lineares. O conceito de pré-condicionamento
aplicado ao problema de fluxo multiproduto inteiro tem como base teórica o resultado a seguir.
Lema 4.1 Seja ϕ ⊂ Z+ e X = {xi ∈ < | xi ≥ 0, ∀i ∈ ϕ}. Então:
X
xi = 0 ⇐⇒ xi = 0, ∀ xi ∈ X
i∈ϕ
e
xi − xj = 0 ⇐⇒ xi = xj
Este resultado mostra simplesmente que a soma de números reais positivos é nula
se e somente se todos os fatores da soma são positivos; além disso, mostra também
que a diferença entre dois números reais positivos é nula se e somente se os dois
fatores são idênticos.
4.4
Modelagem dos sistemas lineares homogêneos
4.3.1
32
Modelagem dos sistemas lineares homogêneos
A restrição de conservação de fluxo presente na equação (2.1) pode ser resumida
em |P| igualdades do tipo:
Bxi = bi , i = 1, . . . , |P|.
(4.3)
Considere a matriz resultante do lado esquerdo da equação (4.3). Cada elemento
(i, j) dessa matriz é composto por um somatório (incluindo diferenças) de fluxos,
os quais representam a quantidade do produto j no nó i. Esses elementos podem
ser transformados em vetores, nos quais a variável de fluxo é substituída por seu
coeficiente (1, -1 ou zero, caso a variável de fluxo não esteja no vetor). Por exemplo,
i
arc1
numa rede com 5 arcos, 4 nós e 2 produtos,
+
se o elemento (2,1) de Bx for x
arc3
arc5
x
− x , então será formado o vetor 1 0 1 0 −1 .
Pela expressão (4.2), para cada produto, existem |N | − 2 sistemas lineares homogêneos. Esses sistemas, agora, são constituídos de elementos pertencentes ao
conjunto {1, 0, −1} e cada posição comum desses vetores representa a mesma variável de fluxo, possibilitando aplicar um método iterado de resolução. Para isso, basta
aplicar o Lema 4.1 seqüencialmente sobre os vetores de um determinado produto,
atualizando as variáveis e repetindo o processo até que não existam possibilidades
de alterações sobre elas.
A proposta da técnica de pré-otimização considerada na presente dissertação
consiste em eliminar variáveis que representam uma condição de fluxo infactível, caso
não fossem nulas, em virtude da orientação da rede. Neste sentido, são determinadas,
então, um conjunto de soluções prévias do problema em análise, ou seja, de variáveis
que, a priori, antes da aplicação de qualquer método para a solução do PMFI, têm
seu valor determinado como nulo.
Na utilização de métodos heurísticos para resolver o problema de fluxo multiproduto, esse conceito torna-se muito útil, pois há a possibilidade de uma redução
significativa no espaço de busca ou região de vizinhança explorados pela heurística
empregada. Em virtude da complexidade do problema tratado, métodos exatos apresentam dificuldades na tentativa de solucionar o problema, tornando a utilização
de técnicas heurísticas uma boa opção.
4.4
Aplicação do método de pré-otimização
Nesta seção é apresentada uma rotina computacional que ilustra o conceito de
pré-otimização aplicado ao problema de fluxo multiproduto inteiro, com as devidas restrições especificadas anteriormente. O pseudocódigo associado é apresentado
na Figura 4.1. O algoritmo computacional implementado utilizando o conceito de
pré-otimização pode ser visto em Silva e Souza (2007e).
Seja p = |P| a quantidade de produtos, n = |N | a quantidade de nós e a = |A|
a quantidade de arcos envolvidos numa rede. Considere:
σ = min (p, n)
υ = max (p, n, a)
4.4
Aplicação do método de pré-otimização
33
procedimento Pré-Otimiza
1)
repita produto = 1 → #produtos
2)
maior_elemento_vetor ();
3)
aloca_estruturas();
4)
enquanto(mudança)
5)
repita nó = 1 → #nós
6)
se(sistema homogêneo)
7)
varre_vetor ();
8)
se(condição de anulação)
9)
zera_x ();
10)
constroi_lista_para_atualização();
11)
fim-se
12)
fim-se
13)
fim-repita
14)
repita nó = 1 → #nós
15)
varre_vetor
16)
varre_lista();
17)
atualiza_matriz_verifica_mudança();
18)
fim-varre_vetor
19)
fim-repita
20)
fim-enquanto
21) fim-repita
fim Pré-Otimiza
Figura 4.1: Pseudocódigo para o procedimento de pré-otimização.
O custo computacional dessa rotina de pré-otimização torna o procedimento atrativo, pois sua complexidade Φ é dada por:
Θ σ2 ≤ Φ ≤ Θ υ3
(4.4)
O custo computacional, portanto, é de ordem polinominal e, além disso, relativamente baixo. Em alguns casos, o número de variáveis pré-definidas pelo método
representa uma quantidade significativa em relação ao número total de variáveis a
serem definidas pelos métodos de resolução aplicados ao problema.
O pseudocódigo do método proposto é dividido basicamente em duas partes:
eliminação de variáveis por nós e atualização da matriz principal, caracterizadas
pelas linhas 5-13 e 14-19, respectivamente, ambas feitas sobre um loop gerado pela
mudança da composição dos vetores.
Quando é identificado um sistema linear homogêneo, aplica-se o Lema 4.1 e
eliminam-se as variáveis correspondentes. Este procedimento é representado pelas
linhas 6-9. Em seguida, é criada uma lista para a atualização dos vetores-linha da
matriz. Por fim, a matriz é atualizada e o processo é repetido até que não existam
alterações na composição dos vetores, sendo esse procedimento aplicado para cada
produto.
A fim de obter um melhor entendimento do processo de pré-otimização, é descrito
a seguir o desenvolvimento do algoritmo através de algumas ilustrações.
4.5
Aplicação do método de pré-otimização
34
Considere uma sub-matriz advinda da restrição de conservação de fluxo, representada pelos coeficientes das variáveis de fluxo como descrito na sub-seção 4.3.1,
supondo já determinado os sistemas lineares homogêneos, conforme a linha 6 do
algoritmo 4.1. A partir daí, percorre-se os vetores de fluxo, visando a aplicação do
Lema 4.1, de acordo com a linha 8. A determinação das variáveis para a aplicação
do Lema 4.1 é exibida pela matriz 1 da Figura 4.2
Figura 4.2: Determinação das variáveis para a aplicação do Lema 4.1.
Após identificada as variáveis suscetíveis ao Lema 4.1, inicia-se o processo de
eliminação, representado pela linha 9 do algoritmo de pré-otimização. A eliminação
consiste em zerar as variáveis, as quais representam um fluxo infactível. Esta etapa
é representada pela matriz 2 da Figura 4.3
Figura 4.3: Determinar fluxo infactível.
Como cada coluna da matriz refere-se a um arco, a variável da mesma coluna das
linhas i e j quaisquer, representam exatamente a mesma variável. Desta maneira,
pode-se eliminar (zerar variáveis) por coluna. Este processo é caracterizado pelas
linhas 14 a 19 no algoritmo proposto. Por fim, a matriz final 3 da Figura 4.4, é
exibida depois de todo o processo de pré-otimização.
Figura 4.4: Atualização da matriz.
Nota-se neste exemplo, uma redução de 13 variáveis a partir da matriz 1, para
um total de 6 variáveis, conforme a matriz 3 da Figura 4.4.
4.5
Resultados computacionais
4.5
35
Resultados computacionais
Para a realização dos testes computacionais, foram utilizadas redes com 32 nós,
tendo a quantidade de arcos variando entre 96 e 320 e a quantidade de produtos dada
por 48, 192 e 320. As instâncias utilizadas foram propostas inicialmente em Alvelos
(2005). Apesar do atributo de custo associado ao produto ou arco não influenciar no
método (e também no resultado), foram utilizadas instâncias com o custo máximo
de 10 e 1000. Outros parâmetros são exibidos, a fim de analisar seus efeitos no
comportamento do método. São exibidos, também, o número de variáveis e restrições
envolvidas nas instâncias, assim como a quantidade de variáveis encontradas pela
pré-otimização. Esses resultados computacionais foram inicialmente apresentados
em Silva e Souza (2007d).
O algoritmo foi desenvolvido em linguagem C, usando o compilador Borland
C++ Builder 5.0 e testado em um microcomputador com processador Pentium IV,
2.4 GHz, com 256 MB de memória RAM, sob sistema operacional Windows XP. O
fator tempo não foi considerado, devido à rapidez (menos de 1 seg) na obtenção dos
resultados pelo algoritmo.
As Tabelas 4.2 e 4.3 mostram os resultados computacionais referentes à porcentagem de soluções prévias, obtidas pela aplicação do procedimento de pré-condicionamento para o caso das instâncias utilizadas. A Tabela 4.4 indica a quantidade
real de variáveis da solução final obtidas previamente pelo algoritmo.
A legenda para as colunas das tabelas é exibida a seguir:
• Instância: série de instâncias numeradas de 1 a 48, com características descritas nas próprias tabelas;
• A: quantidade de arcos;
• N: quantidade de nós;
• P: quantidade de produtos;
• A/N: razão entre quantidade de arcos e quantidade de nós;
• P/N: razão entre quantidade de produtos e quantidade de nós;
• A/P: razão entre quantidade de arcos e quantidade de produtos;
• C: limite máximo do custo associado ao produto e/ou arco.
Observe que as instâncias representadas nas tabelas 4.2 e 4.3 se diferenciam,
principalmente, pela relação entre o número de arcos e o número de nós existentes
em cada uma delas. As instâncias colocadas na Tabela 4.2 apresentam uma relação
de arco/nó de 3 : 1; as instâncias expostas na Tabela 4.3 apresentam uma relação
arco/nó de 10 : 1. Além disso, se diferenciam, internamente nas tabelas citadas, nas
relações produto/nó e arco/produto.
A Tabela 4.2 mostra a existência de uma variação da porcentagem de soluções
encontradas, entre 3,91% a 26,09% nas instâncias de 1 a 24. Não foi detectado nenhum padrão associado às variáveis disponíveis na tabela, para uma previsão quanto
à porcentagem de soluções previamente obtidas.
4.5
Resultados computacionais
36
Tabela 4.2: Resultados computacionais (% soluções).
Instância
1-2
3-4
5-6
7-8
9-10
11-12
13-14
15-16
17-18
19-20
21-22
23-24
A
96
96
96
96
96
96
96
96
96
96
96
96
N
32
32
32
32
32
32
32
32
32
32
32
32
P
48
48
48
48
192
192
192
192
320
320
320
320
A/N
3
3
3
3
3
3
3
3
3
3
3
3
P/N
1,5
1,5
1,5
1,5
6
6
6
6
10
10
10
10
A/P
2
2
2
2
0,5
0,5
0,5
0,5
0,3
0,3
0,3
0,3
(%)solução
3,91
17,56
17,56
19,69
4,87
11,81
26,03
13,01
9,83
9,04
26,09
12,91
C
10
1000
10
1000
10
1000
10
1000
10
1000
10
1000
Tabela 4.3: Resultados computacionais (% soluções).
Instância
25-26
27-28
29-30
31-32
33-34
35-36
37-38
39-40
41-42
43-44
45-46
47-48
A
320
320
320
320
320
320
320
320
320
320
320
320
N
32
32
32
32
32
32
32
32
32
32
32
32
P
48
48
48
48
192
192
192
192
320
320
320
320
A/N
10
10
10
10
10
10
10
10
10
10
10
10
P/N
1,5
1,5
1,5
1,5
6
6
6
6
10
10
10
10
A/P
6,67
6,67
6,67
6,67
1,67
1,67
1,67
1,67
1
1
1
1
(%)solução
-
C
10
1000
10
1000
10
1000
10
1000
10
1000
10
1000
A Tabela 4.3 descreve os resultados obtidos utilizando-se as instâncias de 25 a 48,
as quais representam redes com alta relação arco/nó. Neste caso, não foi encontrada
nenhuma solução prévia para os problemas.
Pelas Tabelas 4.2 e 4.3 apresentadas, o único atributo a efetivamente diferenciar
os resultados é a relação arco/nó. Porém, pode-se notar que, em redes nas quais
a quantidade de produtos supera a quantidade de arcos, há uma maior chance de
se obter soluções prévias. Nas instâncias 21-22, por exemplo, que possuem uma
relação arco/produto na ordem de 30%, foi possível reduzir a dimensão do problema
em 26,09%. Pela Tabela 4.4, diante de 30816 variáveis a serem identificadas pelo
método de resolução empregado, não é necessário identificar 8040 variáveis, já que
elas foram encontradas pelo algoritmo de pré-condicionamento como tendo valores
4.6
Conclusão
37
Tabela 4.4: Resultados computacionais (Soluções prévias).
Instância
1-2
3-4
5-6
7-8
9-10
11-12
13-14
15-16
17-18
19-20
21-22
23-24
#variáveis
4704
4704
4704
4704
18528
18528
18528
18528
30816
30816
30816
30816
#restrições
1632
1632
1632
1632
6240
6240
6240
6240
10336
10336
10336
10336
#Soluções Prévias
184
826
826
926
902
2188
4823
2410
3029
2785
8040
3978
nulos. Em virtude do custo computacional baixo e da simples implementação, é
recomendável, desse modo, a utilização deste procedimento ao tipo de problema
abordado. No entanto, em alguns casos, não se obterá nenhuma solução prévia.
4.6
Conclusão
O conceito proposto de pré-otimização aplicado ao problema de fluxo multiproduto inteiro é fundamentado na resolução de sistemas lineares homogêneos iterados.
Tem, como objetivo, eliminar variáveis associadas aos nós da rede, nas quais o fluxo
seria inviável, caso seu valor não fosse nulo. Para técnicas heurísticas, isso representa
uma redução do espaço de buscas ou da região de vizinhança abordada. Os resultados computacionais mostram que é possível reduzir a dimensão do problema em até
pouco mais de 26%, segundo as instâncias avaliadas. Além disso, esse procedimento
possui um custo computacional de ordem polinomial e relativamente baixo, ao lado
de sua simplicidade de implementação.
Capítulo 5
Análise do Espaço Solução de um
Problema de Fluxo Multiproduto
Inteiro
5.1
Introdução
Os problemas de fluxo multiproduto que retratam uma aplicação real, em geral,
apresentam uma elevada dimensão. O conjunto de restrições e as variáveis envolvidas
no modelamento do problema se apresentam em grande quantidade. Neste capítulo,
será apresentado um detalhamento sobre o espaço solução do PFMI, o qual foi
construído a partir da restrição de capacidade do problema. A motivação para essa
análise está no uso deste espaço como região de vizinhança para obtenção de novas
soluções, produzidas pelas heurísticas utilizadas.
5.2
Análise matemática do dimensionamento
A formulação matemática do PFMI considerado é descrita na seção 3.2 pela
equação (3.1), aqui novamente apresentada, para facilidade de acompanhamento da
descrição posta:
min
suj. a
cx
Dx = b
P k
x l ≤ ul , l ∈ A
(5.1a)
(5.1b)
(5.1c)
k∈P
x ∈ Z+
(5.1d)
Vale recordar que a expressão (5.1b) representa a restrição de conservação de
fluxo; a expressão (5.1c) representa a restrição de capacidade dos arcos; e a expressão
(5.1d) representa a condição de integralidade e não negatividade sobre as variáveis
do problema.
Pode-se compor o espaço solução pela interseção de dois conjuntos. Seja C o
conjunto formado pelas restrições (5.1b) e (5.1d) e seja H o conjunto formado pelas
restrições (5.1c) e (5.1d). O diagrama do espaço-solução é dado pela Figura 5.1.
38
5.3
Análise matemática do dimensionamento
39
C
H
Espaço de solução de
um PFMI
Figura 5.1: Diagrama do espaço solução de um PFMI.
Seja p = |P| a quantidade de produtos, n = |N | a quantidade de nós e a = |A|
a quantidade de arcos envolvidos numa rede. A matriz de incidência D ∈ Z n×a
tem posto completo e o número de variáveis é maior que o número de restrições,
logo, tem-se infinitas soluções. Portanto, o conjunto C é infinito. O conjunto H é
compacto e discreto, características geradas pelas restrições (5.1c) e (5.1d). Logo,
H é passível de enumeração. Como dito anteriormente, este espaço corresponde à
região de vizinhança utilizada pelas técnicas heurísticas empregadas. Tal fato motiva
a análise do espaço solução do conjunto H.
Defina a seguinte função auxiliar de contagem:

1
se i = j = 1;


 1
k
+
i
se
j = 1 e i 6= 1;
i−1
(5.2)
kij =
i
P j−1


km
se j 6= 1;

m=1
Seja u[i] a capacidade do arco i. Os elementos do conjunto H são as combinações
das linhas, cujos elementos satisfazem o seguinte sistema de inequações:
x11 + x21 + . . . + xp1 ≤ u[1]
x12 + x22 + . . . + xp2 ≤ u[2]
..
.
x1a + x2a + . . . + xpa ≤ u[a]
(5.3)
(5.4)
(5.5)
no qual xji representa a quantidade do produto j que passa pelo arco i.
Na próxima seção, é feita a enumeração do espaço em estudo através de passos,
os quais refletem sobre a desigualdade referente a um dado arco i. Esta enumeração
é também apresentada em Silva et al. (2007a). Note que o conjunto solução para
essa desigualdade é formada por elementos pertencentes ao intervalo [0, u[i]].
5.3
Enumeração do espaço solução
5.3
40
Enumeração do espaço solução
Nesta seção, é enumerado o espaço representado pelo conjunto H através de
construção.
1o Passo Esse passo é chamado de bloco 2, devido ao fato das permutações atingirem apenas as duas últimas posições do vetor de fluxo corrente. Analogamente, o
passo bloco k atinge as k últimas posições.
Inicialmente, são preenchidas todas as variáveis com o valor zero e, em seguida,
são permutadas as duas últimas posições em todas as combinações possíveis de
valores cuja soma não exceda u[i], ou seja:
0 ···
0 ···
0 ···
.. ..
. .
0 0 0 ···
0
0
0
..
.
0
0
0
..
.
 #solucoes






u[i] + 1





0 u[i] 
0
0
0
..
.
0
1
2
..
.
0 ··· 1
0
0 ··· 1
1
.. .. ..
..
. . .
.
0 0 0 · · · 1 u[i] − 1
0
0
..
.
0
0
..
.
..
.
0 0 0 · · · u[i] 0
Nesse passo tem-se, então:
 #solucoes




u[i]




#solucoes
1
#solucoes = 1 + 2 + . . . + u[i] + (u[i] + 1)
ou
1
#solucoes = ku[i]
+ (u[i] + 1)
2o Passo Neste passo, é feita a análise para o bloco 3, onde as permutações incidem nas três últimas posições. Até o fim da primeira linha contínua, são feitas
as permutações cuja antepenúltima posição do vetor é constituída de 1 unidade. O
próximo intervalo de combinações, que vai até a próxima linha contínua, refere-se às
permutações cuja antepenúltima posição do vetor é constituída de 2 unidades. As
configurações dos intervalos de permutações seguem até a última permutação, onde
a antepenúltima posição do vetor é constituída de u[i] unidades.
0 ··· 1 0
.. .. .. ..
. . . .
0 0 ··· 1 0
0
..
.
 #solucoes

0

..
u[i]
.


u[i] − 1
5.3
Enumeração do espaço solução
0 ··· 1 1
.. .. .. ..
. . . .
0 0 ··· 1 1
0
..
.
41
 #solucoes

0

..
u[i] − 1
.


u[i] − 2
..
.
#solucoes
0 0 · · · 1 u[i] − 1 0
1
——————————————————
0 ··· 2 0
.. .. .. ..
. . . .
0 0 ··· 2 0
0
..
.
0 ··· 2 1
.. .. .. ..
. . . .
0 0 ··· 2 1
0
..
.
 #solucoes

0

..
u[i] − 1
.


u[i] − 2
 #solucoes

0

..
u[i] − 2
.


u[i] − 3
..
.
#solucoes
0 0 · · · 2 u[i] − 2 0
1
——————————————————
..
.
..
.
——————————————————
#solucoes
0 0 · · · u[i] − 1 0 0
2
0 0 · · · u[i] − 1 0 1
#solucoes
0 0 · · · u[i] − 1 1 0
1
——————————————————
0 0 · · · u[i] 1 0
Logo, o número de soluções é dado por:
#solucoes
1
#solucoes = [1 + (1 + 2) + . . . + (1 + 2 + . . . + (u[i] − 1)) + (1 + 2 + . . . + u[i])]
ou
1
1
+ ku[i]
#solucoes = k11 + k21 + . . . + ku[i]−1
5.3
Enumeração do espaço solução
42
3o Passo Assim como no passo anterior, a quantidade de soluções geradas na
primeira configuração das permutações na primeira posição é igual a u[i], diferentemente do passo 1, o qual previa a configuração na totalidade nula. Os intervalos
de configurações seguem o mesmo padrão do passo anterior. Porém, o início do
processo começa na quarta posição, no sentido da direita para esquerda.
0 ··· 1 0 0
.. .. .. .. ..
. . . . .
0 0 ··· 1 0 0
0
..
.
0 ··· 1 0 1
.. .. .. .. ..
. . . . .
0 0 ··· 1 0 1
0
..
.
 #solucoes

0

..
u[i]
.


u[i] − 1
 #solucoes

0

..
u[i] − 1
.


u[i] − 2
..
.
#solucoes
1
——————————————————
0 0 · · · 1 0 u[i] − 1 0
0 ··· 1 1 0
.. .. .. .. ..
. . . . .
0 0 ··· 1 1 0
0
..
.
0 ··· 1 1 1
.. .. .. .. ..
. . . . .
0 0 ··· 1 1 1
0
..
.
 #solucoes

0

..
u[i] − 1
.


u[i] − 2
 #solucoes

0

..
u[i] − 2
.


u[i] − 3
..
.
#solucoes
1
——————————————————
0 0 · · · 1 1 u[i] − 2 0
..
.
——————————————————
#solucoes
0 0 · · · 1 u[i] − 2 0 0
2
0 0 · · · 1 u[i] − 2 0 1
0 0 · · · 1 u[i] − 2 1 0
#solucoes
1
5.3
Enumeração do espaço solução
43
——————————————————
0 0 · · · 1 u[i] − 1 0 0
#solucoes
1
——————————————————
——————————————————
..
.
——————————————————
——————————————————
#solucoes
0 0 · · · u[i] − 1 0 0 0
2
0 0 · · · u[i] − 1 0 0 1
#solucoes
0 0 · · · u[i] − 1 0 1 0
1
——————————————————
#solucoes
0 0 · · · u[i] − 1 1 0 0
1
——————————————————
0 0 · · · u[i] 0 0 0
#solucoes
1
Analisando a enumeração anterior, pode-se deduzir que o número de soluções é
dado por:
#solucoes = 1 + [1 + (1 + 2)] + [1 + (1 + 2) + (1 + 2 + 3)] + . . .
. . . + [1 + (1 + 2) + . . . + (1 + 2 + . . . + u[i])]
ou
1
#solucoes = k11 + k11 + k21 + k11 + k21 + k31 + . . . + k11 + . . . + ku[i]
ou seja:
2
2
#solucoes = k12 + k22 + . . . + ku[i]−1
+ ku[i]
Prosseguindo de maneira indutiva, para cada desigualdade do conjunto H tem-se
que:
#solucoes =
1
ku[i]
+ (u[i] + 1) +
p−2 u[i]
X
X
m=1 n=1
knm (arco i)
5.4
Validação do dimensionamento
44
expressão válida para um certo arco i. Levando-se em consideração o número de
combinações possíveis de soluções, pode-se concluir que o tamanho do espaço solução
de H é dado por:


p−2 u[i]
a
XX
Y
1
ku[i]
+ (u[i] + 1) +
(5.6)
knm 
m=1 n=1
i=1
No Anexo A, é exibido um algoritmo recursivo em linguagem C, para determinar
a dimensão do espaço solução abordado neste capítulo. Neste caso, considera-se que
as capacidades dos arcos sejam iguais. Para alterar esta hipótese, basta criar um
vetor de capacidade e inseri-lo no algoritmo.
5.4
Validação do dimensionamento
Nesta seção é analisada a validação do dimensionamento do espaço de solução
em estudo através de testes. Para validar a expressão (5.6), são feitos dois testes. O
primeiro supõe um arco com capacidade igual a três, tendo três produtos envolvidos;
em um segundo teste, supõe-se um arco com capacidade igual a dois e com cinco
produtos inseridos na rede. Na coluna “# solucoes” estão as configurações das
soluções possíveis e sua quantidade; já na coluna “Fórmula”, está apresentada a
quantidade de soluções determinadas pelo uso da expressão (5.6).
No primeiro caso, então, a = 1, p = 3 e u[1] = 3.
# solucoes

0 0 0 


0 0 1 



0 0 2 



0 0 3 



0 1 0 



0 1 1 



0 1 2 



0 2 0 



0 2 1 



0 3 0
20
1 0 0 


1 0 1 



1 0 2 



1 1 0 



1 1 1 



1 2 0 



2 0 0 




2 0 1 



2 1 0 


3 0 0
Fórmula
1
Q
i=1
k31
+ (3 + 1) +
3−2
P
3
P
m=1 n=1
knm
= (1 + 2 + 3) + (4) + [k11 + k21 + k31 ]
= (1 + 2 + 3) + (4) + [1 + (1 + 2) + (1 + 2 + 3)]
= 10 + 10
= 20
Para o segundo caso, tem-se: a = 1, p = 5 e u[1] = 2.
5.5
Análise para variação de parâmetros
# solucoes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 0
0 0 1 1
0 0 2 0
0 1 0 0
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 0
0 2 0 0
1 0 0 0
1 0 0 0
1 0 0 1
1 0 1 0
1 1 0 0
2 0 0 0
45
Fórmula
0
1
2
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0








































1
Q
i=1
k21
+ (2 + 1) +
5−2
P
2
P
m=1 n=1
knm
=
= k11 + 3 + (k11 + k21 ) + (k12 + k22 ) + (k13 + k23 )
= (1 + 2 + 3) + [1 + (1 + 2)] + [k11 + k11 + k21 ] + [k12 + k12 + k22 ]
= 6 + 4 + (1 + 1 + 1 + 2) + (1 + 1 + 1 + 1 + 2)
21
= 21







































Apesar da simplicidade dos testes exibidos, pode-se constatar a validação da
expressão (5.6) para o dimensionamento do problema tratado neste capítulo. Podese perceber, através de uma contagem computacional, que, para dimensões maiores,
a fórmula encontrada também é válida. Esta validação foi inicialmente apresentada
em Silva et al. (2007b).
5.5
Análise para variação de parâmetros
Nesta seção, é discutida a influência da variação dos parâmetros número de
arcos, número de produtos e capacidade dos arcos no problema em questão.
Todas as curvas resultantes foram ajustadas exponencialmente utilizando o software
Origin 6.0 (Microcal Software, 1999).
As Figuras 5.2, 5.3 e 5.4 mostram, respectivamente, a dependência do número de
soluções em relação à quantidade de arcos, ao número de produtos e a capacidade
dos arcos. Em todos os três casos, há um comportamento exponencial para o número
de soluções, quando o parâmetro analisado tem seu valor aumentado.
A base de dados utilizada para realização da análise gráfica pode ser visualizada
em (Silva, 2007a). A partir dos parâmetros gerados pelo Origin 6.0, encontrados
em (Silva, 2007b), pode-se observar, através de simulações, que o aumento linear na
quantidade de arcos provoca maior dificuldade na resolução do PFMI, pois a taxa
de crescimento do número de soluções é maior em relação ao número de produtos e
capacidade. Porém, o número de arcos não é o fator que fornece maior contribuição
5.5
Análise para variação de parâmetros
Figura 5.2: Variação do número de arcos.
Figura 5.3: Variação de número de produtos.
46
5.5
Análise para variação de parâmetros
47
Figura 5.4: Variação da capacidade nos arcos.
para o aumento do número de soluções. O aumento linear na quantidade de produtos
provoca um maior número de soluções para o PFMI, mas, no entanto, a taxa de
crescimento desse número é menor do que a gerada pelo aumento do número de
arcos, isto analisado individualmente.
Tabela 5.1: Análise da dimensão do espaço solução do PFMI.
#arcos #produtos cap. arco #soluções
20
5
10
6.01e+87
20
10
15
4.71e+148
28
15
8
6.55e+188
30
10
8
4.40e+171
Para a análise do efeito da capacidade, foram supostos arcos de igual capacidade.
Por exemplo, na instância de capacidade 5, os 10 arcos possuem esta capacidade; na
instância de capacidade 6, os 10 arcos possuem capacidade 6. O fator capacidade foi
o de menor impacto em relação a dimensão do PFMI, mesmo assim gerando altos
valores.
Os resultados exibidos na Tabela 5.1 refletem a dificuldade de um problema de
fluxo multiproduto inteiro. Apesar do espaço aqui abordado ser muito maior do que
o espaço solução do problema em questão, trata-se de um espaço no qual se consegue
fazer uma enumeração e será região para geração de vizinhanças na utilização das
heurísticas computacionais na tentativa de solucionar o problema. Os dados da
5.6
Conclusão
48
Tabela 5.1 foram apresentados inicialmente em Silva e Souza (2007a).
5.6
Conclusão
O número de produtos leva o Problema de Fluxo Multuiproduto Inteiro a ter
maior dimensão. Entretanto, o número de arcos gera um crescimento maior da
dimensão. Para os testes aqui realizados, essa taxa chega a ter a relação 2 : 1, o
que leva a concluir que o fator número de arcos é mais impactante ao problema,
pois, com essa taxa, o número de soluções geradas pelo aumento linear do número
de arcos supera os gerados pelo aumento de produtos. Como dito anteriormente,
esse espaço contém efetivamente o espaço solução do PFMI.
Capítulo 6
Métodos Heurísticos
6.1
Introdução
Pode-se definir uma metaheurística como “uma ferramenta algorítmica geral, que
pode ser aplicada a diferentes problemas de otimização, com modificações relativamente pequenas, para torná-las adaptáveis a um problema específico” (Becceneri,
2007). Algumas propriedades são desejáveis para uma metaheurística, como as descritas em Coelho (2006):
• simplicidade: deve ser simples e baseada em um princípio claro, que possa ser
aplicável em geral;
• coerência: deve-se conseguir traduzir para o algoritmo, de forma natural, a
idéia proposta pela metaheurística;
• eficiência: deve-se despender um tempo computacional que seja razoável para
a determinação da solução;
• robustez: deve ser consistente, em uma ampla variedade de problemas testes;
• amigável: deve ser fácil de entender e fácil de usar, e com a menor quantidade
de parâmetros possíveis;
• inovação: deve permitir sua utilização para novos tipos de aplicações.
Os algoritmos metaheurísticos podem ser classificados como não-populacionais,
que trabalham com uma única solução, descrevendo uma trajetória no espaço de
busca durante sua execução, ou então, os baseados em uma população, que descrevem a evolução de um conjunto de soluções no espaço de busca.
Nas metaheurísticas não-populacionais, ou ditas de busca local, a exploração
do espaço solução é feita por meio de movimentos, os quais são aplicados a cada
passo sobre a solução corrente, gerando outra solução promissora em sua vizinhança.
São exemplos dessa categoria: Busca Tabu, GRASP, Iterated Local Search e Simulated Annealing, sendo essas duas últimas abordadas neste trabalho. Os métodos
baseados em busca populacional consistem em manter um conjunto de boas soluções
e combiná-las de forma a tentar produzir soluções ainda melhores. São exemplos
49
Iterated Local Search aplicada ao PFMI
6.2
50
dessa categoria: Colônia de Formiga, PSO e Algoritmo Genético, sendo este último
descrito na sub-seção 3.4.1.
Na Figura 6.1 estão representadas as buscas por soluções de uma algoritmo nãopopulacional e populacional.
(a) Algoritmo não-populacional
(b) Algoritmo populacional
Figura 6.1: Estruturas de busca de algoritmos (Coelho, 2006).
Neste capítulo são abordadas as técnicas heurísticas de busca local Iterated Local
Search e Simulated Annealing, aplicadas ao problema de fluxo multiproduto inteiro.
As metodologias descritas a seguir foram apresentadas em Silva e Souza (2007h).
6.2
Iterated Local Search aplicada ao Problema de
Fluxo Multiproduto Inteiro
A metaheurística Iterated Local Search (ILS) (Lourenço et al., 2002) baseia-se na
idéia de que um procedimento de busca local pode ser melhorado, produzindo novas
soluções obtidas de perturbações na solução ótima local. A perturbação não pode ser
muito restrita, pois, nesse caso, pode-se não sair do ótimo local e, ao mesmo tempo,
não pode ser muito ampla, pois pode provocar um reinício aleatório. A Figura
6.2 ilustra o efeito da perturbação numa dada solução s, no caso de problemas de
otimização envolvendo variáveis contínuas.
Para a aplicação do algoritmo ILS a um dado problema, é necessário especificar
quatro componentes, segundo (Lourenço et al., 2002):
• GeraSolucaoInicial(·): gera uma solução inicial s0 ;
00
• BuscaLocal(·): retorna uma solução melhorada s ;
• Perturbação(·): altera a solução corrente s, guiando-a a uma solução inter0
mediária s ;
• CritérioAceitacao(·): decide em qual solução a próxima perturbação será aplicada.
6.2
Representação de uma solução
51
Figura 6.2: Perturbação sobre uma solução s em problemas de otimização contínua.
procedimento ILS
1) s0 ← GeraSolucaoInicial();
2) s ← BuscaLocal(s0 );
3) enquanto (os critérios de parada não estiverem satisfeitos) faça
4)
s0 ← Pertubacao(historico, s);
5)
s” ← BuscaLocal(s0 );
6)
s ← CriterioAceitacao(s, s”, historico);
7) fim-enquanto;
fim ILS
Figura 6.3: Pseudocódigo da metaheurística Iterated Local Search.
A Figura 6.3 mostra a rotina computacional básica do método ILS.
O desempenho do método ILS em relação à qualidade da solução final e à velocidade de convergência depende fortemente do método de busca local utilizado. O
critério de aceitação decide qual solução continuará a ser explorada e qual perturbação será aplicada.
6.2.1
Representação de uma solução
Uma solução s para o PFMI, representado por uma rede com |N | nós, |A| arcos
e |P| produtos, consiste em uma lista de vetores de fluxo, sendo que o valor contido
na posição k, supondo k 6= α |P| , α ∈ N, representa a quantidade do produto k mod
|P| no arco (k div |P|) + 1; caso k não seja múltiplo da quantidade de produtos,
então o valor contido nessa posição representa a quantidade do produto |P| no arco
(k div |P|). A Figura 6.4 apresenta a estrutura de uma solução s.
A Figura 6.4 descreve uma forma geral da representação exibida pela Figura 3.3.
Cada vetor da lista faz referência a um arco da rede, e cada elemento de um vetor
6.2
Determinação da solução inicial
···
1
|P|
|P| + 1
···
52
|A − 1||P| + 1 · · ·
2|P|
|A||P|
···
arco 1
arco 2
arco |A|
Figura 6.4: Estruturação de uma solução s.
refere-se ao fluxo de um produto.
6.2.2
Determinação da solução inicial
A solução inicial adotada para o PFMI abordado provém de um algoritmo construtivo aleatório, sendo gerada no espaço solução da restrição de capacidade do
problema. Pelo procedimento, a cada produto em cada arco é escolhido um valor
aleatório, o qual, somado ao fluxo dos produtos anteriores, não deve exceder a
capacidade do arco corrente. Desta forma, o fluxo inicial gerado não viola nenhum
arco da rede. O pseudocódigo do método considerado é descrito na Figura 6.5.
procedimento GeraSolucaoInicial
1) Seja |P| a quantidade de produtos e |A| a quantidade de arcos
2) Seja x[k] a quantidade do produto (k mod |P|) no arco (k div |P|)
3) para i = 1 até |A|
4)
aux ← capacidade do arco corrente;
5)
para j = 1 até |P|
6)
aux1 ← valor aleatório entre [0, aux];
7)
x[k] ← aux1;
8)
aux ← aux − aux1;
garantia que o fluxo não exceda
o limite do arco
9)
k = k + 1;
10)
fim-para;
11) fim-para;
Retorne x
fim GeraSolucaoInicial
Figura 6.5: Pseudocódigo do procedimento GeraSolucaoInicial.
6.2.3
Função de avaliação
A função de avaliação consiste na função objetivo do problema, representada pela
expressão (3.1a), acrescida das penalizações oriundas das restrições representadas
pelas expressões (3.1b) e (3.1c). A solução corrente percorre o espaço solução gerado
pela restrição de capacidade (3.1c), não havendo, então, necessidade de se praticar
uma relaxação sobre a mesma. No entanto, o fluxo não é conservado, devido às
perturbações provocadas pela metaheurística ILS. É promovida uma relaxação sobre
a restrição de conservação de fluxo (3.1b), a fim de equilibrar a distribuição dos
6.2
Estruturas de vizinhança
53
produtos entre os centros de oferta e demanda da rede. A função de avaliação é
definida pela expressão (6.1), mostrada a seguir:
f (s) =
P
X
(ci )T xi + α max{0, N x − b}
(6.1)
i=1
O primeiro termo desta expressão representa a própria função objetivo do PFMI,
segundo o modelo apresentado pela expressão (3.1a). O segundo termo se constitui
em um termo de penalização do excesso de fluxo nos nós de oferta/demanda da
rede. O parâmetro α > 0 é o peso atribuído à relaxação feita sobre a restrição de
conservação de fluxo (3.1b). Ele é ajustado conforme as instâncias, equivalendo ao
somatório dos custos dos produtos transportados pelos arcos da rede. Este segundo
termo, portanto, caso detecte um excesso de fluxo no arco (ou seja, infactibilidade da
solução corrente), assumirá valor positivo, penalizando a função objetivo e levando-a
a retornar à factibilidade; caso, por outro lado, detecte a factibilidade da solução,
assumirá valor nulo. Desta maneira, a formulação do problema deixa de ser do tipo
ODE (origem-destino específico), e passa a admitir mais de um centro de oferta
ou demanda por produto, fazendo com que alguns pontos de transbordo tornem-se
pontos de estocagem.
Em Santos et al. (2000) é apresentado um modelo matemático para o problema
de fluxo multiproduto não-linear, o qual faz uso da relaxação sobre a restrição de
conservação de fluxo.
6.2.4
Estruturas de vizinhança
O conjunto solução para o problema tratado pode ser visto como a interseção de
dois subconjuntos gerados pelo espaço solução das restrições (3.1b) e (3.1c).
Conforme a Figura 6.6, o espaço correspondente à restrição de capacidade (3.1c)
é representado pelo subconjunto H, e o espaço referente à restrição de conservação
de fluxo (3.1b) é representado pelo subconjunto C. O espaço de busca das soluções
correntes, obtidas pelo método, faz uso apenas do subconjunto H, sendo essas representadas por s1 , s2 , ..., sk , descrevendo o caminho na obtenção das soluções. Para
exploração do espaço de soluções do PFMI, foi utilizado o movimento de troca entre
fluxos de mesmos arcos. Esse movimento de troca corresponde a permutar o fluxo de
um determinado produto (sorteado aleatoriamente) com o fluxo de outro (também
escolhido de forma aleatória), sendo ambos no mesmo arco.
Desta maneira, as novas soluções geradas permaneceram no espaço de solução
gerado pela restrição de capacidade, já que as soluções geradas anteriormente não
violaram a capacidade do arco objeto do movimento. Note, além disso, que essa
troca corresponde à troca de posições em um mesmo vetor de fluxo, lembrando que
cada vetor de fluxo corresponde a um arco da rede R. Na Figura 6.6, as elipses
concêntricas determinam o lugar geométrico (representação planar) das possíveis
soluções sub-ótimas determinadas pelo método aplicado, caminhando em direção à
solução ótima global presente em algum ponto da intersecção dos conjuntos H e C.
6.2
Aplicação ILS ao PFM
54
s3
s1
s2
sk
H
C
Figura 6.6: Trajetória das soluções sob o espaço de restrições.
6.2.5
Aplicação ILS ao PFM
A fim de resolver o problema de fluxo multiproduto inteiro, cujo modelo de
programação matemática é descrito nas expressões (3.1a) a (3.1d), foi utilizada a
metaheurística ILS (Lourenço et al., 2002), adaptada especificamente ao problema
tratado.
O Método Randômico de Descida (MRD) é o procedimento responsável pela
busca local, refinando a solução perturbada pela metaheurística. No algoritmo desenvolvido, são utilizados os procedimentos DescidaRandomicaComTroca, o qual
representa uma versão do MRD baseada em movimentos de troca entre o fluxo dos
produtos pelos arcos da rede durante a busca, e o procedimento perturbacao, que
também é constituído destes movimentos de troca e que produzirá soluções dentro
do espaço solução gerado pela restrição de capacidade, tornando o fluxo pelos arcos
viável quanto à capacidade dos mesmos. A motivação para a utilização do MRD
baseia-se no baixo custo computacional, quando comparado ao Método de Descida
Clássico.
Foram utilizados 10 níveis de perturbação, que se diferenciam quanto ao tipo
de troca aplicada nas variáveis de fluxo, fazendo uso da aleatoriedade. No primeiro
nível, é realizada uma troca aleatória envolvendo uma variável de fluxo; no segundo
nível, a troca atinge duas variáveis de fluxo, e assim por diante, até atingir os dez
níveis. Inicialmente, é gerada uma solução pelo método descrito na Figura 6.5.
Em seguida, essa solução sofre uma perturbação dentro do espaço H representado
na Figura 6.6, sendo submetida a um refinamento pelo Movimento Randômico de
Descida. Depois de avaliada pelo critério de aceitação, a solução é atualizada, assim
como o número de iterações e o nível de perturbação. O pseudocódigo é apresentado
na Figura 6.7.
6.2.6
Análise dos resultados computacionais
Para a realização dos testes computacionais, foram utilizadas redes com 32 nós,
tendo a quantidade de arcos variando entre 96 e 320 e a quantidade de produtos
6.2
Análise dos resultados computacionais
55
procedimento ILS-Adaptado
1) Seja T o tempo de processamento corrente do algoritmo e T max o
tempo máximo permitido de processamento;
2) Seja ciclos o número de ciclos realizados e CiclosM ax o número
máximo de ciclos permitido;
3) Seja nivel o nível de perturbação corrente;
4) T ← 0; ciclos ← 0; nivel ← 1;
5) Gere uma solução inicial s a partir do método descrito na sub-seção 6.2.3;
6) Faça s∗ ← s, onde s∗ é a melhor solução encontrada;
7) enquanto ((ciclos < CiclosM ax)e(T < T max)) faça
a) s0 ← perturbacao(s∗ , nivel);
b) s0 ← DescidaRandomicaComT roca(s0 );
c) Se (f (s0 ) < f (s∗ )) então;
i) s∗ ← s0 , atualize a melhor solução encontrada;
ii) ciclos ← 0; nivel ← 1;
d) Se (nivel > numN iveis) então ciclos ← ciclos + 1 e
nivel ← 1; onde numN iveis é o número máximo de níveis de
perturbação;
8) Retorne a solução s∗ ;
fim ILS-Adaptado
Figura 6.7: Pseudocódigo da metaheurística ILS-Adaptado.
especificada em 48, 192 e 320, respectivamente. Para cada produto, há um custo
associado, dependente do arco pelo qual ele trafegue. Foram utilizadas as mesmas
instâncias apresentadas na seção 4.5.
O algoritmo ILS foi desenvolvido em linguagem C, usando o compilador Borland
C++ Builder 5.0 e testado em um microcomputador com processador Pentium IV,
2.4 GHz, com 256 MB de memória RAM, sob sistema operacional Windows XP.
Os parâmetros utilizados no algoritmo são exibidos na Tabela 6.1. A referência
Tabela 6.1: Parâmetros presentes no algoritmo ILS.
Parâmetros
Descrição
Valor
Período de tempo máximo de
T max
1800 seg
processamento
CiclosMax
Número máximo de ciclos
2000
numNiveis
Níveis de perturbação
10
P
Penalização sobre a restrição de
α
cij
conservação de fluxo
(i,j)∈A
para os valores dos parâmetros incide sobre a prática das simulações computacionais,
representando limites sobre resultados significativos obtidos. A configuração das
instâncias se dá pela expressão (6.2), ou seja, considerando a instância Bxy−z , tem-
6.2
Análise dos resultados computacionais
56
se que:
x=
l → instância de densidade alta;
s → instância de densidade baixa.
(6.2)
sendo y a quantidade de arcos e z a quantidade de produtos na rede em análise.
A densidade é representada pela razão entre a capacidade (somatório da capacidade dos arcos) e a demanda (somatório das demandas de cada produto) de cada
instância. A qualificação de alta densidade implica numa variação da razão em até
1:10; já a baixa densidade implica em uma variação em até 1:3.
O desempenho do algoritmo ILS adaptado proposto é comparado ao desempenho
do algoritmo ILS clássico quando aplicados ao PFMI, ressalvando que este não faz
uso restrito do espaço solução gerado pela restrição de capacidade. Nas Tabelas 6.2
e 6.3 são apresentados os resultados computacionais obtidos pelos dois algoritmos,
aplicados em instâncias que variam de acordo com a densidade da rede, em relação
à capacidade e demanda, além da quantidade de arcos e produtos.
A Tabela 6.2 representa os resultados das redes de alta densidade, enquanto a
Tabela 6.3 as de baixa densidade. Em ambas as tabelas a mesma nomenclatura
é adotada. A coluna “f ∗ ” representa o valor ótimo da função de avaliação utilizada, considerando como tal a função de avaliação do algoritmo ILS, dada pela
expressão (6.1). A coluna “%” representa a percentagem de arcos violados pelo algoritmo aplicado; a coluna “t” o tempo em segundos, despendido pelo processamento
∗
∗
computacional e, por fim, a coluna “P D” (=|fILS1
− fILS2
|) representa a diferença
em percentagem dos resultados, relativos à aplicação de cada um dos métodos,
levando em conta o valor da função de avaliação. A nomenclatura ILS1 representa
o algoritmo restrito ao espaço solução gerado pela restrição de capacidade e ILS2
representa o algoritmo clássico adaptado para resolver o PFMI.
Tabela 6.2: Resultados computacionais para redes de alta densidade. ILS1: algoritmo ILS-Adaptado; ILS2: algoritmo ILS clássico.
ILS1
ILS2
∗
∗
Instâncias
f
%
t
f
%
t
PD
Bl96−48
4957670 0 26,53 3788042 28,3 11,68 23,59
Bl96−192
2944083 0 26,36 2439149 21,0 24,02 17,15
Bl96−320
2544675 0 73,14 2747307 24,1 52,47 7,38
Bl320−48 11179351 0 41,45 10159259 28,7 22,23 9,12
Bl320−192 10247344 0 104,83 9649701 26,2 144,16 5,83
Bl320−320
8864295 0 280,48 9166921 23,1 171,44 3,30
Médias
25,23
11,06
Conclui-se, pelos dados das tabelas, que em cerca de 60% dos casos, o algoritmo ILS2 apresenta melhor resultado em relação à função de avaliação. Porém,
a quantidade de arcos violados é considerada alta. Para redes de alta densidade, a
quantidade de arcos violados está próxima de 25% do total de arcos existentes na
rede e, para redes de baixa densidade, esse valor se aproxima a 20%.
Cabe ressaltar, além disso, que estes valores obtidos para a função de avaliação
diferem apenas em torno de 10%, quando da aplicação de cada método, em favor
6.3
Simulated Annealing aplicada ao PFMI
57
Tabela 6.3: Resultados computacionais para redes de baixa densidade. ILS1: algoritmo ILS-Adaptado; ILS2: algoritmo ILS clássico.
ILS1
ILS2
∗
∗
Instâncias
f
%
t
f
%
t
PD
Bs96−48
3265437 0 25,77 3466607 25,0 10,30 5,80
Bs96−192 5625599 0 22,00 5115071 29,3 17,75 9,08
Bs96−320 2857068 0 41,51 2154003 21,0 66,06 24,61
Bs320−192 9545462 0 138,52 9636106 23,1 86,72 0,94
Bs320−320 9850022 0 153,45 7747286 19,3 416,70 21,35
Médias
19,62
10,30
do algoritmo ILS2. Ou seja, trata-se de uma pequena diferença de valores, que, de
outro lado, como dito, implica em um aumento no número médio de arcos violados.
Assim, a aparente vantagem do algoritmo ILS2 sobre o ILS1 em relação aos valores
de função de avaliação deve ser contraposta aos problemas decorrentes da perda de
factibilidade.
Outra análise comparativa importante a ser feita entre o comportamento das
duas implementações é com relação ao tempo de processamento computacional. O
maior tempo computacional médio está associado ao algoritmo que garantiu, para as
instâncias analisadas, a obtenção de soluções factíveis, qual seja, o algoritmo ILS1.
No entanto, como anteriormente, esse custo deve ser avaliado à luz da perspectiva de
obtenção de soluções factíveis e de boa qualidade, fato não garantido pelo algoritmo
ILS2, que, por outro lado, leva a menores tempos computacionais. Os resultados
obtidos e comparados entre as duas adaptações da metaheurística ILS apresentadas,
estão presentes em Silva e Souza (2007g).
6.3
Simulated Annealing aplicada ao Problema de
Fluxo Multiproduto Inteiro
Simulated Annealing é uma técnica de busca probabilística, proposta por Kirkpatrick et al. (1983), baseada na termodinâmica, que busca simular o resfriamento
de um conjunto de átomos aquecidos. Partindo de uma solução inicial qualquer, o
procedimento gera, aleatoriamente, em cada iteração, um único vizinho da solução
corrente.
Essa metaheurística é utilizada no presente trabalho para a determinação da
solução inicial do PFMI, para que, junto ao ILS, gerem uma metaheurística híbrida
eficiente para resolver o problema. O resultado híbrido é comparado ao resultado
obtido pela metaheurística pura adaptada, apresentada na seção anterior.
Considere ∆ a variação de valor da função de avaliação ao se mover para uma
solução vizinha candidata, ou seja, ∆ = f (s0 ) − f (s). O método aceita o movimento
e a solução vizinha passa a ser a nova solução corrente se ∆ < 0; caso contrário,
(∆ ≥ 0) e a solução vizinha candidata poderá ser aceita, mas, neste caso, assumindo uma probabilidade e−∆/T , em que T representa um parâmetro denominado
de temperatura.
6.3
Simulated Annealing aplicada ao PFMI
58
procedimento SA
1) s∗ ← s;
(melhor solução obtida)
2) IterT ← 0; (iterações da temperatura T)
3) T ← T0 ;
(temperaura corrente)
4) enquanto (T > 0) faça
5)
enquanto (IterT < SAmax) faça
6)
IterT ← IterT + 1;
7)
Gere um vizinho qualquer s0 ∈ N (s);
8)
∆ = f (s0 ) − f (s);
9)
se (∆ < 0)
10)
então
11)
s ← s0 ;
12)
se (f (s0 ) < f (s∗ )) então s∗ ← s0 ;
13)
senão
14)
Tome x ∈ [0, 1];
15)
se (x < e−∆/T ) então s ← s0 ;
16)
fim-se;
17) fim-enquanto;
18) T ← β × T ;
19) IterT ← 0;
20) fim-enquanto;
21) s ← s∗ ;
22) Retorne s;
fim SA
Figura 6.8: Pseudocódigo para algoritmo Simulated Annealing.
O valor inicial da temperatura pode ser definido de duas maneiras: pela média
dos custos das soluções vizinhas ou por simulação. No primeiro caso, é gerada uma
solução inicial qualquer. Em seguida, gera-se um determinado número de vizinhos
e calcula-se o seu custo. A média dos custos das soluções torna-se a temperatura
inicial.
A temperatura inicial por simulação é gerada a partir de um valor de temperatura
baixo, contando-se a quantidade de vizinhos que são aceitos em um determinado
número de iterações. Caso o número de vizinhos aceitos seja alto, retorna-se o
valor da temperatura corrente como sendo o valor da temperatura inicial; se não,
aumenta-se a temperatura e repete-se o processo.
A temperatura T assume inicialmente um valor T0 , obtido por simulação, que,
após um número fixo de iterações (até o sistema atingir o equilíbrio térmico em uma
dada temperatura), é gradativamente diminuída por uma razão de resfriamento
dada por β, tal que Tk ← βTk−1 , com β ∈ (0, 1). A solução vizinha é obtida por um
movimento de troca entre o fluxo de um produto i e o fluxo de um produto j, ambos
presentes no mesmo arco, ou seja, no mesmo vetor de fluxo. Este tipo de troca
garante a viabilidade da solução em relação à capacitação dos arcos. Os parâmetros
de controle do procedimento são a razão de resfriamento, dada por β = 0,99; o
número de iterações para cada temperatura (SAmax = 100000); e a temperatura
6.3
Aplicação da metaheurísitca híbrida SA-ILS ao PFMI
59
procedimento SA-ILS
1) Seja T o tempo de processamento corrente do algoritmo e T max o
tempo máximo permitido de processamento;
2) Seja ciclos o número de ciclos realizados e CiclosM ax o número
máximo de ciclos permitido;
3) Seja nivel o nível de perturbação corrente;
4) T ← 0; ciclos ← 0; nivel ← 1;
5) Gere uma solução inicial s a partir do método descrito na Figura 6.8;
6) Faça s∗ ← s, onde s∗ é a melhor solução encontrada;
7) enquanto ((ciclos < CiclosM ax)e(T < T max)) faça
a) s0 ← perturbacao(s∗ , nivel);
b) s0 ← DescidaRandomicaComT roca(s0 );
c) Se (f (s0 ) < f (s∗ )) então;
i) s∗ ← s0 , atualize a melhor solução encontrada;
ii) ciclos ← 0; nivel ← 1;
d) Se (nivel > numN iveis) então ciclos ← ciclos + 1 e
nivel ← 1; onde numN iveis é o número máximo de níveis de
perturbação;
8) Retorne a solução s∗ ;
fim SA-ILS
Figura 6.9: Pseudocódigo da metaheurística híbrida SA-ILS.
inicial T0 . O pseudocódigo do método é descrito na Figura 6.8.
6.3.1
Aplicação da metaheurística híbrida SA-ILS ao PFMI
O algoritmo SA-ILS foi desenvolvido sob mesma linguagem de programação e
configuração de hardware utilizada na implementação presente na sub-seção 6.2.6.
O pseudocódigo da metaheurística híbrida SA-ILS é apresentado na Figura 6.9.
O algoritmo SA-ILS adaptado é comparado ao algoritmo ILS aplicado ao PFMI
sob o espaço de restrição de capacidade exibido pela Figura 6.7. Na Tabela 6.4, são
apresentados os resultados computacionais, obtidos pelos dois algoritmos aplicados
em instâncias que variam de acordo com a quantidade de arcos e produtos. A análise
dos resultados apresentados, envolvendo a hibridização heurística proposta, podem
ser também confirmados em Silva e Souza (2007f).
Na Tabela 6.4, a coluna “f ∗ ” representa o valor ótimo da função de avaliação
utilizada, considerando como tal a função, dada pela expressão (6.1). A coluna
∗
∗
“PD”(=|fILS
− fSA-ILS
|) representa a diferença em percentagem sobre os métodos
em relação a função de avaliação; as colunas “t_ILS ” e “t_SA-ILS ”, representam o
tempo em segundos, despendido pelo processamento computacional pelos algoritmos
ILS e SA-ILS respectivamente, por fim, a coluna “PDt”(= |t_SA−ILS−t_ILS|.100
) indica
t_SA−ILS
a diferença em percentagem dos tempos computacionais obtidos pelos algoritmos.
Pela Tabela 6.4, conclui-se que o método SA-ILS, apesar de apresentar maior
tempo computacional, em virtude do acréscimo requerido pela metaheurística Simulated Annealing para obter uma solução inicial, apresenta resultados em média
6.4
Conclusão
60
Tabela 6.4: Resultados computacionais da aplicação da metaheurística híbrida SAILS ao PFMI.
ILS
SA-ILS
Instâncias
f∗
f∗
t_ILS t_SA-ILS PD
PDt
96-48
3279462 3265437
26,05
36,86
0,43 29,31
320-48
10517523 10017484 34,75
64,80
4,75 46,47
320-192
13029738 12509966 94,22
138,76
3,98 32,09
96-192
5625599 4441846
21,70
32,07
21,04 32,33
320-320
19144988 13504288 100,17
126,91
29,46 21,07
Médias
11,93 32,23
11,93% melhores. Essa média varia de acordo com a proporção arcos/produtos
da rede utilizada, girando em torno de 3% para razões menores que um, e cerca
de 25% para razões cuja quantidade de arcos equivale ou supera a quantidade de
produtos.
6.4
Conclusão
Neste capítulo foi apresentada a aplicação das metaheurísticas de busca local
Iterated Local Search e Simulated Annealing ao problema de fluxo multiproduto
inteiro. Nas sub-seções 6.2.1, 6.2.3 e 6.2.4, foram apresentados, respectivamente,
o significado e a representação de uma solução utilizada por ambas as técnicas;
a função de avaliação empregada, levando em consideração a penalização sobre a
restrição de conservação de fluxo, tornando alguns pontos do grafo, centros de estocagem de produtos; e a descrição da estrutura de vizinhança adotada, na qual as
soluções produzidas pertencem ao espaço solução gerado pela restrição de capacidade, não violando o limite de fluxo da capacidade dos arcos presentes na rede.
Foram implementados três algoritmos, sendo o primeiro utilizando a metaheurística Iterated Local Search (ILS), não considerando o espaço gerado pela restrição de
capacidade; a segunda implementação foi feita utilizando a mesma metaheurística,
porém, sob o espaço de capacidade; e, na terceira implementação, foi utilizada a
metaheurística Simulated Annealing para gerar uma solução inicial e, posteriormente, compor a hibridização heurística junto ao ILS, para resolver o problema.
Foi possível constatar a relevância do espaço utilizado pelas metaheurísticas como
espaço de busca. Através desse espaço, foi possível gerar soluções de melhor qualidade. Outro fato a ser mencionado é a respeito da hibridização heurística, a qual
foi capaz de melhorar a solução gerada por uma metaheurística simples.
Capítulo 7
Conclusão Geral e Trabalhos Futuros
Este trabalho teve como foco principal os problemas de fluxo multiproduto inteiro (PFMI). O tema foi apresentado segundo a abordagem de tópicos como: a
modelagem matemática e computacional do problema; a pré-otimização aplicada
ao PFMI; a análise da região de vizinhança utilizada pelos métodos heurísticos; e
a comparação entre metaheurístiscas de busca local, na tentativa de solucionar o
problema.
Na primeira abordagem, foi descrita a formulação matemática do problema,
além da análise referente às estruturas algébricas presentes nas restrições de conservação de fluxo e restrição de capacidade. Utilizou-se a representação das estruturas matemáticas por lista lineares, a fim de facilitar as operações realizadas pelos
métodos heurísticos. Este modelamento computacional foi idealizado tanto para
as metaheurísticas locais (Iterated Local Search e Simulated Annealing), pelas quais
foram realizados os teste computacionais, quanto para a metaheurística populacional
(Algoritmo Genético), a qual foi descrita com um modelamento teórico baseado em
suas características evolutivas.
Na segunda abordagem, foi apresentado um conceito sobre pré-otimização à
classe de problemas tratados neste trabalho. Utilizando a formulação origem-destinoespecífico foi possível constatar a presença de sistemas lineares homogêneos, referentes à restrição de conservação de fluxo. Conforme a densidade da rede apresentada,
especialmente se a quantidade de produtos for maior do que a quantidade de arcos,
foi possível determinar soluções prévias. A aplicação deste conceito produziu uma
redução em cerca de 26% na dimensão do PFM tratado, apesar de que, em algumas
redes, não foi possível determinar nenhuma solução prévia. Porém, em virtude de
seu baixo custo computacional e simplicidade de implementação do algoritmo de
pré-otimização apresentado, este conceito torna-se bastante interessante no intuito
de pré-condicionar o problema abordado.
Na terceira abordagem, foi apresentado um detalhamento matemático sobre a
região de busca utilizada pelas metaheurísticas. Foi possível constatar que o número
de produtos gera maior dimensão ao PFMI. Entretanto, o número de arcos gera um
crescimento maior da dimensão. Além disso, foi exibida a enumeração de tal região,
refletindo a grande dificuldade de se resolver essa classe de problemas.
Na quarta e última abordagem, foram feitos testes computacionais utilizando as
metaheurísticas de busca local Iterated Local Search (ILS) e Simulated Annealing
(SA) para resolver o PFMI. Foram implementados três algoritmos. O primeiro
61
7.0
Conclusão Geral e Trabalhos Futuros
62
retrata uma aplicação da metaheurística ILS, não restrita à região de busca explicitada pela última abordagem. O segundo algoritmo implementado incide sobre a
metaheurística ILS, restrita ao espaço gerado pela restrição de capacidade. Nos dois
casos, é utilizada a geração construtiva aleatória para produzir a solução inicial.
Quando comparados, o valor da função de avaliação diferiu em cerca de 10% em
vantagem ao primeiro algoritmo, porém, o mesmo apresentou cerca de 20 a 25% de
arcos violados, gerando infactibilidade. Por esse motivo, o segundo algoritmo tornouse mais eficiente, não violando a capacidade de nenhum arco da rede. Tais fatos
tornam interessante o uso do espaço de busca gerado pela restrição de capacidade.
No terceiro algoritmo, foi utilizada uma metaheurística probabilística de busca local para a geração da solução inicial, promovendo a construção de algoritmo híbrido.
Quando comparado ao segundo algoritmo, pode-se constatar que, apesar de apresentar um maior tempo computacional, em virtude do uso da metaheurística SA para a
obtenção da solução inicial, os resultados obtidos pelo terceiro algoritmo foram cerca
de 12% mais eficientes. Isto torna interessante a idéia de hibridização heurística,
para a resolução da classe de problemas abordados neste trabalho.
Como trabalhos futuros, pretende-se estender o conceito de otimização para a fase
de pós-otimização, utilizando, por exemplo, a técnica de reconexão por caminhos.
Espera-se, futuramente, realizar os testes computacionais segundo a modelagem
matemática e computacional bio-inspirada para o PFMI apresentada no capítulo
3. Estes resultados seriam comparados aos obtidos no capítulo 6, promovendo uma
comparação entre metaheurísticas da classe local e populacional. Outro objetivo
futuro é o de realizar os testes com instâncias de maior porte e verificar a eficiência
tanto dos métodos heurísticos restritos ao espaço de buscal descrito neste trabalho,
quanto à técnica de pré-otimização apresentada.
Apêndice A
Algoritmo Recursivo para
Determinação da Dimensão do
Espaço-Solução
#include <stdlib.h>
#include <stdio.h>
double arcos = 20;
double arcos = 20;
double produtos = 5;
double soma = 0;
double soma_anterior = 0;
double total = 0;
double produtorio = 1;
double aux = 0;
long int *u;
double k(double m, double n) {
int i;
if ((n==1))
return(1);
else
{
if (m==1)
return(k(1,n-1) + n);
else
{
if (m!=1)
{
for(i=1;i<=n;i++)
soma+= k(m-1,i);
}
}
63
A
Dimensão do espaço-solução
}
soma_anterior = soma - soma_anterior;
soma = soma_anterior;
return(soma_anterior);
}
int main() {
int i, j, m, a;
i=j=m=a=0;
u = (long int *)malloc((arcos+1)*sizeof(long int));
u[1] = 10;
m = 1;
for(a=1;a<=arcos;a++){
for(i=1;i<=produtos-2;i++)
for(j=1;j<=u[m];j++)
//depois trocar m por a
{
aux += k(i,j);
}
//printf("%f\n",k(3,1));
//total = soma\_anterior + k(1,u[m]) + (u[m]+1);
total = aux + k(1,u[m]) + (u[m]+1);
produtorio = produtorio*total;
}
//printf("%f\n",aux + k(1,u[m]) + (u[m]+1));
printf("%f\n",produtorio);
//printf("%f\n",total);
//printf("%d\n",soma_anterior + k(1,u[m]) + (u[m]+1));
getchar();
return(0);
}
64
Apêndice B
Algoritmos de Pré-otimização
SEM PRÉ-OTIMIZAÇÃO
Código C (Obtendo registro a partir do arco )
find( int linha, int p, struct lista *x) {
int i;
int total = 0;
int inicio,fim;
inicio = (linha-1)*p;
fim = linha*p;
for(i=inicio;i<=fim;i++)
total+= x[i].valor;
//return (?)
//inicio da sub-lista
//fim da sub-lista
//fluxo no arco ’linha’
a cargo do usuario
}
Código C (Obtendo registro a partir do produto)
find( int coluna, int p, int a, struct lista *x) {
int i,pos;
int total = 0;
inicio = (1-1)*p + coluna;
fim = (a-1)*p + coluna;
for(i=inicio;i<=fim;i++){
pos = (i-1)*p + coluna;
total+= x[pos].valor; }
//return (?)
//inicio da sub-lista
//fim da sub-lista
// posicao do registro corrente
//fluxo do produto ’coluna’ em todos arcos
a cargo do usuario
}
65
B
Pré-Otimização
66
COM PRÉ-OTIMIZAÇÃO
Código C (Obtendo registro a partir do arco)
find( int linha, int *t, struct lista *x) {
int i;
int total = 0;
int inicio=fim=0;
for(i=1;i<=linha-1;i++)
inicio+= t[i];
inicio+=1;
//inicio da sub-lista
for(i=1;i<=linha;i++)
fim+= t[i];
//fim da sub-lista
for(i=inicio;i<=fim;i++)
total+= x[pos].valor;
//fluxo no arco ’linha’
//return (?)
a cargo do usuario
}
Código C (Obtendo registro a partir do produto)
find( int coluna, int a, int *t, struct lista *x) {
int i,j;
int total =pos= 0;
for(j=1;j<=a-1;j++){
if t[j]>0{
pos = 0;
for(i=1;i<=j;i++)
pos+= t[i];
pos+= coluna;
}
total+= x[pos].valor;
}
//return (?)
}
//fluxo do produto ’coluna’ em todos arcos
a cargo do usuario
Referências Bibliográficas
Ahuja, R.K.; Magnanti, T.L. e Orlin, J.B. (1993). Network Flows. Prentice Hall,
New York, USA.
Alminana, M.; Escudero, L.F.; Monge, J.F. e Soriano, J.S. (2007). On the enrouting protocol problem solving under uncertainty. European Journal of Operational
Research, v. 181, n. 2, p. 887–902.
Alvelos, F.P. Branch-and-price and multicommodity flows. PhD thesis, Departamento de Produção e Sistemas da Escola de Engenharia, Universidade do Minho,
Portugal, (2005).
Barnhart, C.; Hane, C.A.; Johnson, E.L. e Sigismondi, G. (1995). A column generation and partitioning approach for multicommodity flow problems. Telecommunications Systems, v. 3, n. 3, p. 239–258.
Barnhart, C.; Hane, C.A. e Vance, P.H. (1996). Integer multicommodity flow problems. Lectures Notes in Economic and Mathematical Systems 450, v. , p. 17–31.
Barnhart, C.; Hane, C.A. e Vance, P.H. (2000). Using branch-and-price-and-cut to
solve origin-destination integer multicommodity flow problems. Operations Research,
v. 48, n. 2, p. 318–326.
Bazaraa, M.S.; Jarvis, J.J. e Sherali, H.D. (1990). Linear Programming and Network
Flows. Wiley, New York, USA.
Becceneri, J.C. (2007). Meta-heurísticas e otimização. Relatório técnico, Laboratório
Associado de Computação e Matemática Aplicada (LAC), INPE.
Blickle, T. Theory of evolutionary algorithms and application to system synthesis.
PhD thesis, Swiss Federal Institute of Technology, Zurique, (1996).
Boman, E. e Hendrickson, B. (2004). Support theory of preconditioning. SIAM
Journal of Matrix, v. 25, n. 3, p. 697–717.
Bradley, S.P. (1965). Solution techniques for the traffic assignment problem. Relatório técnico, University of California, Berkley, USA.
Carrano, E.G.; Neto, O.M. e Takahashi, R.H.C. (2004). Algoritmos genéticos aplicados ao projeto e planejamento de expansão de redes de distribuição de energia
elétrica. Anais do XV Congresso Brasileiro de Automática, Gramado, RS.
67
Referências Bibliográficas
68
Castro, J. (2003). Solving difficult multicommodity problems with a specialized
interior-point algorithm. Annals of Operations Research, v. 124, p. 35–48.
Clark, S. e Surkis, J. (1968). An operations research approach to racial desegregation
of school systems. Socio-Econ. Plan. Sci., v. 1, n. 3, p. 259–272.
Coelho, A.M. Uma abordagem via algoritmos meméticos para a solução do problema
de horário escolar. Dissertação de Mestrado, Modelagem Matemática e Computacional, CEFET-MG, Belo Horizonte, (2006).
Cordeau, J.; Laporte, G. e Pasin, F. (2006). An iterated local search heuristic for
the logistics network design problem with single assignment. International Journal
of Production Economics, v. .
Erickson, M.; Resende, M.G.C e Pardalos, P.M. (2002). A genetic algorithm for the
weight setting problem in OSPF routing. Combinatorial Optimization, v. 6, n. 3, p.
299–333.
Farvolden, J.M.; Powell, W.B. e Lustig, I.J. (1993). A primal partitioning solution
for the arc-chain formulation of a multicommodity network flow problem. Operations
Research, v. 41, n. 4, p. 669–693.
Ford, L.R. e Fulkerson, D.R. (1962). Flows in Network. Princeton University Press.
Gendron, B.; Crainic, T. e Frangioni, A. (1998). Multicommodity capacitated
network design. Telecommunications Network Planning, v. , p. 1–19.
Geoffrion, A.M. e Graves, G.W. (1974). Multicommodity distribution system design
by benders decomposition. Management Science, v. 20, n. 5, p. 822–844.
Goldbarg, M.C. e Luna, H.P.L. (2005). Otimização Combinatória e Programação
Linear. Campus/Elsevier.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine
Learning. Addison-Wesley, Menlo Park, CA, USA.
Golub, G.H. e Loan, C.F. Van. (1996). Genetic Algorithms in Search, Optimization
and Machine Learning. Johns Hopkins University Press, Baltimore.
Gorman, M.F. (1998). An application of genetic and tabu searches to the freight
railroad operating plan problem. Annals of Operations Research, v. 78, p. 51–69.
Gremban, K.D.; Miller, G.L. e Zagha, M. (1994). Performance evaluation of a new
parallel preconditioner. Relatório Técnico CMU-CS-94-205, School of Computer
Science, Carnegie Mellon University.
Grötschel, M.; Monma, C.L. e Stoer, M. (1995). Design of survivable networks.
Network Models, v. 7, p. 617–672.
Hax, A.C. e Candea, D. (1984). Production and Inventory Management. Englewood
Cliffs, N.J. : Prentice-Hall.
Referências Bibliográficas
69
Holland, J. (1975). Adaptation in Natural and Artificial Systems. University of
Michigan Press, Ann Arbor.
Hu, T.C. (1963). Multicommodity network flows. Operations Research, v. 11, p.
344–360.
Hu, T.C. (1969). Integer Programming and Network Flows. Addison-Wesley.
Jones, K.L.; Lustig, I.J.; Farvolden, J.M. e Powell, W.B. (1992). Multicommodity
network flows: The impact of formulation on decomposition. Relatório Técnico
SOR-91-23, Princeton University.
Kennington, J.L. e Helgason, R.V. (1980). Algorithms for Network Programming.
John Wiley & Sons Inc.
Kirkpatrick, S.; Gellat, J.C. e Vecchi, M.P. (1983). Optimization by simulated
annealing. Science, v. 220, n. 4598, p. 671–680.
Lasdon, L.S. (1970). Optimization Theory for Large Systems. MacMillan Publishing.
Lourenço, H. R.; Martin, O. e Stuetzle, T. (2002). Iterated local search. Handbook
of Metaheuristics, v. 7, p. 321–353.
Maggs, B.; Miller, G.; Parekh, O.; Savi, R. e Wu, S. Solving symmetric diagonallydominant systems by preconditioning, (2002).
Mccallum, J.C.J. (1977). A generalized upper bounding approach to communications network planning problem. Networks, v. 7, n. 1, p. 1–23.
Michalewicz, Z.; Vignaux, G.A. e Hobbs, M. (1991). A nonstandard genetic algorithm for the nonlinear transportation problem. ORSA J. Comput., v. 3, p.
307–316.
Microcal Software, Inc. Data analysis and technical graphics software. Origin Version 6.0. Northampton, MA, EUA, (1999).
Moscato, P. (2001). Memetic Algorithms. Oxford University Press.
Moz, M. e Pato, M.V. (2003). An integer multicommodity flow model applied to
the rerostering of nurse schedules. Annals of Operations Research, v. 119, n. 1-4, p.
285–301.
Naniwada, M. (1969). Multicommodity flows in a communication network. Eletronics and Communications in Japan, v. 52-A, n. 11, p. 34–41.
Ozdaglar, A.E. e Bertsekas, D.P. June(2003). Optimal solution of integer multicommodity flow problems with application in optical networks. Proceedings of
Symposium on Global Optimization, p. 411–435, Santorini, Greece.
Pioró, M. e Gajowniczek, P. (1997). Solving multicommodity integral flow problem
by simulated allocation. Telecommunication Systems, v. 7, p. 17–28.
Referências Bibliográficas
70
Potts, R.B. e Oliver, R.M. (1972). Flows in Transportation Networks. Academic
Press.
Przewozniczek, M. e Walkowiak, K. (2005). Evolutionary algorithm for congestion
problem in connection-oriented networks. Lecture notes in Computer Science, v.
3483, p. 802–811.
Rardin, R.L. e Choe, U. (1979). Tighter relaxations of fixed charge network flow
problems. Relatório Técnico J-79-18, School of Industrial and Systems Engineering,
Georgia Institute of Technology.
Rardin, R.L. e Wolsey, L.A. (1993). Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems.
European Journal of Operational Research, v. 71, n. 1, p. 95–109.
Resende, M.G.C. e Veiga, G. (2003). An annotated bibliography of network interior
point methods. Networks, v. 42, n. 2, p. 114–121.
Santos, M.A.; Bocanegra, S.R. e Campos, F. (2000). Uma proposta de solução para
o problema não linear de fluxo multiproduto utilizando pontos interiores. Anais da
Semana de Ciência da Computação - UFL, volume 1, p. 69–73, Lavras, MG.
Schultz, G.L. e Meyer, R.R. (1991). An interior point method for block angular
optimization. SIAM Journal on Optimization, v. 1, n. 4, p. 583–602.
Shan, Y.-S. A Dynamic Multicommodity Network Flow Model for Real Time Optimal
Rail Freight Car Management. PhD thesis, Princeton University, Canada, (1985).
Sheng, S.; Dechen, Z. e Xiaofei, X. (2006). Genetic algorithm for the transportation
problem with discontinuous piecewise linear cost function. International Journal of
Computer Science and Network Security, v. 6, n. 7, p. 182–189.
Silva, C. A. (2007)a. Arquivos de dados para análise do espaço solução do pfmi.
http://www.calex.mat.br/arquivos/MMC/multicommodity_solution_space.txt
Último acesso em 27/04/2007.
Silva, C. A. (2007)b. Parâmetros para análise de dados do espaço solução do pfmi.
http://www.calex.mat.br/arquivos/MMC/origin.txt Último acesso em 27/04/2007.
Silva, C.A.; Mourão, F.P. e Souza, S.R. agosto(2007)a. Dimensionamento da região
de vizinhança para uma abordagem heurística ao problema de fluxo multiproduto.
II SMAT/ERMAC - II Simpósio de Matemática, p. 1–6, Presidente Prudente, SP.
Silva, C.A.; Mourão, F.P. e Souza, S.R. novembro(2007)b. Discretização do dimensionamento de um problema de fluxo multiproduto. Anais do VII ERMAC(R3) Encontro Regional de Matemática Aplicada e Computacional (Regional 3), Recife,
PE.
Silva, C.A. e Souza, S.R. junho(2007)a. Análise do espaço solução de um problema de fluxo multiproduto inteiro. Anais do VII ERMAC - Encontro Regional de
Matemática Aplicada e Computacional, p. 171–175, Uberlândia, MG.
Referências Bibliográficas
71
Silva, C.A. e Souza, S.R. novembro(2007)b. Modelagem computacional bio-inspirada
aplicada a problemas de fluxo multiproduto. Anais do X EMC - Encontro de Modelagem Computacional, Nova Friburgo, RJ.
Silva, C.A. e Souza, S.R. novembro(2007)c. Modelamento matemático e computacional para uma abordagem heurística de busca local a problemas de fluxo multiproduto inteiro. Anais do X SPOLM - Simpósio de Pesquisa Operacional e Logística
da Marinha, Rio de Janeiro, RJ.
Silva, C.A. e Souza, S.R. junho(2007)d. Pré-otimização via resolução de sistemas
lineares homogêneos iterados para problemas de fluxo multiproduto inteiro. Proceedings of XXVIII CILAMCE - Iberian Latin American Congress on Computational
Methods in Engeeniering, p. 1–11, Porto, Portugal.
Silva, C.A. e Souza, S.R. junho(2007)e. Um algoritmo iterativo polinomial de précondicionamento aplicado a problemas de fluxo multiproduto. Anais do I ERPO Encontro Regional de Pesquisa Operacional do Nordeste, p. 1–11, Recife, PE.
Silva, C.A. e Souza, S.R. setembro(2007)f. Uma aplicação da metaheurística híbrida
simulated annealing-iterated local search ao problema de fluxo multiproduto sob o
espaço capacitado. Anais do XXX CNMAC - Congresso Nacional de Matemática
Aplicada e Computacional, p. 1–6, Florianópolis, SC.
Silva, C.A. e Souza, S.R. agosto(2007)g. Uma aplicação da metaheurística iterated
local search ao problema de fluxo multiproduto inteiro sob o espaço de restrição de
capacidade. Anais do XXXIX SBPO - Simpósio Brasileiro de Pesquisa Operacional,
Fortaleza, CE.
Silva, C.A. e Souza, S.R. novembro(2007)h. Uma metodologia heurística de busca
local para a resolucão de problemas de fluxo multiproduto inteiro. Anais do VII
Congreso Chileno de Investigación Operativa, Puerto Montt, Chile.
Spielman, D. e Teng, S. (2003). Solving sparse, symmetric, diagonally-dominant
linear systems in time o(m1.31 ). Proceedings of the 44th Annual IEEE Symposium
on Foundations of Computer Science, p. 416–427, Cambridge, MA, USA.
Staniec, C.J. Solving the Multicommodity Transshipment Problem. PhD thesis,
Naval Postgraduate School, Monterey, California, (1987).
Tu, M.-Y.; Tsai, F. T.-C. e Yeh, W.W.-G. (2005). Optimization of water distribution
and water quality by hybrid genetic algorithm. Journal of Water Resources Planning
and Management, v. 131, n. 6, p. 431–440.
Vaidya, P. Solving linear equations with symmetric diagonally dominant matrices
by constructing good preconditioners, (1991).
Verweij, B.; Aardal, K. e Kant, G. (1997). On an integer multicommodity flow
problem from the airplane industry. Relatório Técnico UU-CS-38, Department of
Computer Science, Utrecht University, Utrecht.
Referências Bibliográficas
72
Yang, X.Q.; Mees, A.I. e Campbell, K. (2000). Simulated annealing and penalty
methods for binary multicommodity flow problems. Progresss in Optimization: Contributions from Australasia, v. 1, p. 93–105.