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

Mircea Parpalea

.

DOI: 10.4236/ojdm.2011.13015                

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.

Keywords

Dynamic Network, Parametric Cost, Bi-Criteria Minimum Cost Flow, Successive Shortest Path

Conflicts of Interest

The authors declare no conflicts of interest.

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.