Variable neighborhood search-based solution methods for the pollution location-inventory-routing problem

Abstract

This work presents efficient solution approaches for a new complex NP-hard combinatorial optimization problem, the Pollution Location Inventory Routing problem (PLIRP), which considers both economic and environmental issues. A mixed-integer linear programming model is proposed and first, small problem instances are solved using the CPLEX solver. Due to its computational complexity, General Variable Neighborhood Search-based metaheuristic algorithms are developed for the solution of medium and large instances. The proposed approaches are tested on 30 new randomly generated PLIRP instances. Parameter estimation has been performed for determining the most suitable perturbation strength. An extended numerical analysis illustrates the effectiveness and efficiency of the underlying methods, leading to high-quality solutions with limited computational effort. Furthermore, the impact of holding cost variations to the total cost is studied.

1 Introduction

The Location Inventory Routing Problem (LIRP) is a complex NP-hard combinatorial optimization problem, which simultaneously tackles strategic (location/allocation), tactical (inventory levels and replenishment rates) and operational (routing schedules) decisions [20, 30, 39]. The main goal of this problem is to determine an optimal schedule for achieving economic benefits, like total cost minimization [18]. However, due to the fact that the supply chain activities emit pollutants, such as carbon dioxide $(\hbox {CO}_{2})$, the environmental impact of logistics should also be taken under consideration [7, 25]. More specifically, $\hbox {CO}_{2}$ emissions are considered as the main cause of the global warming, one of the major environment challenges [7, 8]

Freight transportation is mentioned as the main source of $\hbox {CO}_{2}$ [27]. Especially, road transportation generates more than 20% of the total $\hbox {CO}_{2}$ emissions in European Union [27] and 30% in the Organization for Economic Co-operation and Development (OECD) countries [31]. $\hbox {CO}_{2}$ emissions are proportional to the amount of consumed fuel and the fuel consumption depends on speed, acceleration, distance and total weight of the vehicle (curb and freight weight) [25].

The green logistics concept has been studied in many literature contributions. The majority of them focus on routing problems, such as the Vehicle Routing Problem [4, 25, 29, 32]. However, the structure of a supply chain network can affect its functional efficiency by leading to unnecessary delivery routes or redundant facilities [1]. A limited amount of works study the effect of environmental impact consideration on the design of logistics optimization problems [11]. Koc et al. [26] investigated the combined impact of depot location, fleet composition and routing decisions on vehicle emissions especially in last mile deliveries. They developed an Adaptive Large Neighborhood Search (ALNS) metaheuristic and applied it on several instances with up to 100 customers. They, concluded that circuitous routes can lead to faster speeds and lower costs and $\hbox {CO}_{2}$ emissions. Toro et al. [36] proposed a bi-objective mixed-integer-linear programming (MILP) model for the Green Capacitated Location Routing Problem (G-CLRP). They observed that the use of more vehicles leads to significant fuel economy in the long term. Cheng et al. [6] examined the impact of four carbon emission regulation policies. They proposed mixed-integer-nonlinear programming (MINLP) models and linearization methods along with a Genetic Algorithm (GA) for solving various problem instances. Furthermore, several managerial insights were reported by extensive sensitivity analyses. Cheng et al. [7] introduced a Green Inventory Routing Problem (GIRP) with heterogeneous fleet of vehicles in which environmental impacts were taken into consideration. An exact branch-and-cut algorithm was developed for solving various problem instances and reporting managerial insights.

Despite the significance of considering the environmental impact of logistic activities there is a lack of works on more complex and potentially realistic problems, such as the Location Inventory Routing Problem (LIRP). Zhalechian et al. [38] proposed a multi-objective MINLP model for the closed-loop LIRP. A stochastic–possibilistic approach was used for handling the problem uncertainty. A hybrid self-adaptive GA and a Variable Neighborhood Search (VNS) metaheuristic algorithm was developed in order to solve large-sized instances. Karakostas et al. [22] introduced a Pollution LIRP and proposed a Basic VNS (BVNS) metaheuristic algorithm for the solution of medium-sized problem instances.

This work presents a Pollution LIRP, which considers both economic and environmental impacts of the main logistic activities, such as facilities location, inventory control and vehicle routing. The main contributions of this work are summarized as follows:

• A new complex logistics optimization problem with environmental considerations is proposed.

• An MIP model is formulated by integrating and modifying two models from the literature [7, 39].

• Driving wages are taken under consideration.

• Three VNS-based algorithms have been developed.

• A new benchmark set with the current largest instances of the Pollution LIRP (PLIRP) reported in the open literature have been generated and made publicly available.

