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

Author(s)
Mircea Parpalea

ABSTRACT

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.

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.

Cite this paper

nullM. 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.

nullM. Parpalea, "A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem,"

References

[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.

[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.