July  2006, 2(3): 237-254. doi: 10.3934/jimo.2006.2.237

Maximum flow problem in the distribution network


Department of Mathematics, National Cheng-Kung University, Tainan, Taiwan


Product Development Department, Shinkong Life Insurance Co., LTD., Taipei, Taiwan


Department of Industrial and Information Management, National Cheng-Kung University, Tainan, Taiwan

Received  September 2005 Revised  December 2005 Published  July 2006

In this paper, we are concerned with the maximum flow problem in the distribution network, a new kind of network recently introduced by Fang and Qi. It differs from the traditional network by the presence of the $D$-node through which the commodities are to be distributed proportionally. Adding $ D $-nodes complicates the network structure. Particularly, flows in the distribution network are frequently increased through multiple cycles. To this end, we develop a type of depth-first-search algorithm which counts and finds all unsaturated subgraphs. The unsaturated subgraphs, however, could be invalid either topologically or numerically. The validity are then judged by computing the flow increment with a method we call the multi-labeling method. Finally, we also provide a phase-one procedure for finding an initial flow.
Citation: R.L. Sheu, M.J. Ting, I.L. Wang. Maximum flow problem in the distribution network. Journal of Industrial & Management Optimization, 2006, 2 (3) : 237-254. doi: 10.3934/jimo.2006.2.237

Zehui Shao, Huiqin Jiang, Aleksander Vesel. L(2, 1)-labeling of the Cartesian and strong product of two directed cycles. Mathematical Foundations of Computing, 2018, 1 (1) : 49-61. doi: 10.3934/mfc.2018003


I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929


Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119


Weishi Yin, Jiawei Ge, Pinchao Meng, Fuheng Qu. A neural network method for the inverse scattering problem of impenetrable cavities. Electronic Research Archive, 2020, 28 (2) : 1123-1142. doi: 10.3934/era.2020062


Jia Shu, Jie Sun. Designing the distribution network for an integrated supply chain. Journal of Industrial & Management Optimization, 2006, 2 (3) : 339-349. doi: 10.3934/jimo.2006.2.339


Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066


Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021, 11 (3) : 643-652. doi: 10.3934/mcrf.2021016


Paolo Maremonti. On the Stokes problem in exterior domains: The maximum modulus theorem. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 2135-2171. doi: 10.3934/dcds.2014.34.2135


Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks & Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255


Chun Zong, Gen Qi Xu. Observability and controllability analysis of blood flow network. Mathematical Control & Related Fields, 2014, 4 (4) : 521-554. doi: 10.3934/mcrf.2014.4.521


Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670


Ming Huang, Cong Cheng, Yang Li, Zun Quan Xia. The space decomposition method for the sum of nonlinear convex maximum eigenvalues and its applications. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1885-1905. doi: 10.3934/jimo.2019034


Ting Hu. Kernel-based maximum correntropy criterion with gradient descent method. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4159-4177. doi: 10.3934/cpaa.2020186


Yanfei Wang, Qinghua Ma. A gradient method for regularizing retrieval of aerosol particle size distribution function. Journal of Industrial & Management Optimization, 2009, 5 (1) : 115-126. doi: 10.3934/jimo.2009.5.115


Fabio Scalco Dias, Luis Fernando Mello. The center--focus problem and small amplitude limit cycles in rigid systems. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1627-1637. doi: 10.3934/dcds.2012.32.1627


Alexander Schaub, Olivier Rioul, Jean-Luc Danger, Sylvain Guilley, Joseph Boutros. Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem. Advances in Mathematics of Communications, 2020, 14 (3) : 491-505. doi: 10.3934/amc.2020060


Yan Wang, Yanxiang Zhao, Lei Wang, Aimin Song, Yanping Ma. Stochastic maximum principle for partial information optimal investment and dividend problem of an insurer. Journal of Industrial & Management Optimization, 2018, 14 (2) : 653-671. doi: 10.3934/jimo.2017067


Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062


Shaolin Ji, Xiaole Xue. A stochastic maximum principle for linear quadratic problem with nonconvex control domain. Mathematical Control & Related Fields, 2019, 9 (3) : 495-507. doi: 10.3934/mcrf.2019022


Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71

2020 Impact Factor: 1.801


  • PDF downloads (78)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]