Keywords

1 Introduction

Today, the management of supply chain operations is a trending topic for many businesses where competition is of utmost importance. Thus, it is inevitable to provide effective coordination between the production and distribution phases of the supply chain. Fulfilling customer demands with the required quantity on time becomes an extremely difficult task, especially for companies which apply the zero-inventory model and make-to-order businesses. The integrated approach is also beneficial for time management of time-sensitive or perishable products. Considering all these aspects, operational integration for the two main stages is carried out by making decisions simultaneously for production scheduling and vehicle routing. According to the integrated approach, as the output of either does not affect the other, the decisions on production and distribution stages will not limit each other.

Recently, there has been a remarkable growth in the online shopping sector [2]. Due to the abundance of competitors in the market and the ease of communication between customers and companies, firms are under increasing pressure to ensure customer satisfaction. For this reason, they have turned to customer-oriented performance measures rather than classical measures such as cost and profit. According to the current applications, customers know when they can receive the orders and even specify their own preferences regarding delivery time, which is often handled by time windows in the vehicle routing literature.

A current survey, which covers the enlarged literature on integrated production scheduling and outbound vehicle routing problems, can be found in [4]. In the survey, the literature is classified in terms of the number of operations, the number of vehicles, and the number of trips. According to this classification, the problem under study can be represented in a section of parallel machines, several vehicles, and single trips, as in the studies of [3, 5, 6, 11, 12, 18].

Although there are several criteria (i.e., objectives) identified by researchers, in general, objectives can be divided into two main groups: cost and service. In addition, sometimes multiple criteria can be handled simultaneously as a summation of objectives in a single form [5, 9, 21, 22] or multi-objective structure [7, 14, 23]. While many criteria that are related to the problem under study have been defined in the literature [4], the objective of this study can be expressed as minimizing the sum of total earliness and tardiness. Ullrich [18] considers a variant of the integrated problem with the objective of minimizing the total tardiness and proposes a genetic algorithm to produce optimal or near optimal solutions in a reasonable amount of time. Wu et al. [20] formulate a mathematical model for a production scheduling-based routing problem with time windows and setup times for minimizing total tardiness. Hou et al. [10] address an integrated problem where the production stage has multiple factories, and each factory has multiple machines based on the flow shop environment. For the objective of minimizing total weighted earliness and tardiness, they propose a swarm intelligence approach which is called brainstorm optimization algorithm.

In the integrated problem under investigation, the distribution phase has a homogeneous fleet that can only be utilized once, while the production environment consists of identical parallel machines and each job has a single operation that needs to be performed on any machines. It is very important for customer satisfaction to deliver orders according to the predefined time windows. In addition, vehicles that arrive earlier must wait idle until the lower time bound of any customer. So, the objective is to minimize the sum of total earliness and tardiness. After formulating the problem, we propose a metaheuristic approach, Iterated Local Search (ILS), to obtain good quality solutions in a reasonable time.

The contribution of the paper can be summarized as follows: (i) The sum of the total earliness and tardiness is studied simultaneously for the first time for the integrated problem at hand. (ii) A new mixed integer programming formulation is developed. (iii) A metaheuristic algorithm, Iterated Local Search (ILS), is presented, and a perturbation mechanism is proposed for the only production environment adapted for the integrated problem.

The remainder of the study is organized as follows: In Sect. 2, we define the MIP formulation for the integrated problem with an illustrative example. While in Sect. 3, the proposed ILS structure is given, in Sect. 4, computational experiments are discussed based on the different problem parameters. Finally, in Sect. 5, conclusions and future directions are discussed.

2 Problem Definition

This section is dedicated to two subsections including the MIP model and an illustrative example for visual presentation.

2.1 MIP Model

The assumptions of the problem can be summarized as follows: There is a single production facility in which a set of identical parallel machines is used to produce customer orders. After the production of a particular batch is completed, a limited number of vehicles is delivering the consolidated orders to associated customers by considering the time window of each customer. Vehicles can be used only once (i.e., multiple use is not allowed). Vehicle capacities are homogeneous, and the capacity of a vehicle is enough to serve all customers. As a result, there is no requirement to use all vehicles in the system. The sequence of production and distribution does not have to be identical. The objective is to minimize the sum of total earliness and tardiness penalties. The notations used in the MIP formulation are shown in Table 1.

Table 1. Notations used in the MIP model.
Full size table

Based on the formal definition and notations, we formulate an MIP model for the problem as follows:

$$ minimize \mathop \sum \limits_{{j \in N_{C} }} \left( {E_{j} + T_{j} } \right) $$
(1)

Subject to;

