Non-dominated sorting genetic algorithm III with stochastic matrix-based population to solve multi-objective solid transportation problem

Abstract

The transportation problems, which consist of multiple objectives with heterogeneous conveyances, are the pragmatic representation of the transportation occurring in the real world. However, situations do exist where the solutions obtained by the classical optimization techniques do not reflect the acumen of the decision-maker. Against this backdrop, a systematic algorithm is proposed in this paper to generate an initial population to tackle the multi-objective solid transportation problem efficiently. In addition, the non-dominated sorting genetic algorithm (NSGA) III is carried out to acquire solutions that can demonstrate the varying degrees of objectives. Furthermore, two problems of different sizes are framed, and their performance is compared via NSGA II, hybrid genetic algorithm, and fuzzy programming technique.

1 Introduction

The ability to deal with complex optimization problems in limited time makes meta-heuristic algorithms (Lee and Geem 2005; Sang-To et al. 2022; Rao 2016; Kennedy and Eberhart 1995; Booker et al. 1989) as locus of attraction. Researchers are also modifying these algorithms according to the need of problem definition (Le Thanh et al. 2022; Das 2022; Huang and Hao 2009; Cuong-Le et al. 2021; Minh et al. 2021a, b; To et al. 2022). Evolutionary algorithms, a class of population-based meta-heuristic algorithms, in principle, mimic natural evolution in view to obtain and maintain multiple solutions in a single simulation run. Genetic algorithm(GA), which is a member of a family of evolutionary algorithms and centered on natural selection and natural genetics, is a precise and systematic optimization technique, therefore, effectively implemented for various sophisticated optimization problems. Following Darwin’s theory of “Survival of the fittest,” its development was commenced by John Holland in early 1960. This algorithm, in a nutshell, uses a set of the population in order to generate stochastic solutions and then mimic genetic operators to obtain the optimal solutions In the presence of multiple objectives, non-dominated solutions, loosely speaking, more than one optimal solutions typically exist. In this regard, Schaffer (1985) modified GA to unfold a multi-objective optimization problem. Since, at each generation, the population is segregated into several sub-populations according to objectives considered, each sub-population is assigned a fitness based on distinct goals; therefore, this algorithm is also named vector evaluated genetic algorithm. In addition, this algorithm tends to converge in a specific part of the Pareto-optimal front, which highlights the need for suitable modification in GA according to the problem of interest. Thereupon, several GA were introduced for multiple objective problems like weight-based genetic algorithm by Hajela et al. (1993), multi-objective GA of Fonseca and Fleming (1993), etc. A revolution came when in 1989, Goldberg (1989) recommended the use of the concept of domination in the multi-objective evolutionary algorithm. The first direct implementation of non-dominated sorting was done by Srinivas and Deb (1994) in his algorithm, NSGA. Through this algorithm, the non-dominated solutions were obtained by the non-dominated sorting (NDS) procedure, and the diversity between the solutions was maintained by the sharing function approach. Because of the need to specify user-defined parameters, lack of elitism, and high computational complexity, this algorithm comes out to be inefficient. Later, Deb et al. (2002) proposed its updated version, NSGA II, which is free from user-defined parameters and equipped with a remarkable diversity preserving operator. Moreover, Deb also modified the NDS approach and called it a fast non-dominated sorting approach. In literature, some exciting applications of NSGA II can be found, for instance, generation expansion planning (Kannan et al. 2008), spectrum sharing networks (Martínez-Vargas et al. 2016), fault diagnosis in power system (Wang et al. 2019), and feature selection for facial expression (Soyel et al. 2011). In view to ease the high computational complexities of crowded comparison operator in NSGA II, Deb and Jain (2013) came up with NSGA III, which is predominantly based on a reference point strategy in which decision maker tried to obtain a solution near the predefined reference points. NSGA III is successfully employed to solve economic and environmental dispatch problems by Bhesdadiya et al. (2016). Ji et al. (2021) figured out the applicable region of the MMC controller parameter for satisfying the stability constants by NSGA III.

Furthermore, GA and its derivative algorithms are utilized to address a variety of real-world optimization problems with multiple objectives. One of them is the transportation problem. In the current progressive world, an efficient transport system, especially in terms of cost and time, is the foundation of productive trade. Such systems channelize commodities from numerous origins (for example, warehouses, plants, factories, etc.) to their ultimate destinations (for example, retailers, customers, warehouses, etc.). In literature, the aforesaid systems have been scrutinized in great detail under the framework of the transportation problem (TP). In connection with the above discussion, it is important to point out that the distinctive feature of a conventional transportation problem is that sources have a fixed amount of capacity for transfer, while destinations need a specific volume at the same time that might differ from the source capacity. Owing to these concerns, the prime goal of the DM is to optimize transportation costs, subject to the study’s source and demand constraints. In this regard, Hitchcock (1941) was the first who studied its mathematical structure in 1941  and Dantzig (1963) proposed the solution procedure for the conventional transportation problem through lp concepts. Multi-dimensional objectives, on the other hand, instead of uni-dimensional objectives, became the need of the hour to take care of emerging transportation problems. As compared to uni-dimensional objectives, multi-dimensional objectives are substantially conflicting in nature, for instance, reducing transportation costs, further improving the product quality, enhancing the users’ readiness, and many more. The large-scale occurrence of the multi-objective scenarios in the real world has shifted the paradigm from the conventional TP to the multi-objective transportation problems.

