The supplier selection problem with quantity discounts and truckload shipping

Abstract

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.

Introduction

The selection of a set of suppliers is a key procurement decision for many companies. Different considerations influence this decision, e.g., a supplier's quality and reliability, but also his pricing and discount policy (see [25] for a study on the importance of different attributes that companies consider when selecting suppliers). The continuing growth of e-commerce, with reverse auctions as a web-based counterpart to traditional procurement, has fueled an interest in procurement optimization, and in recent years the research community has made significant advances in this area.

Two distinct streams of research can be identified in procurement optimization: a first stream assuming that demand is deterministic and a second stream assuming that demand is stochastic. We highlight a few papers in each research stream. Rosenblatt et al. [22] analyze procurement policies involving both supplier selection and purchase frequency and quantity setting. Benton [7] studies a procurement problem in which suppliers offer quantity discounts. Various extensions of the problem considered by Benton are investigated and an exact method for their solution is presented in Goossens et al. [16]. Xia and Wu [26] also look at supplier selection in the presence of quantity discounts. The setting studied has multiple suppliers offering multiple products with limited availability and discounts on total business volume and considers qualitative and quantitative factors in their selection. Chauhan and Proth [10] present a procurement problem with concave purchase cost and minimal and maximal order quantities and propose different heuristics as solution methods. Awasthi et al. [6] study a supplier selection problem for a single manufacturer facing stochastic demand. The suppliers quote different prices and have restrictions on minimum and maximum order quantities. A heuristic solution procedure is proposed. Zhang and Zhang [28] extend the previous setting by including holding and shortage costs and a fixed cost incurred when a supplier is selected. A branch and bound algorithm is presented for its solution. Burke et al. [8] study single period, single product sourcing decisions under demand uncertainty. Their approach considers product prices, supplier costs, supplier capacities, supplier reliabilities and firm specific inventory costs. The same authors analyze the impact of supplier pricing schemes and supplier capacity limitations on the optimal sourcing policy for a single firm [9]. Heuristic solution methods are developed to identify a quantity allocation decision for the firm. Anupindi and Akella [4] analyze purchase quantity allocation between two uncertain suppliers and its effects on inventory policies, whereas Dada et al. [11] study an environment with multiple unreliable suppliers. Yang et al. [27] study a procurement problem, where a buyer, while facing random demand, has to decide ordering quantities from a set of suppliers with different yields and prices.

However, procurement costs are not just determined by purchasing costs. Typically, transportation costs form a substantial component of procurement cost. Therefore, we study a procurement setting that explicitly incorporates both. We consider a company that has to select a set of suppliers from which to purchase a number of products. The suppliers offer discounts based on the total quantity purchased. The transportation costs are modeled as truckload shipping costs, and thus depend on the total quantity purchased as well. This transportation cost structure is appropriate as it is common practice to out-source the transportation to a carrier company.

More specifically, let $K≔\{1,\dots ,n\}$ be the set of products to be purchased and let $S≔\{1,\dots ,m\}$ be the set of suppliers to choose from. Each product k, $k\in K$, can be purchased at a subset $S_k\subseteq S$ of suppliers at a unit price $p_{\mathit{ik}}>0$, $i\in S_k$ (potentially different for each supplier). There is discrete demand d_k for product $k\in K$ and product availability q_ik for product $k\in K$ at supplier $i\in S_k$. We assume that ${\sum }_{i\in S_k}{q}_{\mathit{ik}}\ge d_k$ for all $k\in K$. Each supplier $i\in S$ defines r_i consecutive, non-overlapping discount intervals $[l_i^r,u_i^r]$, $r\in R_i:=\{1,\dots ,r_i\}$, each with an associated discount rate f_i^r; discount rates satisfy $f_i^r>f_i^{r-1}$ for $r=2,\dots ,r_i$ for $i\in S$. The interval in which the total quantity purchased falls determines the discount applied to the total purchase cost. For convenience, we convert these discounts into unit prices $p_{\mathit{ik}}^r$ for product k, $k\in K$, at supplier i, $i\in S_k$, in interval r, $r\in R_i$. A fixed transportation cost c_i is charged for each visit to a supplier i, $i\in S$. The number of visits to a supplier depends on the total quantity purchased at that supplier and the truck capacity Q. The company wants to select a set of suppliers to satisfy the demand for each product in such a way that procurement costs, i.e., total purchase and transportation costs, are minimized. We refer to this problem as the Supplier Selection Problem with Quantity Discounts and Truckload Shipping (SSP-QDTS). The piecewise linear non-convex and non-concave purchase cost function and the step-wise transportation cost function make this a computationally challenging optimization problem.

SSP-QDTS generalizes the total quantity discount problem, which is known to be strongly NP-hard and for which exact and heuristic approaches have been proposed (see [16] and more recently [19]). SSP-QDTS is also related to the traveling purchaser problem (see [18]) which takes purchasing costs and traveling costs into account (see [20] for a variant of the problem with a budget constraint and [2], [3] for a dynamic variant with supplier quantities decreasing over time). The traveling purchaser problem does not consider total quantity discounts, but allows for more general transportation options.

Given the complexity of the problem, obtaining optimal solutions to meaningful instances in a reasonable amount of time is virtually impossible. Therefore, we have developed integer programming based heuristics that are capable of producing high-quality solutions quickly. The proposed heuristics are iterative rounding schemes based on the linear programming relaxation of a natural integer programming formulation of the SSP-QDTS. The linear programming solution in combination with a quantity discount analysis guides the choice of both a supplier and the number of visits to that supplier. After fixing the number of visits to the selected supplier, the linear programming relaxation is resolved and the process is repeated. When the number of visits to each of the suppliers is fixed, the remaining integer program is solved to determine the product quantities to be bought from the selected suppliers. To enhance the effectiveness of the guidance provided by the linear programming relaxation, the formulation has been strengthened by a set of valid inequalities. Finally, simple post-processing is used to eliminate any unnecessary costs incurred.

Our research provides various contributions. First, it explicitly integrates purchasing and transportation considerations in the context of procurement, which, as far as we have been able to establish, has not been done before, even though both aspects are relevant in almost all practical procurement environments. Second, our heuristics can be seen as another example of the growing body of literature on solution approaches that incorporate the solution of small well-chosen integer programs (see for example [1], [5], [12], [17], [24]). Finally, the extensive experimental analysis on a large set of instances provides insights and rules-of-thumb that can be used by companies to help them develop effective vendor selection strategies. In fact, a major goal of our research has been to study the impact of the characteristics of the procurement environment on the structure of vendor selection strategies. Effective vendor selection strategies depend on the number of suppliers and products, on the product availabilities (both on the number of suppliers of a particular product and the quantities of product available at the suppliers), on the quantity discount parameters, the location of the suppliers and the truckload shipping costs, the relative importance of purchase and transportation costs, etc.

The paper is organized as follows. In Section 2, we describe the mathematical formulation of the SSP-QDTS, discuss properties of its continuous relaxation, and introduce valid inequalities. In Section 3, we present a number of heuristics, each representing a specific implementation of a general iterative rounding scheme. In Section 4, we discuss an extensive computational study in which we introduce various procurement settings and analyze the characteristics of effective supplier selection strategies. Finally, in Section 5, we draw some conclusions and indicate some possible future research direction.