Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach |
| |
Affiliation: | 1. Department of Engineering Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand;2. Departamento de Matemáticas, Estadística e Investigación Operativa. Universidad de La Laguna, C.P. 38271, San Cristóbal de La Laguna, Santa cruz de Tenerife, España;1. Department of Economics and Statistics, University of Naples Federico II, Italy;2. Hewlett Packard Enterprise, HPE Tech Partners Italia S.r.l., Italy;3. Department of Industrial Engineering, University of Naples Federico II, Italy;1. Dipartimento di Informatica, Università di Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy;2. Dipartimento di Ingegneria dell’Informazione, Università di Pisa, Largo Lucio Lazzarino 1, 56122 Pisa, Italy;1. University of Valencia, Department of Statistics and Operations Research, Burjassot, Valencia, Spain;2. University of Castilla-La Mancha, Department of Mathematics, Albacete, Spain |
| |
Abstract: | We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|