Solving biobjective network flow problem associated with minimum cost-time loading

Document Type : Research Article

Authors

• O. Baghani ¹
• S. Ghafoori ²

¹ Department of Applied Mathematics, Faculty of Mathematics and Computer Sciences, Hakim Sabzevari University, P.O. Box 397, Sabzevar, Iran.

² Department of Mathematics, Faculty of Mathematics, Statistics and Computer Science, Semnan University, P.O. Box 363, Semnan, Iran.

10.22067/ijnao.v10i2.84890

Abstract

We apply a primal-dual simplex algorithm for solving the biobjective min imum cost-time network flow problem such that the total shipping cost and the total shipping fixed time are considered as the first and second objective functions, respectively. To convert the proposed model into a single-objective parametric one, the weighted sum scalarization technique is commonly used. This problem is a mixed-integer programming, which the decision variables are directly dependent together. Generally, the previous works have consid ered the linear biobjective problem with the traditional network flow con straints, while in this paper, corresponding to each flow variable, a binary variable is defined. These zero-one variables are utilized to describe a fixed shipping time for positive flows. The proposed method is successful in finding all supported efficient solutions of a real numerical example.

Keywords

• Biobjective network flow
• Minimum cost-time
• Primal-dual algorithm
• Fixed time

20.1001.1.24236977.2020.10.2.2.4

---

References

1. M. Abareshi, M. Zaferanieh, A bilevel capacitated P-median facility location problem with the most likely allocation solution, Trans. Res. B-Meth. 123 (2019) 1–20.

2. Abo-Sinna, M.A. andRizk-Allah, R.M. Decomposition of parametric space for biobjective optimization problem using neural network approach, Opsearch, 55(2) (2018) 502–531.

3. Ahuja, R.,Magnanti, T.L. and Orlin, J.Network flows: Theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, 1993.

4. Arbel, A. Multi-objective interior primal-dual linear programming algorithm, Comput. Oper. Res. 21 (1994) 33–445.

5. Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. Linear programming and network flows, third edition. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2005.

6. Benson, H.P. and Sun, E. Outcome space partition of the weight set in multi-objective linear programming, J. Optimiz. Theory App. 105 (2000) 17–36.

7. Calvete, H.I., Gal´eb, C., Iranzo, J.A. and Toth, P. A matheuristic for the two-stage fixed-charge transportation problem, Comput. Oper. Res. 95 (2018) 113–122.

8. Ehrgott, M. and Puerto, J. Primal-Dual simplex method for multi-objective linear programming, J. Optimiz. Theory App. 134 (2007) 483–497.

9. Ehrgott, M., Shao, L. and Sch¨obel, A. An approximation algorithm for convex multi-objective programming problems, J. Global Optim. 50 (2011) 397–416.

10. Eus´ebio, A. and Figueira, J.R. Finding nondominated solutions in biobjective integer network flow problems, Comput. Oper. Res. 36 (2009) 2554–2564.

11. Eus´ebio, A., Figueira, J.R. and Ehrgott, M. A primal-dual simplex algorithm for bi-objective network flow problems, 4OR J. Oper. Res. 7 (2009) 255–273.

12. Eus´ebio, A., Figueira, J.R. and Ehrgott, M. On finding representative nondominated points for biobjective integer network flow problems, Comput. Oper. Res. 48 (2014) 1–10.

13. Guisewite, G. and Pardalos, P. Minimum concave-cost network flow problems: Applications, complexity, and algorithms, Ann. Oper. Res. 25 (1990) 75–99.

14. Hamacher, H.W., Pedersen, C.R. and Ruzika, S. Multiple objective minimum cost flow problems: a review, European J. Oper. Res. 176 (2007) 1404–1422.

15. Hochbaum, D.S. and Segev, A. Analysis of a flow problem with fixed charges, Networks, 19 (1989) 291–312.

16. Keshavarz, E. and Toloo, M. A biobjective minimum cost-time network flow problem, Procedia Econ. Finance. 23 (2015) 3–8.

17. Mohammadi, S., PourKarimi, L. and Pedram, H. Integer linear programming based multi-objective scheduling for scientific workflows in multi cloud environments, J. Supercomput. 75 (2019) 6683–6709.

18. Moradi, S., Raith, A. and Ehrgott, M. A biobjective column generation algorithm for the multi-commodity minimum cost flow problem, European J. Oper. Res. 244 (2015) 369–378.

19. Mungu´ıa, L., Ahmed, S.,Bader, D.A., Nemhauser, G.L., Goel, V. and Shao, Y. A parallel local search framework for the fixed charge multicommodity network flow problem, Comput. Oper. Res. 77 (2017) 44–57.

20. Nicholson, C.D. and Zhang, W. Optimal network flow: A predictive analytics perspective on the fixed-charge network flow problem, Comput. Ind. Eng. 99 (2016) 260–268.

21. Ortega, F. and Wolsey, L. A branch-and-cut algorithm for the single commodity, uncapacitated, fixed-charge network flow problem, Networks, 41 (2003) 143–158.

22. Przybylski, A. Application of primal-dual simplex method for MOLP to the MO assignment problem, Technical Report, University of Nantes, Nantes, France, 2005.

23. Przybylski, A., Gandibleux, X. and Ehrgott, M. The two-phase method for multi-objective combinatorial optimization problems, In A. R. Mahjoub (Ed.), Progress in combinatorial optimization (pp. 559–596), London, IS

TEWiley, 2011.

24. Raith, A. and Ehrgott, M. A two-phase algorithm for the biobjective integer minimum cost flow problem, Comput. Oper. Res. 36 (2009) 1945–1954.

25. Sede˜no-Noda, A. and Gonzalez-Martin, C. The biobjective minimum cost flow problem, European J. Oper. Res. 124 (2000) 591–600.

26. Steuer, R.E. Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, New York, 1986.