• The impact of the flexible replenishment policy on building better routing patterns is illustrated.

• A sensitivity analysis is performed for testing how the variation on holding costs can affect the objective values of the problem instances.

The current work is structured as follows. Sections 2 and 3 present the problem statement and the proposed solution algorithm, respectively. Section 4 provides the computational analysis for evaluating the performance of the proposed method. Finally, Sect. 5 draws up concluding remarks and some thoughts on potential future extensions.

2 Problem description

The PLIRP is defined as a two-echelon supply chain network. Given:

• a set of time periods,

• a set of potential capacitated depots,

• a set of geographically distributed customers,

• a set of homogeneous capacitated fleet of vehicles,

• a single type of product,

• a period-variable demand of each customer

Determine:

• the number and location of depots to be established,

• the allocation of customers to the opened depots,

• the inventory levels at each customer,

• the replenishment quantities and rates for each customer,

• the routes of vehicles,

• the selection of a speed level for traveling each link of the scheduled network.

In order to: minimize an objective function representing the total cost.

The key model assumption are as follows:

• each customer is serviced by one depot,

• each customer is serviced by at most one vehicle in each time period,

• a vehicle departs from and returns to the same depot after servicing one or more customer(s),

• the total delivered quantity to each customer over the time horizon must be equal to its total demand,

The problem is formulated as a mixed integer programming model, by integrating an LIRP model [39] with a Green Inventory-Routing problem (G-IRP) model [7]. Its sets, parameters and variables are provided in Tables 1, 2, 3, and 4.

Table 1 Sets of the mathematical model

Table 2 Vehicles’ parameters

The value of the parameter $f_{c}$ is calculated as the average of the petrol prices in 40 European countries taken from the website www.globalpetrolprices.com in 26th of February in 2018. The value of parameters $f_{e}$ and $f_{d}$ are converted into Euro currency (26th of February, 2018).

Table 3 Rest PLIRP model parameters

Table 4 PLIRP model variables

The objective of the problem is the minimization of total supply chain system cost, including the following cost components:

• Location Cost: $\sum _{j \in J} {{f_j}{y_j}}$, which represents the cost of opening the needed number of depots.

• Inventory Cost $\sum _{i \in I} {h_i} \sum _{t \in H} \Big ( \frac{1}{2}{d_{it}} + \sum _{p \in H,p < t} {w_{itp}}\left( {t - p} \right) + \sum _{p \in H,p > t} {w_{itp}}\left( {t - p + \mathopen |H\mathopen |} \right) \Big )$. It consists of three cost components. The first component represents the average inventory holding cost. The remaining terms impose penalty costs for any early or late replenishment.

• Routing Cost: $\sum _{i \in V} {\sum _{j \in V} {\sum _{t \in H} {\sum _{k \in K} {{c_{ij}}{x_{ijkt}}} } } }$. It represents general routing costs, such as vehicles’ maintenance and/or insurance costs.

• Fuel Consumption Cost: $\sum _{i \in V} \sum _{j \in V} \sum _{k \in K} \sum _{t \in H} \bigg \{ \lambda \left( f_{c} + \left( f_{e}\sigma \right) \right) \Bigg ( \sum _{r \in R} { \frac{\left( zz_{ijktr} ~EFF_{k} ~ES_{k} ~ED_{k} ~c_{ij} \right) }{s_{r}} } + \bigg ( \alpha \gamma _{k} \left( CW_{k} ~x_{ijkt} + a_{ijkt} \right) ~c_{ij} \bigg ) + \left( \beta _{k} ~\gamma _{k} \sum _{r \in R} \left( s_{r}~ zz_{ijktr} \right) ^2 \right) \Bigg ) \bigg \}$. The Comprehensive Modal Emission Model (CMEM) is adopted [3]. Thus, the fuel consumption is affected by vehicle specific characteristics, such as the weight of the load, the vehicle’s speed and obviously the traveling distance. More specifically, the following formulas are utilized.

  • $\lambda = \frac{\epsilon }{HVDF*\psi }$

  • $\gamma _{k} = \frac{1}{1000 ~ VDTE ~ \eta }$

  • $\alpha = \tau + g~ CR ~\sin {\theta } + g ~CR ~\cos {\theta }$

  • $\beta _{k} = 0.5~ CAD~ \rho ~FSA_{k}$

  The first component is the fuel consumption based on the vehicles’ engine function, while the second cost term represents the cost of consumed fuel because of the total vehicles’ weight (curb weights plus load weights). The third one represents the fuel consumption cost related to the vehicles’ speed levels.

