The multicommodity network flow problem: state of the art classification, applications, and solution methods | Operational Research Skip to main content
Springer Nature Link
Log in

The multicommodity network flow problem: state of the art classification, applications, and solution methods

  • Original paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

Over the past decades, the Multicommodity Network Flow (MCNF) problem has grown popular in the academic literature and a growing number of researchers are interested in this field. It is a powerful operational research approach to tackle and solve many complicated problems, especially in transportation and telecommunication contexts. Yet, few literature reviews have made an effort to classify the existing articles accordingly. In this article, we present a taxonomic review of the MCNF literature published between 2000 and 2019. Based on an adapted version of an existing comprehensive taxonomy, we have classified 263 articles into two main categories of applications and solution methods. We have also analyzed the research interests in the MCNF literature. This classification is the first to categorize the articles into this level of detail. Results show that there are topics, which need to be addressed in future researches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  • Achterberg T, Raack C (2010) The MCF-separator: detecting and exploiting multicommodity flow structures in MIPs. Math Program Comput 2(2):125–165

    Google Scholar 

  • Adhikari RS, Aste N, Manfren M (2012) Multicommodity network flow models for dynamic energy management – Smart Grid applications. Energy Procedia 14:1374–1379

    Google Scholar 

  • Agarwal YK (2002) Design of capacitated multicommodity networks with multiple facilities. Oper Res 50(2):333–344

    Google Scholar 

  • Ahmed W, Hasan O, Pervez U, Qadir J (2017) Reliability modeling and analysis of communication networks. J Netw Comput Applcations 78:191–215

    Google Scholar 

  • Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, NewJersey

    Google Scholar 

  • Aickelin U, Clark A (2011) Heuristic optimisation. J Oper Res Soc 62(2):251–252

    Google Scholar 

  • Akyuz MH, Oncan T, Altınel IK (2012) Efficient approximate solution methods for the multicommodity capacitated multi-facility Weber problem. Comput Oper Res 39(2):225–237

    Google Scholar 

  • Akyüz M, Öncan T, Altınel (2018) Branch and bound algorithms for solving the Multicommodity capacitated multi-facility Weber problem. Ann Oper Res 279:1–42

    Google Scholar 

  • Alavidoost M, Tarimoradi M, Zarandi M (2018) Bi-objective mixed-integer nonlinear programming for multicommodity tri-echelon supply chain networks. J Intell Manuf 29(4):809–826

    Google Scholar 

  • Albrecht C (2001) Global routing by new approximation algorithms for multicommodity flow. IEEE Trans Comput Aided Des Integr Circuits Syst 20(5):622–632

    Google Scholar 

  • Aldous D, McDiarmid C, Scott A (2009) Uniform multicommodity flow through the complete graph with random edge-capacities. Oper Res Lett 37(5):299–302

    Google Scholar 

  • Alfaki M, Haugland D (2013) A Multicommodity flow formulation for the generalized pooling problem. J Global Optim 56(3):917–937

    Google Scholar 

  • Ali I, Charnes A, Tiantai S (1985) Karmarkar's projective algorithm: a null space-variant for multicommodity generalized networks. Acta Math Appl Sin 2(2):168–190

    Google Scholar 

  • Al-Khayyal F, Hwang S-J (2007) Inventory constrained maritime routing and scheduling for multicommodity liquid bulk, Part I: applications and model. Eur J Oper Res 176(1):106–130

    Google Scholar 

  • Aloise D, Ribeiro C (2011) Adaptive memory in multistart heuristics for multicommodity network design. J Heuristics 17(2):153–179

    Google Scholar 

  • Alumur S, Nickel S, Saldanha-da-Gama F, Verter V (2012) Multi-period reverse logistics network design. Eur J Oper Res 220(1):67–78

    Google Scholar 

  • Alvarez A, González-Velarde J, De-Alba K (2005) GRASP embedded scatter search for the multicommodity capacitated network design problem. J Heuristics 11(3):233–257

    Google Scholar 

  • Amit K, Amarpreet K (2011) Application of classical transportation methods for solving fuzzy transportation problems. J Transp Syst Eng Inf Technol 11(5):68–80

    Google Scholar 

  • Amrani H, Martel A, Zufferey N, Makeeva P (2011) A variable neighborhood search heuristic for the design of multicommodity production-distribution networks with alternative facility configurations. OR Spectr 33(4):989–1007

    Google Scholar 

  • Aneja Y, Nair K (1982) Multicommodity network flows with probabilistic losses. Manag Sci 28(9):1080–1086

    Google Scholar 

  • Aringhieri R, Cordone R (2004) The multicommodity multilevel bottleneck assignment problem. Electron Notes Discrete Math 17:35–40

    Google Scholar 

  • Assad AA (1978) multicommodity network flows—a survey. Networks 8(1):37–91

    Google Scholar 

  • Awerbuch B, Khandekar R (2009) Greedy distributed optimization of multicommodity flows. Distrib Comput 21(5):317–329

    Google Scholar 

  • Awerbuch B, Leighton T (1993) A simple local-control approximation algorithm for multicommodity flow. In: 34th annual symposium on foundations of computer science. IEEE, pp 459–468

  • Ayar B, Yaman H (2012) An intermodal multicommodity routing problem with scheduled services. Comput Optim Appl 53(1):131–153

    Google Scholar 

  • Arani Azadi Moghaddam A, Jolai F, Nasiri M (2019) A Multicommodity network flow model for railway capacity optimization in case of line blockage. Int J Rail Transp 7:1–24

    Google Scholar 

  • Babonneau F, Du Merle O, Vial J-P (2006) Solving large-scale linear multicommodity flow problems with an active set strategy and proximal-ACCPM. Oper Res 54(1):184–197

    Google Scholar 

  • Baier G, Köhler E, Skutella M (2005) The k-splittable flow problem. Algorithmica 42(3–4):231–248

    Google Scholar 

  • Balakrishnan A, Li G, Mirchandani P (2017) Optimal network design with end-to-end service requirements. Oper Res 65(3):729–750

    Google Scholar 

  • Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper Res 52(5):723–738

    Google Scholar 

  • Barnhart C, Hane CA, Vance PH (2000) Using Branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper Res 48(2):318–326

    Google Scholar 

  • Balma A, Salem S, Mrad M, Ladhari T (2018) Strong Multicommodity flow formulations for the asymmetric traveling salesman problem. Eur J Oper Res 27:72–79

    Google Scholar 

  • Barnhart C, Hane C, Johnson E, Sigismondi G (1995) A column generation and partitioning approach for multicommodity flow problems. Telecommun Syst 3(3):239–258

    Google Scholar 

  • Bartolini E, Schneider M (2018) A two-commodity flow formulation for the capacitated truck-and-trailer routing problem. Discrete Appl Math 275:3–18

    Google Scholar 

  • Bazan O, Jaseemuddin M (2008) Multicommodity flow problem for multi-hop wireless networks with realistic smart antenna model. In: International conference on research in networking. Springer, Berlin, pp 922–929

  • Bélanger N, Desaulniers G, Soumis F, Desrosiers J (2006) Periodic airline fleet assignment with time windows, spacing constraints, and time-dependent revenues. Eur J Oper Res 175(3):1754–1766

    Google Scholar 

  • Bektaş T, Chouman M, Crainic T (2010) Lagrangean-based decomposition algorithms for multicommodity network design problems with penalized constraints. Netw Int J 55(3):171–180

    Google Scholar 

  • Beljadid A, Hafid A, Boushaba M (2013) Reliability analytical measurement to design wireless mesh networks. In: IEEE international conference on advanced networks and telecommunications systems (ANTS). IEEE, Kattankulathur, India, pp 1–6

  • Bera S, Misra S, Jamalipour A (2019) Flowstat: adaptive flow-rule placement for per-flow statistics in SDN. IEEE J Sel Areas Commun 37(3):530–539

    Google Scholar 

  • Bevrani B, Burdett RL, Bhaskar A, Yarlagadda PK (2019) A multi commodity flow model incorporating flow reduction functions. Flexible Serv Manuf J. https://doi.org/10.1007/s10696-019-09349-4

    Article  Google Scholar 

  • Białoń P (2017) A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees. Telecommun Syst 64(3):525–542

    Google Scholar 

  • Bin Obaid HS, Trafalis TB (2020) An approximation to max min fairness in multi commodity networks. Comput Manag Sci 17:65–77

    Google Scholar 

  • Boccia M, Crainic T, Sforza A, Sterle C (2018) Multicommodity location-routing: flow intercepting formulation and branch-and-cut algorithm. Comput Oper Res 89:94–112

    Google Scholar 

  • Boland N, Kalinowski T, Rigterink F (2016) New Multicommodity flow formulations for the pooling problem. J Global Optim 66(4):669–710

    Google Scholar 

  • Brandt S, Foerster K-T, Wattenhofer R (2017) Augmenting flows for the consistent migration of multicommodity single-destination flows in SDNS. Pervasive Mobile Comput 36:134–150

    Google Scholar 

  • Brotcorne L, Labbé M, Marcotte P, Savard G (2001) A bilevel model for toll optimization on a multicommodity transportation network. Transp Sci 35(4):345–358

    Google Scholar 

  • Brunetta L, Conforti M, Fischetti M (2000) A polyhedral approach to an integer multicommodity flow problem. Discrete Appl Math 101(1–3):13–36

    Google Scholar 

  • Cabrera G, Toledo C (2010) A Tabu search algorithm with a probabilistic neighbor selection criterion for capacitated multicommodity network flow problem. In: International conference on technologies and application of artificial intelligence. IEEE, Hsinchu, Taiwan, pp 1–5

  • Caimi G, Chudak F, Fuchsberger M, Laumanns M, Zenklusen R (2011) A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling. Transp Sci 45(2):212–227

    Google Scholar 

  • Çakır O (2009) Benders decomposition applied to multi-commodity, multi-mode distribution planning. Expert Syst Appl 36(4):8212–8217

    Google Scholar 

  • Canel C, Khumawala BM, Law J, Loh A (2001) An algorithm for the capacitated, multicommodity multi-period facility location problem. Comput Oper Res 28(5):411–427

    Google Scholar 

  • Cao B, Uebe G (1993) An algorithm for solving capacitated multicommodity p-median transportation problems. Oper Res Soc 44(3):259–269

    Google Scholar 

  • Cappanera P, Frangioni A (2003) Symmetric and asymmetric parallelization of a cost-decomposition algorithm for multicommodity flow problems. INFORMS J Comput 15(4):369–384

    Google Scholar 

  • Cappanera P, Gallo G (2004) A multicommodity flow approach to the crew rostering problem. Oper Res 52(4):583–596

    Google Scholar 

  • Cariou P, Cheaitou A, Larbi R, Hamdan S (2018) Liner shipping network design with emission control areas: a genetic algorithm-based approach. Transp Res Part D: Transp Environ 63:604–621

    Google Scholar 

  • Castro J (2000) A specialized interior-point algorithm for multicommodity network flows. SIAM J Optim 10(3):852–877

    Google Scholar 

  • Castro J (2003) Solving difficult multicommodity problems with a specialized interior-point algorithm. Ann Oper Res 124(1–4):35–48

    Google Scholar 

  • Castro J, Nabona N (1996) An implementation of linear and nonlinear multicommodity network flows. Eur J Oper Res 92(1):37–53

    Google Scholar 

  • Castro J Frangioni A (2000) A parallel implementation of an interior-point algorithm for multicommodity network flows. In: International conference on vector and parallel processing. Springer, Berlin, pp 301–315

  • Cattaruzza D, Absi N, Feillet D, Vigo D (2014) An iterated local search for the multicommodity multi-trip vehicle routing problem with time windows. Comput Oper Res 51:257–267

    Google Scholar 

  • Chale-Gongora HG, Weck O, Doufene A, Ishimatsu T, Krob D (2014) Planning an Itinerary for an electric vehicle. In: IEEE international energy conference (ENERGYCON). IEEE, Cavtat, Croatia, pp 1385–1391

  • Chardaire P, Lisser A (2002) Simplex and interior point specialized algorithms for solving nonoriented multicommodity flow problems. Oper Res 50(2):260–276

    Google Scholar 

  • Charikar M, Naamad Y, Rexford J, Zou X (2018) Multicommodity flow with in-network processing. In: International symposium on algorithmic aspects of cloud computing. Springer, Cham, pp 73–101

  • Chekuri C, Khanna S, Shepherd FB (2013) The all-or-nothing multicommodity flow problem. SIAM J Comput 42(4):1467–1493

    Google Scholar 

  • Chen YL, Chin YH (1992) Multicommodity network flows with safety considerations. Oper Res 40(1):S48–S55

    Google Scholar 

  • Cheng Y, Sterbenz JP (2014) Geodiverse routing with path jitter requirement under regional challenges. In: 6th international workshop on reliable networks design and modeling (RNDM). IEEE, Barcelona, Spain, pp 179–186

  • Cheng C, Tang H, Zhao C (2008) Approximation algorithm for a bicriteria multicommodity flow problem. In: IEEE international conference on service operations and logistics, and informatics. IEEE, Beijing, China, pp 1756–1760

  • Cheng X, Tang K, Li X (2018) New multicommodity flow formulations for the generalized pooling problem. IFAC-PapersOnLine 51(18):162–167

    Google Scholar 

  • Chien T, Hung H (2018) Extended linear multicommodity multi-cost network and maximal flow limited cost problems. Int J Comput Netw Commun 10:79–93

    Google Scholar 

  • Choi D-S, Choi I-C (2006) On the effectiveness of the linear programming relaxation of the 0–1 multicommodity minimum cost network flow problem. In: International computing and combinatorics conference. Springer, Berlin, Heidelberg, pp 517–526

  • Chouman M, Crainic T, Gendron B (2016) Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed-charge network design. Transp Sci 51(2):650–667

    Google Scholar 

  • Ciappina JR, Yamakami A, Silva RC (2012) Decomposition’s Dantzig–Wolfe applied to fuzzy multicommodity flow problems. Comput Oper Res 39(12):3394–3407

    Google Scholar 

  • Clausen J (1999) Branch and bound algorithms principles and examples. University of Copenhagen, Department of Computer Science, pp 1–30

    Google Scholar 

  • Cortés P, Muñuzuri J, Guadix J, Onieva L (2013) An optimal algorithm for the demand routing problem in multicommodity flow distribution networks with diversification constraints and concave costs. Int J Prod Econ 146(1):313–324

    Google Scholar 

  • Costa A, Cordeau J-F, Gendron B (2009) Benders, metric and cutset inequalities for multicommodity capacitated network design. Comput Optim Appl 42(3):371–392

    Google Scholar 

  • Crainic TG, Frangioni A, Gendron B (2001) Bundle-based relaxation methods for multicommodity capacitated fixed-charge network design. Discrete Appl Math 112(1–3):73–99

    Google Scholar 

  • Crainic T, Gendron B, Hernu G (2004) A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design. J Heuristics 10(5):525–545

    Google Scholar 

  • Crainica TG, Li Y, Toulouse M (2006) A first multilevel cooperative algorithm for capacitated multicommodity network design. Comput Oper Res 33(9):2602–2622

    Google Scholar 

  • Dai W, Sun X, Wandelt S (2016) Finding feasible solutions for multicommodity flow problems. In: 35th Chinese control conference (CCC). IEEE, Chengdu, China, pp 2878–2883

  • Dantzing G, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8(1):101–111

    Google Scholar 

  • Detlefsen N, Wallace S (2002) The simplex algorithm for multicommodity networks. Netw Int J 39(1):15–28

    Google Scholar 

  • Ding S (2017) Uncertain minimum cost multicommodity flow problem. Soft Comput 21(1):223–231

    Google Scholar 

  • Dorneles Á, de Araújo O, Buriol L (2017) A column generation approach to high school timetabling modeled as a multicommodity flow problem. Eur J Oper Res 256(3):685–695

    Google Scholar 

  • Dragan F, Kahng A, Mandoiu I, Muddu S, Zelikovsky A (2002) Provably good global buffering by generalized multiterminal multicommodity flow approximation. IEEE Trans Comput Aided Des Integr Circuits Syst 21(3):263–274

    Google Scholar 

  • Eickmeyer K, Kawarabayashi K-I (2013) Approximating multi commodity network design on graphs of bounded pathwidth and bounded degree. In: International symposium on algorithmic game theory. Springer, Berlin, pp 134–145

  • Erdös PL, Székely LA (1992) Evolutionary trees: an integer multicommodity max-flow - min-cut theorem. Adv Appl Math 13(4):375–389

    Google Scholar 

  • Erera AL, Morales JC, Savelsbergh M (2005) Global intermodal tank container management for the chemical industry. Transp Res Part E: Logist Transp Rev 41(6):551–566

    Google Scholar 

  • Erez E, Feder M (2009) Improving the multicommodity flow rates with network codes for two sources. IEEE J Sel Areas Commun 27(5):814–824

    Google Scholar 

  • Evans JR (1981) The multicommodity assignment problem: a network aggregation heuristic. Comput Math Appl 7(2):187–194

    Google Scholar 

  • Even G, Medina M (2012) Online multicommodity flow with high demands. In: International workshop on approximation and online algorithms. Springer, Berlin, pp 16–29

  • Fakhri A, Ghatee M (2014) Fractional multicommodity flow problem: duality and optimality conditions. Appl Math Model 38(7–8):2151–2162

    Google Scholar 

  • Fakhri A, Ghatee M (2016) Application of Benders decomposition method in solution of a fixed-charge multicommodity network design problem avoiding congestion. Appl Math Model 40(13–14):6468–6476

    Google Scholar 

  • Farrugia N, Briffa J, Buttigieg V (2018) An evolutionary multipath routing algorithm using SDN. In: 9th international conference on the network of the future (NOF). IEEE, Poznan, Poland, pp 1–8

  • Farrugia N, Briffa JA, Buttigieg V (2019) Solving the multicommodity flow problem using a multi-objective genetic algorithm. In: IEEE congress on evolutionary computation (CEC). IEEE, Wellington, New Zealand, pp 2816–2823

  • Ferland JA, Girard A, Lafond L (1978) Multicommodity flow problem with variable arcs capacities. The J Oper Res Soc 29(5):459–467

    Google Scholar 

  • Fleischer LK (2000) Approximating fractional multicommodity flow independent of the number of commodities. SIAM J Discrete Math 13(4):505–520

    Google Scholar 

  • Fleischer L, Skutella M (2002) The quickest multicommodity flow problem. In: International conference on integer programming and combinatorial optimization. Springer, Berlin, pp 36–53

  • Fleischer L, Sethuraman J (2005) Efficient algorithms for separated continuous linear programs: the multicommodity flow problem with holding costs and extensions. Math of Oper Res 30(4):916–938

    Google Scholar 

  • Fleischer L, Jain K, Mahdian MM (2004) Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: 45th annual IEEE symposium on foundations of computer science. IEEE, Rome, Italy, pp 277–285

  • Ford L Jr, Fulkerson D (1958) A suggested computation for maximal multicommodity network flows. Manag Sci 5(1):97–101

    Google Scholar 

  • Fortz B, Gouveia L, Joyce-Moniz M (2017) Models for the piecewise linear unsplittable multicommodity flow problems. Eur J Oper Res 261(1):30–42

    Google Scholar 

  • Foulds LR (1981) A multicommodity flow network design problem. Transp Res Part B: Methodol 15(4):273–283

    Google Scholar 

  • Frangioni A, Gendron B (2009) 0–1 reformulations of the multicommodity capacitated network design problem. Discrete Appl Math 157(6):1229–1241

    Google Scholar 

  • Frangioni A, Gorgone E (2014) Bundle methods for sum-functions with “easy” components: applications to multicommodity network design. Math Program 145(1–2):133–161

    Google Scholar 

  • Gabrel V, Knippel A, Minoux M (1999) Exact solution of multicommodity network optimization problems with general step cost functions. Oper Res Lett 25(1):15–23

    Google Scholar 

  • Gabrel V, Knippel A, Minoux M (2003) A comparison of heuristics for the discrete cost multicommodity network optimization problem. J Heuristics 9(5):429–445

    Google Scholar 

  • Gamst M (2013) A local search heuristic for the multicommodity k-splittable maximum flow problem. Optim Lett 8(3):919–937

    Google Scholar 

  • Gamst M, Petersen B (2012) Comparing branch-and-price algorithms for the multicommodity k-splittable maximum flow problem. Eur J Oper Res 217(2):278–286

    Google Scholar 

  • Gamst M, Jensen PN, Pisinger D, Plum C (2010) Two-and three-index formulations of the minimum cost multicommodity k-splittable flow problem. Eur J Oper Res 202(1):82–89

    Google Scholar 

  • Gao X, Lee GM (2018) A stochastic programming model for multicommodity redistribution planning in disaster response. In: IFIP international conference on advances in production management system. Springer, Cham, pp 67–78

  • Garg P, Upadhyaya S (2018) Hybrid multi-commodity-based widest disjoint path algorithm (HMBWDP). In: Next-generation networks. Springer, Singapore, pp 333–340

  • Gautier A, Granot F (1995) forest management: a multicommodity flow formulation and sensitivity analysis. Manag Sci 41(10):1654–1668

    Google Scholar 

  • Gebremariam W, Bikdash M (2013) LP-based flow rate control and modeling of capacity collapse propagation over long links. In: Proceedings of IEEE southeastcon. IEEE, Jacksonville, FL, USA, pp 1–6

  • Gendron B, Larose M (2014) Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design. EURO J Comput Optim 2(1–2):55–75

    Google Scholar 

  • Gendron B, Gouveia L (2016) Reformulations by discretization for piecewise linear integer multicommodity network flow problems. Transp Sci 51(2):629–649

    Google Scholar 

  • Gendron B, Potvin J-Y, Soriano P (2003a) A parallel hybrid heuristic for the multicommodity capacitated location problem with balancing requirements. Parallel Comput 29(5):591–606

    Google Scholar 

  • Gendron B, Potvin J-Y, Soriano P (2003b) A tabu search with slope scaling for the multicommodity capacitated location problem with balancing requirements. Ann Oper Res 122(1–4):193–217

    Google Scholar 

  • Geoffrion AM, Graves GW (1974) Multicommodity distribution system design by benders decomposition. Manage Sci 20(5):822–844

    Google Scholar 

  • Ghamlouche I, Crainic TG, Gendreau M (2003) Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design. Oper Res 51(4):655–667

    Google Scholar 

  • Ghamlouche I, Crainic T, Gendreau M (2004) Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design. Ann Oper Res 131(1–4):109–133

    Google Scholar 

  • Ghasemi P, Khalili-Damghani K, Hafezolkotob A, Raissi S (2019) Uncertain multi-objective Multicommodity multi-period multi-vehicle location-allocation model for earthquake evacuation planning. Appl Math Comput 350:105–132

    Google Scholar 

  • Ghatee M (2011) QoS-based cooperative algorithm for integral multicommodity flow problem. Comput Commun 34(7):835–846

    Google Scholar 

  • Ghatee M, Hashemi S (2007) Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly. Appl Math Comput 188(1):555–566

    Google Scholar 

  • Ghatee M, Hashemi M (2009) Some concepts of the fuzzy multicommodity flow problem and their application in fuzzy network design. Math Comput Modell 49(5–6):1030–1043

    Google Scholar 

  • Gouveia L (1996) Multicommodity flow models for spanning trees with hop constraints. Eur J Oper Res 95(1):178–190

    Google Scholar 

  • Grandoni F, Rothvoß T (2011) Approximation algorithms for single and multicommodity multi-commodity. In: International conference on integer programming and combinatorial optimization. Springer, Berlin, pp 248–260

  • Groß M, Skutella M (2015) A tight bound on the speed-up through storage for quickest Multicommodity flows. Oper Res Lett 43(1):93–95

    Google Scholar 

  • Guo J, Niedermeier R (2006) A fixed-parameter tractability result for multicommodity demand flow in trees. Inf Process Lett 97(3):109–114

    Google Scholar 

  • Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In; Proceedings of the thirty-third annual ACM symposium on theory of computing, pp 389–398

  • Hadjiat M, Maurras J-F, Vaxes Y (2000) A primal partitioning approach for single and non-simultaneous multicommodity flow problems. Eur J Oper Res 123(2):382–393

    Google Scholar 

  • Haghani A, Oh S-C (1996) Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations. Transp Res Part A: Policy Pract 30(3):231–250

    Google Scholar 

  • Hajiaghayi M, Leighton T (2006) On the max-flow min-cut ratio for directed multicommodity flows. Theoret Comput Sci 352(1–3):318–321

    Google Scholar 

  • Hall A, Hippler S, Skutella M (2007) Multicommodity flows over time: efficient algorithms and complexity. Theoret Comput Sci 379(3):387–404

    Google Scholar 

  • Hao J, Shi Y, Sun H, Sheng M, Li J (2019) Rerouting based congestion control in data center networks. In: IEEE international conference on communications workshops (ICC workshops). IEEE, Shanghai, China, pp 1–6

  • Hernández-Pérez H, Salazar-González J-J (2009) The Multicommodity one-to-one pickup-and-delivery traveling salesman problem. Eur J Oper Res 196(3):987–995

    Google Scholar 

  • Hirai H, Koichi S (2011) On duality and fractionality of multicommodity flows in directed networks. Discrete Optim 8(3):428–445

    Google Scholar 

  • Holmberg K, Yuan D (2003) A multicommodity network-flow problem with side constraints on paths solved by column generation. INFORMS J Comput 15(1):42–57

    Google Scholar 

  • Holmberg K, Joborn M, Melin K (2008) Lagrangian based heuristics for the multicommodity network flow problem with fixed costs on paths. Eur J Oper Res 188(1):101–108

    Google Scholar 

  • Hossain M, Alam S, Abbass H (2017) A dynamic multicommodity flow optimization algorithm for estimating airport network capacity. Air Traffic Manag Syst II:205–220

    Google Scholar 

  • Hu TC (1963) Multicommodity network flows. Oper Res 11(3):344–360

    Google Scholar 

  • Huang T, Lv B, Liu J (2014) Work in progress: a novel virtual network mapping algorithm with weighted multicommodity flow. In: 9th international conference on communications and networking in China (CHINACOM). IEEE, Maoming, China, pp 166–169

  • Huerta M, Hesselbach X (2004) Application of the theory of the multicommodity for the flows distribution in MPLS networks. In: The 13th IEEE workshop on local and metropolitan area network. IEEE, Mill Valley, CA, USA, pp 119–124

  • Hurkens C, Schrijver A, Tardos É (1988) On fractional multicommodity flows and distance functions. Discrete Math 73(1–2):99–109

    Google Scholar 

  • Jacquet-Lagreze E, Lebbar M (1999) A column generation model for a scheduling problem with maintenance constraints. Electron Notes Discrete Math 1:1–12

    Google Scholar 

  • Jadin M, Aubry F, Schaus P, Bonaventure O (2019) CG4SR: near optimal traffic engineering for segment routing with column generation. In: IEEE INFOCOM 2019—IEEE conference on computer communications. IEEE, Paris, France, pp 1333–1341

  • Jeenanunta C, Kasemsontitum B, Noichawee T (2011) A multicommodity flow approach for aircraft routing and maintenance problem. In: IEEE international conference on quality and reliability. IEEE, Bangkok, Thailand, pp 150–155

  • Jia X, Cai Y, Zhou Q, Chen G, Li Z, Li Z (2014) MCFRoute: a detailed router based on multicommodity flow method. In: IEEE/ACM international conference on computer-aided design (ICCAD). IEEE, San Jose, CA, USA, pp 397–404

  • Jia X, Cai Y, Zhou Q, Yu B (2017) A multicommodity flow based detailed router with efficient. IEEE Trans Comput Aided Des Integr Circuits Syst 37(1):217–230

    Google Scholar 

  • Jiang Y, Zhang X, Rong Y, Zhang Z (2014) A multimodal location and routing model for hazardous materials transportation based on Multicommodity flow model. Procedia-So Behav Sci 138:791–799

    Google Scholar 

  • Jiao F, Dong S (2016) Ordered escape routing for grid pin array based on min-cost multicommodity flow. In: 21st Asia and South Pacific design automation conference (ASP-DAC). IEEE, Macau, China, pp 384–389

  • Jin W-L (2012) A kinematic wave theory of Multicommodity network traffic flow. Transp Res Part B: Methodol 46(8):1000–1022

    Google Scholar 

  • Jin W-L (2018) Unifiable multicommodity kinematic wave model. Transp Res Part B: Methodol 117:639–659

    Google Scholar 

  • Jin Q, Feng S, Li-xin M, Gui-jun T (2009) April) Optimal model and algorithm for multicommodity logistics network design considering stochastic demand and inventory control. Syst Eng Theory Pract 29(4):176–183

    Google Scholar 

  • Joe YY, Gan OP, Lewis FL (2014) Multicommodity flow dynamic resource assignment and matrix-based job dispatching for multi-relay transfer in complex material handling systems (MHS). J Intell Manuf 25(4):681–697

    Google Scholar 

  • Kabadurmus O, Smith AE (2016) Multicommodity k-splittable survivable network design problems with relays. Telecommun Syst 62(1):123–133

    Google Scholar 

  • Kacprzak P, Kaleta M, Kołtyś K, Pałka P, Pieńkosz K, Toczyłowski E, Żółtowska I (2010) Multicommodity exchange model for trading bandwidth in undirected networks. In: 14th international telecommunication network strategy and planning symposium (NETWORKS). IEEE, Warsaw, Poland, pp 1–5

  • Kalantari M, Shayman M (2006) Routing in multicommodity sensor networks based on partial differential equations. In: 40th annual conference on information sciences and systems. IEEE, Princeton, NJ, USA, pp 402–406

  • Karimi B, Bashiri M (2018) Designing a multicommodity multimodal splittable supply chain network by logistic hubs for intelligent manufacturing. Proc Manuf 17:1058–1064

    Google Scholar 

  • Karsten CV, Pisinger D, Ropke S, Brouer BD (2015) The time-constrained multicommodity network flow problem and its application to liner shipping network design. Transp Res Part E: Logist Transp Rev 76:122–138

    Google Scholar 

  • Katayama N (2019) A combined fast greedy heuristic for the capacitated multicommodity network design problem. J Oper Res Soc 70:1–14

    Google Scholar 

  • Katayama N, Chen M, Kubo M (2009) A capacity scaling heuristic for the multicommodity capacitated network design problem. J Comput Appl Math 232(1):90–101

    Google Scholar 

  • Kennington JL (1978) A survey of linear cost multicommodity network flows. Oper Res 26(2):209–236

    Google Scholar 

  • Kennington J, Shalaby M (1977) An Effective subgradient procedure for minimal cost multicommodity flow problems. Manage Sci 23(9):994–1004

    Google Scholar 

  • Khouja M, Michalewicz Z, Wilmot M (1998) The use of genetic algorithms to solve the economic lot size scheduling problem. Eur J Oper Res 110(3):509–524

    Google Scholar 

  • Khuller S, Raghavachari B, Young N (1994) Designing multicommodity flow trees. Inf Process Lett 50(1):49–55

    Google Scholar 

  • Kiwiel K (2011) An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems. Math Program 130(1):59–84

    Google Scholar 

  • Koca E, Yıldırım E (2012) A hierarchical solution approach for a multicommodity distribution problem under a special cost structure. Comput Oper Res 39(11):2612–2624

    Google Scholar 

  • Kolar V, Abu-Ghazaleh N (2006) A multicommodity flow approach for globally aware routing in multi-hop wireless networks. In: Fourth annual IEEE international conference on pervasive computing and communications (PERCOM'06). IEEE, Pisa, Italy, pp 313–317

  • Kollias A, Nikolaidis I (2015) Seasonally aware routing for thermoelectric energy harvesting wireless sensor networks. In: International conference on smart cities and green ICT systems (SMARTGREENS). IEEE, Lisbon, Portugal, pp 1–11

  • Kuiteing A, Marcotte P, Savard G (2018) Pricing and revenue maximization over a multicommodity transportation network: the nonlinear demand case. Comput Optim Appl 71(3):641–671

    Google Scholar 

  • Kumar A, Gupta A, Roughgarden T (2002) A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In: The 43rd annual IEEE symposium on foundations of computer science. IEEE, Vancouver, BC, Canada, pp 333–342

  • Larsson T, Yuan D (2004) An augmented lagrangian algorithm for large scale multicommodity routing. Comput Optim Appl 27(2):187–215

    Google Scholar 

  • Lawphongpanich S (2000) Simplicial with truncated Dantzig-Wolfe decomposition for nonlinear multicommodity network flow problems with side constraints. Oper Res Lett 26(1):33–41

    Google Scholar 

  • Layeb SB, Heni R, Balma A (2017) Compact MILP models for the discrete cost multicommodity network design problem. In: International conference on engineering & MIS (ICEMIS). IEEE, Monastir, Tunisia, pp 1–7

  • Lee K (2010) Integral polyhedra related to integer multicommodity flows on a cycle. Discrete Appl Math 158(3):235–238

    Google Scholar 

  • Lee S, Younis M, Murali A, Lee M (2019) Dynamic local vehicular flow optimization using real-time traffic conditions at multiple road intersections. IEEE Access 7:28137–28157

    Google Scholar 

  • Lei Q, Jiang D, Zhao P, Ma T (2013) Research on the disrupted airline scheduling. In: 10th international conference on service systems and service management IEEE. IEEE, Hong Kong, China, pp 332–336

  • Leighton T, Makedon F, Plotkin S, Stein C, Tardos É, Tragoudas S (1995) Fast approximation algorithms for multicommodity flow problems. J Comput Syst Sci 50(2):228–243

    Google Scholar 

  • Letchford A, Salazar-González J-J (2015) Stronger Multicommodity flow formulations of the capacitated vehicle routing problem. Eur J Oper Res 244:730–738

    Google Scholar 

  • Letchford A, Salazar-González J-J (2016) Stronger Multicommodity flow formulations of the (capacitated) sequential ordering problem. Eur J Oper Res 251(1):74–84

    Google Scholar 

  • Leveque O, Madan R, Shah D (2006) Uniform multicommodity flow in wireless networks with gaussian fading channels. In: IEEE international symposium on information theory. IEEE, Seattle, WA, USA, pp 1846–1850

  • Levitin G, Gertsbakh I, Shpungin Y (2013) Evaluating the damage associated with intentional supply deprivation in Multicommodity network. Reliab Eng Syst Saf 119:11–17

    Google Scholar 

  • Li J, Chu F, Prins C (2009) Lower and upper bounds for a capacitated plant location problem with multicommodity flow. Comput Oper Res 36(11):3019–3030

    Google Scholar 

  • Li X, Wei K, Aneja Y, Tian P (2016) Design-balanced capacitated multicommodity network design with heterogeneous assets. Omega 67:145–159

    Google Scholar 

  • Lim C, Smith JC (2007) Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans 39(1):15–26

    Google Scholar 

  • Lin Y-K (2001) Study on the multicommodity reliability of a capacitated-flow network. Comput Math Appl 42(1–2):255–264

    Google Scholar 

  • Lin Y-K (2002) Study on the system capacity for a multicommodity stochastic-flow network with node failure. Reliab Eng Syst Saf 78:57–62

    Google Scholar 

  • Lin Y-K (2004) An algorithm to evaluate the system reliability for multicommodity case under cost constraint. Comput Math Appl 48(5):805–812

    Google Scholar 

  • Lin Y-K (2006) A simple algorithm to generate all (d, B)-MCs of a multicommodity stochastic-flow network. Reliab Eng Syst Saf 91(8):923–929

    Google Scholar 

  • Lin Y-K (2007a) On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint. Eur J Oper Res 176(1):347–360

    Google Scholar 

  • Lin Y-K (2007b) System reliability of a limited-flow network in multicommodity case. IEEE Trans Reliab 56(1):17–25

    Google Scholar 

  • Lin Z, Kwan R (2013) An integer fixed-charge multicommodity flow (FCMF) model for train unit scheduling. Electron Notes Discrete Math 41:165–172

    Google Scholar 

  • Liu C-M (1997) Network dual steepest-edge methods for solving capacitated multicommodity network problems. Comput Ind Eng 33:697–700

    Google Scholar 

  • Liu Q, Zhao Q, Zang W (2008) Study on multi-objective optimization of flow allocation in a multicommodity stochastic-flow network with unreliable nodes. J Appl Math Comput 28(1–2):185–198

    Google Scholar 

  • Liu L, Cao X, ChengY (2013) Energy-aware optimal resource allocation in MR-MC wireless networks. In: IEEE global communications conference (GLOBECOM). IEEE, Atlanta, GA, USA, pp 4865–4870

  • Liu L, Cao X, Cheng Y, Du L, Song W, Wang Y (2014) Energy-efficient capacity optimization in wireless networks. In: IEEE conference on computer communications. IEEE, Toronto, ON, Canada, pp 1384–1392

  • Lozovanu D, Fonoberova M (2006) Optimal dynamic multicommodity flows in networks. Electron Notes Discrete Math 25:93–100

    Google Scholar 

  • Lu Y, Benlic U, Wu Q (2019) A population algorithm based on randomized tabu thresholding for the multicommodity pickup-and-delivery traveling salesman problem. Comput Oper Res 101:285–297

    Google Scholar 

  • Machado C, Mayerle S, Trevisan V (2010) A linea model for compound multicommodity network flow problems. Comput Oper Res 37(6):1075–1086

    Google Scholar 

  • Madan R, Shah D, Lévêque O (2008) Product multicommodity flow in wireless networks. IEEE Trans Inf Theory 54(4):1460–1476

    Google Scholar 

  • Maharjan B, Matis TI (2012) Multicommodity flow network model of the flight gate assignment problem. Comput Ind Eng 63(4):1135–1144

    Google Scholar 

  • Mahey P, de Souza MC (2007) Local optimality conditions for multicommodity flow problems with separable piecewise convex costs. Oper Res Lett 35(2):221–226

    Google Scholar 

  • Mamer JW, McBride RD (2000) A decomposition-based pricing procedure for large-scale linear programs: an application to the linear multicommodity flow problem. Manag Sci 46(5):693–709

    Google Scholar 

  • Manfren M (2012) Multicommodity network flow models for dynamic energy management—mathematical formulation. Energy Proc 14:1380–1385

    Google Scholar 

  • Marla L, Barnhart C, Biyani V (2014) A decomposition approach for commodity pickup and delivery with time-windows under uncertainty. J Sched 17(5):489–506

    Google Scholar 

  • Masri H, Krichen S, Guitouni A (2015) A multi-start variable neighborhood search for solving the single path multicommodity flow problem. Appl Math Comput 251:132–142

    Google Scholar 

  • Masri H, Krichen S, Guitouni A (2019) Metaheuristics for solving the bi-objective single-path multicommodity communication flow problem. Int Trans Oper Res 26(2):589–614

    Google Scholar 

  • Maurras J-F, Vaxes Y (1997) Multicommodity network flow with jump constraints. Discrete Math 165:481–486

    Google Scholar 

  • McBride RD (1998) advances in solving the multicommodity-flow problem. Interfaces 28(2):32–41

    Google Scholar 

  • McBride R, Mamer J (2001) Solving the undirected multicommodity flow problem using a shortest path-based pricing algorithm. Netw Int J 38(4):181–188

    Google Scholar 

  • McCarter M, Barker K, Johansson J, Ramirez-Marquez E, J. (2018) A bi-objective formulation for robust defense strategies in Multicommodity networks. Reliab Eng Systm Saf 176:154–161

    Google Scholar 

  • McDiarmid C, Scott A, Withers P (2017) Uniform multicommodity flows in the hypercube with random edge-capacities. Random Struct Algorithms 50(3):437–463

    Google Scholar 

  • Mejri I, Layeb S, Haouari M, Zeghal Mansour F (2019) A simulation-optimization approach for the stochastic discrete cost multicommodity flow problem. Eng Optim 52:1–20

    Google Scholar 

  • Mendes RR, Yamakami A, Alves IC (1997) Modelling and solving a class of fuzzy multicommodity transportation problem. In: Proceedings of the sixth IEEE international conference on IEEE fuzzy systems, vol 1, pp 313-318

  • Mesquita M, Moz M, Paias A, Pato M (2015) A decompose-and-fix heuristic based on Multicommodity flow models for driver rostering with days-off pattern. Eur J Oper Res 245(2):423–437

    Google Scholar 

  • Minoux M (2001) Discrete cost multicommodity network optimization problems and exact solution methods. Ann Oper Res 106(1–4):19–46

    Google Scholar 

  • Mohammadi M, Jula P, Tavakkoli-Moghaddam R (2017) Design of a reliable multi-modal multicommodity model for hazardous materials transportation under uncertainty. Eur J Oper Res 257(3):792–809

    Google Scholar 

  • Moitra A (2009) Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: 50th annual IEEE symposium on foundations of computer science. IEEE, Atlanta, GA, USA, pp 3–12

  • Mollah MA, Yuan X, Pakin S, Lang M (2017) Rapid calculation of max-min fair rates for multicommodity flows in fat-tree networks. IEEE Trans Parallel Distrib Syst 29(1):156–168

    Google Scholar 

  • Momeni M, Sarmadi M (2016) A genetic algorithm based on relaxation induced neighborhood search in a local branching framework for capacitated multicommodity network design. Netw Spatial Econ 16(2):447–468

    Google Scholar 

  • Morabito R, de Souza MC, Vazquez M (2014) Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks. Eur J Oper Res 232(3):618–629

    Google Scholar 

  • Moradi S, Raitha A, Ehrgott M (2015) Abi-objective column generation algorithm for the Multicommodity minimum cost flow problem. Eur J Oper Res 244(2):1–10

    Google Scholar 

  • Moshref-Javadi M, Lee S (2016) The customer-centric, multicommodity vehicle routing problem with split delivery. Expert Syst Appl 56:335–348

    Google Scholar 

  • Moungla H, Touati N, Mehaoua A (2013) Efficient heterogeneous communication range management for dynamic WBAN topology routing. In: First international symposium on future information and communication technologies for ubiquitous healthcare (Ubi-HealthTech). IEEE, Jinhua, China, pp 1–5

  • Moz M, Pato M (2003) An integer multicommodity flow model applied to the rerostering of nurse schedules. Ann Oper Res 119(1–4):285–301

    Google Scholar 

  • Moz M, Pato M (2004) Solving the problem of rerostering nurse schedules with hard constraints: new multicommodity flow models. Ann Oper Res 128(1–4):179–197

    Google Scholar 

  • Mrad M, Haouari M (2008) Optimal solution of the discrete cost multicommodity network design problem. Appl Math Comput 204(2):745–753

    Google Scholar 

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

    Google Scholar 

  • Myung Y-S (2001) An efficient algorithm for the ring loading problem with integer demand splitting. SIAM J Discrete Math 14(3):291–298

    Google Scholar 

  • Myung Y-S (2006) Multicommodity flows in cycle graphs. Discrete Appl Math 154(11):1615–1621

    Google Scholar 

  • Myung Y-S, Kim H-G, Tcha D-W (1997) Optimal load balancing on SONET bidirectional rings. Oper Res 45(1):148–152

    Google Scholar 

  • Nace D, Doan LN, Klopfenstein O, Bashllari A (2008) Max–min fairness in multicommodity flows. Comput Oper Res 35(2):557–573

    Google Scholar 

  • Nagamochi H, Ibaraki T (1990) Multicommodity flows in certain planar directed networks. Discrete Appl Math 27(1–2):125–145

    Google Scholar 

  • Nasiri GR, Davoudpour H, Movahedi Y (2010) A genetic algorithm approach for the multi-commodity, multi-period distribution planning in a supply chain network design. In: International conference on swarm, evolutionary, and memetic computing. Springer, Berlin, pp 494–505

  • Noguera JF, Leirens S (2010) Modelling and simulation of a multicommodity pipeline network. In: IEEE ANDESCON. IEEE, Bogota, Colombia pp 1–6

  • Oğuz M, Bektaş T, Bennell J (2018) Multicommodity flows and Benders decomposition for restricted continuous location problems. Eur J Oper Res 266(3):851–863

    Google Scholar 

  • Okamura H (1983) Multicommodity flows in graphs. Discrete Appl Math 6(1):55–62

    Google Scholar 

  • Okamura H, Seymour PD (1981) Multicommodity flows in planar graphs. J Comb Theory Ser B 31(1):75–81

    Google Scholar 

  • Onaga K, Kakusho O (1971) On feasibility conditions of multicommodity flows in networks. IEEE Trans Circuit Theory 18(4):425–429

    Google Scholar 

  • Ouaja W, Richards B (2004) A hybrid multicommodity routing algorithm for traffic engineering. Netw Int J 43(3):125–140

    Google Scholar 

  • Ouorou A, Mahey P (2000) A minimum mean cycle cancelling method for nonlinear multicommodity flow problems. Eur J Oper Res 121(3):532–548

    Google Scholar 

  • Ouorou A, Mahey P, Vial J-P (2000) A survey of algorithms for convex multicommodity flow problems. Manag Sci 46(1):126–147

    Google Scholar 

  • Ouorou A, Luna H, Mahey P (2001) Multicommodity network expansion under elastic demands. Optim Eng 2(3):277–292

    Google Scholar 

  • Ozdaglar, A. E., & Bertsekas, D. P. (2004). Optimal solution of integer multicommodity flow problems with application in optical networks. In: Frontiers in global optimization, pp 411–435

  • Padmanabh K, Roy R (2006) Multicommodity flow based maximum lifetime routing in wireless sensor network. In: 12th international conference on parallel and distributed systems—(ICPADS'06). IEEE, Minneapolis, MN, USA, pp 1–8

  • Papadimitriou D, Fortz B, Gorgone E (2015) Lagrangian relaxation for the time-dependent combined network design and routing problem. In: IEEE international conference on communications (ICC). IEEE, London, UK, pp 6030–6036

  • Paraskevopoulos DC, Gürel S, Bektas T (2016) The congested multicommodity network design problem. Transp Res Part E: Logist Transp Rev 85:166–187

    Google Scholar 

  • Paraskevopoulos DC, Bektas T, Crainic TG, Potts CN (2015) A cycle-based evolutionary algorithm for the Þxed-charge capacitated multicommodity network design problem. Eur J Oper Res 253(2):1–35

    Google Scholar 

  • Pierre-Olivier B, Walid B-A, Eric G (2013) A new model for multicommodity flow problems, and a strongly polynomial algorithm for single-source maximum concurrent flow. Electron Notes Discrete Math 41:311–318

    Google Scholar 

  • Pióro M, Fouquet Y, Nace D, Poss M (2016) Optimizing flow thinning protection in multicommodity networks with variable link capacity. Oper Res 64(2):273–289

    Google Scholar 

  • Pirkul H, Jayaraman V (1998) a multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Comput Oper Res 25(10):869–878

    Google Scholar 

  • Poh T-V, Jiang J, Reed MJ (2004) Multicommodity flow optimization in support for packet-switched network traffic engineering. In: International workshop on IP operations and management. IEEE, Beijing, China, pp 23–28

  • Powell WB, Carvalho TA (1997) Dynamic control of multicommodity fleet management problems. Eur J Oper Res 98(3):522–541

    Google Scholar 

  • Psaraftis HN (2011) A multi-commodity, capacitated pickup, and delivery problem: the single and two-vehicle cases. Eur J Oper Res 215(3):572–580

    Google Scholar 

  • Qu Y, Bektaş T, Bennell J (2016) Sustainability SI: multimode multicommodity network design model for intermodal freight transportation with transfer and emission costs. Netw Spatial Econ 16(1):303–329

    Google Scholar 

  • Quansheng L, Peng Z (2013) Research on the disrupted airline scheduling. In: IEEE 10th international conference on service systems and service management (ICSSSM), pp 332–336

  • Queiroz M, Humes C (2001) The projected pairwise multicommodity flow polyhedron. Appl Math Lett 14(4):443–448

    Google Scholar 

  • Quilliot A, Liberalino H, Bernay B (2013) Scale multicommodity flow handling on dynamic networks. In: International conference on large-scale scientific computing. Springer, Berlin, pp 297–304

  • Rahmaniani R, Crainic T, Gendreau M, Rei W (2018) Accelerating the Benders decomposition method: application to stochastic network design problems. SIAM J Optim 28(1):875–903

    Google Scholar 

  • Ralphs TK, Galati MV (2011) Decomposition methods for integer programming. In: Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC (eds) Wiley encyclopedia of operations research and management science

  • Retvari G, Biro JJ, Cinkler T (2004) A novel lagrangian-relaxation to the minimum cost multicommodity flow problem and its application to OSPF traffic engineering. In: Ninth international symposium on computers and communications. IEEE, Alexandria, Egypt, pp 957–962

  • Ríos-Mercado RZ, López-Pérez JF, Castrillón-Escobar A (2013) A GRASP for a multi-depot multicommodity pickup and delivery problem with time windows and heterogeneous fleet in the bottled beverage industry. In: International conference on computational logistics. Springer, Berlin, pp 143–157

  • Robinson AR, Chan Y, Dietz DC (2006) Detecting a security disturbance in multi commodity stochastic networks. Telecommun Syst 31(1):11–27

    Google Scholar 

  • Rodrıguez-Martın I, Salazar-Gonzalez JJ (2011) The multicommodity one-to-one pickup-and-delivery traveling salesman problem: a metaheuristic. In: International conference on network optimization. Springer, Berlin, pp 401–405

  • Rothfarb B, Frisch I (1970) Common terminal multicommodity flow with a concave objective function. SIAM J Appl Math 18(2):489–502

    Google Scholar 

  • Rudi A, Frohling M, Zimmer K, Schultmann F (2014) Freight transportation planning considering carbon emissions and in-transit holding costs: a capacitated Multicommodity network flow model. EURO J Transp Logist 5(2):1–38

    Google Scholar 

  • Sallam G, Gupta G, Li B, Ji B (2018) Shortest path and maximum flow problems under service function chaining constraints. In: IEEE conference on computer communications IEEE INFOCOM 2018, pp 2132–2140

  • Samani A, Wang M (2018) MaxStream: SDN-based flow maximization for video streaming with QoS enhancement. In: IEEE 43rd conference on local computer networks (LCN), pp 287–290

  • Sami S, Lin L, Shehabinia A, Su R, Chong C, Jeon S (2014) Discrete-event based vehicle dispatching and scheduling in multicommodity transportations. In: 13th international conference on control automation robotics & vision (ICARCV). IEEE, Singapore, pp 169–174

  • Sankaran J (1995) Column generation applied to linear programs in course registration. Eur J Oper Res 87(2):328–342

    Google Scholar 

  • Sarubbi J, Mateus GR (2007) Model and algorithms for the multicommodity traveling salesman problem. In: 7th international conference on hybrid intelligent systems. IEEE, Kaiserlautern, Germany, pp 113–119

  • Sarubbi J, Miranda G, Luna HP, Mateus G (2008) A cut-and-branch algorithm for the multicommodity traveling salesman problem. In: IEEE international conference on service operations and logistics, and informatics. IEEE, Beijing, China, pp 1806–1811

  • Schneur RR, Orlin JB (1998) A scaling algorithm for multicommodity flow problems. Oper Res 46(2):231–246

    Google Scholar 

  • Schauer C, Raidl GR (2016) A multicommodity flow-based model for multi-layer hierarchical ring network design. Electron Notes Discrete Math 52:189–196

    Google Scholar 

  • Schrijver A (1991) Short proofs on multicommodity flows and cuts. J Comb Theory Ser B 53(1):32–39

    Google Scholar 

  • Sedeno-Noda A, Gonzalez-Martın C, Gutierrez J (2005) The bi-objective undirected two-commodity minimum cost flow problem. Eur J Oper Res 164(1):89–103

    Google Scholar 

  • Seymour P (2015) Criticality for multicommodity flows. J Comb Theory Ser B 110:136–179

    Google Scholar 

  • Shepherd B, Zhang L (2001) A cycle augmentation algorithm for minimum cost multicommodity flows on a ring. Discrete Appl Math 110(2–3):301–315

    Google Scholar 

  • Shetty B, Muthukrishnan R (1990) A Parallel projection for the multicommodity network model. J Oper Res Soc 41(9):837–842

    Google Scholar 

  • Shi L, Meyer R, Bozbay M, Miller A (2004) A nested partitions framework for solving large-scale multicommodity facility location problems. J Syst Sci Syst Eng 13(2):158–179

    Google Scholar 

  • Shi H, Blaauwbroek N, Nguyen P, Kamphuis R, (. (2015) Energy management in multicommodity smart energy systems with a greedy approach. Appl Energy 167:385–396

    Google Scholar 

  • Shishehgar S, Tavakkoli-Moghaddam R, Siadat A, Mohammadi M (2014) Design of a dynamic bi-objective relief routing network in the earthquake response phase. In: IEEE international conference on industrial engineering and engineering management. IEEE, Bandar Sunway, Malaysia, pp 325–329

  • Shitrit HB, Berclaz J, Fleuret F, Fua P (2014) Multicommodity network flow for tracking multiple people. IEEE Trans Pattern Anal Mach Intell 36(8):1614–1627

    Google Scholar 

  • Singh I, Ahn C (1978) A dynamic multicommodity model of the agricultural sector. Eur Econ Rev 11(2):155–179

    Google Scholar 

  • Srivastav A, Stangier P (2000) On complexity, representation, and approximation of integral multicommodity flows. Discrete Appl Math 99(1–3):183–208

    Google Scholar 

  • Sun C, Wallace S, Luo L (2017a) Stochastic multicommodity network design: the quality of deterministic solutions. Oper Res Lett 45(3):266–268

    Google Scholar 

  • Sun L, Karwan M, Kwon C (2017b) Generalized bounded rationality and robust multicommodity network design. Oper Res 66(1):42–57

    Google Scholar 

  • Tanonkou G, Benyoucef L, Xie X (2007) Design of multicommodity distribution network with random demands and supply lead-times. In: IEEE international conference on automation science and engineering. IEEE, Scottsdale, AZ, USA, pp 698–703

  • Tao PD (2002) DC programming approach for multicommodity network optimization problems with step increasing cost functions. J Global Optim 22(1–4):205–232

    Google Scholar 

  • Teyeb H, Balma A, Hadj-Alouane N, Tata S (2014) Optimal virtual machine placement in large-scale cloud systems. In: IEEE 7th international conference on cloud computing. IEEE, Anchorage, AK, USA pp 424–431

  • Thanh PN, Péton O, Bostel N (2010) A linear relaxation-based heuristic approach for logistics network design. Comput Ind Eng 59(4):964–975

    Google Scholar 

  • Thiongane B, Cordeau J-F, Gendron B (2015) Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem. Comput Oper Res 53:1–8

    Google Scholar 

  • Tomlin J (1966) Minimum-cost multicommodity network flows. Oper Res 14(1):45–51

    Google Scholar 

  • Tonneau Q, Bostel N, Dejax P, Hospital R, Mülhauptz V, Yeung T (2015) Multimodal multi-flow problem with transformation: application to waste supply chain. In: International conference on industrial engineering and systems management (IESM). IEEE, Seville, Spain, pp 876–882

  • Topaloglu H, Powell W (2006) Dynamic-programming approximations for stochastic time-staged integer multicommodity-flow problems. INFORMS J Comput 18(1):31–42

    Google Scholar 

  • Truemper K, Soun Y (1979) Minimal forbidden subgraphs of unimodular multicommodity networks. Math Oper Res 4(4):379–389

    Google Scholar 

  • Truffot J, Duhamel C, Mahey P (2005) Using branch-and-price to solve multicommodity k-splittable flow problems. In: Proceedings of international network optimization conference (INOC)

  • Vahdani B, Veysmoradi D, Shekari N, Mousavi S (2018) Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repair. Neural Comput Appl 30(3):835–854

    Google Scholar 

  • Vaziri S, Etebari F, Vahdani B (2019) Development and optimization of a horizontal carrier collaboration vehicle routing model with multicommodity request allocation. J Clean Prod 224:492–505

    Google Scholar 

  • Velichko A, Gribova V, Fedori L (2018) Simulation software for multicommodity flows model of interregional trade. In: 3rd Russian-Pacific conference on computer technology and applications (RPC). IEEE, Vladivostok, Russia, pp 1–5

  • Venkatadri U, Elaskari S, Kurdi R (2017) A Multicommodity network flow-based formulation for the multi-period cell formation problem. Int J Adv Manuf Technol 91(1–4):175–187

    Google Scholar 

  • Vu DM, Crainic TG, Toulouse M (2013) A three-phase metaheuristic for capacitated multicommodity fixed-cost network design with design-balance constraints. J Heuristics 19(5):757–795

    Google Scholar 

  • Wadie CS, Ashour M (2013) Multicommodity flow, multiple paths load balanced routing in ad-hoc networks. In: 15th international conference on advanced communications technology (ICACT). IEEE, PyeongChang, South Korea, pp 1128–1133

  • Wagner D, Raidl G, Pferschy U, Mutzel P, Bachhiesl P (2007) A multicommodity flow approach for the design of the last mile in real-world fiber optic networks. In: Operations research proceedings. Springer, Berlin, Heidelberg, pp 197–202

  • Wang D, Kleinberg R (2009) Analyzing quadratic unconstrained binary optimization problems via multicommodity flows. Discrete Appl Math 157(18):3746–3753

    Google Scholar 

  • Wang IL (2003) Shortest paths and multicommodity network flows (doctoral dissertation). School of Industrial and Systems Engineering, Georgia Institute of Technology

    Google Scholar 

  • Ward J (1999) Minimum-aggregate-concave-cost multicommodity flows in strong-series-parallel networks. Math Oper Res 24(1):106–129

    Google Scholar 

  • Wei K, Li X, Lin S, Yue C (2014) A simulated annealing based heuristic for the multi-source single-path Multicommodity network flow problem. In: 11th international conference on service systems and service management (ICSSSM). IEEE, Beijing, China, pp 1–6

  • Weibin D, Zhang J, Xiaoqian S (2017) On solving Multicommodity flow problems: an experimental evaluation. Chin J Aeronaut 30(4):1481–1492

    Google Scholar 

  • Whitman M, Barker K, Johansson J, Darayi M (2017) Component importance for multicommodity networks: application in the swedish railway. Comput Ind Eng 112:274–288

    Google Scholar 

  • Wright M, Gomes G, Horowitz R, Kurzhanskiy A (2017) On node models for high-dimensional road networks. Transp Res Part B: Methodol 105:212–234

    Google Scholar 

  • Xu X, Zhang Y, Lu J (2017) Routing optimization of small satellite networks based on multicommodity flow. In: International conference on machine learning and intelligent communications. Springer, Cham, pp 355–363

  • Xue D, Li Z, Xue N (2012) Multicommodity logistics network design based on heuristic algorithm. In: Advances in electronic engineering, communication and management, vol 1. Springer, Berlin, Heidelberg, pp 75–80

  • Yaghini M, Akhavan R (2012) Multicommodity network design problem in rail freight transportation planning. Proc-Soc Behav Sci 43:728–739

    Google Scholar 

  • Yaghini M, Momeni M, Sarmadi M (2012) A Simplex-based simulated annealing algorithm for node-arc capacitated multicommodity network design. Appl Soft Comput 12(9):2997–3003

    Google Scholar 

  • Yeh W-C (2008) A simple minimal path method for estimating the weighted multicommodity multistate unreliable networks reliability. Reliab Eng Syst Saf 93(1):125–136

    Google Scholar 

  • Yeh W-C (2011) A sequential decomposition method for estimating flow in a multi-commodity multistate network. IEEE Trans Reliab 60(3):612–621

    Google Scholar 

  • Zaleta NC, Socarrás AM (2004) Tabu Search-based algorithm for capacitated multicommodity network design problem. In: 14th international conference on electronics, communications and computers. IEEE, Veracruz, Mexico, pp 1–5

  • Zanjirani Farahani R, Miandoabchi E, Szeto W, Rashidi H (2013) A review of urban transportation network design problems. Eur J Oper Res 229(2):281–302

    Google Scholar 

  • Zantuti AF (2005) The capacity and non-simultaneously multicommodity flow problem in wide area network and data flow management. In: 18th international conference on systems engineering (ICSEng'05). IEEE, Las Vegas, NV, USA, pp 76–80

  • Zeng Z, Meng L, Hong X (2018) Integrated optimization of rolling stock and crew rescheduling for high-speed railway. In: International conference on intelligent rail transportation (ICIRT). IEEE, Singapore, pp 1–5

  • Zhang P, Fan N (2017) Analysis of budget for interdiction on multicommodity network flows. J Global Optim 67(3):495–525

    Google Scholar 

  • Zhang D, Yu C, Desai J, Lau HY, Srivathsan S (2017a) A time-space network flow approach to dynamic repositioning in bicycle sharing systems. Transp Res part B: Methodol 103:188–207

    Google Scholar 

  • Zhang J, Zhang X, Sun M (2017) Two-level decomposition for Multicommodity multicast traffic engineering. In: IEEE 36th international performance computing and communications conference (IPCCC). IEEE, San Diego, CA, USA, pp 1–2

  • Zhang J, Zhang X, Sun M, Yang C (2018) Minimizing the maximum link utilization in multicast multicommodity flow networks. IEEE Commun Lett 22(7):1478–1481

    Google Scholar 

  • Zhang T, Li H, Zhang S, Wang P, Li J (2018) STAG-based dynamic two-commodity maximum flow algorithm for time-varying networks. In: 10th international conference on wireless communications and signal processing (WCSP). IEEE, Hangzhou, China, pp 1–5

  • Zhang T, Li H, Li J, Zhan S, Shen H (2018) A dynamic combined flow algorithm for the two-commodity max-flow problem over delay-tolerant networks. IEEE Trans Wireless Commun 17(12):7879–7893

    Google Scholar 

  • Zhang Z, Cheang B, Li C, Lim A (2019) Multicommodity demand fulfillment via simultaneous pickup and delivery for a fast-fashion retailer. Comput Oper Res 103:81–96

    Google Scholar 

  • Zhong W, Chen S, Geng Y, Yoshimura T (2013) Lagrangian relaxation based pin assignment and through-silicon via planning for 3-D SoCs. In: 10th international conference on ASIC. IEEE, Shenzhen, China, pp 1–4

Download references

Author information

Authors and Affiliations

  1. CIIORG, Persian Gulf University, 75168, Bushehr, Iran

    Khodakaram Salimifard

  2. Dipartimento di Informatica, Università degli Studi di Torino, Corso Svizzera 185, 10149, Torino, Italy

    Sara Bigharaz

Authors
  1. Khodakaram Salimifard
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sara Bigharaz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Khodakaram Salimifard.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Salimifard, K., Bigharaz, S. The multicommodity network flow problem: state of the art classification, applications, and solution methods. Oper Res Int J 22, 1–47 (2022). https://doi.org/10.1007/s12351-020-00564-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-020-00564-8

Keywords

Search

Navigation