$$ \mathop \sum \limits_{{j \in N_{C} }} W_{jm} \le 1\,\,\,\,\,\,\,\,\,\,\forall m \in M $$
(2)
$$ \mathop \sum \limits_{{i \in N_{C} }} Z_{ji} + L_{j} = 1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(3)
$$ \mathop \sum \limits_{m \in M} W_{jm} + \mathop \sum \limits_{{i \in N_{C} }} Z_{ij} = 1\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(4)
$$ C_{j} \ge p_{j} - H\left( {1 - W_{jm} } \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} ; m \in M $$
(5)
$$ C_{j} \le p_{j} + H\left( {1 - W_{jm} } \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} ; m \in M $$
(6)
$$ C_{i} - C_{j} + HZ_{ij} + \left( {H - p_{i} - p_{j} } \right)Z_{ji} \le H - p_{j} \,\,\,\,\,\,\,\,\forall i,j \in N_{C} ;i \ne j $$
(7)
$$ \mathop \sum \limits_{{j \in N_{C} }} X_{0jk} \le 1\,\,\,\,\,\,\,\,\,\,\,\forall k \in K $$
(8)
$$ \mathop \sum \limits_{k \in K} \mathop \sum \limits_{i \in N} X_{ijk} = 1\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(9)
$$ \mathop \sum \limits_{u \in N} X_{ujk} = \mathop \sum \limits_{i \in N} X_{jik} \,\,\,\,\,\,\,\,\forall j \in N;\forall k \in K $$
(10)
$$ \mathop \sum \limits_{u \in N} F_{uj} - \mathop \sum \limits_{i \in N} F_{ji} = d_{j} \,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(11)
$$ d_{j} \mathop \sum \limits_{k \in K} X_{ijk} \le F_{ij} \,\,\,\,\,\,\,\,\,\,\,\forall i,j \in N;i \ne j $$
(12)
$$ Q - d_{i} + \mathop \sum \limits_{k \in K} X_{ijk} \ge F_{ij} \,\,\,\,\,\,\,\,\,\forall i,j \in N;i \ne j $$
(13)
$$ R_{jk} = \left( {\mathop \sum \limits_{{i \in N_{C} }} X_{jik} } \right) + X_{j0k} \,\,\,\,\,\,\,\,\forall j \in N_{C} ;\forall k \in K $$
(14)
$$ C_{i} - C_{j} \le H\left( {1 - G_{ij} } \right)\,\,\,\,\,\,\,\,\forall i,j \in N_{C} ;i \ne j $$
(15)
$$ C_{j} - C_{i} \le HG_{ij} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall i,j \in N_{C} ;i \ne j $$
(16)
$$ V_{k} \ge C_{i} - H\left( {1 - X_{ijk} } \right)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall i,j \in N;i \ne j;\forall k \in K $$
(17)
$$ \begin{array}{*{20}c} {V_{k} \le C_{j} + H(1 - (R_{jk} - \mathop \sum \limits_{{i \in N_{C} }} AX3_{jik} } & {\forall j \in N_{C} ;\forall k \in K} \\ { + \mathop \sum \limits_{{i \in N_{C} }} \left( {G_{ij} + G_{ji} - 1} \right)))} & {} \\ \end{array} $$
(18)
$$ V_{k} - Y_{j} + s_{0} + t_{0j} \le H\left( {1 - X_{0jk} } \right)\,\,\,\,\,\,\,\,\,\forall j \in N_{C} ;\forall k \in K $$
(19)
$$ Y_{j} - V_{k} - s_{0} - t_{0j} \le H\left( {1 - X_{0jk} } \right)\,\,\,\,\,\,\,\,\,\forall j \in N_{C} ;\forall k \in K $$
(20)
$$ Y_{i}^{*} - Y_{j} + s_{i} + t_{ij} \le H\left( {1 - \mathop \sum \limits_{k \in K} X_{ijk} } \right)\,\,\,\,\,\,\,\forall i,j \in N_{C} ;i \ne j $$
(21)
$$ Y_{j} - Y_{i}^{*} - s_{i} - t_{ij} \le H\left( {1 - \mathop \sum \limits_{k \in K} X_{ijk} } \right)\,\,\,\,\,\,\,\,\forall i,j \in N_{C} ;i \ne j $$
(22)
$$ T_{j} \ge Y_{j}^{*} - b_{j} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(23)
$$ E_{j} \ge a_{j} - Y_{j} \,\,\,\,\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(24)
$$ Y_{j} - a_{j} \le H\left( {1 - O_{j} } \right)\,\,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(25)
$$ a_{j} - Y_{j} \le HO_{j} \,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(26)
$$ Y_{j}^{*} = Y_{j} - AX4_{j} + a_{j} O_{j} \,\,\,\,\,\,\,\,\,\forall j \in N_{C} $$
(27)