• Driver Wages Cost: $\sum _{i \in V} {\sum _{j \in V} {\sum _{k \in K} {\sum _{t \in H} {\sum _{r \in R} {f_{d}\frac{\left( zz_{ijktr} ~c_{ij} \right) }{{s_{r}}}}}}}}$, which represents the cost of the drivers wages.

Thus, the total cost (TC) is calculated as: $\text {TC} = \text {Location Cost} + \text {inventory Cost} + \text {Routing Cost} + \text {Fuel Consumption Cost} + \text {Driver Wages Cost}$.

The mathematical formulation, of the problem under consideration, is as follows:

$$\begin{aligned} \begin{array}{l} \min \quad TC \end{array} \end{aligned}$$

(1)

Subject to

$$\begin{aligned}&\sum \limits _{r \in R} {zz_{ijktr}} = 1 \quad \forall i,j \in V, \forall k \in K,\quad \forall t \in H \end{aligned}$$

(2)

$$\begin{aligned}&\sum \limits _{i \in V} {a_{ijkt}} - \sum \limits _{i \in V} {a_{jikt}} = q_{jkt} PW \quad \forall j \in I, \forall k \in K, q\quad \forall t \in H \end{aligned}$$

(3)

$$\begin{aligned}&\sum \limits _{j \in V} {x_{ijkt}} - \sum \limits _{j \in V} {x_{jikt}} = 0 \quad \forall i \in V, \forall k \in K, \forall t \in H \end{aligned}$$

(4)

$$\begin{aligned}&\sum \limits _{j \in V} {\sum \limits _{k \in K} {{x_{ijkt}}} } \le 1 \quad \forall t \in H,\quad \forall i \in I \end{aligned}$$

(5)

$$\begin{aligned}&\sum \limits _{j \in V} {\sum \limits _{k \in K} {{x_{jikt}}} } \le 1 \quad \forall t \in H,\quad \forall i \in I \end{aligned}$$

(6)

$$\begin{aligned}&\sum \limits _{i \in I} \sum \limits _{j \in J} {{x_{ijkt}}} \quad \le 1 \quad \forall k \in K,\quad \forall t \in H \end{aligned}$$

(7)

$$\begin{aligned}&{x_{ijkt}} = 0 \quad \forall i,j \in J,\quad \forall k \in K,\quad \forall t \in H,\quad i \ne j \end{aligned}$$

(8)

$$\begin{aligned}&\sum \limits _{i \in I} {{q_{ikt}}} \le {Q_k} \quad \forall k \in K,\quad \forall t \in H \end{aligned}$$

(9)

$$\begin{aligned}&\sum \limits _{j \in J} {{z_{ij}} = 1} \quad \forall i \in I \end{aligned}$$

(10)

$$\begin{aligned}&{z_{ij}} \le {y_j} \quad \forall i \in I,\quad \forall j \in J \end{aligned}$$

(11)

$$\begin{aligned}&\sum \limits _{i \in I} {\left( {{z_{ij}}\sum \limits _{t \in H} {{d_{it}}} } \right) } \le {C_j} \quad \forall j \in J \end{aligned}$$

(12)

$$\begin{aligned}&\sum \limits _{u \in I} {{x_{ujkt}}} + \sum \limits _{u \in V\backslash \{ i\} } {{x_{iukt}}} \le 1 + {z_{ij}} \quad \forall i \in I,\quad \forall j \in J,\quad \forall \mathrm{{k}} \in \mathrm{{K}}, \ \forall t \in H \end{aligned}$$

(13)

$$\begin{aligned}&\sum \limits _{i \in I} {\sum \limits _{k \in K} {\sum \limits _{t \in H} {{x_{jikt}}} } } \ge {y_j} \quad \forall j \in J \end{aligned}$$

(14)

$$\begin{aligned}&\sum \limits _{i \in I} {{x_{jikt}}} \le {y_j} \quad \forall j \in J,\forall k \in K,\forall t \in H \end{aligned}$$

(15)

$$\begin{aligned}&\sum \limits _{p \in H} {{w_{itp}}} = {d_{it}} \quad \forall i \in I,\quad \forall \mathrm{{t}} \in \mathrm{{H}} \end{aligned}$$

(16)

$$\begin{aligned}&\sum \limits _{t \in H} {{w_{itp}}} = \sum \limits _{k \in K} {{q_{ikp}}} \quad \forall i \in I,\quad \forall p \in H \end{aligned}$$

(17)

