631Accesses
9Citations
Abstract
Applying traditional integer programming techniques in order to solve real logistic problems can be an important challenge. To ensure tractability, real instances are often either simplified in scope or limited in size, given rise to solutions that may not address realistic issues. In this paper we present a novel approach to solve a multicommodity capacitated network flow problem with concave routing costs, considering also outsourcing, overload and underutilization facility costs. It is derived from a real NP production and transportation problem concerning to the processing of biological samples in a large health-care network, with consideration of volume-based price incentives—i.e. economies of scale—on the shipping costs. It is a tactical level model providing the global view of network layout and the coordinating policy among facilities with realistic assessment of long-term operations costs. The goal is to find an efficient resolution procedure in order to integrate it into a Decision Support System used by planners. With this aim, we analyse three alternative methods of linearizing the involved modified all-units discount cost function. Performance of the different modelling techniques is shown through extensive computations.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Aissaoui, N., Haouari, M., & Hassini, E. (2007). Supplier selection and order lot sizing modeling: A review.Computers & Operations Research,34(12), 3516–3540.
Amiri, A., & Pirkul, H. (1997). New formulation and relaxation to solve a concave-cost network flow problem.Journal of the Operational Research Society,48, 278–287.
Andrade-Pineda, J. L., Gonzalez-R, P. L., & Framinan, J. M. (2013). A decision-making tool for a regional network of clinical laboratories.Interfaces,43(4), 360–372.
Arshinder, Kanda A., & Deshmukh, S. G. (2008). Supply chain coordination: Perspectives, empirical studies and research directions.International Journal of Production Economics,115(2), 316–335.
Ayhan, M. B., & Kilic, H. S. (2015). A two stage approach for supplier selection problem in multi-item/multi-supplier environment with quantity discounts.Computers & Industrial Engineering, 85(1), 1–12.
Bai, L., & Rubin, P. A. (2009). Combinatorial benders cuts for the minimum tollbooth problem.Operations Research,57(6), 1510–1522.
Balakrishnan, A., & Graves, S. C. (1989). A composite algorithm for a concave-cost network flow problem.Networks,19(2), 175–202.
Balakrishnan, A., & Natarajan, H. P. (2014). Integrated procurement planning in multi-division firms.Production and Operations Management,23(10), 1795–1810.
Bichler, M., Schneider, S., Guler, K., & Sayal, M. (2011). Compact bidding languages and supplier selection for markets with economies of scale and scope.European Journal of Operational Research,214(1), 67–77.
Bienstock, D., & Günlük, O. (1996). Capacitated network design—Polyhedral structure and computation.INFORMS Journal on Computing,8(3), 243–259.
Botton, Q., Fortz, B., Gouveia, L., & Poss, M. (2013). Benders decomposition for the hop-constrained survivable network design problem.INFORMS Journal on Computing,25(1), 13–26.
Chan, L. M. A., Muriel, A., Shen, Z.-J. M., Simchi-Levi, D., & Teo, C.-P. (2002). Effective zero-inventory-ordering policies for the single-warehouse multiretailer problem with piecewise linear cost structures.Management Science,48(11), 1446–1460.
Cohn, A., Davey, M., Schkade, L., Siegel, A., & Wong, C. (2008). Network design and flow problems with cross-arc costs.European Journal of Operational Research,189(3), 890–901.
Croxton, K. L., Gendron, B., & Magnanti, T. L. (2003). A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems.Management Science,49(9), 1268–1273.
Croxton, K. L., Gendron, B., & Magnanti, T. L. (2007). Variable disaggregation in network flow problems with piecewise linear costs.Operations Research,55(1), 146–157.
Fortz, B., & Poss, M. (2009). An improved Benders decomposition applied to a multi-layer network design problem.Operations Research Letters,37(5), 359–364.
Geißler, B., Martin, A., Morsi, A., & Schewe, L. (2012). Using piecewise linear functions for solving MINLPs. In J. Lee & S. Leyffer (Eds.),Mixed integer nonlinear programming (Vol. 154, pp. 287–314). New York: Springer.
Gonçalo, T. E. E., & Alencar, L. H. (2014). A supplier selection model based on classifying its strategic impact for a company’s business results.Pesquisa Operacional, 34(2), 347–369.
Goossens, D. R., Maas, A. J. T., Spieksma, F. C. R., & van de Klundert, J. J. (2007). Exact algorithms for procurement problems under a total quantity discount structure.European Journal of Operational Research,178(2), 603–626.
Guisewite, G. M., & Pardalos, P. M. (1990). Minimum concave-cost network flow problems: Applications, complexity, and algorithms.Annals of Operations Research,25(1), 75–99.
Hammami, R., Temponi, C., & Frein, Y. (2014). A scenario-based stochastic model for supplier selection in global context with multiple buyers, currency fluctuation uncertainties, and price discounts.European Journal of Operational Research,233(1), 159–170.
Harks, T., König, F. G., Matuschke, J., Richter, A. T., & Schulz, J. (2014). An integrated approach to tactical transportation planning in logistics networks.Transportation Science. doi:10.1287/trsc.2014.0541
Hill, J., & Galbreth, M. (2008). A heuristic for single-warehouse multiretailer supply chains with all-unit transportation cost discounts.European Journal of Operational Research,187(2), 473–482.
Ho, W., Xu, X., & Dey, P. K. (2010). Multi-criteria decision making approaches for supplier evaluation and selection: A literature review.European Journal of Operational Research,202(1), 16–24.
Holmberg, K. (1994). Solving the staircase cost facility location problem with decomposition and piecewise linearization.European Journal of Operational Research,75(1), 41–61.
Keha, A. B., De Farias, I. R, Jr, & Nemhauser, G. L. (2006). A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization.Operations Research,54(5), 847–858.
Li, H.-L., Chang, C.-T., & Tsai, J.-F. (2002). Approximately global optimization for assortment problems using piecewise linearization techniques.European Journal of Operational Research,140(3), 584–589.
Li, H.-L., Huang, Y.-H., & Fang, S.-C. (2013). A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems.INFORMS Journal on Computing,25(4), 643–653.
Mansini, R., Savelsbergh, M. W. P., & Tocchella, B. (2012). The supplier selection problem with quantity discounts and truckload shipping.Omega,40(4), 445–455.
Munson, C. L. (2007). The appeal of partially centralised purchasing policies.International Journal of Procurement Management,1(1–2), 117–143.
Muriel, A., & Munshi, F. N. (2004). Capacitated multicommodity network flow problems with piecewise linear concave costs.IIE Transactions (Institute of Industrial Engineers),36(7), 683–696.
Murthy, N. N., Soni, S., & Ghosh, S. (2004). A framework for facilitating sourcing and allocation decisions for make-to-order items.Decision Sciences,35(4), 609–637.
Qin, H., Luo, M., Gao, X., & Lim, A. (2012). The freight allocation problem with all-units quantity-based discount: A heuristic algorithm.Omega,40(4), 415–423.
Saharidis, G. K. D., & Ierapetritou, M. G. (2013). Speed-up Benders decomposition using maximum density cut (MDC) generation.Annals of Operations Research,210(1), 101–123.
Samouei, P., Kheirkhah, A. S., & Fattahi, P. (2014). A network approach modeling of multi-echelon spare-part inventory system with backorders and quantity discount.Annals of Operations Research,226(1), 551–563.
Şen, A., Yaman, H., Güler, K., & Körpeoğlu, E. (2013). Multi-period supplier selection under price uncertainty.Journal of the Operational Research Society,65(11), 1636–1648.
Sridhar, S., Linderoth, J., & Luedtke, J. (2013). Locally ideal formulations for piecewise linear functions with indicator variables.Operations Research Letters,41(6), 627–632.
Stadtler, H. (2007). A general quantity discount and supplier selection mixed integer programming model.OR Spectrum,29(4), 723–744.
Taleizadeh, A. A., Akhavan Niaki, S. T., & Hoseini, V. (2009). Optimizing the multi-product, multi-constraint, bi-objective newsboy problem with discount by a hybrid method of goal programming and genetic algorithm.Engineering Optimization,41(5), 437–457.
Taleizadeh, A. A., Niaki, S. T. A., & Wee, H.-M. (2013). Joint single vendor–single buyer supply chain problem with stochastic demand and fuzzy lead-time.Knowledge-Based Systems,48, 1–9.
Taleizadeh, A. A., Wee, H.-M., & Jolai, F. (2013). Revisiting a fuzzy rough economic order quantity model for deteriorating items considering quantity discount and prepayment.Mathematical and Computer Modelling,57(5–6), 1466–1479.
Vielma, J. P., Keha, A. B., & Nemhauser, G. L. (2008). Nonconvex, lower semicontinuous piecewise linear optimization.Discrete Optimization,5(2), 467–488.
Vielma, J. P., & Nemhauser, G. L. (2011). Modeling disjunctive constraints with a logarithmic number of binary variables and constraints.Mathematical Programming,128(1–2), 49–72.
Xu, J., Lu, L. L., & Glover, F. (2000). The deterministic multi-item dynamic lot size problem with joint business volume discount.Annals of Operations Research,96(1–4), 317–337.
Yin, S., Nishi, T., & Grossmann, I. E. (2014). Optimal quantity discount coordination for supply chain optimization with one manufacturer and multiple suppliers under demand uncertainty.International Journal of Advanced Manufacturing Technology,76(5–8), 1173–1184.
Zhang, J., & Chen, J. (2013). Supplier selection and procurement decisions with uncertain demand, fixed selection costs and quantity discounts.Computers & Operations Research,40(11), 2703–2710.
Author information
Authors and Affiliations
Industrial Engineering and Management Science, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville, Spain
Jose L. Andrade-Pineda, David Canca & Pedro L. Gonzalez-R
- Jose L. Andrade-Pineda
You can also search for this author inPubMed Google Scholar
- David Canca
You can also search for this author inPubMed Google Scholar
- Pedro L. Gonzalez-R
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJose L. Andrade-Pineda.
Appendices
Appendix 1: Discounts shapes and problem size for alternative formulations
A set of five MAUD shapes has been considered in our computations. The details of each of them are shown in Tables 11,12,13,14 and15, presenting on the left side the involved extended range set—i.e. used in the seminal work (Andrade-Pineda et al.2013)—and on the right one the modified range set—i.e. used at each of the alternative formulations. Further, the sizes of the alternative MILPs arisen from addressing the reference network\(\overline{G} ^{A}=(\overline{V^{481}} ,\overline{L^{2835}} ,K^{6})\)—i.e. graph #A1 in our test bed, and base of Class A instances—are outlined, as an illustration of its dependence on the model applied.
Appendix 2: Comparison of logarithmic approaches
The convenience of the modification of the logarithmic approach in Li et al. (2013) which this paper proposes is validated with the comparative results from addressing the Class A instances in our test bed—see Table 16. Particularly, the version from Li et al. (2013) ran out of memory with Instances $17 and $18, which happens not because of the size of the branch-and-bound trees—i.e. with regards to number of nodes—but rather owing to the size of the individual LPs within the tree. In a whole, the LogDCC model, as a locally ideal reformulation of the original in Li et al. (2013) exhibits improved tractability.
Rights and permissions
About this article
Cite this article
Andrade-Pineda, J.L., Canca, D. & Gonzalez-R, P.L. On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization.Ann Oper Res258, 301–346 (2017). https://doi.org/10.1007/s10479-015-1941-2
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative