A novel artificial ecological niche optimization algorithm for car sequencing problem considering energy consumption

Abstract

This article proposes a novel artificial ecological niche optimization algorithm for car sequencing problem considering energy consumption to satisfy the requirements of the paint shop and the assembly line. Energy consumption, which is an important issue, is often neglected during the production process. In this article, the mathematical model of car sequencing problem with energy consumption is established. A new artificial ecological niche optimization algorithm that imitates natural ecosystem is proposed to solve this problem. The car sequence is considered as an ecosystem. Ecological niche theory, niche overlap and niche differentiation principles are applied in this algorithm, which leads the ecosystem to adapt itself to a more ecological balance condition accompanying less violence appear in the car sequence. Energy consumption in the scheduling process of ring sorting buffer was considered as biogenic migration in the algorithm. The proposed algorithm is verified on a set of instances provided by the French car manufacturer Renault. The computation results indicate the effectiveness of the proposed algorithm.

Introduction

Currently, energy consumption has become an important issue and because of global warming and energy prices, more and more automobile manufacturers start to be concerned about low-carbon manufacturing. Due to the individual demands from customers, mixed-model production in the automobile manufacturing shop is inevitable to increase the energy consumption. A modern car manufacturer is usually composed of three major workshops: body shop, paint shop and assembly line. Car sequencing problem (CSP) focuses on the requirements of the paint shop and assembly line. The paint shop has to minimize the consumption of paint solvent, and the assembly line has to smooth the workload. ¹ It was described by Parrello et al. ² as a case of job-shop scheduling in 1986; in order to let the cars produce on a single assembly line homogenous, the line is designed to handle a predetermined ratio of cars with that option to cars without that option. Kis ³ proved that the CSP is nondeterministic polynomial-time hard (NP-hard) in the strong sense and Gent ⁴ also showed that the decision problem associated with the CSP whether there exists an optimal solution without any violations of the constraints defined by the assembly line is NP-hard. It was often described as a simplified approach of mixed-model sequencing ⁵ and now become a well-known combinatorial optimization problem faced by car manufacturers. ⁶ The sequencing problem also widely exists in manufacturing system. Zhao et al. ⁷ proposed a sequence generation approach that is based on an integrated assembly model to solve assembly sequence planning problems for large-scale assembly. Ab Rashid et al. ⁸ developed of a tuneable test problem generator for assembly sequence planning and assembly line balancing. Wilson ⁹ described the philosophy behind the construction of a computer technique that has been used to formulate and solve a set of sequencing problems for efficient use of flexible manufacturing system (FMS).

The approaches that have been proposed for solving CSP can be classified into two types: exact approaches and approximation algorithms. Exact approaches include constraint programming (CP), ¹⁰ integer programming, ¹¹ branch and bound algorithm ⁵ and so on. Approximation algorithms contain greedy approaches, ¹² local search (LS) approaches, ¹³ ant colony optimization (ACO)^14,15 and so on. Recently, considerable work has been reported in the field of heuristic approaches to this problem. Cordeau et al. ¹⁶ introduced an iterated tabu search (TS) heuristic for the daily CSP. The iterated TS heuristic combines classical TS with perturbation operators that help escape from local optimal. Estellon et al. ¹³ described two LS approaches for this problem. One approach was based on an original integer linear programming and another one was based on very fast explorations of small neighborhoods. Ribeiro et al. ¹⁷ proposed a set of heuristics for approximately solving multi-objective real-life CSP, based on the paradigms of the variable neighborhood search (VNS) and iterated local search (ILS) metaheuristics, to which further intensification and diversification strategies have been added. Morin et al. ¹⁵ studied the learning process in an ACO algorithm designed to solve the problem of ordering cars on an assembly line. Solnon et al. ¹⁸ made a synthesis of the methods proposed by the candidate teams in the Challenge ROADEF’2005; only two teams used exact approaches at the qualification stage and one team used CP integrated with large neighborhood search (LNS) among the finalist teams; the other methods proposed are heuristic approaches including greedy heuristic (GH), simulated annealing (SA), TS, VNS, LNS, LS, ILS, genetic algorithm (GA) and ACO.

The existing literatures of CSP commonly find the optimal car sequence to minimize the number of color changes in the paint shop and the violations of constraints in the assembly line. However, the industrial sector in China accounted for a significant proportion of its total energy consumption, and the energy consumption in the CSP was often neglected. In practice, a set of cars that need to be sequenced may have different optimal sequences with the same number of color changes and weighted violations, and the energy consumption for these optimal sequences is different. In this article, the mathematical model of the car sequencing problem with energy consumption (CSP-EC) is proposed, and the objective to minimize the energy consumption of the production process is integrated with the traditional CSP. A novel artificial ecological niche optimization (AENO) algorithm, which imitates natural ecosystem, is presented to solve this problem.

The remainder of this article is organized as follows: in section “Problem formulation,” definition of CSP-EC is presented. The ring sorting buffer is used to assist us to study the energy consumption in sorting process. In section “AENO algorithm,” the AENO algorithm was proposed. The basic principle and the detail process of the algorithm are presented. In section “Computation results,” the computational experiments are presented, and the test data of CSP are provided by Renault. Conclusions and future research are given in section “Conclusion.”

Problem formulation