$$\begin{aligned}&{q_{ikt}} \le M\sum \limits _{j \in V} {{x_{ijkt}}} \quad \forall i \in I,\quad \forall t \in H,\quad \forall k \in K \end{aligned}$$

(18)

$$\begin{aligned}&\sum \limits _{j \in V} {{x_{ijkt}}} \le M{q_{ikt}} \quad \forall i \in I,\quad \forall t \in H,\quad \forall \mathrm{{k}} \in \mathrm{{K}} \end{aligned}$$

(19)

$$\begin{aligned}&{\mathrm{{x}}_{ijkt}} \in \left\{ {0,1} \right\} \quad \forall i \in I, \forall j \in J,\quad \forall t \in H,\quad \forall k \in K \end{aligned}$$

(20)

$$\begin{aligned}&{y_j} \in \left\{ {0,1} \right\} \quad \forall j \in J \end{aligned}$$

(21)

$$\begin{aligned}&{z_{ij}} \in \left\{ {0,1} \right\} \quad \forall i \in I, \quad \forall j \in J \end{aligned}$$

(22)

$$\begin{aligned}&{q_{ikt}} \le \min \left\{ {{Q_k},\sum \limits _{p \in H} {{d_{ip}}} } \right\} \quad \forall i \in I,\quad \forall j \in J, \forall k \in K \end{aligned}$$

(23)

$$\begin{aligned}&{w_{itp}} \le {d_{ip}} \quad \forall i \in I,\quad \forall t,p \in H \end{aligned}$$

(24)

Constraints (2) impose that a vehicle travels between nodes with a specific speed level in each time period. Constraints (3) act as subtour elimination constraints, as they declare that the difference between the total weight of the incoming flow of product to a selected customer and the total weight of the outcoming product flow of that customer equals the product weight delivered to that customer in the selected time period with the selected vehicle. The equilibrium between the interior and exterior flow of vehicles is guaranteed by Constraints (4). Constraints (5) and (6) ensure that exactly one vehicle visits each customer at each time period. Constraints (7) guarantee that a vehicle performs mostly one route at each time period. Constraints (8) forbid the movement of a vehicle between depots. Constraints (9) ensure that, the total amount of products sent by a vehicle at a specific period does not exceed the capacity of that vehicle. Constraints (10) guarantee that a vehicle will be travelled from a depot to a customer only if that customer is allocated to the depot. Constraints (11) impose that a customer is assigned to a depot only if that depot is selected to be opened. Constraints (12) respect the capacity of depots. A customer is connected to a depot, only if that customer is assigned to that depot, according to Constraints (13). A vehicle departures from a depot only if that depot is opened according to Constraints (14) and (15). The delivered amount of product to each customer at each time period satisfies the demand of that customer, as guaranteed by Constraints (16). Constraints (17) ensure the equilibrium between scheduled and actual deliveries. A customer is visited at a specific period, only if a replenishment is scheduled for that period, according to Constraints (18). The rest constraints of the model declare the nature of the decision variables.

3 Solution approach

3.1 Construction heuristic

The scope of the constructive phase is the generation of a feasible initial solution. In this work, a three-phased construction heuristic has been developed. In the first phase, location and allocation decisions are made. Inventory-routing decisions are determined in the second phase, while the speed levels for traveling through the network nodes are selected in the last phase.

Initially, for taking the location and allocation decisions, a ratio-based selection criterion is applied for opening the required depots while a nearest customer allocation strategy has been employed for the assignment step. For each one of the candidate depots, the ratio $\frac{fixed\_opening\_cost}{Capacity}$ is computed and the depot with the minimum ratio is chosen. If two or more depots have the same ratio, one of them is selected arbitrarily (commonly the first found). According to the customers’ allocation process, the nearest, to the opened depot, customer is chosen and in the case that its total demand does not violate the remaining capacity of the depot, the customer is assigned to that depot. This initial step of construction heuristic is completed when all customers have been allocated to the opened depots.

In each time period the allocated, to the opened depots, customers are assigned to vehicles, by considering both their demand and the capacity of vehicles. Then, the route of each utilized vehicle is built in a selected time period by applying the Random Insertion method [13]. According to the inventory decisions, the delivered quantities are set equal to the corresponding demand for each customer at each time period. Obviously, in this initial phase if a customer does not require any quantity of the product in a selected period, he will not be included in any route over that period. In the last phase, the selection of the speed levels for traveling through the nodes of the structured network is randomly performed.

3.2 Neighborhood structures

In this work, five local search operators are used in the improvement phase of each proposed solution method. These neighborhood structures are the following:

