Uma abordagem alternativa ao problema de calcular pares de caminhos disjuntos de custo mínimo com custos duais (c1e c2) foi proposta em Gomes et al. (2006b)3.
Nesta abordagem pretendeu-se resolver o problema usando um algoritmo de k- caminhos mais curtos (foi usado o algoritmo MPS, descrito em Martins et al., 1999) e o algoritmo de Dijkstra. O MPS foi usado para obter um caminho (p) usando um conjunto de custos e o algoritmo de Dijkstra usou o outro conjunto de custos para obter outro caminho (q(p)) num conjunto de arcos aos quais foram retirados os arcos presentes em p.
O algoritmo (designado por DP2LC e descrito em Gomes et al., 2006a,b) fun- ciona usando simultaneamente a abordagem para os dois conjuntos de custos.
Para tal são criados dois conjuntos (A e B) de pares de caminhos, A usando c1
com o algoritmo MPS e c2 com o algoritmo de Dijkstra, e B usando c2 com o
MPS e c1 com o Dijkstra. É possível provar (Gomes et al., 2006b) que usando
em cada momento os elementos de A e B que apresentam menor custo agre-
gado ( sejam estes Ah com custo agregado C(Ah) = c1(pAh) +c
2(q(p
Ah)) e Bk
com custo agregado C(Bk) =c2(pBk) +c
1(q(p
Bk))) é possível obter a partir des-
tes um limiar superior (upper bound) e um limiar inferior (lower bound) para o valor da solução de menor custo agregado. Após encontrar um primeiro par de caminho admissíveis em cada conjunto é possível verificar se se encontrou o óptimo (se os dois limiares forem coincidentes) ou então procurar estreitar os limiares, procurando novos pares (admissíveis) em qualquer dos conjuntos que apresentem custos agregados menores que o custo agregado já encontrado para esse conjunto. A pesquisa de novos pares efectua-se de forma alternada nos dois conjuntos, para que de cada vez que se encontre um novo par com custos agrega- dos menores que o menor desse conjunto, se possa obter um novo limiar inferior, maior ou igual ao anterior. Se o custo agregado encontrado for menor que todos os encontrados até então obtêm-se também um novo limiar superior, inferior ao anterior, e a pesquisa passa a efectuar-se no outro conjunto.
Na presença de recursos computacionais (memória e tempo de CPU) ilimita- dos, o algoritmo permite resolver de forma exacta o problema. No entanto, se se considerarem limitações nestes recursos (algo que é provável em aplicações de encaminhamento com um tempo limitado para chegar à solução) o algoritmo pode chegar a soluções sub-óptimas: aquelas em que não foi possível atingir a 3A autora desta dissertação esteve envolvida neste e no próximo algoritmo na área da definição das experiências para validação dos mesmos e na obtenção e análise dos resultados, mas não na criação dos algoritmos.
E E¯
Z ([0, 10000];([0, 100];[0, 100])[0, 10000]) ([0, 100];([0, 10];[0, 10000])[0, 10000])
¯
Z ([1, 10000];([1, 100];[1, 100])[1, 10000]) ([1, 100];([1, 10];[1, 10000])[1, 10000])
Tabela 3.32:Símbolos correspondentes a gamas de custos.
solução óptima (ou mesmo que tenha sido possível atingi-la não se conseguiu ve- rificar a optimalidade da mesma). O algoritmo permite mesmo nestes casos obter uma medida aproximada da qualidade de uma solução sub-óptima, através do cálculo da distância entre os limiares superior e inferior. O número total de itera- ções a realizar para atingir o óptimo depende da topologia da rede (em princípio, se existirem muitos caminhos alternativos com o mesmo custo a progressão em direcção ao óptimo será mais lenta) mas a existência de limiares permite também considerar a hipótese de parar quando o benefício potencial máximo de atingir o óptimo for inferior a um determinado valor predefinido.
Este algoritmo foi validado através de um conjunto de experiências que pre- tenderam verificar a adequação do algoritmo para utilização prática, quer em termos de tempo necessário para o cálculo quer em termos de distância máxima ao óptimo nas soluções sub-óptimas e qual o seu número. Para tal foram geradas aleatoriamente conjuntos de redes com diferentes números de nós, densidades diferentes e diferentes valores para as gamas de custos. A análise foi efectuada tanto em redes dirigidas com em redes não dirigidas. Nesta secção são apre- sentados alguns resultados para o caso de redes dirigidas, do qual um conjunto mais alargado de resultados pode ser encontrado em Gomes et al. (2006a). Re- sultados para o caso particular de redes não dirigidas foram também publicados em Gomes et al. (2006c).
Numa primeira experiência, foram geradas redes dirigidas conexas com um número de nós n com valores de 50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 600 e 800. Para cada uma destas foram gerados um número de arcos m cor- respondente a 3n, 4n e 6n. Para estas redes foram usados custos duais gerados aleatoriamente por ramo usando gamas predefinidas de valores possíveis para cada um dos conjuntos de custos. As combinações de gamas escolhidas (8 no total) encontram-se referenciadas na Tabela 3.32, e classificadas em função das suas propriedades: assim, foram geradas gamas de custos “iguais” – ou melhor,
aleatórias sobre um mesmo domínio – denotadas por gamasE – e gamas em que
0,000% 0,003% 0,005% 0,008% 0,010% 0,013% 0,015% 0,018% 0,020% 0,023% 250 300 400 450 500 600 800 100 200 250 300 350 400 450 500 600 800 4 6 [0,10] - [0,10000] [0,100] - [0,10000] [1,100] - [1,10000]
Figura 3.17:Percentagem de soluções sub-óptimas, em rede com soluções sub-óptimas para m= 4n, 6n e gamas ¯E.
nulo4– gamasZ – e gamas que não incluem a possibilidade de custos nulos – ga-
mas ¯Z. Nesta experiência foram calculados caminhos disjuntos de custo mínimo
para todos os pares existentes (no total n× (n−1) em cada rede). Os valores
apresentados para cada valor de m, n e gama de custos são médias obtidas em conjuntos de 10 redes.
A experiência foi executada com limitações de memória máxima usada, mas sem limitações de tempo de processamento. No respeitante à capacidade de atingir o óptimo, os resultados das experiências mostram que tal apenas não
ocorreu para a gama ¯E com densidades m=4n e m=6n. Mesmo nestas redes o
óptimo foi atingido em mais de 99.97% dos casos (ver Figura 3.17, sendo de notar que apenas se calcularam percentagens para as redes onde existiram soluções sub-óptimas).
Em termos de tempo de processamento, mesmo incluindo o tempo dos pares em que não se chegou ao óptimo (e que demoraram até terminar muito mais que a média) o tempo por par calculado foi bastante pequeno. Nas gamas E o tempo foi inferior a 2ms mesmo nas redes mais densas e com mais nós (como se pode verificar na Figura 3.18a, sendo de notar que esta gama não apresentou soluções sub-óptimas). Mesmo em gamas que apresentaram soluções sub-óptimas, como
foi o caso das gamas ZE¯ apresentadas na Figura 3.18b o tempo médio de CPU
por par não excedeu os 60ms.
No entanto, como podemos concluir combinando estes resultados com os an- teriores (e foi verificado noutros resultados), tal significou que nalguns pares o algoritmo demorou tempo significativo, antes de atingir o óptimo ou de termi- nar com solução sub-óptima. Estes resultados parecem apontar para a vantagem 4Deve ser notado que embora os custos nulos sejam possíveis nas gamasZ, as dimensões efectiva
0 0,2 0,4 0,6 0,8 1 1,2 1,4 200 500 800 200 500 800 200 500 800 3 4 6 ms [1,100] - [1,100] [1,10000] - [1,10000] (a) Gamas ¯ZE 0 10 20 30 40 50 60 200 500 800 200 500 800 200 500 800 3 4 6 ms [0,10] - [0,10000] [0,100] - [0,10000] (b) GamasZE¯
Figura 3.18:Tempo médio de CPU por par de nós para n=200, 500, 800 e m=3n, 4n, 6n.
0 0,005 0,01 0,015 0,02 0,025 250 300 400 450 500 600 800 100 200 250 300 350 400 450 500 600 800 4 6 [0,10] - [0,10000] [0,100] - [0,10000]
Figura 3.19: Desvio normalizado máximo associado às soluções sub-óptimas, para m = 4n, 6n e gamasZE¯.
de limitar em aplicações reais o tempo de CPU a atribuir ao algoritmo para a resolução do problema, no pressuposto de que o valor máximo de desvio do óp- timo associado às soluções sub-óptimas não é elevado, o que se verificou nesta experiência, ver Figura 3.19. Nesta figura o valor apresentado corresponde ao intervalo entre limiares na solução sub-óptima, dividido pelo valor do limiar in- ferior, o que permite de alguma forma apresentar um valor normalizado para o desvio máximo em relação ao óptimo, e que se verifica nunca ser superior a 3% do valor do limiar inferior
Uma segunda experiência realizada com este algoritmo comparou o algoritmo DP2LC com a formulação do problema como um problema de programação linear inteira (designado algoritmo PLI), resolvido usando a ferramenta ILOG
CPLEX 10.110 na mesma máquina (Pentium IV a 3.2GHz com 2GB de RAM).
Para esta experiência usaram-se redes mais densas (densidades iguais a 10% e
20% do número de arcos totais possíveis) e valores de n mais espaçados (n =
50, 100, 200, 400, 800, 1600, 3200), com as mesmas gamas de custos referidas ante- riormente. Para este exemplo foram testados apenas 100 pares de nós para cada rede, gerados aleatoriamente.
Esta comparação permitiu verificar que o algoritmo DP2LC obtém resultados mais rapidamente que a implementação PLI (desde cerca de 10 vezes mais rápido em redes maiores e mais densas até cerca de 25 vezes mais rápido em redes me- nores e menos densas). A Figura 3.20 ilustra estes resultados, mas também uma maior volatilidade em termos de tempo necessário por resolução no algoritmo DP2LC, em contraste com durações muito mais uniformes na resolução usando o CPLEX. O algoritmo DP2LC gerou também neste caso algumas soluções sub- óptimas, mas raramente (115 casos em 112000 pares testados, ou seja, perto de 0, 1%). A implementação PLI não conseguiu resolver o caso da maior rede com maior densidade.
3.3.3 Um algoritmo para obter o conjunto de pares de caminhos disjuntos