Furthermore, in practice, it is often infeasible to maintain conveyance homogeneity for shipment; therefore, heterogeneous conveyances, particularly ships, cargo, trains, or any particular combination of these, etc., are exercised. As a result, an additional constraint is required in order to figure out the influence of heterogeneous conveyances. Shell (1955) first studied this specific framework, named the solid transportation problem (STP). Haley (1965, 1962) did a remarkable job in the field of multi-objective STP (MOSTP). He designed the solution procedure of MOSTP by extending the modified distribution method and laid down the necessary and sufficient conditions to obtain a feasible solution. Ever since many authors developed a considerable amount of utilitarian and efficient approaches to solve MOSTP, such as Bit et al. (1993) solved MOSTP by FPT, Giri et al. (2015) provided a few methods for calculating the total fuzzy transportation cost for a fully fuzzy fixed charge multi-item STP. Rani and Gulati (2016) proposed a method for finding an optimal compromise solution of completely fuzzy multi-objective multi-item STP with all parameters represented by trapezoidal fuzzy integers. (Dalman et al. 2016) introduced a new interval programming approach for solving multi-objective multi-item STP with limits on some commodities and conveyances, such that some specified commodities cannot be transported by certain conveyances. Chen et al. (2019) introduced entropy-based STP where parameters were independent uncertain variables and used the interior point method to find its solution. To deal with imprecise data in the realistic transportation system, Roy and Midya (2019) structured a multi-objective fixed charge STP with product blending as an additional constraint and added a triangular fuzzy number as a parameter. Ghosh et al. (2021) employed three methods, viz. goal programming, fuzzy programming, and intuitionistic fuzzy programming, to find the best Pareto-optimal solutions of multi-objective fixed charge STP.

However, Vignaux and Michalewicz (1991) first used genetic algorithms to solve transportation problems. Henceforth, various transportation problems were unfolded by the researchers through variants of genetic algorithms. For example, Gen et al. (1994) solved the bi-criterion STP in which cost matrix, supply, demand, and conveyance constraints are treated as the fuzzy number; Jimenez et al. (1996); Jimenez and Verdegay (1997) determined the solution of the multi-objective interval STP by non-standard genetic algorithm and fuzzy STP where supply, demand, and conveyance are fuzzy numbers. Ojha et al. (2010) developed GA to apply on an STP with fixed charges, discounted costs, and vehicle costs which is formulated as a linear programming problem.

Since evolutionary algorithms begin with population generation, they can yield multiple solutions in a single simulation run. They also require only objective function values to solve the problem; as a result, they can be used to solve complex problems. In light of this, this work has been carried out. The main contribution can be summed up as follows:

• 1. As literature survey reveals that MOSTP up to three objectives is dealt with classical approaches. This article is a first attempt to give insight into the direction of MOSTP with more than three objectives.

• 2. Hybrid GA, NSGA II, and NSGA III are first time utilized to deal with MOSTP.

• 3. A stochastic matrix-based initial population generation technique is provided in view to applying variants of GA.

• 4. A comparison of NSGA III is made with other variants (HGA and NSGA II) to show the sustainability and efficacy of NSGA III in the case of problems having multiple objectives.

• 5. Finally, experimental validation and statistical test named Z-test are utilized to show the quality and quantity of the solutions obtained.

This paper consists of five sections. Section 2 throws light on preliminary knowledge about multi-objective optimization, followed by the mathematical model of MOSTP. Section 3 addresses the solution procedure of genetic algorithm, hybrid GA, NSGA II, and NSGA III. Section 4 consists of two numerical examples to show the effectiveness of these methods with sensitivity analysis. Finally, the conclusion is outlined, followed by references.

2 Preliminaries

This section introduces two basic fundamentals namely Pareto-optimal solution and elitism in the light of multi-objective optimization.

2.1 Pareto-optimal solution

A solution $\textbf{x}$ is said to dominate another solution $\textbf{y}$ iff:

• 1. $f_{q}(\textbf{x}) \le f_{q}(\textbf{y})$ for all indices $q \in \{1,2,\cdots Q \}$

• 2. $f_{{\bar{q}}}(\textbf{x}) < f_{{\bar{q}}}(\textbf{y})$ for at least one index ${\bar{q}} \in \{1,2,\cdots Q \}$.

If there is no other solution $\textbf{y}$ in the feasible space that meets the above two conditions, a solution $\textbf{x}$ is said to be Pareto-optimal.

2.1.1 Elitism

During crossover and mutation, unfortunately, some good solutions may be lost. As a result, the generated children lose their fitness compared to the parents. In order to maintain the said fitness, sometimes it becomes essential that some good solution must be passed on to the next generation without change. This process is called elitism, and the selected chromosomes are called elites. Elitism helps in improving the convergence of the algorithm by preventing the loss of reasonable solutions.

3 Mathematical formulation of MOSTP

Assume that there are R origins ${\mathcal {O}}_r$, each having capacity $a_r$, S destination $d_s$ having demand $b_s$ and T number of transportation modes ${\mathfrak {t}}_t$ with capacity $c_t$. Suppose homogeneous items/commodities are to be delivered from $r^{th}$ origin to $s^{th}$ destination through $t^{th}$ transportation mode. Let there are penalties $f_{rst}$ associated with unknown quantity transferred from $r^{th}$ origin to $s^{th}$ destination utilizing $t^{th}$ transportation mode. According to Bit et al. (1993), a MOSTP mathematically can be outlined as:

Model 1