Inter-route relocate In this neighborhood structure a selected customer is removed from its route and moved in the next position of an other selected customer, who is assigned to a different route. Those two customers can be allocated to the same or different depots. Both of the selected customers must be visited by vehicles in the same time periods, in order this move to be applicable. A replenishment shifting may be applied if a vehicle capacity violation occurs. The following cases can be met by applying this neighborhood:

• Case 1: The two selected customers are allocated to the same depot and no vehicle capacity violations occur.

• Case 2: The selected customers are assigned to the same depot and vehicles capacity violations occur.

• Case 3: The two selected customers are assigned to different depots and no vehicle capacity violations occur.

• Case 4: The two selected customers are allocated to different depots and vehicles capacity violations occur.

In the first case only routing decisions are made. In the second case, both routing and inventory decisions are taken, while routing and allocation decisions are considered in the third case of this move. In the last case, routing, inventory and allocation decisions are simultaneously made. Figures 1 and 2illustrate an example of this neighborhood, applied on routes allocated to the same depot. The pairs of customers are (4, 1) in the first time period and (3, 5) in the second time period.

Fig. 1

Routes from the same depot in each time period before the application of the inter-route relocate move

Fig. 2

Routes from the same depot in each time period after the application of the inter-route relocate move

Figures 3 and 4 illustrate an example of this neighborhood, applied on routes allocated to different depots. The move is applied on the pair of customers (2, 5) in all available time periods.

Fig. 3

Routes from different depots in each time period before the application of the inter-route relocate move

Fig. 4

Routes from different depots in each time period after the application of the inter-route relocate move

Inter-route exchange This neighborhood swaps two customers from different routes in the time horizon. The exchanged customers can be allocated either to the same depot or different depots. If the customers are allocated to the same depot, the swapping may not be applied in each time period. However, in the second case the exchanging must be valid for all time periods, in order to be applicable. The special cases of this move are summarized as follows:

• Case 1: Vehicle capacity violation does not occur.

• Case 2: The demand of a customer exceeds the capacity of the vehicle servicing the other customer in one or more time periods.

The first case makes only routing decisions, while in the second case routing and inventory decisions are taken. Changes on allocation decisions will take place only if the swapped customers are allocated to different depots. Figures 5 and 6 present an illustrative example of the inter-route exchange move applied on routes allocated to the same depot for the case of customers (1, 5) in the first period and (2, 4) in the second one.

Fig. 5

Routes from the same depot in each time period before the application of the inter-route exchange move

Fig. 6

Routes from the same depot in each time period after the application of the inter-route exchange move

Figures 7 and 8 depict an instance of the inter-route exchange move applied on routes allocated to different depots for the pair of customers (2, 3).

Fig. 7

Routes from different depots in each time period after the application of the inter-route exchange move

Fig. 8

Routes from different depots in each time period after the application of the inter-route exchange move

Exchange opened–closed depots This neighborhood exchanges a closed depot with an opened depot. For a selected closed depot, the cost change for swapping it with each one of all opened depots, is calculated. Then, the pair of the opened–closed depots with the minimum exchanging cost is selected. Subsequently, it is examined if the scheduled swapping does not violate any capacity constraint. After the validation checking step, the newly opened depot is inserted in the routes assigned to the currently opened depot via a minimum insertion cost procedure. This insertion process may involve customers re-ordering in the routes. Obviously, the move is applied only if the overall cost decreases, which consists of location and routing costs. Figure 9 illustrates the an example of this neighborhood.

Fig. 9

Example of the exchange opened–closed depots neighborhood

Intra-route relocate In this move a selected customer is removed from its current position in its route and moved in a different position in the same route. Figure 10 illustrates an example of the Intra-route Relocate neighborhood, applied on the pair of customers (5, 4).

Fig. 10

Example of the intra-route relocate neighborhood

2–2 replenishment exchange In this neighborhood structure, two time periods $t_1$ and $t_2$ are randomly selected and the two most distant customers i and b, both serviced in those two periods, are identified. The replenishment of customer i in period $t_1$ is moved to the period $t_2$, and the replenishment of customer b is moved from period $t_2$ to period $t_1$. Consequently, there is no need to visit customers i and b in periods $t_1$ and $t_2$ respectively. If the total cost decreases and there are no violations on the vehicles capacities, the move is applied. To clarify the function of this neighborhood, an illustrative example is provided in Figs. 11 and 12. The most distant customers are 3 and 7. The customer 3 is removed from its route in period 1 and his delivery is shifted in period 2, while the customer 7 is removed from his current route in period 2 and his delivered quantity is shifted in period 1.

