Efficient Algorithms for a Large-Scale Supplier Selection and Order Allocation Problem Considering Carbon Emissions and Quantity Discounts

Abstract

This paper considers a multi-period supplier selection and order allocation problem for a green supply chain system that consists of a single buyer and multiple heterogeneous suppliers. The buyer sells multiple products to end customers and periodically replenishes each item’s inventory using a periodic inventory control policy. The periodic inventory control policy used by the buyer starts every period with an order size determination of each item and the subsequent supplier selection to fulfill the orders. Because each supplier in the system is different from other suppliers in the types of carrying items, delivery distance, item price, and quantity discount schedule, the buyer’s problem becomes a complicated optimization problem. For the described order size and supplier selection problem of the buyer, we propose a nonlinear integer programming model and develop two different algorithms to enhance the usability of the model in a real business environment with a large amount of data. The algorithms are developed to considerably cut computational time and at the same time to generate a good feasible solution to a given supplier selection and order allocation problem. Computational experiments that were conducted to test the efficiency of the algorithms showed that they can cut as much as 99% of the computational time and successfully find feasible solutions, deviating not more than 3.4% from the optimal solutions.

1. Introduction

In a highly competitive and uncertain business environment, efficient supply chain construction and management becomes an increasingly important issue to maintain a leading edge (Ware et al. [1]). Among the various kinds of business decision-making problems occurring in a supply chain, supplier selection and order allocation problems are considered to have a significant impact on the successful operation of a retail business. For this and additional reasons, many previous researchers dealt with similar problems with different particular features of such operations (Fox et al. [2], Chen et al. [3], Kiesmüller et al. [4], Lian et al. [5], Kim et al. [6]). Refer to Yao and Minner [7] for a review of papers in this area. Recently, many complicated new characteristics have emerged for the supply chains. One such complication is caused by processes related to carbon emissions, such as maximum carbon emission limits, emission capacity trading, and costs related to such activities. A more realistic supplier selection and order allocation problem should thus include such additional features and have a high degree of computational complexity. The problem introduced in this paper belongs to a sustainable supplier selection and order allocation (SSS & OA) problem. Figure 1. from Zimmer et al. [8], which shows a classification of the SSS & OA problems in terms of the modeling approach, indicates that our problem belongs to the mathematical programming category. Specifically, we analyze in this paper a realistic SSS & OA problem for a single buyer carrying multiple types of products and selling to end customers. We also note that, to make the best decision for the coming period, it is necessary to include data for several future periods in addition to the data for the immediate coming period. We thus define our problem as a supplier selection and order allocation problem with multiple periods of planning horizon and with several realistic characteristics, including carbon emissions and price discounts offered by suppliers.

Although several solution methodologies have been introduced for a similar problem in previous research, there has not been an efficient solution methodology to routinely solve a large-scale real orders and supplier selection problem such as the one introduced in this paper. Park et al. [9] is the example of such methodologies. They introduced a nonlinear programming model for a replenishment problem with a single buyer and multiple buyers and proposed an implementation procedure for the model. Kim et al. [10] formulated a mixed integer linear programming model for a similar SSS & OA problem for a single buyer and multiple supplier system. They proposed a branch-and-freeze algorithm to handle real problems with millions of constraints and variables. However, these two solution methodologies cannot be applied directly to our model because the methodologies are developed using unique properties of a specific model. The size of our model describing a real problem frequently exceeds thousands of constraints and variables. Because our model is a nonlinear integer programming model, it is very hard to get a feasible solution in reasonable amount of time by using an existing optimization package. Considering this research need, we develop two heuristic algorithms to solve a larger instance of the introduced model. Computer experiments showed that the algorithms are sufficiently fast for these bigger problems and also perform to a desired level of accuracy.

2. Literature Review

A large number of papers have been published for the supplier selection and order allocation problem. Review papers, including Yao and Minner [7] and Zimmer et al. [8], state that the subjects and methodologies of the supplier selection problems are very wide. The subjects range from supplier selection criteria analysis to supplier development (Haeri and Rezaei [11], Alikhani et al. [12]). Methodologies used for analysis include qualitative (e.g., Delphi method), mathematical optimization (for example, refer to Bektur [13], Jia et al. [14], Mohammed et al. [15], Moheb-Alizadeh and Handfield [16] for multi-objective optimization), mathematical analytical (e.g., AHP, TOPSIS, game theory), AI (artificial intelligence), and combined models (Ghalehkhondabi et al. [17], Memari et al. [18]). Among numerous topics that appear in the SSS & OA area, we narrowly focus our previous research review on SSS & OA problems considering quantity discount and carbon emissions in the mathematical optimization category.

2.1. Supplier Selection and Order Allocation Considering Quantity Discount

Supplier selection and order allocation problems, including a quantity discount, have been analyzed several times due to the importance of the topic. In the real business world, the most frequently used quantity discount scheme is the all-unit quantity discount. Benton [19] presented an efficient heuristic procedure for a multiple-supplier inventory model with multiple items and all-unit quantity discounts. Chang et al. [20] studied a problem with an all-unit quantity discount, variable lead-time, and stochastic demand and formulated a mixed-integer programming model. Kang and Lee [21] analyzed a multi-period replenishment problem under an all-unit quantity discount and constant demand. They constructed a multiple objective programming model to determine the optimal order amount, which can lead to the minimization of total costs and the maximum yield rate. Afterward, Ayhan and Kilic [22] analyzed a supplier selection problem with all-unit quantity discounts and proposed a two-stage approach to determine the best suppliers and orders for each selected supplier. There also exist numerous works for other kinds of discount schedules; the incremental one can be found in Chaudhry et al. [23], Lee et al. [24], and Kang and Lee [25]. Business volume discount problems were analyzed in Sadrian and Yoon [26] and Dahel [27], to name a few.

