Optimização vectorial em redes

Abstract

O trabalho apresentado consiste numa abordagem teórica e prática do problema do trajecto mais curto multi-objectivo. Neste âmbito, são analisadas questões como a finitude e o princípio de optimalidade, considerando quer valores positivos quer negativos para os custos dos arcos. A utilização de custos irracionais permitiu encontrar novas propriedades do problema do trajecto mais curto. Do ponto de vista computacional, foram implementados mais de 80 códigos baseados não só no algoritmo de rotulação e no de enumeração de trajectos, mas também num terceiro algoritmo resultante da fusão dos dois anteriores. É sugerida uma simplificação do teste de dominância e proposta uma nova abordagem para o estudo da ordem de complexidade em problemas multi-objectivos. A evolução do número de trajectos não dominados foi estudada através de modelos polinomiais (obtidos por regressão linear). Conclui-se, assim, que esse número não varia significativamente com o intervalo onde são gerados os custos; aumenta sub-linearmente com o número de nós e quadraticamente com a densidade e número de objectivos. É realizada uma vasta experiência computacional sobre redes cíclicas geradas aleatoriamente (atingindo instâncias com 10000 nós, 60000 arcos e 6 objectivos) a partir da qual se obtiveram modelos polinomiais para o tempo de processamento e para o espaço de memória. A dimensão dos problemas propostos é superior aos apresentados na literatura consultada. As conclusões que se puderam retirar foram: • o algoritmo de rótulos definitivos revelou-se ligeiramente mais ineficiente do que o algoritmo de rótulos temporários; • o algoritmo de enumeração de trajectos é ineficiente; • o algoritmo de fusão, quando utilizada a enumeração de trajectos sequencial, revelou-se como sendo o mais eficiente.