Fig. 11

Example of network structure before the application of 2–2 Replenishment Exchange neighborhood

Fig. 12

Example of network structure after the application of 2–2 Replenishment Exchange neighborhood

In order to avoid potential violation of vehicles capacities, while applying the Inter-route Relocate and the Inter-route Exchange moves, a shifting of surplus product quantity may be applied.

3.3 Shaking procedure

For escaping local optimum solutions, a shaking procedure with three local search operators is proposed, including the following structures:

• Inter-route Exchange.

• Exchange Opened–Closed Depots.

• Intra-Route Relocate.

In each iteration of this diversification method, one of the proposed local search operators is randomly selected and a predefined number of random jumps are applied. Its pseudo-code is given in Algorithm 1.

The shaking procedure receives an incumbent solution S, the maximum number of iterations $k_{\mathrm{max}}$ executed in the perturbation phase and the number of neighborhood structures $l_{\mathrm{max}}$ as input. A new solution $S'$ is obtained by applying k (where $1< k < k_{\mathrm{max}}$) times one randomly selected neighborhood of the above local search operators.

3.4 Variable neighborhood search (VNS)

Variable Neighborhood Search (VNS) is a flexible framework for building heuristics, which manages a single solution at each step time [15]. It systematically changes predefined neighborhood structures during the search [9, 14, 33] and has been successfully applied several times in location, inventory, and routing problems [19, 21, 24, 28].

The Basic VNS (BVNS), the Variable Neighborhood Descent (VND), and the General Variable Neighborhood Search (GVNS) are three of the most well-known variants of the VNS. The BVNS alternates a shaking procedure with a local search operator, while the VND explores several local search operators without using a diversification procedure [15, 16, 16, 34]. According to the neighborhood change criteria, different sequential VND schemes have been proposed. Two of the mostly used VND schemes are the pipe VND (pVND) and the cyclic VND (cVND) [10]. In the pVND the search continues in the same neighborhood, while improvements occurred. In the cVND, the neighborhood structures are alternated regardless the achieved improvements. The GVNS extents the BVNS, by using a VND scheme as its main improvement step [12, 23]. In this work, a BVNS, two GVNS (GVNS with cVND and GVNS with pVND) solution methods and their corresponding adaptive variants, have been developed. The execution of the developed VNS-based methods is bounded by a time stopping criterion denoted by the parameter $max\_time$. The proposed solution algorithms are provided in the following pseudo-codes.

The pseudo-code of the $GVNS_{cVND}$ algorithm is exactly the same with the pseudo-code of the $GVNS_{pVND}$ algorithm with the only difference that it uses the cVND instead of pVND. The adaptive variants of these methods uses an adaptive re-ordering mechanism of the local search operators. This adaptive mechanism uses past experience, such the number of improvements achieved by each operator and proceeds a different order. More specifically, the array “Improvements_Counter” stores in its positions the improvements achieved by each operator and then a descending sorting is performed on this array by the use of the function $Descending\_Order()$. The pseudo-code of this mechanism is summarized in Algorithm 4.

An example of the adaptive schemes is provided in the following pseudo-code of the Adaptive $GVNS_{pVND}$ algorithm.

4 Computational analysis and results

4.1 Computing environment and parameter settings

The proposed methods have been implemented in Fortran (Intel Fortran compiler 18.0 with optimization option/O3) and ran on a desktop PC running Windows 7 Professional 64-bit with an Intel Core i7-4771 CPU at 3.5 GHz and 16 GB RAM. The execution time limit for the proposed algorithms was set at 60 s. The PLIRP was also modeled in GAMS (GAMS 24.9.1) [5] and its problem instances were solved using CPLEX 12.7.1.0 solver with the time limit of 2 h for the small-sized instances and 5 h for medium and large-sized instances. It should be mentioned that CPLEX ran in the same computing environment with Intel Fortran compiler.

4.2 Computational results on PLIRP instances

In this work 30 new PLIRP instances have been created by following the format of instances proposed in a previous work [39]. They are reported in the form X–Y–Z, where X represents the number of potential depots, Y the number of customers and Z is the number of time periods. These instances are available in: http://pse.cheng.auth.gr/index.php/publications/benchmarks. Table 5 provides the average values of total costs of all the 30 problem instances and for each solution method, using different $k_{\mathrm{max}}$ values. The first sub-column of the main columns 2–4 in Table 5 refers to the average performance of algorithms, while the second one focuses on the best-found solutions.