$$\begin{aligned} {\textbf {min}} \ Z_{q}(x) = \sum _{r=1}^{R} \sum _{s=1}^{S} \sum _{t=1}^{T} f_{rst}^{q} x_{rst}, \;\;\;\;\ q \ge 2, \end{aligned}$$

(1)

subject to the constraints

$$\begin{aligned}&\sum _{s=1}^S\sum _{t=1}^Tx_{rst} =a_r ,\ r=1(1)R, \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{r=1}^R\sum _{t=1}^{T}x_{rst} = b_S, \ s=1(1)S, \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{r=1}^R \sum _{s=1}^{S}x_{rst} = c_{t},\ t=1(1)T, \end{aligned}$$

(4)

$$\begin{aligned} x_{rst} \ge 0 , \forall r,s,t, \end{aligned}$$

where

$$\begin{aligned} a_{r} \ge 0, \forall r ; b_{s} \ge 0, \forall s; c_{t} \ge 0, \forall t, f_{rst}^{q} \ge 0 \ \forall r,s,t,q, \end{aligned}$$

$x_{rst}^p$ stands for the number of transported commodities from the origin ${\mathcal {O}}_r$ to destination $d_s$ using the conveyance ${\mathfrak {t}}_T$.

$$\begin{aligned} \sum _{r=1}^{R}a_{r} = \sum _{s=1}^{S} b_{s} = \sum _{t=1}^{T} c_{t} \quad {\textbf { Balanced ~ Condition}} \end{aligned}$$

(5)

For the existence of a feasible solution to model 1, the equation  5 is a necessary and sufficient condition ( Bit et al. (1993)).

4 Solution methodology

As hybrid GA, NSGA II, and NSGA III are derivatives of GA, it is essential to understand GA before understanding their working procedure. Therefore, the working procedure of GA is given first; then, hybrid GA, NSGA II, and NSGA III are outlined in detail in the successive subsections.

4.1 Genetic algorithm

Owing to its connection with genetics, genetic algorithms use a vocabulary predominantly borrowed from natural genetics. The fundamental steps involved in a basic genetic algorithm may be sequentially expressed in the following points:

• Step 1 initialization procedure Taking note of all the constraints, a population comprising individuals / solutions, known as genotypes or chromosomes, is constructed. In the literature, several approaches, in order to construct a population, are discussed. Besides, researchers (Liu et al. 2008; Gen and Cheng 1999; Eckert and Gottlieb 2002) have been contributing in this area by developing appropriate approaches according to the problem of interest. To generate initial population for MOSTP, authors have designed a stochastic solution approach such that the solutions are qualified to satisfy demand, supply, and conveyance constraints simultaneously which is discussed in Sect. .

• Step 2 fitness evaluation The second inherent step (see Sivanandam and Deepa 2008), involved in GA, is the examination of the solution’s fitness through which one figures out the goodness of the solutions as well as its proximity with the optimal one. For this purpose, we have calculated the objective function of model MOSTP satisfying all the constraints for the hybrid genetic algorithm. Following (Deb 2001) suggestion, in most cases, fitness function is made equal to the objective function value. However, for NSGA II and NSGA III, Pareto-optimality concept is hybridized with objective function value to evaluate fitness.

• Step 3 selection operator This operator is used to choose the potential ones from the population of strings based on their fitness information. In this study, we considered a binary tournament selection operator through which a chromosome is preferred over the others if its fitness is better than the others.

• Step 4 crossover operation In this step, fit individuals, as obtained in step 3, crossed over in order to produce better individuals / children. In this study, we have used the arithmetic crossover operator. For understanding, if $P_1$ and $P_2$ are parents, then $C_1 = x_1P_1 + x_2P_2$ and $C_2 = x_2P_1 +x_1P_1$ are children, where $x_1+x_2 = 1$ and $x1,x2 >0$. This technique assures that both children are feasible because the initialization procedure generates a feasible solution and the constraint set is convex.

• Step 5 mutation operation In order to preserve diversity and avoid the trap in local minima, a mutation operator is generally applied which in turn induces a slight change in the chromosomes. In this study, we have extracted a sub-matrix from the selected parent by randomly selecting rows and columns. The row and column sums of this sub-matrix represent supply and demand capacity, respectively. Then, follow initialization procedure 2 to reallocate $x_{ij}$. Thus, child individual can be obtained by inserting this sub-matrix into the parent matrix.

  

• Step 6 Steps 2–5 are replicated until the termination criterion is attained.

This subsection presents hybrid GA for MOSTP to determine the best efficient solution with different aspiration levels (ALs) of DM.

4.2 GA-based hybrid approach to solve MOSTP

In a multi-objective optimization setting, it is argued that a solution should portray the decision maker’s perception. More specifically, a solution should highlight the multiplicity of value judgment as well as complex dynamic changes that occurred in the process of decision making. In this regard, the Al effectively provides a rationalized trade-off channel. Following this idea, Dhodiya and Tailor (2016); Tailor and Dhodiya (2021) developed a hybrid GA. The procedure of the algorithm is as follows :

• 1. Consider the mathematical model of MOSTP described in model 1.

• 2. Calculate the positive ideal solution (PIS) and negative ideal solution (NIS) for each objective functions (see Gupta et al. 2013)as: ${\begin{array}{ll} {\textbf {PIS}} \hbox {for} f_q &{} {\textbf {NIS}} \hbox {for }f_q\\ f_q^{PIS} = \hbox {min} f_{q} &{} f_q^{NIS} = \hbox {max} f_{q}\\ \hbox {Subject to the constraints:}(2) to (4) &{} \hbox {Subject to the constraints}:(2) to (4).\\ \end{array}}$