2.2. Supplier Selection and Order Allocation Considering Carbon Emissions

Low carbon emissions with an environmentally sustainable inventory policy are considered the essential factor for business operations in green supply-chain management. In this area, many works have been published considering carbon emission requirements. Carbon emission constraints include carbon capacity trading, carbon taxes, and strict emissions restrictions. Konur and Schaefer [28] studied an integrated inventory control and transportation planning problem with carbon emissions regulations. They proposed an EOQ (economic order quantity) model with transportation under carbon regulation policies. Hammami et al. [29] first dealt with the carbon emissions tax and carbon emissions cap on the model. Salehi et al. [30] analyzed the integrated problem of green truck transport schedules and driver assignment issues. They proposed a multi-objective model to minimize the total carbon emissions and total transportation costs. Kaur and Singh [31] solved an environmentally sustainable procurement problem using a nonlinear integer programming model. The model aims to optimize the replenishment plan of a buyer considering carrier selection under uncertainty and environmental sustainability requirements. Lamba et al. [32] developed a nonlinear integer programming model to decide the optimal lot size. Their problem includes multiple periods, multiple products, multiple suppliers, and carbon emissions costs.

In addition, works on the supplier selection problem incorporating carbon emissions costs are described in Martí et al. [33], Gurtu et al. [34], Elhedhli and Merrick [35]. Kim et al. [10] studied a large-scale supplier selection and order allocation problem with a minimum order quantity or minimum purchase amount. They developed an integer linear programming model for the problem and proposed an efficient algorithm based on the branch and bound method.

2.3. Research Gaps and the Distinct Features of Our Work

As shown in the

Table 1. Comparison of related studies regarding the inventory problem under various constraints.

Author(S)	Number of Items		Number of Suppliers		Number of Periods		Demand Process			Constraints			Transportation Lead Time	Model Type
	Single	Multi	Single	Multi	Single	Multi	Deterministic	Stochastic		Quantity Discount	Carbon Emission	Sustainability
								Stationary	Non-Stationary
Benton [19]		✓		✓	✓		✓			✓				MIP
Chaudhry et al. [19]	✓			✓	✓		✓			✓				MIP
Sadrian and Yoon [22]	✓		✓		✓		✓			✓				MIP
Dahel [27]		✓		✓	✓		✓			✓				MIP
Chang et al. [20]	✓			✓	✓			✓		✓			✓	MIP
Shin and Benton [36]	✓		✓			✓	✓			✓			✓	EOQ
Kang and Lee [25]	✓			✓		✓	✓			✓				MIP
Kang and Lee [21]	✓			✓		✓		✓		✓				MIP
Lee et al. [24]	✓			✓		✓	✓			✓				MIP
Meena and Sarmah [37]	✓			✓	✓		✓			✓				NLP1
Konur and Schaefer [28]	✓		✓		✓		✓				✓		✓	EOQ
Ayhan and Kilic [22]		✓		✓	✓		✓			✓				MIP
Gurtu et al. [34]	✓				✓		✓				✓			EOQ
Hammami et al. [29]		✓		✓		✓	✓				✓		✓	MIP
Salehi et al. [30]		✓		✓		✓	✓				✓		✓	NLP1
Kaur and Singh [28]		✓		✓		✓		✓			✓	✓		NLP1
Lamba et al. [32]		✓		✓		✓	✓				✓	✓		NLP1
Park et al. [9]		✓		✓		✓		✓	✓				✓	NLP1
Kim et al. [10]		✓		✓		✓		✓	✓			✓	✓	MIP
This model		✓		✓		✓		✓	✓	✓	✓	✓	✓	NLP1

comparison, this is the first study to consider a more realistic procurement problem that includes a quantity discount and carbon emissions. The completed mathematical model includes almost all the various important features, such as production capacity, warehouse capacity, transportation lead time, and distance. The formulated model is a nonlinear integer programming model, which is very hard to solve to a desired level of accuracy using currently available commercial packages. For example, a popular commercial solver failed to generate a feasible solution for a small instance of such a problem with 8 items, 8 suppliers, and 12 time periods, let alone the optimal solution during our computational experiment. When we consider that much bigger models with thousands of constraints and variables will be necessary for a real-world application, we notice a need to develop more efficient solution methodologies for handling such complex data-oriented problems. Our model, as well as proposed algorithms, partially satisfy this need by providing a model and solution methods for dealing with important but computationally difficult problems.

The remainder of this paper is structured as follows. A problem definition, concerned system description, and mathematical model are discussed in the following Section. Section 4 introduces two algorithms for the proposed model. Section 5 provides a computational experiment to test the validity and efficiency of the algorithms. In Section 6, implications and conclusions are discussed.

3. Mathematical Model

3.1. System Description and Assumptions

The single buyer in the system carries multiple types of products for sale to end-customers. At the beginning of each period, the buyer should determine each item’s order amount and select suppliers to fulfill the orders. Each supplier in the system is heterogeneous in terms of carrying item type, price and discount schedules, delivery distance, and lead times. Our research objective sought in this paper is to find an efficient solution methodology which can construct a good SSS & OA plan for the buyer. The plan should minimize the sum of relevant costs occurring to the buyer during a planning horizon and, at the same time, satisfy all the constraints set to the buyer. Assumptions made for the problem can be summarized as follows.

3.2. List of Assumptions

• The fixed amount of major ordering cost is charged per order to a supplier.
• The minor ordering cost is charged for each item type included in an order.
• The holding cost is incurred in proportion to the level of on-hand inventory.
• The supplier offers an all-unit quantity discount schedule for each carried item.
• The buyer can purchase items from a spot market but at a higher price than the regular price of a supplier.
• The buyer has limited warehouse capacity.
• Each supplier has a limited production capacity.
• Only one type of vehicle is available with a known container volume.
• A per-vehicle transportation cost is incurred in proportion to the delivery distance from a supplier to the buyer.
• The carbon emission capacity can be traded at the end of the planning horizon.
• The carbon emissions occur from the inventory items, order placement, item handling, and transportation.