The objective function minimizing the sum of total earliness and tardiness is given in (1). It is determined whether a job is the successor of any job on the same machine or the first/last job to be processed on any machine by Cons. (2)–(4). While Cons. (5) and (6) are used to determine the production completion time of the first jobs on each machine, Cons. (7) defines the production completion time for predecessor and successor jobs on each machine. Cons. (8) identifies the first customer on any tour. Cons. (9) and (10) guarantee that each customer must be visited exactly once, and the number of entering and leaving arcs must be the same for any node, respectively. Cons. (11)–(13) are based on a single-commodity flow formulation described by [8]. This set of constraints guarantee a connected tour. So, we define \(F_{ij}\) as a continuous variable indicating the amount of load flowing between nodes \(i\) and \(j.\) In order to assure subtour elimination in the formulation, we impose tight bounds on the flow variables \(F_{ij}\) in addition to a set of flow conservation constraints. Cons. (11) and (12) indicate that the total amount of load on any vehicle decreases as it delivers the order to the related customer. According to Cons (13), the total amount of load on any vehicle should not exceed its capacity. While Cons. (14) defines the variable of \(R_{jk}\), , Cons. (15) and (16) define the variable of \(G_{ij}\). . According to Cons. (17) and (18), each vehicle must wait in production facility until the production process of the batch assigned completes. Cons. (19) and (20) specify the arrival time to the first customer on any tour. Cons. (21) and (22) state the arrival time to the two consecutive customers on any tour. Cons. (23) and (24) calculate tardiness and earliness, respectively, if either of them occurs. Cons. (25) and (26) define the variable of \(O_{j}\). . According to Cons. (27), the service starting time of any customer is equal to the maximum value of the lower bound of the time windows and arrival time for that customer.

As can be seen, the developed model is not linear because it consists of the product of two variables. So, while we use the Cons. (28)–(30) for \(AX1_{ijk} ,AX2_{ij}\) and \(AX3_{ijk}\) where both x and y are binary variables, Cons. (31)–(33) are used for the linearization of \(AX4_{j}\) where x is a binary variable and y is a non-negative continuous variable, and M is a sufficiently large number.

$$ z \le x $$
(28)
$$ z \le y $$
(29)
$$ z \ge x + y - 1 $$
(30)
$$ z \le xM $$
(31)
$$ z \le y $$
(32)
$$ z \ge y - \left( {1 - x} \right)M $$
(33)

2.2 Illustrative Example

Based on the formal definition given in the previous section, we present an illustrative problem for visualizing the integrated approach. In the example, whose parameters are listed in Table 2, there are nine customers, four identical parallel machines, and two homogenous vehicles with enough capacity to serve all customers. Table 1 contains the descriptions of parameters listed in the first row of Table 2.

Table 2. Parameters of an illustrative example
Full size table

A feasible solution for the given example is illustrated in Fig. 1. According to Fig. 1, jobs 7 and 5 are processed on the first machine. Jobs assigned to other machines are depicted similarly. While customers 2, 7, 8, and 6 are served by the first vehicle, the second vehicle delivers orders 1, 9, 3, 5, and 4, respectively. Shipping boxes show the service time spent on each customer. Vehicle one (v1) departs from the depot when the production process of the first batch completes at time 22, then goes directly from the depot to customer 2 at time 54. Based on the time window of customer 2, the vehicle must wait 1 min until the lower bound of the time window (i.e., 55). This process proceeds in the same way for other customers. Based on the following feasible solution, earliness occurs for customers 2 and 4, while tardiness occurs for customers 1, 3, 5, 6, and 8, as seen from Fig. 1. So, the objective value of the problem is equal to the 156 which is a summation of 6 earliness and 150 tardiness.

Fig. 1.
figure 1

A Gantt chart of a feasible solution (also optimal solution) for the illustrated example.

Full size image

3 Iterated Local Search

The idea of Iterated Local Search (ILS) as an extension of the local search procedure was first introduced in [13]. Basically, ILS is formed by incorporating a perturbation mechanism into the local search process to avoid getting stuck in local optima. ILS has been used for many combinatorial optimization problems in the literature [15,16,––17, 19]. The pseudo code of the proposed ILS is given in Fig. 2.

Fig. 2.
figure 2

The pseudocode of the proposed ILS.

Full size image

In the perturbation process, we use the regeneration operator proposed by [1]. In the selection process, parents are selected as the current local optimal solution and the neighbor solution with the best objective. The encoding scheme developed by Afralizad and Rezaeian [1] is also adapted to the integrated problem. According to the adapted chromosome, while the first and third rows represent the permutation of the jobs and customers, respectively, the second and fourth rows demonstrate the assignments of machines and vehicles for each job and customer in the corresponding position. The encoding scheme for the illustrated problem is depicted in Fig. 3. In the local search process, we use swap, insert, and 2-opt operators for both production and distribution phases so as to consider inter and intra machines and vehicles.