• 3. Compute fuzzy exponential membership value $\mu _{f_{q}}$ for $f_{q}$.

  $$\begin{aligned} \mu _{f_{q}(x)} = {\left\{ \begin{array}{ll} 1; &{} \text {if} f_{q}\le f_{q}^{PIS},\\ \frac{\exp (-s*\psi _{q}(x))-\exp {(-s)}}{1-\exp {(-s)}}; &{}\text {if} f_{q}^{PIS} \le f_{q} \le f_{q}^{NIS},\\ 0; &{} \text {if} f_{q}\ge f_{q}^{NIS},\\ \end{array}\right. } \end{aligned}$$

  (6)

  where $\psi _{q}(x) = \frac{f_{q}-f_{q}^{PIS}}{f_{q}^{NIS}-f_{q}^{PIS}}$ and S is nonzero shape parameter(Sp), regulated by the DM and $0\le \mu _{f_{q}} (x) \le 1$. It should be noted that the membership function in $[f_{q}^{PIS},f_{q}^{NIS}]$ is strictly convex (concave) for $S < 0,(S > 0)$.

• 4. According to Gupta et al. (2013), MOSTP is converted in the single-objective optimization problem as follows. model-2 objective function:

  $$\begin{aligned} max W = \prod _{q=1}^{Q} \mu _{f_{q}}, \end{aligned}$$

  (7)

  Subject to the constraints: (2) to (4) and

  $$\begin{aligned} \mu _{f_{q}}(x) - \overline{\mu _{f_{q}}(x)}\ge 0; q= 1,2, \cdots Q. \end{aligned}$$

  (8)

  Where the required AL of fuzzy goals corresponding to each objective is $\mu { f q }(x)$. However, the above-mentioned model can be solved by altering the DM’s ALs to achieve various fuzzy goals.

• 5. Discover various transportation schemes for the model-2, developed in step-4, through GA with different choices of the Sp.

4.3 NSGA II

The key to understand working methodology of NSGA II is to understand its two special operators—non-dominated sorting (NDS) operator and crowded distance tournament selection (CDTS) operator, discussed as below:

4.3.1 Non-dominated sorting (NDS) operator

In this operator, we have evaluated following two entities for each considered solution:

• 1. Domination count $n_p$, the non-negative integer used to reflect the number of solutions that dominate the solution p ,

• 2. $S_p$ a set of solutions dominated by solution p.

Now we begin the process by comparing each member of the population to each other member of the population using the idea of domination, which provide the first/principal non-dominated front. The domination count for all solutions belonging to the principal non-dominated front will be zero. Now, for each solution with $n_p=0$, we go over each member q of its set $S_p$ and apply the idea of dominance to each one, lowering the domination count by one. During this process, every member with a domination count of zero is moved to a different list. The member of this new list is referred to as the second non-dominated front. Similarly, the third front is determined by repeating this technique with each member of $S_q$. This procedure is repeated until all possible fronts have been found.

4.3.2 Crowded distance tournament selection (CDTS) operator

The compactness of a given solution i in the population is measured after the NDS procedure by taking the average distance between two solutions on both sides of the solution i along each of the objectives. The crowding distance is used to calculate the perimeter of the cuboid using nearest neighbors as vertices (see Deb 2001).

The algorithm for determining the crowding distance

By the NDS procedure, we get non-dominated fronts ($F_{1}, F_2, \cdots$ and so on). All the solutions of front $F_1$ have assigned rank 1, members of front $F_2$ have assigned rank 2, and similarly, solutions of other fronts are assigned ranks. For calculating crowding distance, we arrange the solutions with the same rank in worse order of their objective values. Now boundary solutions of each front are assigned crowding distance infinity, and crowding distance for rest members is calculated as follows:

$$\begin{aligned} l_{({I}_{j}^{q})} = l_{({I}_{j}^{q} )} + \frac{f_{q}^{(I_{j+1}^{q})}-f_{q}^{(I_{j-1}^{q})}}{f_{q}^{max}-f_{q}^{min}}. \end{aligned}$$

(9)

where $I_j$ is the $j^{th}$ solution in the sorted list . $f_q^{max}$ and $f_q^{min}$ are the maximum and minimum objective values for $q^{th}$ criterion.

A solution x wins CDTS with y if the following two conditions are satisfied:

• 1. It has lesser rank, i.e., $r_x <r_y$ .

• 2. If $r_x = r_y$, then $l_x$ should be greater then $l_y$.

In NSGA II, a binary tournament selection operator is utilized; however, the selection criterion is based on the crowding distance tournament operator (see Deb et al. 2002).

4.3.3 Process

In this section, the NSGA II algorithm is outlined in the following two phases. In phase 1, the initial population ($A_{t}$) of size N is generated, which is further segregated into different fronts employing the non-dominated sorting procedure. Next, we have assigned fitness to solutions. Then, we have applied three genetic operators viz. selection, crossover, and mutation and obtained the offspring population $(B_t)$ of size N. In second phase, initial population $A_{t}$ and offspring population $B_{t}$ are combined to form population $C_t$ of size 2N. Then, implement the NDS procedure on combined population $C_t$ and get different fronts (such as $F_1, F_2$ and so on). In order to select N members, we first choose fronts according to their ranking and add them into a new empty set $S_t$ and check whether the cardinality of $S_t$ is greater than or equal to N and start adding fronts to $S_t$ until cardinality of $S_t$ is greater than or equal to N. If $S_t$ has exactly N population members, then we apply genetic operators on it and get new population $A_{t+1}$ else we apply crowded distance tournament selection operator to choose $N - \textit{cardinality of} S_t$ population members then apply genetic operator. This phase continued until the termination criterion is met.

However, some of the Pareto-optimal solutions from the first front give way to other non-dominated yet non-Pareto-optimal solutions when the number of solutions in the first non-dominated front exceeds the population size. These non-Pareto-optimal solutions are then replaced by another Pareto-optimal solution in subsequent iterations. But this cycle slows down the process of NSGA II to get a well-distributed set of solutions (Deb 2001). However, the reference point strategy prevents NSGA III from experiencing such an issue.

4.4 NSGA III

Despite its similarity with NSGA II, NSGA III differs in the way its selection operator works. More specifically, in NSGA II, the crowding distance operator works as a diversity preserving operator while NSGA III is incorporated with reference point strategy to maintain diversity among Pareto-optimal solution.

In order to select individuals, the process started like in NSGA II, but if the situation arises to select a partial number of elements from the critical front, which do, then the working process of NSGA III differs. To illustrate the working process of selecting a partial number of members from the last front, we follow the following steps:

Step 1:

We began the algorithm by obtaining $Z_{q}^{min} (q= 1,2,\cdots Q)$ from $\cup _{\tau =0}^{t} S_{\tau }$ and form translated objective function as $f_{q}^{'} (x)=f_q (x)-Z_q^{min}$.

Step 2:

In this step, Q- dimensional hyperplane is generated with the help of Q extreme vectors obtained in the previous step. Now we calculate intercept $x_{q}$ of the $q^{th}$ axis and normalize objective functions using $f_q^n (x) = \frac{f_{q}^{'}(x)}{x_{q}}$, $\forall q=1,2, \cdots Q$.

Step 3:

Now the reference points using Das and Dennis approach (Das and Dennis 1998) are generated.

Step 4:

In this step, we create reference lines by linking the reference points and the origin. Then, perpendicular distance between each population member of $S_{t}$ and reference line is calculated and the reference point with the minimum perpendicular distance considered to be associated with population member.

Step 5:

Finally, niche preservation operator is used to choose member from last front to fulfill vacant position of $A_{t+1}$.

4.4.1 Niche preservation operator

To begin, calculate the niche count $\rho _h$ for the $h^{th}$ reference point as the number of individuals in $S_t/F_l$ who are linked to the $h^{th}$ reference point. Then, look for

$$\begin{aligned} H_{min} = \{ h: argmin_{h} \rho _h\}. \end{aligned}$$

When $|H_{min}| \ge 1$, one $\bar{h} \in H_{min}$ is chosen at random. There are two possibilities now:

• 1. If $\rho _{\bar{h}} =0$, one or more individuals may be associated with $\bar{h}$ in front $F_l$. In this scenario, the individual with the shortest perpendicular distance to $\bar{h}$ is chosen for the $A_{t+1}$ population, and if there is no member associated with $\bar{h}$, reference point $\bar{h}$ is removed from consideration for the current generation.

• 2. if $\rho _{\bar{h}} \ge 1$, then if there exist individuals in the set $F_l$ that are associated with $\bar{h}$, then any one can be chosen randomly.

Each time after addition of new individual to $A_{t+1}$, $\rho _{\bar{h}}$ incremented by one.

This process is repeated k number of times.

4.5 Procedure to generate initial population for MOSTP

We introduce a new matrix-based representation for a MOSTP capable of generating initial feasible solutions within the positive and negative ideal solution range. The proposed method is illustrated through one example in this section (Table 1).

Table 1 Cost matrix

Consider a transportation cost matrix related to a solid transportation problem with three origins having supply (8, 9, 5), demand centers having demands (7, 6, 9), and transportation mode of capacity (10, 5, 7).

Now, Table 2 corresponding to first transportation mode is obtained by picking column $\{1,4,7\}$.

Table 2 Matrix corresponding to first conveyances

After that, we randomly select a cell corresponding to the third row and first column of this table and fill the minimum of supply, demand, and capacity of transportation mode. Since the third supply is fulfilled, so we remove the third row and update supply, demand, and capacity of transportation mode by subtracting the minimum value from each of them. Now, we select another cell corresponding to the first row and second column and fill the minimum of supply, demand, and capacity of transportation mode. Since $E(1)=0$ and third row is deleted therefore, for next step we choose $\{1,2\}$ row and $\{2,5,8\}$ column; this provides Table 3.

Table 3 Matrix corresponding to second conveyance

We repeat the process by randomly selecting cells corresponding to the first row and second column, then second-row third column.

Table 4 Matrix corresponding to third conveyance

Since in this step demand of the second column is fulfilled, we remove all$\{4,5,6\}$ columns and make Table 4 by selecting row $\{1,2\}$ and column $\{3,9\}$ from the original table and repeat the process to fulfill supply, demand, and capacity of transportation mode (Table 5).

So, final table is $\cdots$

Table 5 Encoded chromosome

Table 6 Transportation cost for MOSTP-1

5 Numerical illustrations for MOSTP

5.1 Multi-objective solid transportation problem-1

To demonstrate the applications of the method, we consider a MOSTP with five sources, five destinations, and five conveyances. The capacity of origins, destinations, and transportation mode is below given by the notations $a_i$, $b_j$, and $c_k$ corresponding to $i^{th}$ source, $j^{th}$ destination, and $k^{th}$ transportation mode, respectively.

Supplies $a_{1} = 7, a_2 = 9, a_3= 8, a_4 = 6, a_5 = 13,$

Demands $b_1= 11, b_2 = 9, b_3 = 5, b_4 = 8, b_5 = 10,$

Conveyance capacity $c_1 = 13, c_2= 6, c_3 = 7, c_4= 9, c_5= 8$.

Coefficients $f_{1}, f_{2}, f_{3}, \text {and} f_4$ are shown in Tables 6, 7, 8 and 9:

Table 7 Distance for MOSTP-1

Table 8 Product deterioration for MOSTP-1

Table 9 Risk of MOSTP-1

Table 10 Encoded chromosome for MOSTP-1

The considered problem can be modeled as follows:

$$\begin{aligned} {\textbf {min}} \ Z_{q}(x) = \sum _{r=1}^{5} \sum _{s=1}^{5} \sum _{t=1}^{5} f_{rst}^{q} x_{rst}, \;\;\ q =1(1)4, \end{aligned}$$

subject to the constraints

$$\begin{aligned}{} & {} \sum _{s=1}^5\sum _{t=1}^5x_{1st} =7, \;\ \sum _{s=1}^5\sum _{t=1}^5x_{2st} = 9,\;\ \sum _{s=1}^5\sum _{t=1}^5x_{3st} = 8 \\{} & {} \sum _{s=1}^5\sum _{t=1}^5x_{4st} = 6,\;\ \sum _{s=1}^5\sum _{t=1}^5x_{5st} = 13, \sum _{r=1}^5\sum _{t=1}^{5}x_{r1t} =11,\\{} & {} \sum _{r=1}^5\sum _{t=1}^{5}x_{r2t} =9, \;\ \sum _{r=1}^5\sum _{t=1}^{5}x_{r3t} =5, \;\ \sum _{r=1}^5\sum _{t=1}^{5}x_{r4t} =8 \\{} & {} \sum _{r=1}^5\sum _{t=1}^{5}x_{r5t} =10, \sum _{r=1}^5 \sum _{s=1}^{5}x_{rs1} =13, \sum _{r=1}^5 \sum _{s=1}^{5}x_{rs2}=6, \\{} & {} \sum _{r=1}^5 \sum _{s=1}^{5}x_{rs3}=7, \;\ \sum _{r=1}^5 \sum _{s=1}^{5}x_{rs4}=9, \sum _{r=1}^5 \sum _{s=1}^{5}x_{rs5}=8,\\{} & {} x_{rst} \ge 0 , r = 1(1)5 \;\ s = 1(1)5,\;\ t = 1(1)5. \end{aligned}$$

A chromosome with given supply, demand, and conveyance capacity can be encoded as in matrix 10.

Mutation For demonstrating mutation, we have here chosen the encoded chromosome shown in Table 10 as the parent matrix. Then, the two rows $\{4,5\}$ and three columns $\{17,20,21\}$ of the parent matrix are randomly chosen, which lead to the corresponding submatrix Y as shown in Table 11.

Thus, supply at origins of Y is 3, 10, and demands are 3, 2, 8, respectively. After re-initialization of Y, the matrix may get the form shown in Table 12

Table 11 Sub-matrix corresponding to encoded chromosome 10

Table 12 Sub-matrix after re-initialization

Table 13 Mutated chromosome for MOSTP-1

Finally, the child offspring after mutation corresponding to parent matrix 10 is obtained as shown in Table 13.

The PIS and NIS for the considered example are provided in Table 14.

Hybrid GA We have shown the results of hybrid GA for MOSTP-1 in Table 16 by taking different estimations of the ALs for each combination of the Sp shown in Table 15.

Table 14 Positive and negative ideal solution

Table 15 Cases taken by DM for MOSTP-1

Fig. 1

Efficient solution of MOSTP-1 at different combination of SP and AL

Fig. 2

Degree of satisfaction of MOSTP-1

The ESs of objective values at different combinations of SP and AL are shown in Table 15 in Fig. 1. The degree of satisfaction for various combinations of SP and AL given in Table 15 is shown in Fig. 2. The variation in SP values affects each objective, as shown in Fig. 2.

The hybrid GA convergence curve for MOSTP-1 is depicted in Fig. 3 for case 1 of Table 15. The convergence curve remains the same for all additional occurrences of Table 15.

Fig. 3

Convergence curve of GA for MOSTP-1

Fig. 4

Pareto-optimal set by NSGA II

Table 16 Summary results for MOSTP-1

Parameter settings To make a fair comparison between NSGA II and NSGA III, simulations have been done on the same value of Parameter used in algorithms using Taguchi Orthogonal Array (Karna and Sahai 2012). Parameters which are utilized in employing Taguchi Orthogonal Array are given in Table 17. However, the parameters which proves best in terms of run time and performance measure are given in the comparison table.

Results of NSGA II and NSGA III Simulation has been done by 18 times, and each time performance measure parameter coverage is calculated. Tables 18 and  19 show the results obtained at 120 population size, 80 iterations, 0.6 crossover rate, and 0.03 mutation rate with the best coverage value (Fig. 4).

NSGA II gives a Pareto-optimal set containing 6 solutions which are listed in Table 18.

NSGA III

Table 17 Parameters for Taguchi orthogonal array for MOSTP-1

From simulations, it is observed that NSGA III gives more number of Pareto-optimal solution then NSGA II. Tables 18 and 19 show that some of the solutions obtained by NSGA II are dominated by NSGA III’s solutions.

Table 18 Results obtained from NSGA II

Figure 6 shows variation in population size and iteration affect the objective values. The compromise solution of the problem by FPT under the linear membership function is given in Table 20.

From Fig. 5, it is clear that we obtained multiple solutions with varying degrees of objective values.

Table 19 Pareto-set obtained from NSGA III

Fig. 5

Pareto-front by NSGA III

Fig. 6

Variation in objective value with respect to population size

Table 20 Solution of MOSTP-1 by fuzzy programming technique

Fig. 7

Convergence rate for MOSTP-2

5.1.1 Discussion for MOSTP-1

The run time of FPT for MOSTP-1 is less compared to other adopted evolutionary algorithms ( Table 21) but it provides a single solution in the single run by converting the multi-objective problem into a single objective. On the other hand, Table 15 shows the four particular cases taken by DM, and Table 16 represents the obtained optimally compromised solutions by hybrid GA. DM, according to their convenience to reflect their aspiration level, may choose any solution (Fig. 7). On the other hand, NSGA II on different combinations of parameters (made by Taguchi orthogonal array) provides a number of Pareto-optimal solutions; all of them are non-dominated by FPT. Furthermore, all solutions from the Pareto-optimal set are equally important as well as all are non-dominated. So, DM may choose any solution from the Pareto-optimal set compatible with his criteria. On the other hand, some of the solutions from the Pareto-optimal set of NSGA III clearly dominate the NSGA II’s solutions. NSGA III gives more options to DM to choose a solution representing his aspiration level. A table containing comparative results is shown in Table 21. Moreover, Table 21 shows the run time for each algorithm from which it can be concluded that NSGA III provides multiple alternatives to DM in comparatively less time by treating numerous objectives simultaneously.

Table 21 Comparison table describes developed technique for MOSTP-1

Table 22 Transportation cost for MOSTP-2

Table 23 Product deterioration for MOSTP-2

5.2 Multi-objective solid transportation problem-2

In a company, there are five construction machines $N_1,N_2,$ $N_3,N_4$, and $N_5$, which can produce 10, 7, 17, 4, and 11 units of a commodity, respectively. These quantities were transported to four required destinations $D_1, D_2, D_3$ and $D_4$ with demands 20, 9, 6, 14 utilizing four different conveyances with capacity 13, 5, 16, and 15 units, respectively. Transportation cost, product deterioration, weight, distance, and risk of that are given in Tables 22, 23, 24, 25, and 26, respectively:

Table 24 Weight of the product for MOSTP-2

Table 25 Distance for MOSTP-2

Table 26 Risk involved in MOSTP-2

Table 27 Encoded chromosome for MOSTP-2

The considered problem MOSTP-2 can be modeled as follows:

$$\begin{aligned}&{\textbf {min}} \ Z_{q}(x) = \sum _{r=1}^{5} \sum _{s=1}^{4} \sum _{k=1}^{4} f_{rst}^{q} x_{rst} , q =1(1)5,\\&\sum _{s=1}^4\sum _{t=1}^4x_{1st} =10, \;\ \sum _{s=1}^4\sum _{t=1}^4x_{2st} = 7,\;\ \sum _{s=1}^4\sum _{t=1}^4x_{3st} = 17,\\&\sum _{s=1}^4\sum _{t=1}^4x_{4st} = 4, \sum _{s=1}^4\sum _{t=1}^4x_{5st} = 11, \sum _{r=1}^5\sum _{t=1}^{4}x_{r1t} =20,\\&\sum _{r=1}^5\sum _{t=1}^{4}x_{r2t} =9, \;\ \sum _{r=1}^5\sum _{t=1}^{4}x_{r3t} =6,\;\ \sum _{r=1}^5\sum _{t=1}^{4}x_{r4t} =14,\\&\sum _{r=1}^5 \sum _{s=1}^{4}x_{rs1} =13,\;\ \sum _{r=1}^5 \sum _{s=1}^{4}x_{rs2}=5, \;\ \sum _{r=1}^5 \sum _{s=1}^{4}x_{rs3}=16,\\&\;\ \sum _{r=1}^5 \sum _{s=1}^{4}x_{rs4}=15,\\&x_{rst} \ge 0, r =1(1)5, \ s = 1(1)4, \ t=1(1)4. \end{aligned}$$

Chromosome encoding

Encoded chromosome shown in Table 27.

Mutation Let the above-encoded chromosome be selected as the parent solution for mutation (Table 27). Then, randomly choose two rows $\{3,5\}$ and two columns $\{6,10\}$ of the selected matrix (Table 28), then corresponding submatrix Y is

Supply at origins of Y is 4, 2, and demands are 5, 2. After re-initialization Y, the matrix may convert in matrix as shown in Table 29

Table 28 Sub-matrix Y corresponding to encoded chromosome 27

Table 29 Matrix Y after re-initialization

Table 30 Child offspring for MOSTP-2

Table 31 Compromise solution obtained from fuzzy programming technique

Table 32 Positive and negative ideal solution for MOSTP-2

Table 33 Different cases taken by DM for MOSTP-2

Table 34 Summary result for MOSTP-2

So, finally, the child offspring after mutation operator corresponding to parent matrix 27 is shown in Table 30:

Results obtained from fuzzy programming technique using linear membership function and PIS and NIS for MOSTP-2 are given in 31 and 32, respectively:

Different shape parameters corresponding to different ALs for MOSTP-2 are considered in Table 33, and the result is obtained as shown in Table 34. Figure 6 shows the ESs of objectives at different combination of SP and AL given in Table 33. The degree of satisfaction and the resulting ALs are depicted in Fig. 8. It also implies that changes in SP values influence all objectives.

Fig. 8

Efficient solution of MOSTP-2 at different combinations of SP and AL

Fig. 9

Degree of satisfaction of goal for MOSTP-2

Figure 9 represents the convergence rate for the MOSTP-2. This graph is drawn among population size, iterations, and the values of max $W= \prod _{q=1}^{5}Z_{q}$. The hybrid GA started converging after 50 population sizes and 5 iteration for case 1 given in Table 33.

Parameter setting Table 35 shows the values of parameter of NSGA II and NSGA III which are used in making Taguchi Orthogonal Array to decide the parameters for the simulation of MOSTP-2 by NSGA II and NSGA III. However, the parameters which prove best in terms of run time and performance measure are given in comparison Table 38 NSGA II and NSGA III gives Pareto-optimal set. Some of the points from this set are listed in Tables 36 and 37, respectively.

It is apparent from Table 38 that some of the solution obtained by NSGA III dominates the solutions obtained by NSGA II. The figure also represents the varying degree of objective values.

Figure 10 indicates that the variation in the number of divisions affects the objective values.

Table 35 Parameters for Taguchi Orthogonal Array for MOSTP-2

Table 36 Pareto-optimal solution of NSGA II for MOSTP-2

5.2.1 Discussion for MOSTP-2

Table 33 shows different cases considered by DM, and the obtained optimally compromised solutions are shown in Table 34. Solution (197, 256, 278, 311, 223) obtained corresponding to the considered case-1 is better in four objectives from the fuzzy programming technique’s result. From Table 36, we can conclude that most of the points from the Pareto-optimal set obtained by NSGA II (Fig. 11) are better in three or four objectives from the solution obtained by fuzzy programming technique and hybrid GA. Furthermore, the result obtained by NSGA III contains a Pareto-optimal solution shown in Table 37 which is better in most of the solutions(Fig. 12) in 3 objectives from NSGA II, and some of the solutions dominate NSGA II (Fig. 13).

Table 37 Result of NSGA III for MOSTP-2

Fig. 10

Effect of number of division on objective values

Fig. 11

Pareto-optimal set obtained from NSGA II

Fig. 12

Pareto-front by NSGA III

Fig. 13

Variation in objective values with population size and iteration

Table 38 Comparison table describes developed technique for the MOSTP-2

Although genetic algorithms and their derivative algorithms have been utilized to tackle a variety of engineering issues, no work has been done on STP with more than three objectives so far. In addition, traditional methods are used on MOSTP, even though they all produce a single solution in a simulation run. NSGA III, on the other hand, when equipped with a stochastic matrix-based population, can provide several solutions in a single simulation run. Moreover, Table 38 shows that NSGA III is also a better approach in terms of time as it takes less time to provide multiple solutions because of its inherent property of optimizing several objectives simultaneously.

6 Experimental validation and statistical analysis

To check the claim that NSGA III covers a wide range of optimal solutions from the Pareto-optimal set, eighteen times simulations have been conducted with the help of the Taguchi Orthogonal Array. Also, Z- test is applied with the null hypothesis that there is no significant difference between the number of solutions provided by NSGA II and NSGA III, while the alternative hypothesis is considered as NSGA III provides more optimal solutions. At the $5\%$ level of significance, null hypothesis is rejected, which proves our claim.

The performance of NSGA III is evaluated based on the performance metric “coverage.” Coverage is defined as

$$\begin{aligned} Cov(A,B)=\frac{\mid \{b\in B| \exists a \in A : a \prec = b\}\mid }{|B|} \end{aligned}$$

Cov (NSGA II, NSGA III) comes out to 0.25385 while Cov(NSGA III, NSGA II) comes out to 0 for MOSTP-1 and Cov(NSGA II, NSGA III) and Cov(NSGA III, NSGA II) come out 0.4537 and 0.012 for MOSTP-2. The values of coverage imply that NSGA III dominates NSGA II more efficiently.

7 Conclusion

Multi-objective solid transportation problem is a common problem faced by enterprises. This study focuses on providing multiple transportation schemes to MOSTP. In this regard, two problems of different sizes and a different number of objectives are considered, and a stochastic matrix-based initial population generation technique is provided in view to applying variants of GA. Moreover, provided chromosome generation technique is able to generate chromosomes for MOSTP having even greater than three objectives keeping the computational complexity of NSGA III at $MN^2$. NSGA II and NSGA III provide multiple solutions in a single simulation run, but the time taken by NSGA III is less than NSGA II, and also, NSGA III provides more number of solutions in the Pareto set than NSGA II. On the other hand, hybrid GA provides an alternate solution, but there is a need to set shape parameters and aspiration levels for each run. FPT, being a classical approach, provides a single solution. Moreover, the solutions obtained by variants of GA are non-dominated by each other and from FPT. Thus, our study shows that variants of GA are a better approach to dealing with MOSTP. Especially, NSGA III proves to be a better candidate from the class of variants of GA to deal with MOSTP in less time. But, the NSGA III equipped with the proposed initial population generation technique is problem specific, i.e., to apply on different variants of STP or on different optimization problems like traveling salesman problem, vehicle routing problem, VLSI, or chip design needed some modification. Despite all these limitations, this approach can be modified to deal with STP in a different environment like fuzzy, stochastic, uncertain, etc.