Share This Article:

A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem

Abstract Full-Text HTML Download Download as PDF (Size:427KB) PP. 116-126
DOI: 10.4236/ojdm.2011.13015    2,806 Downloads   6,443 Views   Citations
Author(s)    Leave a comment


This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

M. Parpalea, "A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem," Open Journal of Discrete Mathematics, Vol. 1 No. 3, 2011, pp. 116-126. doi: 10.4236/ojdm.2011.13015.


[1] R. Ahuja, T. Magnanti and J. Orlin, “Network Flows. Theory, Algorithms and Applications,” Prentice Hall, Inc., Englewood Cliffs, New Jersey, 1993.
[2] J. A. Aronson, “A Survey of Dynamic Network Flows,” Annals of Operations Research, Vol. 1, No.1, 1989, pp. 1-66. doi:10.1007/BF02216922
[3] W. Powell, P. Jaillet and A. Odoni, “Stochastic and Dynamic Networks and Routing,” In: Ball, M. O., Magnanti, T. L., Monma, C. L. and Nemhauser G. L., Ed., Network Routing, Handbooks in Operations Research and Management Science, Chapter 3, North Holland, Amsterdam, The Netherlands, Vol. 8, 1995, pp. 141-295.
[4] N. Kamiyama, A. Takizawa, N. Katoh and Y. Kawabata, “Evaluation of Capacities of Refuges in Urban Areas by Using Dynamic Network Flows,” Proceedings of the Eighth International Symposium on Operations Research and Its Applications, ORSC & APORC, Zhangjiajie, China, 2009, pp. 453-460.
[5] I. Chabini and M. Abou-Zeid, “The Minimum Cost Flow Problem in Capacitated Dynamic Networks,” Annual Meeting of the Transportation Research Board, Washington, D.C., 2003, pp. 1-30.
[6] E. Nasrabadi and S. M. Hashemi, “Minimum Cost Time- Varying Network Flow Problems,” Optimization Methods and Software, Vol. 25, No. 3, 2010, pp. 429-447. doi:10.1080/10556780903239121
[7] H. Lee and S. Pulat, “Bicriteria Network Flow Problems: Continuous Case,” European Journal of Operational Research, Vol. 51, No. 1, 1991, pp. 119-126. doi:10.1016/0377-2217(91)90151-K
[8] S. Gass and T. Saaty, “The Computational Algorithm for the Parametric Objective Function,” Naval Research Logistics Quarterly, Vol. 1, No. 1-2, 1955, pp. 39-45. doi:10.1002/nav.3800020106
[9] A. M. Geoffrion, “Solving Bicriterion Mathematical Programs,” Operations Research, Vol. 15, No. 1, 1967, pp. 39-54. doi:10.1287/opre.15.1.39
[10] Y. P. Aneja and K. P. Nair, “Bicriteria Transportation Problem,” Management Science, Vol. 25, No. 1, 1979, pp. 73-78. doi:10.1287/mnsc.25.1.73
[11] A. Skriver, “A Classification of Bicriterion Shortest Path (BSP) Algorithms,” Asia-Pacific Journal of Operational Research, No. 17, 2000, pp. 199-212.
[12] X. Cai, D. Sha and C. Wong, “Time-Varying Network Optimization,” Springer, New York, 2007.

comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.