Um Algoritmo Polinomial para Problemas Tri-Objetivo de Otimização de Caminhos em Grafos
Autores
|
4382 |
3,1963
|
|
|
4383 |
3,1963
|
Informações:
Publicações do PESC
O foco deste trabalho é o problema de caminho ótimo tri-objetivo onde duas funções objetivo são do tipo gargalo, por exemplo, MinMax ou MaxMin. A terceira função objetivo pode ser do mesmo tipo ou podemos considerar uma função linear, por exemplo, MinSum ou MaxProd. Um algoritmo O(m2n2é) apresentado para gerar o conjunto mínimo completo de soluções Pareto-ótimas, onde n e nz são o número de nós e arcos do grafo. A geração do conjunto máximo completo também é possível. Demonstrações de otimalidade do algoritmo e extensões para vários casos especiais são apresentadas. Experimentos computacionais para problemas gerados aleatoriamente também são apresentados.
Tlie focus of tliis work is tlie tricriterion optiinal path problem where two objective functions are of the bottleiieck type, for example, MinMax or MaxMin. The tliird objective f~iiictioni nay be of tlie same Irind or we may consider a linear objective f~inctionli ke, for exainple, MinSuin or MaxProd. Ai1 O(m2n2) algorithm is presented that inay generate the iniiliinal complete set of Pareto-optimal solutions where n and nz are tlie nuinber of nodes and arcs of tlie graph. Tlie coinputation of the maxiinal complete set is also possible. Optiinality proofs are giveii and extensions for several other special cases are presented. Computational experiente for randomly generated problems is reported.