General Models for Optimal Design of Star–Star Gathering Pipeline Network
Publication: Journal of Pipeline Systems Engineering and Practice
Volume 12, Issue 3
Abstract
The arrangement of gas gathering stations (GGS) and central processing facilities (CPF) in the natural gas gathering pipeline network really counts. Their reasonable number and locations can make the pipeline network economically optimal. Although many scholars have studied the layout optimization of the star–star pipeline network, they have only studied their specific constraints, such as processing capacity, and have not proposed a comprehensive mathematical model. Based on the star-shaped pipeline network structure, this paper proposes a star–star gas gathering station and central processing facility location problem (SSCPLP). Considering the constraints such as capacity, number, radius, and their combination, a general mathematical model of the problem is established correspondingly, which can be used to optimize the pipeline network layout and station location under different constraints according to the engineering application environment. Our layout optimization problem is a location-allocation problem of GGSs and the CPF in discrete space and is a kind of nondeterministic polynomial complete (NP-complete) problem, which can be expressed as a mixed-integer linear programming problem and solved by CPLEX. Two random cases and two real-world cases of actual gas gathering fields are analyzed under three different constraints (capacity, number, and radius). The obtained results not only prove the correctness of the proposed model, but also verify that the model can solve the layout optimization of the actual star–star topology under different engineering requirements.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
This work was part of the program “Study on the optimization method and architecture of oil and gas pipeline network design in discrete space and network space,” funded by the National Natural Science Foundation of China, Grant No. 51704253. The authors are grateful to all study participants.
References
Akinc, U., and B. M. Khumawala. 1977. “An efficient branch and bound algorithm for the capacitated warehouse location problem.” Manage. Sci. 23 (6): 585–594. https://doi.org/10.1287/mnsc.23.6.585.
Alumur, S. A., B. Y. Kara, and O. E. Karasan. 2009. “The design of single allocation incomplete hub networks.” Transp. Res. Part B: Methodol. 43 (10): 936–951. https://doi.org/10.1016/j.trb.2009.04.004.
Alumur, S. A., H. Yaman, and B. Y. Kara. 2012. “Hierarchical multimodal hub location problem with time-definite deliveries.” Transp. Res. Part E 48 (6): 1107–1120. https://doi.org/10.1016/j.tre.2012.04.001.
Ambrosino, D., and A. Sciomachen. 2016. “A capacitated hub location problem in freight logistics multimodal networks.” Optim. Lett. 10 (5): 875–901. https://doi.org/10.1007/s11590-016-1022-8.
Babaoğlu, İ. 2016. “Utilization of bat algorithm for solving uncapacitated facility location problem.” In Vol. 5 of Proc., in Adaptation, learning and optimization: Intelligent and evolutionary systems, edited by K. Lavangnananda, S. Phon-Amnuaisuk, W. Engchuan, and J. Chan. Cham, Switzerland: Springer.
Bahl, L. R., and D. T. Tang. 1972. “Optimization of concentrator locations in teleprocessing networks. In Proc. Symp. on Computer-Communication Networks and Teletraffic. New York: Polytechnic Press.
Balinski, M. L. 1965. “Integer programming: Methods uses computations.” Manage. Sci. 12 (3): 253–313. https://doi.org/10.1287/mnsc.12.3.253.
Calık, H., S. A. Alumur, B. Y. Kara, and O. E. Karasan. 2009. “A tabu-search based heuristic for the hub covering problem over incomplete hub networks.” Comput. Oper. Res. 36 (12): 3088–3096. https://doi.org/10.1016/j.cor.2008.11.023.
Erlenkotter, D. 1978. “A dual-based procedure for uncapacitated facility location.” Oper. Res. 26 (6): 992–1009. https://doi.org/10.1287/opre.26.6.992.
Feldman, E., F. A. Lehrer, and T. L. Ray. 1966. “Warehouse location under continuous economies of scale.” Manage. Sci. 12 (9): 670–684. https://doi.org/10.1287/mnsc.12.9.670.
Fernandes, D. R., C. Rocha, D. Aloise, G. M. Ribeiro, E. M. Santos, and A. Silva. 2014. “A simple and effective genetic algorithm for the two-stage capacitated facility location problem.” Comput. Ind. Eng. 75 (1): 200–208. https://doi.org/10.1016/j.cie.2014.05.023.
Geoffrion, A. M., and R. McBride. 1978. “Lagrangian relaxation applied to capacitated facility location problems.” AIIE Trans. 10 (1): 40–47. https://doi.org/10.1080/05695557808975181.
Gondran, M., and M. Minoux. 1985. Graphes et Algorithmes. Paris: Eyrolles.
Guastaroba, G., and M. G. Speranza. 2012. “Kernel search for the capacitated facility location problem.” J. Heuristics 18 (6): 877–917. https://doi.org/10.1007/s10732-012-9212-8.
Guignard, M., and K. Spielberg. 1979. “A direct dual method for the mixed plant location problem with some side constraints.” Math. Program. 17 (1): 198–228. https://doi.org/10.1007/BF01588244.
Guo, P., W. Cheng, and Y. Wang. 2017. “Hybrid evolutionary algorithm with extreme machine learning fitness function evaluation for two-stage capacitated facility location problems.” Expert Syst. Appl. 71 (Apr): 57–68. https://doi.org/10.1016/j.eswa.2016.11.025.
Hakimi, S. L. 1964. “Optimum locations of switching centers and the absolute centers and medians of a graph.” Oper. Res. 12 (3): 450–459. https://doi.org/10.1287/opre.12.3.450.
Kershenbaum, A. 1987. “Capacitated facility location.” In Current advances in distributed computing and communications. New York: Computer Science Press.
Kole, A., P. Chakrabarti, and S. Bhattacharyya. 2014. “An ant colony optimization algorithm for uncapacitated facility location problem.” Artif. Intell. Appl. 2014 (1): 55–61. https://doi.org/10.15764/AIA.2014.01004.
Kuehn, A. A., and M. J. Hamburger. 1963. “A heuristic program for locating warehouses.” Manage. Sci. 9 (4): 643–666. https://doi.org/10.1287/mnsc.9.4.643.
Lo, C. C., and A. Kershenbaum. 1989. “A two-phase algorithm and performance bounds for the star-star concentrator location problem.” IEEE Trans. Commun. 37 (11): 1151–1163. https://doi.org/10.1109/26.46509.
Mirzaian, A. 1985. “Lagrangian relaxation for the star-star concentrator location problem: Approximation algorithm and bounds.” Networks 15 (1): 1–20. https://doi.org/10.1002/net.3230150102.
Mirzaian, A., and K. Steiglitz. 1981. “A note on the complexity of the star-star concentrator problem.” IEEE Trans. Commun. 29 (10): 1549–1552. https://doi.org/10.1109/TCOM.1981.1094884.
Nickel, S., A. Schöbel, and T. Sonneborn. 2001. “Hub location problems in urban traffic networks.” In Mathematical methods on optimization in transportation systems. Applied optimization, edited by M. Pursula and J. Niittymäki, 95–107. Boston: Springer.
O’Kelly, M. E., and H. J. Miller. 1994. “The hub network design problem. A review and synthesis.” J. Transp. Geogr. 2 (1): 31–40. https://doi.org/10.1016/0966-6923(94)90032-9.
Petrek, J., and V. Sledt. 2001. “A large hierarchical network star-star topology design algorithm.” Trans. Emerging Telecommun. Technol. 12 (6): 511–522. https://doi.org/10.1002/ett.4460120607.
Posta, M., J. A. Ferland, and P. Michelon. 2014. “An exact cooperative method for the uncapacitated facility location problem.” Math. Program. Comput. 6 (3): 199–231. https://doi.org/10.1007/s12532-014-0065-z.
Rahmani, A., and S. A. Mirhassani. 2014. “A hybrid Firefly-Genetic Algorithm for the capacitated facility location problem.” Inf. Sci. 283 (Nov): 70–78. https://doi.org/10.1016/j.ins.2014.06.002.
Saha, S., A. Kole, and K. Dey. 2011. “A modified continuous particle swarm optimization algorithm for uncapacitated facility location problem.” In Information technology and mobile communication. Communications in computer and information science, edited by V. V. Das, G. Thomas, and F. Lumban Gaol. Berlin: Springer.
Sakir, E., K. Tarık, and T. Nükhet. 2014. Fuzzy C-means algorithm with fixed cluster centers for uncapacitated facility location problems: Turkish case study. Berlin: Springer.
Sun, M. 2012. “A tabu search heuristic procedure for the capacitated facility location problem.” J. Heuristics 18 (1): 91–118. https://doi.org/10.1007/s10732-011-9157-3.
Wang, B., Y. Liang, M. Yuan, J. Wang, H. Zhang, and X. Li. 2018a. “Optimal design of oilfield surface pipeline networks for the cyclic water injection development method.” J. Pet. Sci. Eng. 171 (Dec): 1400–1408. https://doi.org/10.1016/j.petrol.2018.08.065.
Wang, B., Y. Liang, T. Zheng, M. Yuan, and H. Zhang. 2018b. “Multi-objective site selection optimization of the gas-gathering station using NSGA-II.” Process Saf. Environ. Prot. 119 (Oct): 350–359. https://doi.org/10.1016/j.psep.2018.08.017.
Yaman, H. 2009. “The hierarchical hub median problem with single assignment.” Transp. Res. Part B Methodol. 43 (6): 643–658. https://doi.org/10.1016/j.trb.2009.01.005.
Yoon, M. G., and J. Current. 2008. “The hub location and network design problem with fixed and variable arc costs: Formulation and dual-based solution heuristic.” J. Oper. Res. Soc. 59 (1): 80–89. https://doi.org/10.1057/palgrave.jors.2602307.
Zhang, H., Y. Liang, W. Zhang, B. Wang, X. Yan, and Q. Liao. 2017. “A unified MILP model for topological structure of production well gathering pipeline network.” J. Pet. Sci. Eng. 152 (Apr): 284–293. https://doi.org/10.1016/j.petrol.2017.03.016.
Zhang, H., X. Wei, M. A. Liang, and S. O. Management. 2015. “A new semi-Lagrangian relaxation method to solve the un-capacitated facility location problem.” Oper. Res. Trans. 19 (4): 37–47. https://doi.org/10.1016/j.jspi.2005.06.001.
Zhou, J., J. Gong, X. Li, T. Tong, M. Cheng, and S. Zhang. 2014. “Optimization of coalbed methane gathering system in China.” Adv. Mech. Eng. 6: 147381. https://doi.org/10.1155/2014/147381.
Zhou, J., G. Liang, and T. Deng. 2018. “Optimal design of star-tree oil-gas pipeline network in discrete space.” J. Pipeline Syst. Eng. Pract. 9 (1): 04017034. https://doi.org/10.1061/(ASCE)PS.1949-1204.0000302.
Zhou, J., G. Liang, T. Deng, and S. Zhou. 2017. “Optimization design of coalbed methane pipeline network-coupled wellbore/reservoir simulation.” Adv. Mech. Eng. 9 (6): 168781401770890. https://doi.org/10.1177/1687814017708905.
Zhou, J., J. Peng, G. Liang, and T. Deng. 2019. “Layout optimization of tree-tree gas pipeline network.” J. Pet. Sci. Eng. 173 (Feb): 666–680. https://doi.org/10.1016/j.petrol.2018.10.067.
Information & Authors
Information
Published In
Journal of Pipeline Systems Engineering and Practice
Volume 12 • Issue 3 • August 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Aug 7, 2020
Accepted: Dec 30, 2020
Published online: May 6, 2021
Published in print: Aug 1, 2021
Discussion open until: Oct 6, 2021
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.