3.3. Mathematical Formulation

Indices:

$i$	item number, $i=1,2,\cdots ,I,$
$j$	supplier number, $j=1,2,\cdots ,J,$
$t$	planning period, $t=1,2,\cdots ,T,$
${\eta }_{i,j}$	price break of item $i$ in a discount schedule specified by supplier j, ${\eta }_{i,j}=1,2,\cdots ,N_{i,j}$.

Parameters:

$\widehat{J}\left(i\right)$	set of suppliers who sell item $i$, $\forall i,$
$\widehat{I}\left(j\right)$	set of item numbers sold by supplier $j$, $\forall j,$
$f_{i,t}$	buyer’s forecast of demand for item $i$ during period $t$, $\forall i, t,$
$lb{q}_{i,j,{\eta }_{i,j}}^{}$	lower bound quantity of supplier $j$ for price break ${\eta }_{i,j}$ of item $i$, $\forall i,{\eta }_{i,j},j\in \widehat{j}\left(i\right),$
$ub{q}_{i,j,{\eta }_{i,j}}^{}$	upper bound quantity of supplier $j$ for price break ${\eta }_{i,j}$ of item $i$, $\forall i,{\eta }_{i,j},j\in \widehat{j}\left(i\right),$
$u_{i,j}$	per-period maximum purchase limit for item $i$ set by supplier $j,\forall i,j\in \widehat{j}\left(i\right),$
$v_i$	volume of item $i$, $\forall i,$
$w_t$	buyer’s warehouse capacity during period $t$, $\forall t,$
$m{j}_j$	major ordering cost of supplier $j$, $\forall j,$
$m{i}_{i,j}$	minor ordering cost of item $i$ of supplier $j$, $\forall i,j\in \widehat{J}\left(i\right),$
$h{c}_i$	unit holding cost of item $i$, $\forall i,$
$s{c}_i$	unit shortage cost of item $i$, $\forall i,$
$t{c}_{j,t}$	transportation cost per vehicle per unit distance of supplier $j$ in $t$ period, $\forall t,j\in \widehat{J}\left(i\right),$
$p_{i,t}^s$	unit purchase price of item $i$ from spot market of during period $t$,$\forall i, t,$
$p_{i,j,{\eta }_{i,j}}$	unit purchase price of item $i$ of supplier $j$ in price break range of ${\eta }_{i,j}$, $\forall i,{\eta }_{i,j},j\in \widehat{j}\left(i\right),$
$l_j$	delivery lead time of supplier j, $\forall j,$
${\tilde{\mathrm{x}}}_{\mathrm{i},\mathrm{j},\mathrm{t}}$	purchase order made at past period $t$ of item $i$ to supplier $j$, $\forall i,j\in \widehat{J}\left(i\right),$ $t=-1,-2,\cdots ,1-l_j,$
$z_{i,0}$	inventory position of item $i$ at the start of the present period (period 1), $\forall i,$
$C$	carbon cap for the entire planning period,
$cp$	carbon price per unit,
$C{E}_t^o$	carbon emission from placing an order in period $t,$ $\forall t,$
$C{E}_t^h$	carbon emission from holding inventory in period $t,$ $\forall t,$
$C{E}_t^v$	carbon emission from handling items in period $t,$ $\forall t,$
$\mathsf{\Omega }$	capacity of the vehicle,
$d_j$	distance of supplier $j$ from the buyer, $\forall j,$
$\mathsf{\rho }$	carbon emission factor for transportation,
$M$	a large number.

Decision variables:

$p_{i,k,t}^{DC}$	unit discount price of item $i$ paid to supplier $j$ during period $t$, $\forall i,t,j\in \widehat{J}\left(i\right),$
$x_{i,j,1}$	purchase quantity of item $i$ from supplier $j$ for the present period, $\forall i,j\in \widehat{J}\left(i\right),$
$x_{i,j,t}$	planned purchase quantity of item $i$ from supplier $j$ for the future period $t$, $\forall i,j\in \widehat{J}\left(i\right),t=2,\cdots ,T,$
$x_{i,1}^s$	purchase quantity of item $i$ from the spot market at the start of the present period, $\forall i,$
$x_{i,t}^s$	planned purchase quantity of item $i$ from the spot market for the future period $t$, $\forall i, t,$
$I{L}_{i,t}$	inventory level of item $i$ at the end of period $t$, $\forall i, t,$
$R{L}_{i,t}$	replenishment level (inventory position) of item $i$ at the start of period $t$ after the arrival of orders scheduled to arrive during period $t$, $\forall i, t,$
$n{c}_{j,t}$	number of carriers required by supplier $j$ in period $t$, $\forall j, t,$
$C{E}_t^{+}/C{E}_t^{-}$	residual/excess of carbon cap in period $t$, $\forall t,$
${\beta }_{i,j,t}^{MI}$	binary variable for controlling the minor ordering cost, $\forall i, j,t,$
${\beta }_{j,t}^{MJ}$	binary variable for controlling the major ordering cost, $\forall j, t,$
${\beta }_{i,j,t,{\eta }_{i,j}}^{DC}$	binary variable for controlling the discount price, $\forall i,j,t,{\eta }_{i,j}.$

3.4. Model Formulation

In this section, we introduce the objective function and constraints of the model for the defined problem. For the objective function, we derive the cost factors that collectively define the function.

3.4.1. Objective Function