The traditional CSP is proposed by Renault for ROADEF Challenge in 2005. ¹ In the paint shop, it is to minimize the consumption of paint solvent. The paint solvent is used to wash spray guns each time when the paint color is changed between two consecutive scheduled vehicles. Therefore, there is a requirement to group vehicles together by paint color that is to reduce the number of paint color changes (PCC) in the sequence of scheduled vehicles. In order to smooth the workload on the assembly line, vehicles that require special assembly operations have to be evenly distributed throughout the total processed cars. These vehicles are considered to be “hard to assemble.” This requirement is modeled by a ratio constraint N/P. Ratio constraints are associated with car characteristics, which require extra operations on the assembly line (for instance, sunroof and air conditioning). A ratio constraint N/P means that at most N cars in each consecutive sequence of P are associated with the constraint. For instance, if N/P = 3/5, there must not be more than three constrained cars on any consecutive sequence of five cars. There are two classes of ratio constraints, high-priority level constraints and low-priority level constraints. High-priority level ratio constraints are due to car characteristics that require a heavy workload on the assembly line. Low-priority level ratio constraints result from car characteristics that cause small inconvenience to production. High-priority level ratio constraints must be satisfied preferentially to low-priority level constraints.

To summarize, this multi-objective CSP consists of scheduling the production of a set of cars to minimize three different objectives: (a) the number of PCC, (b) the number of violations of high-priority ratio constraints (HPRC) and (c) the number of violations of low-priority ratio constraints (LPRC). These objectives usually conflict. However, they can be considered with different priority levels varying from one factory to another or at different times in the same factory. Renault tackled the problem using a weighted sum method that groups the three objectives into a single-objective function, by assigning different weights to each objective, according to their priority levels. Three problem classes with different objective functions are considered with weights $W_1>>W_2>>W_3$ :

• Class 1. Objective function 1 = W₁· number of PCC +W₂· number of violations of HPRC +W₃· number of violations of LPRC;

• Class 2. Objective function 2 = W₁· number of violations of HPRC +W₂· number of PCC +W₃· number of violations of LPRC;

• Class 3. Objective function 3 = W₁· number of violations of HPRC +W₂· number of violations of LPRC +W₃· number of PCC.

In this article, instances in the test set X were taken in AENO algorithm performance test. The traditional CSP can be formulated as follows

$$\arg min\mathrm{OP}(I)=(W_1\times C+W_2\times H+W_3\times L)$$

(1)

$$I={[\begin{array}{cccc}{I}^1& I^2& \cdots & I^n\end{array}]}^T$$

(2)

$$Z={[\begin{array}{cccc}\hfill Z_1\hfill & \hfill Z_2\hfill & \hfill \cdots \hfill & \hfill Z_i\hfill \end{array}]}^T$$

(3)

$$P=\left[\begin{array}{cccc}\hfill P_{R_1}^{{\mathrm{PL}}_1}\times K\hfill & \hfill P_{R_2}^{{\mathrm{PL}}_2}\times K\hfill & \hfill \cdots \hfill & \hfill P_{R_{\mathrm{j}}}^{{\mathrm{PL}}_{\mathrm{j}}}\times K\hfill \end{array}\right]$$

(4)