Table 5 Shaking strength analysis on the performance of proposed methods

According to the reported solutions, the parameter value $k_{\mathrm{max}} = 5$ produces in average the best values for the proposed BVNS, ABVNS and ${ GVNS}_{{ cVND}}$ algorithms. The ${ AGVNS}_{{ cVND}}$ algorithm performs better by using a shaking strength of $k_{\mathrm{max}} = 15$, while the ${ AGVNS}_{{ pVND}}$ algorithm produces better solution using the parameter value $k_{\mathrm{max}} = 20$. The results achieved using the ${ GVNS}_{{ pVND}}$ with the parameter value $k_{\mathrm{max}} = 10$ were the best found solutions in average compared with either the same scheme but with different $k_{\mathrm{max}}$ values or the other schemes (18.5% from BVNS, 7.5% from ABVNS, and 6.3% from ${ GVNS}_{{ cVND}}$, 7% from ${ GVNS}_{{ cVND}}$ and 1.94% from ${ AGVNS}_{{ pVND}}$).

From a problem size perspective, the ${ AGVNS}_{{ pVND}}$ algorithm produces better solutions for small-sized instances (using $k_{\mathrm{max}} = 20$) and medium-sized instances (using $k_{\mathrm{max}} = 5$) than other approaches, while the ${ GVNS}_{{ pVND}}$ algorithm using the shaking strength $k_{\mathrm{max}} = 10$ is more efficient than other methods for the solution of large problem cases.

From this analysis it is noticed that classic GVNS-based methods provide better solutions than their corresponding adaptive variants. An explanation of this conspicuous observation is that using the adaptive re-ordering mechanism leads to further time consumption. Thus, the number of iterations of the improvement phase is significantly decreased for the case of large-sized instances.

The ${ GVNS}_{{ pVND}}$ uses the Speed Selection Procedure after each local search operator. Table 6 illustrates potential difference between this GVNS scheme and ${ GVNS}_{{ pVND}}$ which applies the SSP once after the completion of a ${ pVND}$ iteration. The initial scheme is called ${ GVNS}_{{ pVND}}\_1$ and the second one, ${ GVNS}_{{ pVND}}\_2$.

Table 6 Results achieved by the two ${ GVNS}_{{ pVND}}$ schemes on the 30 PLIRP instances

Despite the fact that, the ${ GVNS}_{{ pVND}}\_2$ scheme produces more best values than the ${ GVNS}_{{ pVND}}\_1$, the ${ GVNS}_{{ pVND}}\_1$ is slightly better in terms of average solution quality. The previous results demonstrate that a further improved solution method can be proposed by adopting a hybrid scheme. More specifically, for the solution of small- and medium-sized instances the ${ AGVNS}_{{ pVND}}$ method with a shaking strength of $k_{\mathrm{max}} = 20$ will be applied, while the ${ GVNS}_{{ pVND}}$ using $k_{\mathrm{max}} = 10$ will be selected for larger problems. The overall process of the solution method is illustrated in Algorithm 6.

The second column of Table 7 reports the results achieved by GAMS/CPLEX. As it can be noticed, the CPLEX solver can solve only eight out of ten small-sized instances within a time limit of 2 h. No solution, using CPLEX, was found for the rest of the problem instances. In the third column, the average objective values achieved by the ${ Hybrid}\_{ GVNS}_{{ pVND}}$, while the fourth column contains the best results achieved by the ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm. The last two columns provide the solution gaps between CPLEX and ${ Hybrid}\_{ GVNS}_{{ pVND}}$. According to the reported results, the ${ Hybrid}\_{ GVNS}_{{ pVND}}$ provides 2.4% better results than CPLEX (approximately 3% focused on the best found solutions of the ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm). Based on the fact that, the CPLEX solver cannot provide any feasible solution for medium- and large-sized instances even within a time limit of 5 h and its high computational time for finding the reported solutions in the case of the small-sized instances it can be concluded that, the proposed ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm is an efficient method for solving large-scale PLIRP instances.

Table 7 Comparative analysis between CPLEX and ${ Hybrid}\_{ GVNS}_{{ pVND}}$ on the small- and medium-sized instances

Table 8 reports the best known solutions of the 30 PLIRP instances.

Table 8 Best known solutions for the 30 PLIRP instances

Table 9 summarizes the number of the vehicles used for each problem instance using the ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm. According to the number of opened depots, all the proposed methods open exactly two depots in each problem instance. Based on the total demand of customers, two depots are the minimum required for fulfilling customers demands per instance. A replenishment policy highly impacts the produced solutions. Furthermore, a flexible replenishment policy enables the building of cost efficient routing patterns [37, 39].

