zbMATH — the first resource for mathematics

On seeking efficient Pareto optimal points in multi-player minimum cost flow problems with application to transportation systems. (English) Zbl 1426.90227
Summary: In this paper, we propose a multi-player extension of the minimum cost flow problem inspired by a transportation problem that arises in modern transportation industry. We associate one player with each arc of a directed network, each trying to minimize its cost function subject to the network flow constraints. In our model, the cost function can be any general nonlinear function, and the flow through each arc is an integer. We present algorithms to compute efficient Pareto optimal point(\(s\)), where the maximum possible number of players (but not all) minimize their cost functions simultaneously. The computed Pareto optimal points are Nash equilibriums if the problem is transformed into a finite static game in normal form.
90C29 Multi-objective and goal programming
90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
Full Text: DOI
[1] Gupta, S.D., Pavel, L.: Multi-player minimum cost flow problems with nonconvex costs and integer flows. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 7617-7622. IEEE (2016)
[2] Turban, E., Outland, J., King, D., Lee, J.K., Liang, T.-P., Turban, D.C.: Electronic Commerce 2018: A Managerial and Social Networks Perspective. Springer, Berlin (2017)
[3] Galloway, S.: The Four: The Hidden DNA of Amazon, Apple, Facebook, and Google. Portfolio, New York (2017)
[4] Li, L.: Managing Supply Chain and Logistics: Competitive Strategy for a Sustainable Future. World Scientific Publishing Co Inc, Singapore (2014)
[5] Mendez, V.M., Monje, Jr, Carlos, A., White, V.: Beyond traffic: trends and choices 2045: a national dialogue about future transportation opportunities and challenges. In: Disrupting Mobility, pp. 3-20. Springer, Cham (2017)
[6] Laseter, T.M., Rabinovich, E.: Internet Retail Operations: Integrating Theory and Practice for Managers. CRC Press, Boca Raton (2011)
[7] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[8] Miettinen, K.: Nonlinear Multiobjective Optimization, vol. 12. Springer, Berlin (2012) · Zbl 1282.90166
[9] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993) · Zbl 1201.90001
[10] Bertsimas, D.; Nasrabadi, E.; Stiller, S., Robust and adaptive network flows, Oper. Res., 61, 1218-1242, (2013) · Zbl 1291.90046
[11] Vaidyanathan, B.; Ahuja, RK, Fast algorithms for specially structured minimum cost flow problems with applications, Oper. Res., 58, 1681-1696, (2010) · Zbl 1231.90111
[12] Magnanti, TL; Wong, RT, Network design and transportation planning: models and algorithms, Transp. Sci., 18, 1-55, (1984)
[13] Graves, SC; Orlin, JB, A minimum concave-cost dynamic network flow problem with an application to lot-sizing, Networks, 15, 59-71, (1985) · Zbl 0579.90032
[14] Daskin, M.S.: Network and Discrete Location: Models, Algorithms, and Applications. Wiley, Hoboken (2011) · Zbl 1276.90038
[15] Feltenmark, S., Lindberg, P.O.: Network Methods for Head-Dependent Hydro Power Scheduling. Springer, Berlin (1997) · Zbl 0878.90072
[16] Yaged, B., Minimum cost routing for static network models, Networks, 1, 139-172, (1971) · Zbl 0228.90011
[17] He, Q.; Ahmed, S.; Nemhauser, GL, Minimum concave cost flow over a grid network, Math. Program., 150, 79-98, (2015) · Zbl 1309.90004
[18] Tuy, H.; Ghannadan, S.; Migdalas, A.; Värbrand, P., The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, J. Glob. Optim., 6, 135-151, (1995) · Zbl 0833.90039
[19] Fontes, DBMM; Hadjiconstantinou, E.; Christofides, N., A branch-and-bound algorithm for concave network flow problems, J. Glob. Optim., 34, 127-155, (2006) · Zbl 1098.90080
[20] Zangwill, WI, Minimum concave cost flows in certain networks, Manag. Sci., 14, 429-450, (1968) · Zbl 0159.49102
[21] Jorjani, S.; Lamar, BW, Cash flow management network models with quantity discounting, Omega, 22, 149-155, (1994)
[22] Gamarnik, D.; Shah, D.; Wei, Y., Belief propagation for min-cost network flow: convergence and correctness, Oper. Res., 60, 410-428, (2012) · Zbl 1274.90455
[23] Kim, D.; Pardalos, PM, A dynamic domain contraction algorithm for nonconvex piecewise linear network flow problems, J. Glob. Optim., 17, 225-234, (2000) · Zbl 0988.90002
[24] Yan, S.; Shih, Y-L; Lee, W-T, A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems, J. Glob. Optim., 49, 539-559, (2011)
[25] Raith, A.; Ehrgott, M., A two-phase algorithm for the biobjective integer minimum cost flow problem, Comput. Oper. Res., 36, 1945-1954, (2009) · Zbl 1179.90303
[26] Lee, H.; Pulat, PS, Bicriteria network flow problems: integer case, Eur. J. Oper. Res., 66, 148-157, (1993) · Zbl 0780.90040
[27] Eusébio, A.; Figueira, JR, Finding non-dominated solutions in bi-objective integer network flow problems, Comput. Oper. Res., 36, 2554-2564, (2009) · Zbl 1179.90049
[28] Hernández, S.; Peeta, S.; Kalafatas, G., A less-than-truckload carrier collaboration planning problem under dynamic capacities, Transp. Res. Part E Logist. Transp. Rev., 47, 933-946, (2011)
[29] Barnhart, C., Hane, C.A., Vance, P.H.: Integer multicommodity flow problems. In: Integer Programming and Combinatorial Optimization, pp. 58-71. Springer, Berlin (1996) · Zbl 1415.90132
[30] Brunetta, L.; Conforti, M.; Fischetti, M., A polyhedral approach to an integer multicommodity flow problem, Discrete Appl. Math., 101, 13-36, (2000) · Zbl 0944.90008
[31] Ozdaglar, A.E., Bertsekas, D.P.: Optimal solution of integer multicommodity flow problems with application in optical networks. In: Frontiers in global optimization, pp. 411-435. Springer, Boston (2004) · Zbl 1048.90050
[32] Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization, vol. 6. Athena Scientific, Belmont (1997)
[33] Basar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory, vol. 23. SIAM, Philadelphia (1995) · Zbl 0828.90142
[34] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998) · Zbl 0970.90052
[35] Bertsimas, D., Weismantel, R.: Optimization Over Integers, vol. 13. Dynamic Ideas, Belmont (2005)
[36] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 123-231, (2013)
[37] Cox, D., Little, J., O’shea, D.: Ideals, Varieties, and Algorithms, vol. 3. Springer, Berlin (2007) · Zbl 1118.13001
[38] Bertsekas, D.P., Ozdaglar, A.E., Nedic, A.: Convex Analysis and Optimization. Athena Scientific Optimization and Computation Series. Athena Scientific, Belmont (2003) · Zbl 1140.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.