The objective function consists of the item purchase price paid to the suppliers or to the spot market, the major and minor ordering costs, purchase costs, holding and shortage costs, transportation costs, and carbon-related costs.

With regard to the major and minor ordering costs, the major ordering cost is expressed by Equation (1).

$$\mathrm{Major} \mathrm{ordering} \mathrm{cost}={\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{j=1}^{J}m{j}_j{\beta }_{j,t}^{MJ},$$

(1)

where

$${{\displaystyle \sum }}_{i\in \widehat{I}\left(j\right)}{x}_{i,j,t}\le M{\beta }_{j,t}^{MJ},\forall j, t,$$

(2)

$${\beta }_{j,t}^{MJ} \mathrm{binary} \mathrm{variable},\forall j, t.$$

(3)

The minor ordering cost is represented by Equation (4).

$$\mathrm{Minor} \mathrm{ordering} \mathrm{cost}={\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{i=1}^I{\displaystyle \sum }_{j\in \widehat{J}\left(i\right)}^{}m{i}_{i,}{\beta }_{i,j,t}^{MI},$$

(4)

where

$$x_{i,j,t}\le M{\beta }_{i,j,t}^{MI},\hspace{1em}\forall i,t,j\in \widehat{J}\left(i\right),$$

(5)

$${\beta }_{i,j,t}^{MI} \mathrm{binary} \mathrm{variable},\hspace{1em}\forall i,t,j\in \widehat{J}\left(i\right).$$

(6)

Purchase cost: the purchase cost is composed of the prices paid to each supplier and to the spot market. It is expressed as Equation (7).

$$\mathrm{Purchase} \mathrm{cost}={\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{i=1}^I{\displaystyle \sum }_{j\in \widehat{J}\left(i\right)}^{}{p}_{i,j,t}^{DC}{x}_{i,j,t}+{\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{i=1}^I{p}_{i,t}^s{x}_{i,t}^s.$$

(7)

Holding and shortage costs: the per-period holding cost for an item is the average inventory level multiplied by the holding cost. Summing it over all item types and all periods gives the expected holding cost occurring during the planning horizon.

$$\mathrm{Holding} \mathrm{cost}=\frac{1}{2}{\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{i=1}^{I}h{c}_i\left(R{L}_{i,t}+I{L}_{i,t}^{+}\right).$$

(8)

The shortage cost for the planning horizon can be calculated similarly.

$$\mathrm{Shortage} \mathrm{cost}={\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{i=1}^{I}s{c}_{i}I{L}_{i,t}^{-}.$$

(9)

Transportation cost: the transportation cost for a supplier is the number of vehicles used multiplied by the distance and by the per-vehicle unit distance transportation cost. Summing this for the planning horizon gives the following transportation cost factor.

$$\mathrm{transportation} \mathrm{cost}={\displaystyle \sum }_{t=1}^T{\displaystyle \sum }_{j=1}^{J}n{c}_{j,t}t{c}_{j,t}{d}_j{\beta }_{j,t}^{MJ}.$$

(10)

Carbon-related cost: the carbon-related cost is derived from the cost or from the profit occurred by purchasing or from the profit by selling the capacity. It is expressed as in Equation (11)

$$\mathrm{Excess} \mathrm{carbon} \mathrm{cost}=cp{\displaystyle \sum }_{t=1}^T(C{E}_t^{+}-C{E}_t^{-}).$$

(11)

Based on the above cost factors, we can complete the objective function as follows:

$$\begin{gathered} \mathcal{T}={\displaystyle \sum }_{t=1}^T\left({\displaystyle \sum }_{i=1}^I\left(\frac{1}{2}h{c}_i\left(R{L}_{i,t}+I{L}_{i,t}^{+}\right)+s{c}_{i}I{L}_{i,t}^{-}+p_{i,t}^s{x}_{i,t}^s\right)+{\displaystyle \sum }_{j=1}^J\left(m{j}_j{\beta }_{j,t}^{MJ}+n{c}_{j,t}t{c}_{j,t}{d}_j{\beta }_{j,t}^{MJ}\right) \\ +{\displaystyle \sum }_{i=1}^I{\displaystyle \sum }_{j\in \widehat{J}\left(i\right)}^{}\left(m{i}_{i,}{\beta }_{i,j,t}^{MI}+p_{i,j,t}^{DC}{x}_{i,j,t}\right)\right)+cp{\displaystyle \sum }_{t=1}^T(C{E}_t^{+}-C{E}_t^{-}). \end{gathered}$$

(12)

The following sections discuss the constraints required for our model.

3.4.2. Constraints for the Discounted Purchase Price

To assign the correct discount price based on a discount schedule offered by a supplier, we include the following Equations (13)–(16) as constraints.

$$p_{i,j,t}^{DC}={\displaystyle \sum }_{{\eta }_{i,j}=1}^{N_{i,j}}{p}_{i,j,{\eta }_{i,j}}{\beta }_{i,j,t,{\eta }_{i,j}}^{DC},\hspace{1em}\forall i, t, j\in \widehat{J}\left(i\right),$$

(13)

$$\begin{gathered} lb{q}_{i,k,{\eta }_{i,j}}^{}+M\left({\beta }_{i,j,t,{\eta }_{i,j}}^{DC}-1\right)\le x_{i,j,t}<ub{q}_{i,j,{\eta }_{i,j}}^{}+M\left(1-{\beta }_{i,j,t,{\eta }_{i,j}}^{DC}\right), \\ \forall i,t,{\eta }_{i,j}, j\in \widehat{J}\left(i\right), \end{gathered}$$

(14)

$${\displaystyle \sum }_{{\eta }_{i,j}=1}^{N_{i,j}}{\beta }_{i,j,t,{\eta }_{i,j}}^{DC}=1,\hspace{1em}\forall i, t, j\in \widehat{J}\left(i\right),$$

(15)

$${\beta }_{i,j,t,{\eta }_{i,j}}^{DC} \mathrm{binary} \mathrm{variable},\hspace{1em}\forall i,j,{\eta }_{i,j}, j\in \widehat{J}\left(i\right).$$

(16)

Equations (14)–(16) ensure that only one variable, ${\beta }_{i,j,t,{\eta }_{i,j}}^{DC}$ among all the binary variables in (16), has the value of one when the order amount $x_{i,j,t}$ belongs to the price break range of $\left(lb{q}_{i,k,{\eta }_{i,j}}^{}, ub{q}_{i,j,{\eta }_{i,j}}^{}\right)$ and forces all other ${\beta }_{i,j,t,{\eta }_{i,j}}^{DC}$ variables to become zero. By these binary variables, Equation (13) assigns an appropriate price value to the purchase price variable, $p_{i,j,t}^{DC}$.

3.4.3. Constraints for Carbon Emissions

$$\begin{gathered} {\displaystyle \sum }_{j=1}^J{\displaystyle \sum }_{t=1}^{T}C{E}_t^o{\beta }_{j,t}^{MJ}+{\displaystyle \sum }_{i=1}^I{\displaystyle \sum }_{t=1}^{T}C{E}_t^{h}I{L}_{i,t}+{\displaystyle \sum }_{i=1}^I{\displaystyle \sum }_{j=1}^J{\displaystyle \sum }_{t=1}^{T}C{E}_t^v{x}_{i,j,t}+\mathsf{\rho }{\displaystyle \sum }_{j=1}^J{\displaystyle \sum }_{t=1}^{T}n{c}_{j,t}{d}_j+{\displaystyle \sum }_{t=1}^{T}C{E}_t^{-} \\ =C+{\displaystyle \sum }_{t=1}^{T}C{E}_t^{+}. \end{gathered}$$

(17)

The carbon emissions constraint makes the total carbon emitted, which is given in the left-hand side of Equation (17) equal to the total carbon emission capacity set for the planning horizon.

3.4.4. Mathematical Model for the Defined Problem

Based on the above objective function and constraints, a mathematical model for our problem is completed. Since it contains several nonlinear functions, the model is categorized as a nonlinear integer programming model.

$$\mathrm{NLP}1: \mathrm{Minimize} \mathcal{T},$$

(18)

subject to

$$I{L}_{i,t-1}+{{\displaystyle \sum }}_{j\in \widehat{J}\left(i\right)|l_j=0}{x}_{i,j,t}+{{\displaystyle \sum }}_{\begin{array}{c}j\in \widehat{J}\left(i\right)|l_j\ge 1\\ t-l_j\le 0\end{array}}{\tilde{x}}_{i,j,t-l_j}+{{\displaystyle \sum }}_{\begin{array}{c}j\in \widehat{J}\left(i\right)|l_j\ge 1\\ t-l_j>0\end{array}}{x}_{i,j,t-l_j}+x_{i,t}^s=R{L}_{i,t},\hspace{1em}\forall i, t,$$

(19)

$$R{L}_{i,t}-f_{i,t}=I{L}_{i,t},\hspace{1em}\forall i, t,$$

(20)

$$I{L}_{i,t}=I{L}_{i,t}^{+}-I{L}_{i,t}^{-},\hspace{1em}\forall i, t,$$

(21)

$$x_{i,j,t}\le u_{i,j},\forall i, t,\hspace{1em}j\in \widehat{J}\left(i\right),$$

(22)

$${\displaystyle \sum }_{i=1}^I{v}_{i}R{L}_{i,t}\le w_t,\hspace{1em}\forall t,$$

(23)

$${\displaystyle \sum }_{i\in \widehat{I}\left(j\right)}{x}_{i,j,t}\le M{\beta }_{j,t}^{MJ},\hspace{1em}\forall j, t,$$

(24)

$$x_{i,j,t}\le M{\beta }_{i,j,t}^{MI},\hspace{1em}\forall i, t, j\in \widehat{J}\left(i\right),$$

(25)

$$n{c}_{j,t}=\frac{{{\displaystyle \sum }}_{i=1}^I{x}_{i,j,t}{v}_i}{\mathsf{\Omega }},\hspace{1em}\forall j, t,$$

(26)

Constraints (13)–(17),

$$x_{i,j,t}\ge 0, {\beta }_{i,j,t}^{MI} \mathrm{binary},\forall i, j\in \widehat{J}\left(i\right),t,$$

(27)

$$x_{i,t}^s, R{L}_{i,t}, I{L}_{i,t}^{+}, I{L}_{i,t}^{-}\ge 0, \forall i, t,$$

(28)

$${\beta }_{j,t}^{MJ} \mathrm{binary},n{c}_{j,t} \mathrm{nonnegative} \mathrm{integer}, \forall j, t,$$

(29)

$$I{L}_{i,t} \mathrm{real},\hspace{1em}\forall i, t,$$

(30)

$$C{E}_t^{+},C{E}_t^{-}\ge 0\hspace{1em}\forall t,$$

(31)

$$M \mathrm{large} \mathrm{real} \mathrm{number}.$$

(32)

Equation (19) regulates the replenishment level, initial inventory, and arrivals of previous orders and spot market orders. Equation (20) controls the start and end of period inventories. Equation (21) is for the on-hand inventory and the shortage. Equation (22) is for the maximum purchase limit and (23) is for the warehouse capacity limit. Equations (24) and (25) are for the minor and major ordering cost allocation. Finally, number of carriers required for transportation is set by Equation (26).

The completed model, NLP1, has nonlinear terms in the objective function, as well as many binary and general integer variables. It thus belongs to a nonlinear integer programming model, which is known to be very hard to solve. NLP1 has a total of $T+3IT+2JT+4IJT+IJT\underset{i,j}{\max }{\eta }_{i,j}$+1 constraints and $2T+5IT+2JT+2IJT+IJT\underset{i,j}{\max }{\eta }_{i,j}$ variables. For a problem having 30 item types, 10 suppliers, 20 time periods, and a maximum of 5 price breaks, NLP1 will have a total of 56,221 constraints and 45,440 variables, among which 36,200 variables are integer ones. In the retail industry, it is not rare to meet a buyer handling thousands of item types and hundreds of suppliers. The current practice is to install a heavy and costly commercial retail supply chain management system specifically tailored to a retailer. Our approach is not to find a general method to substitute such a system. Rather, our results can contribute to improving a small portion of such a system. Even with this practical target in mind, we still have a big obstacle to the practical application of our model. The problem is that it is hard to find any existing commercial solver that can find a feasible solution, not to mention the optimal one, for this sort of model. It is thus essential to develop an efficient solution method that can handle reasonably big problems frequently encountered in the real world to improve the usability of our model. In the following section, we discuss the background and procedures of such methods.

4. Methodology

The computational complexity of NLP1 is mainly caused by the nonlinear terms and integer variables. Based on this observation, we develop two different quick and handy algorithms. For the first algorithm, we note that there is a relationship between purchase quantity ($x_{i,j,t}$) and indication variables for major and minor ordering costs (${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$). The relationship can be described as follows: if $x_{i,j,t}$ has a positive (integer or real) value, then ${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$ must be equal to 1. If $x_{i,j,t}$ has a value of 0, then ${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$ also have the value of 0.

4.1. Binary Variables Removal of NLP1 (BON)

The first algorithm, called BON, solves NLP1 without the binary variables (${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$) to remove the nonlinear terms in the objective function, which lowers the computational complexity. The output of this modified model provides a feasible solution to the original model because the output satisfies all the constraints of the original model. The objective function value generated from the modified model is not a legitimate one because the major and minor ordering costs are omitted from the calculation. Using this output, however, we can construct an accurate cost function value, including ordering costs. By solving the less complex modified model and reconstructing an objective function value, we can considerably cut computational time, and can solve a much bigger problem. However, this method cannot guarantee the optimality of a solution obtained because it is only a feasible one, which is not necessarily optimal. The key to the success of this heuristic approach thus depends on how close the output is to the optimal solution of the original model. This question will be answered later in the computational experiments section.

Algorithm BON

Step 1: Removal of binary variables Step 1.1 All ${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$ in NLP1 are set to 1 in NLP1. Step 1.2 Solve the modified problem. Step 1.3 If the modified problem is infeasible, then stop (the original problem is infeasible.). Step 2: Reconstruct cost function value, including ordering costs Step 2.1 Set all binary variables (${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}$) corresponding to $x_{i,j,t}>0$ to 1. Step 2.2 Calculate objective function value by adding the ordering costs with restored binary variables in Step 2.1. Step 2.3 Prepare a solution using the output in Steps 1.2 and 2.1. Generate it as a solution and the value from Step 2.2 as its corresponding objective function value. Step 3: Stop.

4.2. Relaxation of NLP1 (RON)

Another heuristic approach we have taken is to replace the binary variables (${\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ})$ with real-valued bounded variables. When we remove the integer restriction from the variables, then they can have any nonnegative value. Because they are binary originally, we can set the upper bound of each binary variable to 1. This kind of relaxation can be found in the branch and bound method in the integer linear programming area. We can refer to integer programming textbooks such as Nowak [38] for a detailed discussion of relaxation methods of integer optimization model and relationships between the original model and a relaxed model. The second algorithm using this relaxation is named RON and can be described as follows:

Algorithm RON

Step 1: Apply the relaxation to NLP1 Step 1.1 Transform the binary variables in NLP1 into $0\le {\beta }_{i,j,t}^{MI}$, ${\beta }_{j,t}^{MJ}\le 1$. Step 1.2 Solve the relaxed problem. Step 1.3 If the modified problem is infeasible, then stop (the original problem is infeasible.). Step 2: Construct a modified model using the output in Step 1 and resolve Step 2.1 Identify the binary variables with positive values in the output obtained in Step 1.2. Step 2.2 Construct a modified model by setting all binary variables with positive values in Step 2.1 to 1. Step 2.3 Resolve the model in Step 2.2 and generate the output as a solution. Step 3: Stop.

4.3. Finiteness and Convergence of the Proposed Algorithms

The first algorithm (BON) solves a relaxed version of the original nonlinear integer programming model, which is another NLP. There are many known algorithms for NLP, which theoretically converges to a local optimum point in finite number of iterations. When we use a commercial optimization package to implement Step 1.2 of BON, the implementation will be finished within a finite time limit. The remaining Steps of BON do not have a convergence or finiteness issue. Similarly, the second algorithm (RON) solves an NLP model twice in Step 1.2 and Step 2.3, which arrives at a local optimal point in finite iterations if the original model is feasible. From these observations, we can be sure that two algorithms are finite and converge to a local optimum point of the relaxed model. The generated output will be a feasible solution to the original model if the model is feasible. Otherwise, both algorithms will terminate after completing Step 1.3 and indicate the infeasibility of the original model (if the relaxed problem is infeasible, the original problem is also infeasible). Finally, a reconstructed model in Step 2.3 of RON cannot be infeasible when Step 1 generates a feasible solution. Thus, infeasibility is not considered in Step 2.3.

5. Numerical Experiments

5.1. Design of Experiments

We performed experiments to test the efficiency of the algorithms introduced in the previous section. The measure of efficiency is obtained by comparing the objective function value of the solutions from the algorithms with the ones obtained by existing commercial solvers, GAMS/LINDO GLOBAL (version 25.1.2). The test was performed using a PC with Microsoft 10 OS, 3.4 GHz CPU (Intel Core i7), and 24 GB of RAM.

The following virtual supply chain system is chosen for the test.

• The number of item types ranges from 2 to 24.
• The number of suppliers is set from 2 to 8. Each supplier sells from 2 to 24 item types.
• Unit time is set to 1 week.
• Transportation lead time is 1 week.
• The planning horizon length is twenty-four time units, which corresponds to a half year.
• The end customer’s demand for each product is assumed to be normally distributed.

The normal distribution is frequently used in many previous papers including Shin and Benton [36], Kang and Lee [25], and Park et al. [9]. The demand data for our test were generated from a normal distribution with the mean and standard deviation set to values randomly generated from uniform distributions, $U\left(200, 1000\right)$ and $U\left(20, 100\right)$. The forecast necessary for implementing the test was prepared using the IBM SPSS statistics package. Other input parameters for the experiment are described in

Table 2. Input parameters for the experiment.

Buyer’s Warehouse Capacity $\left({\mathit{w}}_{\mathit{t}}\right)$	A Large Number $\left(\mathit{M}\right)$	Carbon Cap $\left(\mathit{C}\right)$	Capacity of the Vehicle $\left(\mathbf{\Omega }\right)$	Initial Inventory Level $\left({\mathit{z}}_{\mathit{i},0}\right)$
5000	1,000,000	U$\left(0.5, 1.5\right)\times {\widehat{d_i}}^{*}$	50	0

${\widehat{d_i}}^{*}$ stands for the average demand forecast for period t.

,

Table 3. Input parameters for items.

Item	Holding Cost $\left({\mathit{h}}_{\mathit{i}}\right)$	Shortage Cost $\left({\mathit{b}}_{\mathit{i}}\right)$	Volume $\left({\mathit{v}}_{\mathit{i}}\right)$	Spot Market Price $\left({\mathit{p}}_{\mathit{i},\mathit{t}}^{\mathit{s}}\right)$
All items	U$\left(0.1, 0.2\right)$	U$\left(10, 15\right)$	U$\left(1, 3\right)$	U$\left(11,16\right)$

U stands for a uniform distribution.

,

Table 4. Input parameters for suppliers.

Supplier	Major Ordering Cost $\left({\mathit{A}}_{\mathit{k}}\right)$	Transportation Cost $\left(\mathit{t}{\mathit{c}}_{\mathit{j},\mathit{t}}\right)$	Minor Ordering Cost $\left({\mathit{a}}_{\mathit{i},\mathit{k}}\right)$	Per-Period Production Capacity $\left({\mathit{u}}_{\mathit{i},\mathit{k},\mathit{t}}\right)$	Distance from Suppliers to Buyer
			All Items	All Items
All suppliers	U$\left(200, 250\right)$	U$\left(2, 4\right)$	U$\left(0.1, 0.2\right)$	U$\left(1.5, 2.5\right)\times {\widehat{d_i}}^{*}$	U$\left(50, 200\right)$

${\widehat{d_i}}^{*}$ stands for the average demand forecast for period t.

,

Table 5. Input parameters for carbon emissions cost.

Supplier	Carbon Price Per Unit $(\mathit{c}\mathit{p})$	Carbon Emission Factor $\left(\mathsf{\rho }\right)$	Ordering $\left(\mathit{C}{\mathit{E}}_{\mathit{t}}^{\mathit{o}}\right)$	Holding $\left(\mathit{C}{\mathit{E}}_{\mathit{t}}^{\mathit{h}}\right)$	Handling $(\mathit{C}{\mathit{E}}_{\mathit{t}}^{\mathit{v}})$
All suppliers	2	0.5	$N\left(10, {0.1}^2\right)$	$N\left(1.0, {0.1}^2\right)$	$N\left(0.2, {0.2}^2\right)$

N stands for a normal distribution.

and

Table 6. Discount schedules of suppliers.

Item	Price Break $\left({\mathit{n}}_{\mathit{i},\mathit{k}}\right)$	All Suppliers
		Purchase Amount $\left({\mathit{x}}_{\mathit{i},\mathit{k},\mathit{t}}\right)$	Unit Price $\left({\mathit{p}}_{\mathit{i},\mathit{k},{\mathit{n}}_{\mathit{i},\mathit{k}}}\right)$
All items	1	0—U$\left(150, 300\right)$	$N\left(4, {0.5}^2\right)$
	2	(Initial value + 1) to (Initial value + 200)	95% of $N\left(4, {0.5}^2\right)$
	3	(Initial value + 201) to (Initial value + 400)	90% of $N\left(4, {0.5}^2\right)$
	4	(Initial value + 401) to infinite value	85% of $N\left(4, {0.5}^2\right)$

Initial value means a starting value generated from U$\left(150, 200\right)$.

.

5.2. Efficiency Measure

We performed an experiment with the experimental design described in the previous section. Each set of the tests was repeated 10 times to obtain an averaged performance. The efficiency measure defined in Equation (33) is the percent deviation of the total average cost.

$$\mathrm{Percent} \mathrm{deviation} =\frac{{\mathrm{Compared} \mathrm{method}}^{’}\mathrm{s} \mathrm{objective} \mathrm{value}-\mathrm{NLP}{1}^{’}\mathrm{s} \mathrm{objective} \mathrm{value}}{\mathrm{NLP}{1}^{’}\mathrm{s} \mathrm{objective} \mathrm{value}}\times 100.$$

(33)

5.3. Test Result

The results of the experiments are summarized in

Table 7. Comparison between NLP1, BON, and RON for a variety of problem sizes.

No.	I	S	P	NLP1		BON		RON		Avg. Percent Deviation (BON/RON)
				Total Cost	CPU Time	Total Cost	CPU Time (% Cut)	Total Cost	CPU Time (% Cut)
1	2	2	4	31,155	0:00:03.78	31,521	0:00:00.44 (88.36%)	31,215	0:00:00.55 (85.45%)	(1.17%/0.19%)
2	2	4	4	31,174	0:01:45.51	32,134	0:00:00.85 (99.19%)	32,097	0:00:00.97 (99.08%)	(3.08%/2.96%)
3	2	4	8	66,334	0:16:40.28	67,666	0:00:01.80 (99.82%)	66,529	0:00:01.72 (99.83%)	(2.01%/0.29%)
4	4	4	8	138,233	0:16:40.53	142,829	0:00:04.38 (99.56%)	139,135	0:00:04.18 (99.58%)	(3.32%/0.65%)
5	4	4	12	207,872	0:16:41.16	210,863	0:00:08.99 (99.09%)	209,192	0:00:08.41 (99.16%)	(1.44%/0.64%)
6	8	4	12	481,258	0:17:03.39	485,182	0:00:44.27 (95.67%)	483,118	0:00:44.80 (95.62%)	(0.82%/0.39%)
7	8	8	12	n/a	0:21:21.56	485,248	0:08:20.84	468,414	0:04:01.05	n/a
8	8	8	24	n/a	17:17:33.51	1,080,852	0:33:32.87	953,318	0:22:37.40	n/a

I: item, S: supplier, P: period

. The optimal objective function value and CPU time of NLP1 and the two proposed algorithms, BON and RON, are listed. In the rightmost column, the average percent deviation from the optimal objective function value is shown. We observe in Table 7 that it took 3.78 CPU seconds using GAMS/LINDO to solve the NLP1 model for experiment No. 1, which is for a system with two items, two suppliers, and four planning periods. The optimal objective function value is USD 31,155. For the same problem, the BON and RON algorithms generated solutions whose objective function values are 1.17% and 0.19% away from the optimal function value, respectively, and they saved 88.36% and 85.45% of CPU time to get this result compared with the one obtained by GAMS/LINDO.

For somewhat more complex problems, particularly No. 2 to No. 5, a similar efficiency is observed. The solution quality of the proposed algorithms is within 3.32% of the optimal objective function values. The CPU time savings reaches up to 99.83% with a minimum savings value of 99.08%. GAMS/LINDO took 17 min and 3.39 s in CPU time to solve the model in problem No. 6, whereas two proposed algorithms consumed around 5% of the CPU time compared to GAMS/LINDO and successfully produced solutions deviating less than 1% from the optimal solution. For more complex problems, No. 7 and 8, GAMS/LINDO could not find a feasible solution for the given models until the termination of the solver’s run, which ranged from 21 CPU minutes to more than 17 CPU hours. For the same problems, however, the two proposed algorithms could find feasible solutions within 23 CPU minutes. The overall performance of RON is consistently better than BON in terms of solution quality and also in computation time. We can note that the tested problem size is much smaller than the one found in real applications. Therefore, we can say that the two proposed algorithms will be very useful in handling much bigger real-world problems for which a global optimal solution cannot be found in practically acceptable time.

6. Implications and Conclusions

6.1. Implications

This study offers a useful tool for decision makers who must regularly make supplier selection and order allocation decisions in a complex real-world environment. For these kinds of problems, we present a nonlinear integer programming model that includes many realistic aspects of real problems. This original model can have thousands of constraints and variables to describe a real buyer-supplier system to a desired accuracy. The current solution methods programmed in many popular commercial solvers cannot handle this kind of complex problem. To provide a useful and practical tool for this difficult situation, we developed two algorithms that can obtain a good feasible solution for the problem. During the computational experiments, the two algorithms, RON in particular, showed superb performance in cutting computational time, while simultaneously providing a good feasible solution. The results imply that these two algorithms can considerably increase the size of a solvable problem and contribute to the overall usability of such optimization models developed using complex data.

6.2. Conclusions

This paper proposes a supplier selection and order allocation model for a green supply-chain system that consists of a single buyer and multiple heterogeneous suppliers. Each supplier in the model is different from the others in various characteristics, including the type of carried items as well as price discount schedules. In addition, each supplier is located a different distance away from the buyer, which is closely related to the carbon emission requirements. The problem analyzed in this paper is the buyer’s integrated decision problem to construct a good replenishment plan. A non-linear integer programming model was formulated for the buyer’s decision problem. We observed that a realistic size of such a problem frequently far exceeds the solvable size limit of the latest commercial solvers. To improve the usability of the proposed model, we have developed two algorithms which can solve such a big problem quickly and accurately.

The first heuristic algorithm (BON) is developed using a linearization of the NLP1 model. It provides near-optimal solutions with up to 0.85 percent deviation on average from the optimal solutions. The second heuristic algorithm is consistently more efficient than the first one. It can cut computational time by as much as 99.83% compared with that consumed by GAMS/LINDO. High solution quality is also maintained by providing feasible solutions with less than 3% deviation in the objective function value from the optimal one. The desirable properties of these algorithms are observed when we attempt to solve slightly more complex problems. For these problems, with the number of constraints and decision variables reaching up to the hundreds, GAMS/LINDO failed to generate a feasible solution. On the other hand, the two proposed algorithms could find feasible solutions without much difficulty.

Future research in this area of study may include an extension to a multi-objective problem to consider cost factors and also environmental factors. Another interesting direction is the migration to a problem found in a multiple-stage supply chain. Application of our algorithms to complex optimization problems in the area of machine learning and artificial intelligence will be interesting research tasks. Finally, the optimal design of the discount schedules for a supplier in a similar system is another interesting topic.