Fig. 3.
figure 3

The encoding scheme

Full size image

4 Computational Results

For computational experiments, we generate a total of 486 instances randomly based on the number of customers, machines, and vehicles. While the number of customers includes six levels from 5 to 10, machines and vehicles are set to three levels covering 2, 3, and 4. In addition, for each factor level of the parameters, nine different random instances are generated.

The CPLEX solver embedded in GAMS is used as the MIP-solver. The maximum computational time for the CPLEX solver is set to 10800 s, and the stopping criterion for ILS is run \(1000 \times N\) iterations, where \(N\) represents the number of customers.

Table 3 reports the comparative results of CPLEX and ILS based on the problem parameters. The column Parameters describes the level of problem parameters based on the number of customers, machines, and vehicles, respectively. In the CPLEX column, while Obj. Indicates the average objective value (i.e., upper bound), LB represents the lower bound found by CPLEX in a given time limit of 3 h. The number of optimal solutions found by CPLEX and ILS are given in column #Opt. Finally, the solution times in seconds for CPLEX and ILS are indicated by the CPU column. The deviation of objective values from each other (DEV%) is calculated by \(\frac{{Obj_{CPLEX} - Obj_{ILS} }}{{Obj_{CPLEX} }} \times 100\) if the solution found by CPLEX is worse than ILS; otherwise, it is calculated by \(\frac{{Obj_{ILS} - Obj_{CPLEX} }}{{Obj_{ILS} }} \times 100\).

We summarize the following remarks from Table 3: CPLEX can find all optimal solutions for all instances of six and seven customers. As the number of customers increases, the ability of CPLEX to find optimal solutions declines dramatically. For ten customers, CPLEX can only find seven optimal solutions out of 81 instances. Like the first remark, the CPU time also increases drastically when the number of customers increases from 5 to 10 and reaches to about 10,000 s for the level of 10 customers. In addition, when the effect of the number of machines and vehicles are examined, we reach the following results: As the number of machines increases, CPLEX’s ability to find optimal solutions increases. This is a result of the reduction of the tardiness component in the objective function due to the simultaneous use of resources in the production phase. Similarly, as the number of vehicles increases, the average objective value decreases. However, the number of vehicles has not as much an effect as the number of machines in terms of the number of optimal solutions found and CPU times. As can be seen from Table 3, CPLEX is able to find the optimal solution in 331 instances out of 486 instances within 3 h. When the same instances are solved with ILS, it is seen to provide optimal solutions for 329 instances out of 331 instances whose optimality are proven by CPLEX. Especially in instances where the number of customers is set to 9 and 10, the solutions obtained by ILS are of higher quality, and the percent deviation of CPLEX from ILS (DEV%) reaches to 77%. As a result, ILS has shown superior performance in terms of both solution quality and solution time.

Table 3. The comparison of CPLEX and ILS based on the number of customers, machines, and vehicles.
Full size table

5 Final Remarks and Future Directions

In this study, we develop a new MIP model for a variant of the integrated production and distribution problem that consists of parallel machine scheduling and homogeneous vehicle routing problems with time windows. The objective of the model is formed by minimizing the sum of total earliness and tardiness. The performance of the exact method is found to be poor, even for only seven customers. We also examine the performance of CPLEX based on the number of customers, machines, and vehicles. According to the results, the increase in the number of customers reduces the performance of CPLEX dramatically. Especially for nine and ten customers, the exact method can no longer be considered a reasonable solution method for an operational-level problem. On the contrary, the increase in the number of machines positively affects the performance of CPLEX. The reason for this is that the departure times of the vehicles are moved earlier due to the simultaneous use of identical parallel machines in the production environment. Thus, the total tardiness in the objective function tends to decrease. When the number of vehicles increases, we see that the objective function value decreases, but there is no significant difference when CPU time and the number of optimal solutions found is examined. For a customer number of 10, CPLEX can only find optimality in 7 out of 81 instances in a given time limit of 10800 s, and the deviation between the upper and lower bounds found by CPLEX is calculated at 96.7%. Then, we propose the ILS algorithm for solving the integrated problem efficiently. According to the comparative results, the proposed ILS algorithm performs quite well in terms of both solution quality and time. The CPU time of ILS for a level of ten customers is about 8 s, even for 10000 iterations. In addition, ILS is found to produce 77% better solutions in terms of objective function value when compared to CPLEX for ten customers.

Future work may focus on larger instances, and the performance of ILS can be compared to other metaheuristics such as genetic algorithms, particle swarm optimization, etc. By considering specific situations of problem assumptions, such as heterogeneous vehicles, unrelated parallel machines, and sequence dependent set-up times, a new variant of an integrated problem can be handled. In addition, sustainable objectives such as energy-efficient strategies at both the production and distribution levels can be considered.