×

zbMATH — the first resource for mathematics

A combined CLP-MILP approach for scheduling commodities in a pipeline. (English) Zbl 1208.90074
Summary: This paper addresses the problem of developing an optimization model to aid the operational scheduling in a real-world pipeline scenario. The pipeline connects refinery and harbor, conveying different types of commodities (gasoline, diesel, kerosene, etc.). An optimization model was developed to determine pipeline scheduling with improved efficiency. This model combines constraint logic programming (CLP) and mixed integer linear programming (MILP) in a CLP-MILP approach. The proposed model uses decomposition strategies, continuous time representation, intervals that indicate time constraints (time windows), and a series of operational issues, such as the seasonal and hourly cost of electric energy (on-peak demand hours). Real cases were solved in a matter of seconds. The computational results have demonstrated that the model is able to define new operational points to the pipeline, providing significant cost savings. Indeed the CLP-MILP model is an efficient tool to aid operational decision-making within this real-world pipeline scenario.

MSC:
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
90C11 Mixed integer programming
90C05 Linear programming
Software:
LINDO; LINGO; OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Buscemi, M. G., & Montanari, U. (2008). A survey of constraint-based programming paradigms. Computer Science Review, 2, 137–141. · Zbl 1302.68249 · doi:10.1016/j.cosrev.2008.10.001
[2] Cafaro, D. C., & Cerdá, J. (2004). Optimal scheduling of multiproduct pipeline systems using a non-discrete MILP formulation. Computers and Chemical Engineering, 28, 2053–2068. · doi:10.1016/j.compchemeng.2004.03.010
[3] COPEL Companhia Paranaense de Energia (Paranaense’s Company of Energy) (2009). Tax and tariffs of energy, on-line information available at http://www.copel.com in January 2009.
[4] Dantzig, G. B. (1963). Linear programming and extensions. Princeton: Princeton University Press. · Zbl 0108.33103
[5] Floudas, C. A. (1995). Nonlinear and mixed integer optimization: fundamentals and applications. New York: Oxford University Press. · Zbl 0886.90106
[6] Gomes, C. P., & Shmoys, D. (2002). The promise of LP to boost CSP techniques for combinatorial problems. In Fourth international workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems, Le Croisic, France (pp. 291–305).
[7] Heipcke, S. (1999). Combined modelling and problem solving in mathematical programming and constraint programming. Ph.D. thesis, University of Buckingham, UK. · Zbl 1054.90500
[8] Hooker, J. N. (2000) Wiley–Interscience Series in discrete mathematics and optimization. Logic-based methods for optimization: combining optimization and constraint satisfaction. New York: Wiley–Interscience. · Zbl 0974.90001
[9] Hooker, J. N. (2006). An integrated method for planning and scheduling to minimize tardiness. Constraints, 11, 139–157. · Zbl 1103.68811 · doi:10.1007/s10601-006-8060-2
[10] Hürlimann, T. (1998). An efficient logic-to-IP translation procedure. In International conference, applied mathematical programming and modeling, Lymassol, Cyprus (pp. 1–26).
[11] ILOG (2002a). ILOG OPL studio 3.6.1–user’s manual, ILOG Corporation, France.
[12] ILOG (2002b). ILOG OPL studio 3.6.1–language manual, ILOG Corporation, France.
[13] Kalvelagen, E. (2003). On solving the progressive party problem as a MIP. Computers & Operations Research, 30(11), 1713–1726. · Zbl 1088.90040 · doi:10.1016/S0305-0548(02)00101-6
[14] Kennedy, J. L. (1993). Oil and gas pipeline fundamentals. Oklahoma: PennWell Publishing Company.
[15] Lee, H., Pinto, J. M., Grossman, I. E., & Park, S. (1996). Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Industrial and Engineering Chemistry Research, 35, 1630–1641. · doi:10.1021/ie950519h
[16] Magatão, L. (2005). Constraint logic programming and mixed integer linear programming: towards a unified modeling framework. Ph.D. thesis, Graduate School in Electrical Engineering and Industrial Computer Science (CPGEI), Federal University of Technology–Paraná (UTFPR), Curitiba, Paraná, Brazil.
[17] Magatão, L., Arruda, L. V. R., & Neves, F. Jr (2004). A mixed integer programming approach for scheduling commodities in a pipeline. Computers and Chemical Engineering, 28(1–2), 171–185. · doi:10.1016/S0098-1354(03)00165-0
[18] Mitra, G., Lucas, C., Moody, S., & Hadjiconstantinou, E. (1994). Tools for reformulating logical forms into zero-one mixed integer programs. European Journal of Operational Research, 72, 262–276. · Zbl 0800.90719 · doi:10.1016/0377-2217(94)90308-5
[19] Moura, A. V., Souza, C. C., Cire, A. A., & Lopes, T. M. T. (2008). Planning and scheduling the operation of a very large oil pipeline network. In P. J. Stuckey (Ed.), LNCS : Vol. 5202. Proceedings of CP 2008 (pp. 36–51). Berlin: Springer.
[20] Neiro, S. M. S., & Pinto, J. M. (2004). A general modeling framework for the operational planning of petroleum supply chains. Computers and Chemical Engineering, 28, 871–896. · doi:10.1016/j.compchemeng.2003.09.018
[21] Neves-Jr, F., Arruda, L. V. R., Magatão, L., Stebel, S. L., Boschetto, S. N., Felizari, L. C., Czaikowski, D. I., Rocha, R., & Ribas, P. C. (2007). An efficient approach to the operational scheduling of a real-world pipeline network. In Computer aided chemical engineering : Vol. 24. Proceedings of 17th European symposium on computer aided process engineering (ESCAPE 17) (pp. 697–702). Bucareste, 2007. Amsterdam: Elsevier.
[22] Pettersson, M. P., Szymanek, R., & Kuchcinski, K. (2007). A CP-LP approach to network management in OSPF routing. In Proceedings of the 2007 ACM symposium on applied computing (pp. 311–315). Seoul, Korea.
[23] Régin, J. C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of the twelfth national conference on artificial intelligence (AAAI’94) (pp. 362–367). Seattle, Washington, United States, 1.
[24] Rejowski, R. Jr., & Pinto, J. M. (2004). Efficient MILP formulations and valid cuts for multiproduct pipeline scheduling. Computers and Chemical Engineering, 28, 1511–1528.
[25] Rejowski, R. Jr., & Pinto, J. M. (2008). A novel continuous time representation for the scheduling of pipeline systems with pumping yield rate constraints. Computers and Chemical Engineering, 32, 1042–1066. · doi:10.1016/j.compchemeng.2007.06.021
[26] Reklaitis, G. V. (1992). Overview of scheduling and planning of batch process operations. In Proceedings of the NATO advanced study institute on batch processing systems (pp. 660–705). Antalya, Turkey.
[27] Relvas, S., Matos, H. A., Barbosa-Póvoa, A. P. F. D., Fialho, J., & Pinheiro, A. S. (2006). Pipeline scheduling and inventory management of a multiproduct distribution oil system. Industrial and Engineering Chemistry Research, 45, 7841–7855. · doi:10.1021/ie060309c
[28] Relvas, S., Matos, H. A., Barbosa-Póvoa, A. P. F. D., & Fialho, J. (2007). Reactive scheduling framework for a multiproduct pipeline with inventory management. Industrial and Engineering Chemistry Research, 46, 5659–5672. · doi:10.1021/ie070214q
[29] Rossi, F. (2003). Constraint processing. Constraint logic programming. (pp. 413–440). San Francisco: Morgan Kaufmann. ISBN 978-1-55-860890-0.
[30] Rossi, F., Beek, P., & Walsh, T. (2006). Handbook of constraint programming. Foundations of artificial intelligence. New York: Elsevier. ISBN 0444527265. · Zbl 1175.90011
[31] Schrage, L. (2000). Optimization modeling with LINGO. Chicago: LINDO Systems Inc.
[32] Simonis, H. (2008). Constraint logic programming. Orsay: COSYTEC SA.
[33] Subrahmanyam, S., Bassett, M. H., Pekny, J. F., & Reklaitis, G. V. (1995). Issues in solving large scale planning, design and scheduling problems in batch chemical plants. Computers and Chemical Engineering, 19(suppl.), 577–582. · doi:10.1016/0098-1354(95)87097-0
[34] Van Hentenryck, P., Perron, L., & Puget, J. F. (2000). Search and strategies in OPL. ACM Transactions on Computational Logic, 1, 285–320. · Zbl 1365.90281 · doi:10.1145/359496.359529
[35] Wallace, M. (2007). Constraint programming–the paradigm to watch. Constraint Programming Letters, 1, 7–13.
[36] Williams, H. P. (1995). Logic applied to integer programming and integer programming applied to logic. European Journal of Operational Research, 81, 605–616. · Zbl 0906.90130 · doi:10.1016/0377-2217(93)E0359-6
[37] Williams, H. P., & Wilson, J. M. (1998). Connections between integer linear programming and constraint logic programming–an overview and introduction to the cluster of articles. INFORMS Journal on Computing, 10(3), 261–264. · Zbl 1049.90500 · doi:10.1287/ijoc.10.3.261
[38] Wu, D., & Ierapetritou, M. G. (2003). Decomposition approaches for the efficient solution of short-term scheduling problems. Computers and Chemical Engineering, 27, 1261–1276. · doi:10.1016/S0098-1354(03)00051-6
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.