Table 9 Number of used vehicles per instance using ${ Hybrid}\_{ GVNS}_{{ pVND}}$

Figure 13 illustrates the effect of flexible replenishment policy on the routing and the inventory costs. More specifically, the values of routing and inventory costs reported in the successful iterations of the ${ GVNS}_{{ pVND}}\_1$ are depicted. Routing costs can be decreased by allowing flexible reorder points and order quantities for the customers due to the reduction of deliveries or the efficient clustering of customers into routes. For instance, the deliveries to a distant customer can be reduced by replenishing it with more product quantities in less time periods. Also, this shifting of product quantities results on more available space in the vehicles, so more customers can be serviced by the same vehicle. This can lead to cost efficient routing circuits. On the other hand, the deferred deliveries leads to an increase in the inventory cost.

Fig. 13

Effect of flexible replenishment policy on the relationship between routing and inventory costs

It should be mentioned that, the solutions obtained by the ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm do not always follow the previous relation. In some cases, the algorithm splits the routes in order to reduce the routing cost without increasing the inventory cost. However, the splitting strategy leads to the usage of more vehicles.

4.3 Sensitivity analysis

To further consider the significance of the flexible replenishment policy, the effect of holding costs on the total cost is studied through a parametric analysis. Holding costs are crucial for the performance of logistics design and operation. In the literature, several works studied the effect of holding cost variations on the overall performance of logistic systems [2, 17]. In this work, two testing scenarios are considered. In the first one, a holding cost increase by 10% is examined, while in the second one the holding cost is increased by 15%. The ${ Hybrid}\_{ GVNS}_{{ pVND}}$ algorithm, which marked as the most efficient between the proposed solution methods, was used for solving the problem instances in these two scenarios. Table 10 provides both the average and best found results per scenario. To clarify, the terms ${ OV}\_{ Avg}\_X\%$ and ${ OV}\_{ Best}\_X\%$ refer to the Objective Value in average or best case (respectively), under a holding cost variation of $X\%$.

Table 10 The average and best found results in sensitivity analysis scenarios

The results indicate that, the second scenario produces 0.45% worse solutions in average comparing to the first one. Moreover, the initial average solutions of the instances are 1.98% and 2.44% better than those achieved in the first and the second scenario respectively, which means that the objective value seems to be sensitive on the changes of the holding costs. However, the adoption of a flexible replenishment policy keeps the increase of the cost in relatively low levels.

Also, there are some instances in which better solutions were produced by increasing the holding costs. This is justified as, an increase in the holding costs, forces the usage of more vehicles (max two more than the reported vehicles in Table 9) in order to form better routing patterns, thus leading to further routing cost reduction.

5 Conclusions

This work presents a new green supply chain network optimization problem, which considers both economic and environmental concerns. GVNS- and Adaptive GVNS-based solution approaches have been developed for the efficient solution of medium- and large-sized instances. A new set of 30 random generated instances is used in extended numerical analyses. A computational $k_{\mathrm{max}}$ parameter analysis has been made. This analysis indicates that, the GVNS scheme which uses the pipe VND (${ GVNS}_{{ pVND}}$) method in its improvement process is proved to be the most efficient method. In addition, the effect of executing the Speed Selection Procedure either after each local search operator or in the end of each VND iteration is tested. The GVNS scheme which uses the Speed Selection Procedure after each local search operator proved as the most efficient solution method. However, from a problem size perspective, a hybrid solution approach, which uses the Adaptive GVNS (${ AGVNS}_{{ pVND}}$) algorithm with different $k_{\mathrm{max}}$ values for the solution of small- and medium-sized instances and the ${ GVNS}_{{ pVND}}$ for solving large problem cases. This hybrid solution scheme is compared with the CPLEX solver in ten small-sized instances. The proposed solution method produces approximately 3% better solutions than CPLEX. Finally, a sensitivity analysis is performed to study the effect of the variations of holding costs on the objective value. The results illustrate that, any increase on the holding costs affects the objective value. However, the use of the flexible replenishment policy keeps the increase of total cost in relatively low levels. Some exceptions are noticed by using more vehicles.

Current work focuses on the investigation of an adaptive mechanism for re-ordering the shaking operators in alternative shaking schemes, in order to further improve the efficiency of the proposed methods. Also, other local search operators will be investigated both in the improvement and shaking steps of the algorithm. Finally, the consideration of the average time-to-target may be a useful metric for further performance evaluation of the developed methods.