Back
 OJDM  Vol.1 No.3 , October 2011
A Parametric Approach to the Bi-criteria Minimum Cost Dynamic Flow Problem
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.
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.
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.

 
 
Top