$$\mathrm{PL}=\{\begin{array}{cc}\hfill 1\hfill & \hfill \mathrm{HPRC}\hfill \\ \multicolumn{1}{c}{0}& \hfill \mathrm{LPRC}\hfill \end{array}$$

(5)

$$K=\{\begin{array}{cc}\hfill 0\hfill & \hfill \mathrm{the}\mathrm{car}\mathrm{has}\mathrm{the}\mathrm{option}{P}_i\hfill \\ \multicolumn{1}{c}{1}& \hfill \mathrm{the}\mathrm{car}\mathrm{does}\mathrm{not}\mathrm{have}\mathrm{the}\mathrm{option}{P}_i\hfill \end{array}$$

(6)

where $C$ is the number of PCC, $H$ is the number of violations of HPRC, $I$ is the set of car sequence, $K$ is the car whether has this option or not, $L$ is the number of violations of LPRC, $P$ is the set of options for car, $\mathrm{PL}$ is the priority level, $R$ is the ratio constraint $N/P$ , $Z$ is the set of car’s colors and $W_1-W_3$ are the weights of objectives.

The input car sequence contains n cars with $i$ kinds of different colors. Each car has $j$ kinds of options with different ratio constraint $R$ and priority level $\mathrm{PL}$ . The state matrix of the input car sequence can be formulated as equation (7)

$$I=\left[\begin{array}{c}\hfill I^1\hfill \\ \multicolumn{1}{c}{I^2}\\ \multicolumn{1}{c}{⋮}\\ \multicolumn{1}{c}{I^n}\end{array}\right]=\left|\begin{array}{ccc}\hfill I_{(Z_1,P_{R_1}^{P{L}_1}\times K)}^1\hfill & \hfill \cdots \hfill & \hfill I_{(Z_1,P_{R_j}^{P{L}_j}\times K)}^1\hfill \\ \multicolumn{1}{c}{⋮}& \hfill \ddots \hfill & \hfill ⋮\hfill \\ \multicolumn{1}{c}{I_{(Z_i,P_{R_1}^{P{L}_1}\times K)}^n}& \hfill \cdots \hfill & \hfill I_{(Z_i,P_{R_j}^{P{L}_j}\times K)}^n\hfill \end{array}\right|$$

(7)

A set of cars is taken as an example to demonstrate the computation of the violations as follows. The car sequence has seven cars with three options and three colors. The priority and ratio constraint of each option are shown in Table 1.

Table 1.

Example of a CSP.

Position	Color	Option (priority level, ratio constraint (N/P))
		1 (HPRC, 2/3)	2 (HPRC, 1/3)	3 (HPRC, 1/4)
1	1	1	1	0
2	1	1	1	0
3	2	0	1	0
4	2	0	0	1
5	1	1	1	0
6	2	1	0	0
7	3	0	0	0

HPRC: high-priority ratio constraints.

The state matrix of this car sequence can be formulated as equation (8) corresponding to equation (7)

$$I={\left|\begin{array}{c}\hfill \begin{array}{cccc}\hfill \begin{array}{cccc}\hfill I_{(1,P_{2/3}^1\times 1)}^1\hfill & \hfill I_{(1,P_{2/3}^1\times 1)}^2\hfill & \hfill I_{(2,P_{2/3}^1\times 0)}^3\hfill & \hfill I_{(2,P_{2/3}^1\times 0)}^4\hfill \end{array}\hfill & \hfill I_{(1,P_{2/3}^1\times 1)}^5\hfill & \hfill I_{(2,P_{2/3}^1\times 1)}^6\hfill & \hfill I_{(3,P_{2/3}^1\times 0)}^7\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\begin{array}{cccc}\hfill \begin{array}{cccc}\hfill I_{(1,P_{1/3}^1\times 1)}^1\hfill & \hfill I_{(1,P_{1/3}^1\times 1)}^2\hfill & \hfill I_{(2,P_{1/3}^1\times 1)}^3\hfill & \hfill I_{(2,P_{1/3}^1\times 0)}^4\hfill \end{array}\hfill & \hfill I_{(1,P_{1/3}^1\times 1)}^5\hfill & \hfill I_{(2,P_{1/3}^1\times 0)}^6\hfill & \hfill I_{(3,P_{1/3}^1\times 0)}^7\hfill \end{array}}\\ \multicolumn{1}{c}{\begin{array}{cccc}\hfill \begin{array}{cccc}\hfill I_{(1,P_{1/4}^0\times 1)}^1\hfill & \hfill I_{(1,P_{1/4}^0\times 0)}^2\hfill & \hfill I_{(2,P_{1/4}^0\times 0)}^3\hfill & \hfill I_{(2,P_{1/4}^0\times 0)}^4\hfill \end{array}\hfill & \hfill I_{(1,P_{1/4}^0\times 0)}^5\hfill & \hfill I_{(2,P_{1/4}^0\times 0)}^6\hfill & \hfill I_{(3,P_{1/4}^0\times 0)}^7\hfill \end{array}}\end{array}\right|}^T$$

(8)

In this sequence, option 1 has no conflict. The ratio constraint of this option is 2/3, there are no cases of more than two cars that have the same option in any subsequence of three cars, and option 3 has no conflict as the same reason. However, option 2 has three conflicts, in positions 1–3, positions 2–4 and positions 3–5. Details on the computation of the violations’ number of ratio constraints in each conflict can be described as follows ¹

$$V=T-N$$

(9)

where $N$ is the ratio constraint numerator, $V$ is the number of violations and $T$ is the number of cars associated with the ratio constraint on the sequence.

For option 2, there are two violations in the first conflict and four violations in all. It implies that rolling sequences (on which the violations’ number of ratio constraints is computed) must begin on production day D-1. For a ratio constraint N/P, the first rolling sequence contains the P-1 ultimately scheduled vehicles of production day D-1 and the first scheduled vehicle of production day D. The vehicles of production day D-1 are already scheduled, so their positions cannot be changed. ¹

In this article, the ring sorting buffer is applied in order to study the energy consumption in sorting process. The structure of the ring sorting buffer is shown in Figure 1. In Figure 1, ST is the straight track of the ring sorting buffer, CT is the circular track of the ring sorting buffer, G₀ is the entrance of the ring sorting buffer, G₁ is the exit of CT, G₂ is the entrance of CT and G₃ is the exit of the ring sorting buffer. In the ring sorting buffer, G₃ can go through all the cars that it can schedule the cars exactly as the requirement if the capacity of the buffer is enough. The energy consumption of the sorting proceeding can be formulated as follows

$$E=(W_0+\sum _{i=0}^t{w}_i)\times T$$

(10)

where w_i is the additional power consumption of the car i in the sorting process, T is the operating time of the sorting buffer and W₀ is the unloaded power consumption of sorting buffer.

Figure 1.

Ring sorting buffer.

The cars that need to be scheduled can circulate along the track in the ring sorting buffer until they get the right place in the sequence and exit from the outlet G₃. The rest of cars in the sequence, which do not need to be scheduled can enter the ring sorting buffer from the inlet G₀, go through the track ST and then exit from the outlet G₃ directly. $\sum _{i=0}^t{w}_i$ is a dynamic parameter because the number of cars t in the ring sorting buffer, which constantly change. It is hard to get the value of $W_0+\sum _{i=0}^t{w}_i$ exactly. In order to solve this problem, another approximate model was proposed to calculate the energy consumption

$$E=W_{0}T+\sum _{i=0}^n{w}_i\times (C_i^{a_i}\times \frac{{\mathrm{L}}_{\mathrm{cir}}}{v}+\frac{{\mathrm{L}}_{\mathrm{str}}}{v})$$

(11)

where $a_i$ is the serial number of car $I^i$ , n is the number of cars, v is the traveling speed of the track, $w_i$ is the additional power consumption of the car $I^i$ go through the circle, ${C_i}^{a_i}$ is the number of the car $I^i$ go through the circle, ${\mathrm{L}}_{\mathrm{cir}}$ is the length of the track CT and ST, ${\mathrm{L}}_{\mathrm{str}}$ is the length of the track ST and $W_{0}T$ is the total energy consumption of unload condition.

Parameters $W_{0}T$ , $w_i$ , ${\mathrm{L}}_{\mathrm{cir}}$ , ${\mathrm{L}}_{\mathrm{str}}$ , v and n are assumed constant. Equation (11) can be formulated as equation (12)

$$E=W_{0}T+n\times w\times \frac{{\mathrm{L}}_{str}}{v}+{\displaystyle \sum _{i=0}^{n}w\times C_i^{a_i}\times \frac{{\mathrm{L}}_{cir}}{v}}$$

(12)

In equation (12), ${C_i}^{a_i}$ is the key parameter of reducing energy consumption. The set of car $I$ is taken as an example to study ${C_i}^{a_i}$ in sorting process

$$I=\left[\begin{array}{ccccccc}{I}^{b_1}& I^{b_2}& I^{b_3}& I^{b_4}& I^{b_5}& I^{b_6}& I^{b_7}\end{array}\right]$$

(13)

The $a=[\begin{array}{cccc}{b}_1& b_2& \cdots & b_7\end{array}]$ is a set of serial numbers of the cars and $b_1<b_2<\cdots <b_7$ . $I\prime$ is the target sequence of the cars

$$I\prime =[I^{b_5}{I}^{b_3}{I}^{b_2}{I}^{b_7}{I}^{b_6}{I}^{b_4}{I}^{b_1}]$$

(14)

First, $I^{b_1}{I}^{b_2}{I}^{b_3}{I}^{b_4}{I}^{b_5}$ go through G₀, $I^{b_1}{I}^{b_2}{I}^{b_3}{I}^{b_4}$ enter track CT, $I^{b_5}$ go through G₃, G₃ can get the sequence $I^{b_5}$ ; then $I^{b_1}{I}^{b_2}{I}^{b_3}$ which are already in the CT go through G₁, $I^{b_3}$ go through G₃, $I^{b_1}{I}^{b_2}$ enter CT again, G₃ can get the sequence $I^{b_5}{I}^{b_3}$ , the car sequence in the CT is $I^{b_4}{I}^{b_1}{I}^{b_2}$ ; and then $I^{b_4}{I}^{b_1}{I}^{b_2}$ go through G₁, $I^{b_2}$ go through G₃ directly, $I^{b_4}{I}^{b_1}$ entrance CT again, G₃ can get the car sequence $I^{b_5}{I}^{b_3}{I}^{b_2}$ ; And then $I^{b_6}{I}^{b_7}$ go through G₀, $I^{b_7}$ go through G₃ directly, $I^{b_6}$ entrance CT, G₃ can get the sequence $I^{b_5}{I}^{b_3}{I}^{b_2}{I}^{b_7}$ ; And then $I^{b_4}{I}^{b_1}{I}^{b_6}$ which in the CT go through G₁ and entrance $\mathrm{ST}$ , $I^{b_6}$ go through G₃ directly, $I^{b_4}{I}^{b_1}$ entrance CT again, G₃ can get the sequence $I^{b_5}{I}^{b_3}{I}^{b_2}{I}^{b_7}{I}^{b_6}$ , the car sequence in CT update as $I^{b_4}{I}^{b_1}$ . At last, $I^{b_4}{I}^{b_1}$ go through G₁ and G₃, and then G₃ can get the target sequence $I^{b_5}{I}^{b_3}{I}^{b_2}{I}^{b_7}{I}^{b_6}{I}^{b_4}{I}^{b_1}$ . From above, the number of each car run through the track can show as follows.

$${C_i}^{\prime }=[4213010]$$

(15)

The car has to be sorted by ring sorting buffer when the serial number of it in the CT appears reverse order in the car sequence, so the computation of ${C_i}^{a_i}$ can be formulated as follows in case we ignore the capacity of ring sorting buffer

$$C_i^{a_i}=\{\begin{array}{c}\hfill \sum _{j=\epsilon }^i{D}_j^{a_j}\mathrm{s}.\mathrm{t}\epsilon \le i,\forall (a_1,\dots ,a_{\epsilon -1})<a_i<a_{\epsilon }\hfill \\ \multicolumn{1}{c}{0\mathrm{s}.\mathrm{t}i>j,\forall (a_1,\dots ,a_{i-1})<a_i}\end{array}$$

(16)

$$\mathrm{J}=[j_1{j}_2\cdots j_{\omega }]\mathrm{s}.\mathrm{t}i>\forall j\ge \epsilon ,\forall a_j<a_{\epsilon },j_1<j_2<\cdots j_{\omega }$$

(17)

$$D_{J\tau }^{a_{J_{\tau }}}=\{\begin{array}{c}\hfill 0\hfill \\ \multicolumn{1}{c}{1}\end{array}\begin{array}{c}\hfill \mathrm{s}.\mathrm{t}{a}_{J_{\tau }}>a_{J_{\tau -1}}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}{a}_{J\tau }<a_{J_{\tau -1}}}\end{array}$$

(18)

where $i$ and $j$ are the position of cars in the car sequence; $a_i$ and $a_j$ are the serial number of cars which in the positions $i$ and $j$ . According to equations (16)–(18), the number of each car run through the track CT during the sorting process can be calculated as

$$C_1^{b_5}=\sum _{j=0}^1{D}_j^{a_j}=D_1^{b_5}=0$$

(19)

$$C_2^{b_3}=\sum _{j=1}^2{D}_j^{a_j}=D_1^{b_5}+D_2^{b_3}=1$$

(20)

$$C_3^{b_2}=\sum _{j=1}^3{D}_j^{a_j}=D_1^{b_5}+D_2^{b_3}+D_3^{b_2}=1+1=2$$

(21)

$$C_4^{b_7}=0$$

(22)

$$C_5^{b_6}=\sum _{j=4}^5{D}_j^{a_j}=D_4^{b_7}+D_5^{b_6}=1$$

(23)

$$\begin{array}{cc}\multicolumn{1}{c}{C_6^{b_4}=}& \sum _{j=1}^6{D}_j^{a_j}=D_1^{b_5}+D_2^{b_3}+D_3^{b_2}\hfill \\ +D_4^{b_7}+D_5^{b_6}+D_6^{b_4}=1+1+1=3\hfill \end{array}$$

(24)

$$\begin{array}{l}{C}_7^{b_1}={\displaystyle \sum _{j=1}^7{D}_j^{a_j}}=D_1^{b_5}+D_2^{b_3}+D_3^{b_2}+D_4^{b_7}\\ +D_5^{b_6}+D_6^{b_4}+D_7^{b_1}=1+1+1+1=4\end{array}$$

(25)

With sorting the $C_i^{a_i}$ by the serial number $b_1,b_2,\dots ,b_7$ , ${C_i}^{\prime }=[4213010]$ which is consistent with the result of actual sorting process is obtained. CSP is an NP-hard problem. $I\prime$ is not the only optimal sequence for $I$ ; If $I^{b_1}$ has the same options with $I^{b_5}$ , $I$ can also be sequenced as $I\prime \prime$

$$I\prime \prime =[I^{b_1}{I}^{b_3}{I}^{b_2}{I}^{b_7}{I}^{b_4}{I}^{b_6}{I}^{b_5}]$$

(26)

The number $C\prime \prime$ of each car run through the track CT is different, which can be shown as equation (27) as the same reason

$$C\prime {\prime }_i\mathrm{=}[\begin{array}{ccccccc}0& 0& 1& 0& 1& 1& 2\end{array}]$$

(27)

It can be seen above that the energy consumption is closely related to the order of the target sequence. With the same value of objective function (equation (1)), there may be different optimal sequences with different energy consumptions. The order of the target sequence requires more attention. Therefore, energy consumption and traditional CSP are integrated into a multi-objective optimization problem. The multi-objective function can be formulated as follows

$$\begin{array}{c}\arg minF(I)=\alpha (W_1\times C+W_2\times H+W_3\times L)\hfill \\ +\beta (W_{0}T+n\times w\times \frac{L_{\mathrm{str}}}{v}+\sum _{i=1}^{n}w\times C_i^{a_i}\times \frac{L_{\mathrm{cir}}}{v})\hfill \end{array}$$

(28)

where $\alpha$ and $\beta$ are weight coefficients. Traditional CSP is taken as the first optimization objective and energy consumption optimization is taken as the second optimization objective; therefore, $\alpha >>\beta$ in equation (28).

AENO algorithm

In this section, an AENO algorithm for the CSP-EC is proposed. The main idea of AENO algorithm is imitation of competition and migration process in nature. The car sequence is simulated as an ecosystem, each car is simulated as a population, cars with the same color have the same habitat and the options of cars are simulated as ecological factors. If the car has this option, it means that the population has this ecological factor, the value of the ecological factor of this population in the state matrix is considered 1 and otherwise, it is considered 0. The ratio constraint of options is simulated as the range of foraging. For example, if the ratio constraint of the option is 1/3, it means that in this ecological factor, the total resource in radius of three positions can accommodate only one predator or the niche overlap will happen. Competitive exclusion happens between the populations when niche overlaps appear and then the populations emigrate to somewhere for the abundant resource. This process is shown in Figure 2. The algorithm consists of two stages, the first stage is optimization of habitat distribution including habitat concentration and artificial migration of habitat, the second stage is optimization of population distribution in habitat including initialize the population of habitat, territorial differentiation and priority optimization of ecological factors. During the first stage, populations with the same habitat get together in the process of habitat concentration, and then artificial migration of habitat optimizes the distribution of these habitats. The purpose of the first stage is to optimize resource distribution in global. During the second stage, the population of the habitat is initialized, and territorial differentiation and priority optimization of ecological factors are applied to redistribute populations in each habitat. The purpose of the second stage is to optimize resource distribution in the local. Energy consumption in sorting process of car sequences is simulated as the energy consumption during the migration of populations. In nature, the number of populations and the distance of their migration are related to energy consumption during the migration. It is seen that less number of scheduling cars and a shorter distance of the scheduling during the sorting process can reduce the value of parameter ${\displaystyle \sum _{i=1}^n{C}_i^{a_i}}$ , which leads to less energy consumption.

Figure 2.

Flowchart of AENO algorithm.

Optimization of habitat distribution

During the habitat concentration, all the populations that have the same habitat gather together and then the resource needs will be calculated in each ecological factor for every habitat in equation (29)

$$Q=\sum _{P_s}^{P_e}{K}_i\times \left(\frac{P-N}{N}\right)$$

(29)

where $N$ is the maximum predator number in $P$ , $P$ is the range of foraging and $Q$ is the resource needs of the habitat start at $P_s$ and end at $P_e$ .

If $Q$ in adjacent habitat are both positive numbers, there is a conflict, and then the ecosystem needs to be reconstructed with migrating the habitat to decrease the resource conflicts. All $Q$ can consist as a $Z\times P$ matrix as follows

$$Q_{\mathrm{matrix}}=\left|\begin{array}{ccc}\hfill Q_{Z_1}^{P_1}\hfill & \hfill \cdots \hfill & \hfill Q_{Z_1}^{P_j}\hfill \\ \multicolumn{1}{c}{⋮}& \hfill \ddots \hfill & \hfill ⋮\hfill \\ \multicolumn{1}{c}{Q_{Z_i}^{P_1}}& \hfill \cdots \hfill & \hfill Q_{Z_i}^{P_j}\hfill \end{array}\right|$$

(30)

The following procedure was proposed in order to make the distribution of resource more reasonable. Figure 3 shows the steps of a summary presentation of optimization between habitats. The Proc1 in Figure 3 adjusts the distribution of resources through row operation of $Q_{\mathrm{matrix}}$ in order to reduce the conflict in each ecological factor between the habitats.

Figure 3.

Procedure of optimization between habitats.

Optimization of population distribution in habitat

The distribution of population can be formulated in equation (7). In each habitat, there are more abundant nonliving resources in front of it. The populations in the back area will migrate to the front area for the abundant nonliving resources if the immigrate does not cause ecological niche overlap. When niche overlaps appear between populations in some ecological factors, competition and exclusions will happen. The populations will migrate to somewhere with more abundant resource in the habitat. Figure 4 shows the steps of a summary presentation of optimization in habitat. In Figure 4, $P$ is the number of ecological factors, $Q$ is the state matrix of all population like equation (8), $N_{\mathrm{Index}}$ and $P_{\mathrm{Index}}$ are the maximum predator number and the range of foraging in ecological factor index. If the predator number is more than $N_{\mathrm{Index}}$ in $P_{\mathrm{Index}}$ like line 7 in Figure 4, there is a conflict, and then the population will migrate to somewhere with more resource. On the other hand, if the predator number is less than $N_{\mathrm{Index}}$ in $P_{\mathrm{Index}}$ like line 36 in Figure 4, the predator behind position $b$ will immigrate for more abundant nonliving resources. The migration patterns are shown in Figure 5, including immigration, emigration and exchange; $Q_{Z_i}$ in Figure 5 is the population $b$ in Figure 4. When the optimization of population distribution is completed, the number of niche overlaps in the current ecosystem was calculated as equations (31)–(34). The original population distribution will be replaced by the current population distribution if the number of niche overlaps is reduced

$${\varphi }^{\mu }=[\begin{array}{cccc}\hfill {\varphi }_1^{\mu }\hfill & \hfill {\varphi }_2^{\mu }\hfill & \hfill \dots \hfill & \hfill {\varphi }_{\sigma }^{\mu }\hfill \end{array}]$$

(31)

$${\gamma }_{(N^{\mu },P^{\mu })}^{{\varphi }_i^{\mu }}=\{\begin{array}{c}\hfill 0\hfill \\ \multicolumn{1}{c}{1}\end{array}\begin{array}{c}\hfill {\varphi }_i^{\mu }-{\varphi }_{i-N^{\mu }}^{\mu }\ge P^{\mu }\hfill \\ \multicolumn{1}{c}{{\varphi }_i^{\mu }-{\varphi }_{i-N^{\mu }}^{\mu }<P^{\mu }}\end{array}$$

(32)

$${\theta }_{\mu }=\sum _{i=1}^{\sigma }{\gamma }_{(N^{\mu },P^{\mu })}^{{\varphi }_i}\times V_i^{\mu }$$

(33)

$${\theta }_{total}={\displaystyle \sum _{\mu =1}^P{\displaystyle \sum _{i=1}^{\sigma }{\gamma }_{(N^{\mu },P^{\mu })}^{{\varphi }_i}}}$$

(34)

where $N^{\mu }$ is the maximum predator number in $P^{\mu }$ , $P^{\mu }$ is the range of foraging area, $V_i^{\mu }$ is the number of violations in conflict ${\gamma }_{(N^{\mu },P^{\mu })}^{{\varphi }_i^{\mu }}$ corroding to equation (9), ${\gamma }_{(N^{\mu },P^{\mu })}^{{\varphi }_i^{\mu }}$ is the conflict between the predators in the ecological factor $\mu$ , ${\theta }_{\mathrm{total}}$ is the total number of niche overlap in the current ecosystem, ${\theta }_{\mu }$ is the number of niche overlap in the ecological factor $\mu$ , $\mu$ is the ecological factor and ${\varphi }^{\mu }$ is the position of predators in ecological factor $\mu$ .

Figure 4.

Optimization of population distribution in habitat.

Figure 5.

Migration patterns of population: (a) immigration, (b) emigration and (c) exchange.

When the conflicts appear, the number of niche overlaps in each conflict is calculated according to equation (9). Then the optimal value $\theta {\prime }_{\mu }$ in theory is calculated. If the total number of niche overlaps in the current ecosystem is bigger than the optimal value, ${\theta }_{\mu }$ is compared with $\theta {\prime }_{\mu }$ in each ecological factor. The priority of the ecological factor $\mu$ will be improved if ${\theta }_{\mu }$ is bigger than $\theta {\prime }_{\mu }$ in this ecological factor. In the next turn of optimization, the ecological factor $\mu$ is moved to the first column of the state matrix, which is shown in Figure 6(a), then repeat Proc2 in Figure 4. If ${\theta }_{\mathrm{total}}$ in this turn of optimization is less than before and the number of niche overlaps in HPRC is not increased, the original population distribution will be replaced by the current population distribution. If ${\theta }_{\psi }$ is increased, the ecological factor $\mu$ will move to the position behind the ecological factor $\psi$ , as shown in Figure 6(b) and then repeat Proc2 in Figure 4. The optimization terminates until ${\theta }_{\mathrm{total}}$ equals to ${\theta }_{\mathrm{opt}}$ or all the ecological factors in which ${\theta }_{\mu }$ are bigger than $\theta {\prime }_{\mu }$ repeat priority optimization for 10 times. Figure 7 shows the steps of a summary presentation of optimization in ecological factors. $\mathrm{Column}\_T$ is the set of all the ecological factors in which ${\theta }_{\mu }$ is bigger than $\theta {\prime }_{\mu }$ , and $A\_\mathrm{pre}$ is the distribution of all the population’s ecological factor before ecological factor optimization. $A$ is the distribution of all the population’s ecological factor in ecological factor optimization.

Figure 6.

Priority improvement of the ecological factor $\mu$ .

Figure 7.

Optimization of ecological factors.

Energy consumption optimization

The basic idea of AENO without considering the energy consumption in the sorting process of ring sorting buffer is given above. In the nature, during the migration, the energy consumption is related to the population quantity of migration and their migration distance. It is very similar to the energy consumption in the sorting process of the ring sorting buffer according to equation (12). The program is optimized to reduce the energy consumption as follows:

• The optimization of Proc1 in Figure 3 is shown in Figure 8. Line Insert1 sort E by the distance from D (i) can reduce the migration distance in the optimization process.

• The optimization of Proc2 in Figure 4 is shown in Figure 9, ${\theta }_{\mu }^h$ is the number of niche overlaps in habitat $h$ and ${\theta }_{\mu }^{h\prime }$ is the optimal value in theory of ${\theta }_{\mu }^h$ . Line Insert1–Insert6 can effectively reduce the number of scheduling car, and line Insert7–Insert11 can effectively reduce the scheduling distance from their original position. The effect of this optimization is verified in the next section.

Figure 8.

Program optimization of Proc1.

Figure 9.

Program optimization of Proc2.

Computation results

In order to evaluate the performance of AENO algorithm, this algorithm was tested on instances of test set X provided by Renault. These instances are available from the challenge Web site. ¹ There are three different objective instances in the test set X. The objective of the 2005 ROADEF Challenge is to minimize the violations in the production process, ignoring the order of the cars in optimal sequence, which may lead to more energy consumption. In this article, instances of Class 1, which are combined with energy consumption in ring sorting process, are taken to test the AENO algorithm.

The algorithm proposed in this article was coded in MATLAB R2010b, and all experiments were implemented on a computer with Intel Core 2 CPU at 2.4 GHz and 2 G memory. The computational results and comparisons obtained from ROADEF’2005 are shown in Tables 1–3.

Table 2.

TEST 022_RAF_EP_ENP_S49_J2.

Algorithm	Candidate	Results			Mark
		PCC	HPRC	LPRC
LS	Gavranovic	12.00	2.00	3.00	12002003.00
SA	Kuipers	12.00	2.00	3.00	12002003.00
VNS + SA	Stuetzle	12.00	2.00	3.00	12002003.00
GA	Jaszkiewicz	12.00	2.00	3.00	12002003.00
LS	Pawlak	12.00	2.00	3.00	12002003.00
LS	Nouioua-Gardi	12.00	2.00	3.00	12002003.00
VNS + ILS	Celso	12.00	2.00	3.00	12002003.00
SA	Naddef	12.00	2.00	3.00	12002003.00
TS + ILS	Cordeau	12.00	2.00	3.00	12002003.00
LS	Benoist	12.00	2.00	3.00	12002003.00
LS	Bonizzoni	12.00	2.00	3.20	12002003.20
SA	Bloemen	12.00	2.00	3.40	12002003.40
ACO + LS + TS/VNS	Gravel	12.00	2.00	5.00	12002005.00
TS	Gendreau	12.00	2.00	8.00	12002008.00
SA	Montemanni	12.00	2.00	32.80	12002032.80
CP + LNS	Caseau	12.00	2.00	304.00	12002304.00
TS	Zufferey	12.00	2.00	419.00	12002419.00
TS	Klau	12.20	2.00	4.40	12202004.40
AENO	Author	12.00	2.00	3.00	12002003.00

PCC: paint color changes; HPRC: high-priority ratio constraints; LPRC: low-priority ratio constraints; LS: local search; SA: simulated annealing; VNS: variable neighborhood search; GA: genetic algorithm; ILS: iterated local search; TS: tabu search; ACO: ant colony optimization; CP: constraint programming; LNS: large neighborhood search; AENO: artificial ecological niche optimization.

Table 3.

TEST 035_CH1_RAF_EP_S50_J4.

Algorithm	Candidate	Results			Mark
		PCC	HPRC	LPRC
TS	Zufferey	10.00	0.00	5.00	5010000.00
LS	Benoist	10.00	0.00	5.00	5010000.00
SA	Bloemen	10.00	0.00	5.00	5010000.00
CP + LNS	Caseau	10.00	0.00	5.00	5010000.00
VNS + ILS	Celso	10.00	0.00	5.00	5010000.00
TS + ILS	Cordeau	10.00	0.00	5.00	5010000.00
TS	Gendreau	10.00	0.00	5.00	5010000.00
ACO + LS + TS/VNS	Gravel	10.00	0.00	5.00	5010000.00
SA	Kuipers	10.00	0.00	5.00	5010000.00
SA	Naddef	10.00	0.00	5.00	5010000.00
LS	Nouioua-Gardi	10.00	0.00	5.00	5010000.00
LS	Pawlak	10.00	0.00	5.00	5010000.00
LS	Bonizzoni	11.00	0.00	5.00	5011000.00
VNS + SA	Stuetzle	26.80	0.00	5.00	5026800.00
SA	Montemanni	10.00	0.00	6.00	6010000.00
TS	Klau	–	–	–	no generated
LS	Gavranovic	–	–	–	no generated
GA	Jaszkiewicz	–	–	–	no generated
AENO	Author	10.00	0.00	5.00	5010000.00

PCC: paint color changes; HPRC: high-priority ratio constraints; LPRC: low-priority ratio constraints; TS: tabu search; LS: local search; SA: simulated annealing; CP: constraint programming; LNS: large neighborhood search; VNS: variable neighborhood search; ILS: iterated local search; ACO: ant colony optimization; GA: genetic algorithm; AENO: artificial ecological niche optimization.

In Table 2, there are 11 candidates with the best result with six different algorithms; in Table 3, there are 13 candidates with the best result with seven different algorithms; in Table 4, there are 13 candidates with the best result with eight different algorithms. From Tables 2–4, only five kinds of algorithms are seen with the best result in all three instances, including SA, LS, VNS + ILS, TS + ILS and AENO. However, AENO is a heuristic algorithm in which computing time is fast. The average computing times of 10 times for these three instances, respectively, are 12.553, 0.703 and 0.360 s. Therefore, AENO is one of the effective algorithms for CSP. The ecological niche distributions of these three ecosystems, which have been optimized, are shown in Figures 10–12. The abscissa axes are the ecological factors and the vertical axes are the populations.

Table 4.

TEST 035_CH2_RAF_EP_S50_J4.

Rank	Candidate	Results			Mark
		PCC	HPRC	LPRC
SA	Bloemen	56.00	0.00	6.00	6056000.00
LS	Nouioua-Gardi	56.00	0.00	6.00	6056000.00
TS	Gendreau	56.00	0.00	6.00	6056000.00
SA	Kuipers	56.00	0.00	6.00	6056000.00
TS + ILS	Cordeau	56.00	0.00	6.00	6056000.00
TS	Zufferey	56.00	0.00	6.00	6056000.00
SA	Naddef	56.00	0.00	6.00	6056000.00
VNS + ILS	Celso	56.00	0.00	6.00	6056000.00
LS	Pawlak	56.00	0.00	6.00	6056000.00
LS	Benoist	56.00	0.00	6.00	6056000.00
ACO + LS + TS/VNS	Gravel	56.00	0.00	6.00	6056000.00
GA	Jaszkiewicz	56.00	0.00	6.00	6056000.00
CP + LNS	Caseau	57.00	0.00	6.00	6057000.00
LS	Bonizzoni	57.00	0.00	6.00	6057000.00
VNS + SA	Stuetzle	93.40	0.00	6.00	6093400.00
SA	Montemanni	56.00	0.00	7.00	7056000.00
TS	Klau	–	–	–	no generated
LS	Gavranovic	–	–	–	no generated
AENO	Author	56.00	0.00	6.00	6056000.00

PCC: paint color changes; HPRC: high-priority ratio constraints; LPRC: low-priority ratio constraints; SA: simulated annealing; LS: local search; TS: tabu search; ILS: iterated local search; VNS: variable neighborhood search; ACO: ant colony optimization; GA: genetic algorithm; CP: constraint programming; LNS: large neighborhood search; AENO: artificial ecological niche optimization.

Figure 10.

Ecological niche distribution of ecosystem TEST 022_RAF_EP_ENP_S49_J2.

Figure 11.

Ecological niche distribution of ecosystem TEST 035_CH1_RAF_EP_S50_J4.

Figure 12.

Ecological niche distribution of ecosystem TEST 035_CH2_RAF_EP_S50_J4.

In addition, for every experimental instance, the algorithm has been applied 10 times with and without energy consumption optimization. The optimal sequence is different due to the complexity of CSP. These optimal results have the same number of violations. It is used to help us study the energy consumption in the ring sorting buffer. According to equation (28), $\sum _{i=1}^n{\mathrm{wC}}_i^{a_i}\times (L_{\mathrm{cir}}/v)$ is closely related to additional energy consumption. The 10 times of computational results with or without considering the energy consumption of these optimization sequences are shown in Figures 13–15. The abscissa axis is the times of optimization and the vertical axis is the value of $\sum _{i=1}^n{\mathrm{wC}}_i^{a_i}\times (L_{\mathrm{cir}}/v)$ , and the energy consumption of each car running through the track CT is considered 1 kWh. From Figures 13–15, it can be seen that the energy consumption is significantly saved when considering the objective of the energy consumption. This is because, in Figures 8 and 9, the energy consumption optimization used in AENO reduces the scheduling distance of the scheduling objects, which reduces the $C_i^{a_i}$ in equation (16) by narrowing the scope of summarizing interval of $\sum _{j=\epsilon }^i{D}_j^{a_j}$ , and optimization in Figure 9 reduces the number of scheduling objects, which means some objects do not need to be scheduled anymore; this reduces the energy consumption directly and less scheduling objects make the computing speed faster. The additional energy consumption for each car can be shown in Figures 16–18. The abscissa axis is the car sequence of each test instance and the vertical axis is additional energy consumption of each car. From Figures 16–18, additional energy consumptions of cars are significantly reduced compared with the result without energy consumption optimization.

Figure 13.

Contrast of total additional energy consumption in TEST 022_RAF_EP_ENP_S49_J2.

Figure 14.

Contrast of total additional energy consumption in TEST 035_CH1_RAF_EP_S50_J4.

Figure 15.

Contrast of total additional energy consumption in TEST 035_CH2_RAF_EP_S50_J4.

Figure 16.

Additional energy consumption for each car in TEST 022_RAF_EP_ENP_S49_J2.

Figure 17.

Additional energy consumption for each car in TEST 035_CH1_RAF_EP_S50_J4.

Figure 18.

Additional energy consumption for each car in TEST 035_CH2_RAF_EP_S50_J4.

From the results above, AENO algorithm can effectively solve the CSP. When considering the population quantity of migration and their migration distance in AENO algorithm, the energy consumption will be saved effectively.

Conclusion

In this article, there are three main contributions to the CSP: the modeling of energy consumption in the sorting process, AENO algorithm and the quality of numerical results for CSP-EC. The model in this article combined the traditional CSP-EC. Ring sorting buffer is used in studying the energy consumption in the sorting process, and the model of energy consumption in the ring sorting buffer is proposed. The objective of the model is to find a car sequence with fewer color changes in paint shop, fewer violations in assembly shop and less energy consumption in the sorting process. A novel AENO algorithm is proposed for the CSP-EC, which imitates natural ecosystem. The aim of this heuristic algorithm is to reconstruct a harmonious natural ecosystem with less conflict between populations. The competitive exclusion principle of nature was combined with human intervention in the process of reconstruction. Human intervention is used to reconstruct the distribution of habitats, and competitive exclusion principle is the main principle in population migration. Energy consumption in migration is associated with population quantity and their migration distance. According to a real-life industrial problem, computational results show that AENO algorithm can perform well in traditional CSP, and it can get a better optimal sequence with less energy consumption in the sorting process.

There are still some issues not solved in this article. The AENO can be used only in the CSP instances of Class 1, which do not consider the limitation on the upper batch size in paint color batches. When considering the limitation of batch size, the habitat concentration in AENO will become more complex. Future works will be done to improve AENO algorithm to suit all kinds of CSP.