Solving a two-objective green transportation problem by using meta-heuristic methods under uncertain fuzzy approach

Abstract

Nowadays, one of the most challenging issues for firms, organizations and factories is transportation problems. Major of annual costs is related to these problems. Besides, according to the importance of environmental issues and strict laws for protecting the environment, organizations and firms ought to find the most economical and cleaner ways of transportation. In this paper, we optimized a two-objective fuzzy transportation problem simulated by multi-objective linear integer fuzzy programming technique. The existing fuzzy parameters (transportation costs, demands and supply quantities) are considered triangular fuzzy numbers. The Jimenez method used for Defuzzification the fuzzy model. In addition to principal constraints of transportation problems, the constraints of real-world such as vehicles’ capacity and most shipping time are also included. In order to solve the fuzzy transportation problem, simulated annealing (SA) approach and non-dominated sorting genetic algorithm (NSGA-II) (which has rarely been used) implemented. The results of solving some test problems created in different sizes show that both methods are capable of finding Pareto solutions in a quick time. The results of the comparison between the named algorithms prove that the SA algorithm comes up with more Pareto solutions with better quality in a shorter time than NSGA-II.

Keywords

Green transportation problem multi-objective linear integer mathematical programming simulated annealing (SA)non-dominated sorting genetic algorithm (NSGA-II)Jimenez method

1 Introduction

In today’s competitive market, organizations and firms are supposed to find the best way to deliver customers’ demand and satisfy them. Answering how and when the product should be sent in order to minimize the costs is a great challenge. Transportation models represent a proper framework for confronting this challenge. These models guarantee affordable and efficient shipping and on time deliveries of raw material and final products to customers. The basic transportation problem was first presented by Hitchcock [1]. He proved that transportation problems can be simulated as standard linear programming problem that can be solved by simplex method, but due to unique mathematical structure of transportation problem, researchers found out that the simplex method being used can be modified to a more sufficient method by correcting the assessment and recognition of required information such as entering and leaving variables and optimization condition. Charnes and Cooper [2] developed the stepping stone method which offers an alternate way to determine the required information for simplex method. Dantzing and Thapa [3] used simplex method as a primary transportation simplex method for a transportation problem. An initial basic feasible solution (IBFS) can be calculated by using north-west corner rule (NWC), row minima method, column minima method, matrix minima method (the lowest cost entry method) and Vogel’s approximation method. The modified distribution method is also beneficial for finding optimal solution.

In classic transportation problems, it is assumed that the decision-maker has precise information about transportation costs, feasibility/shipping time of the product and product’s demand, but in real-world transportation problems, precise information about parameters of a problem may not be feasible, because they are always being affected by many factors. Sometimes these uncertain and imprecise information are shown by random variables generated by probability distributions. However, using probability distributions for transportation problems with uncertainty is not always a suitable method.

Fuzzy numbers [4] can also be used for demonstrating uncertain data and fuzzy decision-making method is helpful in these situations. In Zimmermann’s [5] paper, it is established that solutions generated by linear fuzzy programming are always efficient. Then Zimmermann’s linear fuzzy programming method was developed as numerous fuzzy optimization methods for solving transportation problems. Oheigeartaigh [6] presented an algorithm for solving transportation problems in which production capacity and fuzzy set’s demands are functions with linear or triangular membership. Chanas et al. [7] proposed a linear fuzzy programming model with certain cost coefficient and fuzzy demand and supply quantities for solving transportation problems. Chanas and Kutcha [8] presented an optimal solution concept for transportation problem with fuzzy coefficients which are displayed as fuzzy numbers and developed an algorithm for finding optimal solution. Abbas also suggested [9] an algorithm for solving fuzzy transportation problem.

Liu and Kao [10] presented a method for solving fuzzy transportation problem (FTP) based on extension principle. Gani and Razak [11] introduced a fuzzy solution for a two-stage cost minimization fuzzy transportation problem in which supply and demand are trapezoidal fuzzy numbers. They used a parametric method for finding a fuzzy solution and attempted to minimize transportation costs in both stages. Gupta and Mehlawat [12] converted supply quantity of (i)th supplier and demand quantity of (j)th customer data into interval-valued fuzzy numbers by means of fuzzy numbers. Their purpose was to confront the uncertainty of supply and demand parameters. Dinagar and Palanivel [13] studied on fuzzy transportation problems by deploying trapezoidal fuzzy numbers. A fuzzy modified distribution method was also suggested for finding fuzzy optimal solution. Pandian and Natarajan [14] developed a new algorithm called fuzzy zero point method for finding fuzzy optimal solution for fuzzy transportation problems where transportation costs demand and supply parameters are trapezoidal fuzzy numbers. Baykasoù glu and Subulan [35] presented most of the existing methods for solving fully fuzzy mathematical programs based on the standard fuzzy arithmetic operations and/or Zadeh’s extension principle, also presents a novel method based on the constrained fuzzy arithmetic concept to solve fully fuzzy balanced/unbalanced transportation problems, which all the limits (source capacities, demands of destinations, transportation costs, etc.) and decision variables (transportation quantities) fuzzy numbers considered. Du & Li, Yu & Dan and Zhou [36] presented develop a fuzzy bi level programming model for minimizing the total expected transportation risk, when delivering products of hazardous materials to customers from multiple depots. Ebrahimnejad [37] presents a new method of solving fuzzy transportation problem (FTP) in which the transportation costs and values of supplies and demands by non-negative LR flat fuzzy numbers represented. The FTP into four crisp transportation problems converted, these crisp problems with the standard transportation simplex algorithms solved.

Irina Harris and colleagues propose a useful evolutionary multi-objective optimization approach to the capacitated facility location–allocation problem (CFLP) that considers flexibility at the allocation level, where financial costs and CO2 emissions are considered simultaneously [33].

Bandyopadhyay and Bhattacharya [34], minimizes the value of total cost and bullwhip effect in a supply chain. A new crossover algorithm for a fuzzy variable and a new mutation algorithm have also been proposed while applying Nondominated Sorting Genetic Algorithm-II (NSGA-II) to the proposed problem.

By surveying literature and former papers, it is obvious that many researchers chose fuzzy approaches to assess the uncertainty of various parameters of transportation problem and have found out that fuzzy approach is perfectly capable of solving fuzzy transportation problem. In this paper quantities of supply, demand and product’s shipping time (trip time) parameters are uncertain and considered as triangular fuzzy numbers. Although several researchers have used heuristic methods based on classic method developments for solving transportation problems, in this paper we have attempted to test meta-heuristic methods’ abilities in solving these sorts of problems. We took into consideration, multi-objective methods of SA and NSGA-II. Since in our transportation model, the number of feasible solutions to be examined does not allow an exhaustive search, it is necessary to adopt metaheuristic algorithms to obtain sub-optimal solutions within suitable calculation times which is similar a solid transportation problem (STP) [38]. Furthermore, according to importance of environmental issues and organizations and firms obligations to obey strict laws stated by department of environment about minimizing the pollutant emissions, the total emitted contaminants of vehicles is considered as an objective function and minimizing it is set as a goal.

In the second section of this paper we define our considered transportation problem and present a mathematical model for it. In the third section we introduce the methodology and solution procedures. In the section four we have provided some numerical examples to check the efficiency and performance of methods and consequently we brought the results at the end of this part. Ultimately, the fifth part of this study is the summary and conclusion.

2 Basic definitions and mathematical modelling

In classic transportation problems it is assumed that the decision-maker is informed about precise values of transportation costs, delivery time and demand according to Kaur and Kumar studies [15], but in real-world problems, it is possible that some of these parameters are infeasible, because they are influenced by so many factors. For instance, consider a product which is being transported for the first time. The decision-maker has no information about transportation costs. In addition, when a new product is released in a market, the accurate amount of demand for that product cannot be estimated or when there is mass ordering for a specific product, the supplier will face uncertainty about the existing extent of that product in his inventory. Scientists have used fuzzy sets theories in order to face these kinds of transportation problems (Kaur et al. [15], Keshavarz and Khorram [16] and Kundu et al. [17]).

Below, we can find the assumptions about transpiration problems of this study:

Transportation costs, product’s demand and suppliers’ capacities are considered as triangular fuzzy numbers.

Different vehicles with variant costs and capacities are used for transporting products.

There is time constraint for products shipping, in other words, the supplier should send products before violating a specific time limit. The transportation time is variable from a vehicle to another.

The considered transportation problem is uneven. This means the total demand is not equal to suppliers’ total production. Their production amount is more or equal to quantity of customer’s demand.

Constant costs of used vehicles are also included in transportation costs.

The emitted contaminants are considered so as to minimize them.

According to above assumptions, the presented mathematical model for fuzzy transportation problem is proposed in this part:

Subscripts:

i = 1, 2..., M suppliers

j = 1, 2..., N products

k = 1, 2..., K vehicles

Parameters:

${\tilde{C}}_{ijk}$ : Fuzzy cost of transportation from (i) origin to (j) destination by (k) vehicle.

G_ijk: Emitted contaminations by (k) vehicle for transporting product from origin (i) to destination (j).

t_ijk: Product’s transportation time from (i) origin to (j) destination by (k) vehicle.

${\tilde{a}}_{i}$ : Production capacity in (i)th origin which is fuzzy.

${\tilde{b}}_{j}$ : Product demand in (j)th destination which is fuzzy.

F_k: Constant cost of using (k)th vehicle.

Ca_k: Capacity of (k)th vehicle.

T: Maximum allowed time for transporting products among nods.

Decision variables:

X_ijk: Transported amount from (i) origin to (j)th destination by (k) vehicle.

Y_ijk: It equals 1 if the product is transported from (i) origin to (j)th destination by (k) vehicle, otherwise, it is 0.

Mathematical model: $\begin{matrix} min \sum_{i = 1}^{M} \sum_{j = 1}^{N} \sum_{k = 1}^{K} {\tilde{C}}_{ijk} X_{ijk} \\ + \sum_{k = 1}^{K} F_{k} (\sum_{i = 1}^{M} \sum_{j = 1}^{N} Y_{ijk}) \end{matrix}$ (1) $min \sum_{i = 1}^{M} \sum_{j = 1}^{N} \sum_{k = 1}^{K} G_{ijk} Y_{ijk}$ (2) $\sum_{k = 1}^{K} {\sum_{j = 1}^{K} X}_{ijk} \leq {\tilde{a}}_{i} i = 1, \dots, M$ (3) $\sum_{k = 1}^{K} {\sum_{i = 1}^{K} X}_{ijk} \leq {\tilde{b}}_{j} j = 1, \dots, N$ (4) $\begin{matrix} t_{ijk} Y_{ijk} \leq T i = 1 \dots, M, j = 1 \dots, N, \\ k = 1 \dots, K \end{matrix}$ (5) $\begin{matrix} X_{ijk} \leq M * Y_{ijk} i = 1 \dots, M, \\ j = 1 \dots, N, k = 1 \dots, K \end{matrix}$ (6) $\begin{matrix} X_{ijk} \leq {Ca}_{k} i = 1 \dots, M, \\ j = 1 \dots, N, k = 1 \dots, K \end{matrix}$ (7) $\begin{matrix} \sum_{j = 1}^{N} Y_{ijk} \leq 1 i = 1, \dots, M, \\ k = 1, \dots, K \end{matrix}$ (8) $X_{ijk} \geq 0, Integer$ (9) $Y_{ijk} \in {0, 1}$ (10)

The first objective function calculates the sum of constant and variable costs of transportation and tries to minimize it. The second objective function refers to minimization of contaminants emitted by vehicles. Inequalities (3) and (4) are the main constraints of the problem. The 5th one is shipping time constraint for delivering customers’ demand. Product’s shipping time from origin nods to destination nod has to be less than a predicted time. Constraint (6) establishes a logical circumstance for shipping a customer’s demand by a vehicle. A product cannot be shipped to a customer unless a vehicle is selected for shipping it, specifically. The 7th constraint forces transportation capacity not to violate an exact extent while allocating products for shipping. Constraint (8) is also associated with allocation logic in transportation problem so that all of one customer’s demands must be provided by only one supplier and one vehicle. Constraints (9) and (10) convey the decision variables’ circumstances (being non-negative and integer for X_ijk and being 0 or 1 for Y_ijk).

3 Methodology

{In this paper, two meta-heuristic methods are used for solving an integer linear fuzzy programming two-objective model, but before deploying these two methods, fuzzy model should be changed into crisp form. In order to do that, a lot of methods are suggested in literature namely max-min method introduced by Bellman and Zadeh [18], convex combination of max-min operation by Werners [19], fuzzy and operator by Zimmermann [20] and Lai and Hwang [21] method. In this paper Jimenez method have been used to make a crisp form available.

3.1 Jimenez method

In this study, we have used a recommended method given by Jimenez [22] in order to transform the suggested integer complex fuzzy model into an equivalent crisp form. Our principal reasons for choosing this method are given below:

This method is computationally efficient to solve linear fuzzy problems, because not only it preserves its linearity, but also doesn’t increase the number of objective functions and constraints (in terms of unequal relations). Thus, this method can easily be set out for enormous supply chain networks.

This method is devised based on Jimenez [23] suggested ranking method and is able to be executed on uncertain parameters with different fuzzy membership functions such as triangular, trapezoidal and non-linear membership functions.

Essential mathematical concepts like expected value and expected interval of fuzzy numbers are basics of this method. As a result, this method is mathematically borne.

As it was said, the Jimenez method is based on expected value and expected interval which was debuted by Yagar [24]. In order to define them, $\tilde{c} = (c^{p}, c^{m}, c^{o})$ triangular fuzzy number is assumed. The below equations can be defined as $\tilde{c}$ membership functions: $μ_{\tilde{c}} (x) = {\begin{matrix} f_{c} (x) = \frac{x - c^{p}}{c^{m} - c^{p}} & if c^{p} \leq x \leq c^{m} \\ 1 & if x = c^{m} \\ g_{c} (x) = \frac{c^{o} - x}{c^{o} - c^{m}} & if c^{m} \leq x \leq c^{o} \\ 0 & if x \leq c^{p} or x \geq c^{o} \end{matrix}$ (11)

Expected interval (EI) and expected value (EV) of $\tilde{c}$ triangular fuzzy number are respectively as follows: $\begin{matrix} EI (\tilde{c}) & = & [E_{1}^{c}, E_{2}^{c}] \\ = & [\int_{0}^{1} f_{c}^{- 1} (x) dx, \int_{0}^{1} g_{c}^{- 1} (x) dx] \\ = & [\frac{1}{2} (c^{p} + c^{m}), \frac{1}{2} (c^{m} + c^{o})] \end{matrix}$ (12) $EV (\tilde{c}) = \frac{E_{1}^{c} + E_{2}^{c}}{2} = \frac{c^{p} + 2 c^{m} + c^{o}}{4}$ (13)

Figure 1 show the EI and EV of $\tilde{c}$ triangular fuzzy number.

Fig.1

EI and EV of $\tilde{c}$ triangular fuzzy number.

Now consider the following fuzzy mathematical programming model in which all of its parameters are defined as triangular or trapezoidal fuzzy numbers: $\begin{matrix} min z = {\tilde{c}}^{t} (x) \\ s . t . \\ {\tilde{a}}_{i} x \geq {\tilde{b}}_{i}, i = 1, \dots, l \\ {\tilde{a}}_{i} x = {\tilde{b}}_{i}, i = 1 + 1, \dots, m \\ x \geq 0 \end{matrix}$ (14)

The below relations are indifferent with the above ones: $\begin{matrix} [(1 - α) E_{2}^{a_{i}} + α E_{1}^{a_{i}}] x \\ \geq α E_{2}^{b_{i}} + (1 - α) E_{1}^{b_{i}}, i = 1, \dots, l \end{matrix}$ (15) $\begin{matrix} [(1 - \frac{α}{2}) E_{2}^{a_{i}} + \frac{α}{2} E_{1}^{a_{i}}] x \\ \geq \frac{α}{2} E_{2}^{b_{i}} + (1 - \frac{α}{2}) E_{1}^{b_{i}}, i = l + 1, \dots, m \end{matrix}$ (16) $\begin{matrix} [\frac{α}{2} E_{2}^{a_{i}} + (1 - \frac{α}{2}) E_{1}^{a_{i}}] x \\ \leq (1 - \frac{α}{2}) E_{2}^{b_{i}} + \frac{α}{2} E_{1}^{b_{i}}, i = l + 1, \dots, m \end{matrix}$ (17)

As a result, by using EI and EV of fuzzy numbers, the crisp model which is equivalent to fuzzy model with α parameter can be characterized as below: $min EV (\tilde{c}) x$ (18) $\begin{matrix} s . t . \\ [(1 - α) E_{2}^{a_{i}} + α E_{1}^{a_{i}}] x \\ \geq α E_{2}^{b_{i}} + (1 - α) E_{1}^{b_{i}}, i = 1, \dots, l \\ [(1 - \frac{α}{2}) E_{2}^{a_{i}} + \frac{α}{2} E_{1}^{a_{i}}] x \geq \frac{α}{2} E_{2}^{b_{i}} + (1 - \frac{α}{2}) E_{1}^{b_{i}}, \\ i = l + 1, \dots, m \\ [\frac{α}{2} E_{2}^{a_{i}} + (1 - \frac{α}{2}) E_{1}^{a_{i}}] x \leq (1 - \frac{α}{2}) E_{2}^{b_{i}} + \frac{α}{2} E_{1}^{b_{i}}, \\ i = l + 1, \dots, m \\ x \geq 0 \end{matrix}$ (19)

3.2 Non-dominated solving genetic algorithm (NSGA-II)

Srinivas and Deb [25] developed the NSGA method based on Goldberg’s suggestion in 1989 [26]. Fonseca and Fleming [27] proposed multi-objective optimization genetic algorithm (MOGA) based on non-dominated sorting process. Horn et al. [28] also used a Pareto domination tournament instead of non-dominated sorting in solving multi-objective optimization problems. Srinivas and Deb [25] established that non-dominated sorted genetic algorithm is more functional than MOGA algorithm, VEGA algorithm and presented algorithm by Horn et al. in 1994 in terms of constant and uniform reproduction on non-dominated solutions. Deb et al. [29] conveyed an elitist non-dominated sorting genetic algorithm (NSGA-II). They demonstrated that the previous algorithms have three fundamental weaknesses: a) computational complexity due to its non-dominating sorting procedure. b) Non-elitist approach c) the need for specifying sharing parameter by user (sharing parameter is used to make diverse solutions).

They illustrated that NSGA-II alleviated all these weaknesses and also works with an elitist non-dominated sorting approach. They also proved that NSGA-II is practically more helpful than two other contemporary evolutionary algorithms namely Pareto archived evolution strategy (PAES) presented by Knowles and Corne (1999) and strength Pareto evolutionary algorithm (SPEA) suggested by Zinzler [30] in discovering a diverse set of solutions and faster convergence near Pareto optimal set.

NSGA-II steps are as following:

Step 1. Initial population production: producing initial population is based on the size and constraints of the problem in this method.

Step 2. Calculating the value of objective functions: all the objective functions’ values must be calculated separately.

Step 3. Performing the non-dominated sorting method: population members are sorted into fronts where the members of first front are a non-dominated set by other members of existing population. For the second front members, the above procedure is repeated and they are only dominated by first front and this iteration continues in other fronts so as to assign a rank to all members based on front numbers. In fact, at this point, members must be sorted in fronts based on domination and the lesser the number of fronts, the more other members get dominated.

Step 4. Calculating crowding-distance parameter: this parameter is calculated for each member and shows the nearness of a front to other ones. The larger this parameter gets, the divergent the set will be.

Step 5. Choosing parents for reproduction: after being sorted in fronts based on non-domination, some members are chosen in order to form the next generation. The binary tournament selection is used for picking members. In this method two members are chosen randomly, they get compared with each other and the better one goes to pool of solutions. By employing binary selection operator method on each generation’s population, a set of members of that generation get selected for mutation and crossover.

Step 6. Mutation and crossover: after selecting members in previous step, a mating pool is formed which is called the selected population. Then in order to create the offspring, population mutation and crossover genetic operators are deployed.

Step 6.1. Crossover operator: at this level the cut-off point (α) must be determined which can be calculated by choosing a random number between 1 to ((number of columns minus 1)). Then the second parts of both chromosomes will be replaced and consequently two offspring are created.

Step 6.2. Mutation operator: at this stage two columns and two rows are chosen randomly and get replaced.

Step 7. Combination of parent and offspring population: this population combines with the main population and then population members get sorted based on some criterions. The best solution would be chosen according to these two criterions:

Step 7.1. Rank priority: in this criterion, solutions with lesser rank or front will be selected since their members can dominate most of others.

Step 7.2. In some cases it is possible that two members with the same rank or front are chosen which in this case we use CD. Then equal to main population members, the top sorted members of archive get accepted and the other ones get eliminated. The accepted ones form the next generation.

Step 8. Stopping criterion: the presented algorithm continues until all the iterations finish. At this point the algorithm has come to an end and stops.

3.3 Multi-objective simulated annealing algorithm (MOSA)

Simulated annealing is a local search algorithm which is able to get out of local optimum attractor. Simplicity, convergence and using specific moves to prevent local optimum attractor are some great features that make this method desirable for scientists. The main idea of SA was based on annealing and cooling process of metals which was proposed by Metropolis et al. [31]. For the first time and was implemented by Kirkpatrick et al. [32]. For solving optimization problems.

When a substance is heated, it begins to expand slowly and thereby its energy increases and leads to atomic disorder, but when the substance is being cooled down gradually, atom configurations seem actually more ordered and to rephrase it the system’s energy decreases physically. SA algorithm which is also called gradual freezing algorithm has been formed based on above physical freezing phenomenon.

The suggested method is a combination of SA method and Tabu search in which the Tabu list is used for solving the problem. First, these parameters should be defined:

T0: initial temperature

C: current temperature decrease rate (cooling rate)

ST: freezing temperature (a temperature in which the desirable energy level is reached)

X: feasible solution

C(X): objective function value for X

The steps of this algorithm are as following:

Step 1. Assuming X_best = φ and choosing an initial feasible solution (X₀) X_best = φ, X = X₀.

Step 2. Generating X_n in X’s neighbourhood.

Step 3. Does the Tabu list include the candidate solution? If yes go to Step 4, otherwise go to Step 5.

Step 4. If C (X_n) ≤ C (X_best), then X = X_n, X_best = X_n. Next, update the Tabu list and go to Step 6 otherwise, follow Step 2 and choose another candidate.

Step 5. Assume ΔC = C (X_n) - C (X).

Step 5.1. If ΔC ≤ 0, then X = X_n. Update the Tabu list and if C (X_n) ≤ C (X_best), then X_best = X_n.

Step 5.2. If ΔC > 0, then y → U (0, 1) and $z = e^{\frac{- Δ c}{T_{0}}}$ . If y < z, then X = X_n.

Step 6. Are T₀ iterations stopped? If yes go to Step 7, otherwise go to Step 2. By the time the amount of accepted solutions under T₀ temperature reach to a particular extent (predefined), the following circumstance should be examined: $\frac{| {AOV}_{c} - {AOV}_{b} |}{{AOV}_{b}} \leq \in$

AOV_c is the average of objective functions’ accepted solutions under T₀ temperature and AOV_b is the average of accepted solutions of objective function’s value under a temperature before T₀. ∈ is also predefined stability value (0 < ∈ <1). If the above condition is met, the iterations under T₀ temperature will be stopped. This was stated by golden [34].

Step 7. T₀ = C × T₀

Step 8. If the algorithm’s stopping criterion T₀ < ST becomes true, the algorithm will stop, otherwise go to Step 2.

3.3.1 Neighborhood search methods and implemented movement functions

According to movement functions’ impact (function which transform a feasible solution to another one in its neighborhood) on algorithm’s performance and quality of solutions, we did our best to test different movement functions and choose the most appropriate and common ones in the algorithm. By considering movement functions variety and change of model’s main variable’s states, exploring solution space and consequently finding efficient solutions are provided effectively. In the following, the chosen movement functions are introduced:

1. In this move, by selecting a customer, we reverse the order of two chosen product’s allocation for the candidate customer. 2. In this move, we first choose two customers and then reverse the order of product’s allocation which was going to go to potential centers. 3. In this move, we choose two distribution centers randomly and reverse the order of allocated customers and products. 4. In this move, we first choose two customers randomly and then we reverse the order of allocated value to distribution centers for a specific product of these two customers. 5. We consider two potential distribution centers for a specific customer and then reverse the order of allocated products to these two centers, in this move. 6. Here, we reverse the process of allocated potential centers to the customers’ product. This takes place by giving the allocated center of first customer’s first products to the first customer’s last product and allocated centers of first customer’s last product goes to first customer’s first product and so on. 7. In this last move, we reverse the order of allocation and sorting of potential customer, therefore the customers and products allocated to first distribution center will be transferred to the last distribution center and vice versa. This transference will be carried out for other centers either.

4 Numerical examples and results

In this section 10 test problems are generated and solved for assessing the proposed solution methods. These 10 consist of different sizes of problem (from minor to major ones). The minor ones include 5 to 10 suppliers, 8 to 15 customers and 4 to 8 vehicles. The major ones include 30 to 50 suppliers, 75 to 120 customers and 15 to 20 vehicles. These problems’ information is displayed in Table 1.

Table 1
Solved test problems’ data

Problem i j k Problem i j k

1 5 8 4 6 15 40 10

2 5 10 6 7 20 50 10

3 8 15 8 8 30 75 15

4 10 15 8 9 30 90 15

5 15 30 10 10 50 120 20

Problem	i	j	k	Problem	i	j	k
1	5	8	4	6	15	40	10
2	5	10	6	7	20	50	10
3	8	15	8	8	30	75	15
4	10	15	8	9	30	90	15
5	15	30	10	10	50	120	20

Maximum transportation time quantity (T) is considered 35 and parameters of MOSA and NSGA-II algorithms are defined as following:

MOSA: npop = 1, nmove = 7 (the number of neighborhood production methods being used in this problem), TF = 1 and the algorithm stops after 500 iterations.

NSGA-II: npop = 30 (initial population members), pm = 0.3 (mutation probability), pc = 0.7 (crossover probability) and the algorithm stops after 40 iterations.

The computed results of solving the former test problems with MOSA and NSGA-II are gathered in Tables 2 and 3.

Table 2

Calculated results with MOSA algorithm

Problem	Number of Pareto solutions	Cost objective function	Contamination objective function	Diversity	Spacing	Solution time
1	3	48862	92.66	72.17	0.21	7.85
2	5	50854	101	235.9	0.87	6.42
3	3	100933	197.66	167.69	0.74	8.54
4	6	96723	196.33	192.91	0.84	8.73
5	7	233847	569.57	317.32	1.56	16.23
6	3	300248	776.33	200.15	1.63	30.69
7	4	410134	951.57	167.38	0.26	32.09
8	5	611569	1627	149.28	0.47	45.12
9	3	754244	2093.66	206.14	0.24	92.35
10	9	974821	2675.33	449.39	0.91	102.43

Table 3

Calculated results with NSGA-II algorithm

Problem	Number of Pareto solutions	Cost objective function	Contamination objective function	Diversity	Spacing	Solution time
1	10	36165	30.5	293.13	0.52	4.56
2	12	42555	40.4	406.03	0.73	5.73
3	13	66431	71.5	381.18	0.99	6.95
4	16	63337	37.62	292.6	0.7	7.22
5	4	171011	254.25	260.92	1.16	15.72
6	7	255606	570	252.16	0.38	23.64
7	11	356728	655.63	496.67	0.6	30.8
8	5	543352	1248.4	324.9	0.88	56.6
9	11	7677255	2108.45	621.39	0.44	74.85
10	7	911726	2260.14	155.64	0.81	118.75

For each problem, some information about the number of Pareto solutions are obtained and objective function values, assessment criterions of algorithm’s performance and solution time for solving a multi-objective problem are also provided. Table 2 depicts the calculated results with MOSA algorithm:

Table 3 also depicts the calculated results with NSGA-II algorithm:

As the above tables demonstrate, it is obvious that both methods are perfectly capable of solving fuzzy transportation problem with different sizes in a quick time. The greatest problem in size was solved in less than 2 minutes (118.75 seconds, precisely). By comparing the calculated results in above tables, it can be concluded that MOSA algorithm has a better performance than NSGA-II. MOSA algorithm computes a lesser value for transportation cost objective function in 9 out of 10 problems. In all 10 problems, the calculated solutions given by MOSA have lesser emissions than NSGA-II. The number of Pareto solutions gained by this algorithm are also tremendously more than NSGA-II ones. In average, MOSA generates Pareto solutions twice as much as NSGA-II (10 to 5). In 8 problems, the solution time by using MOSA algorithm is quicker than NSGA-II, but for sure, solution time of both algorithms are noticeable and they do not have significant differences. The results of diversity and spacing criterions also prove that MOSA algorithm has priority over NSGA-II. The following charts display the convergence of these two algorithms near the optimal solution:

The Figs. 2 to 5 illustrate that both algorithms have a quick and suitable convergence near optimal solutions which is evident in their quick solution times.

Fig.2

Obtained Pareto solutions with NSGA- II for problem 4.

Fig.3

Obtained Pareto solutions with MOSA for problem 4.

Fig.4

Obtained Pareto solutions with NSGA-II for problem 10.

Fig.5

Obtained Pareto solutions with MOSA for problem 10.

5 Conclusion

In this paper, a two-objective transportation problem with assuming uncertain transportation cost and supply and demand quantity is proposed. In addition to minimizing the costs, an effort was also made to minimize the vehicles’ pollutant emissions. A fuzzy approach is used to cope with uncertainty in our considered transportation problem and all the imprecise parameters are considered as triangular fuzzy numbers. A fuzzy two-objective linear programming model is proposed for our problem and Jimenez method was implemented to offer the equivalent crisp model. According to lack of usage in applying meta-heuristic methods on transportation problems in the literature, MOSA and NSGA-II meta-heuristic methods are used. The computed results show that by solving 10 test problems with the suggested algorithms, both methods are able to solve different sizes of fuzzy transportation problems in a quick time, but in general, MOSA was found more beneficial and had better performance than NSGA-II. Not only it generates solutions for objective functions, but also MOSA obtains more Pareto solutions and consumes less time to solve.

References

Hitchcock

F.L.

, The distribution of a product from several sources to numerous localities, J Math Phys 20(2) (1941), 224–230.

Charnes

and Cooper

W.W.

, The stepping stone method of explaining linear programming calculations in transportation problems, Management Science 1(1) (1954), 49–69.

Dantzig

G.B.

, Linear programming and extensions, Princeton University Press, 1965.

Zadeh

L.A.

, Fuzzy sets, Information and Control 8(3) (1965), 338–353.

Zimmermann

H.-J.

, Fuzzy programming and linear programming with several objective functions, Fuzzy Sets and Systems 1(1) (1978), 45–55.

ÓhÉigeartaigh

, A fuzzy transportation algorithm, Fuzzy Sets and Systems 8(3) (1982), 235–243.

Chanas

, Kołodziejczyk

and Machaj

, A fuzzy approach to the transportation problem, Fuzzy Sets and Systems 13(3) (1984), 211–221.

Chanas

and Kuchta

, A concept of the optimal solution of the transportation problem with fuzzy cost coefficients, Fuzzy Sets and Systems 82(3) (1996), 299–305.

Saad

O.M.

, A parametric study on transportation problem under fuzzy environment, 2002.

10.

Liu

S.-T.

and Kao

, Solving fuzzy transportation problems based on extension principle, European Journal of Operational Research 153(3) (2004), 661–674.

11.

Gani

and Razak

K.A.

, Two stage fuzzy transportation problem, Journal of Physical Sciences 10(1) (2006), 63–69.

12.

Gupta

and Mehlawat

M.K.

, An algorithm for a fuzzy transportation problem to select a new type of coal for a steel manufacturing unit, Top 15(1) (2007), 114–137.

13.

Dinagar

D.S.

and Palanivel

, The transportation problem in fuzzy environment, International Journal of Algorithms, Computing and Mathematics 2(3) (2009), 65–71.

14.

Pandian

and Natarajan

, A new algorithm for finding a fuzzy optimal solution for fuzzy transportation problems, Applied Mathematical Sciences 4(2) (2010), 79–90.

15.

Kaur

and Kumar

, A new method for solving fuzzy transportation problems using ranking function, Applied Mathematical Modelling 35(12) (2011), 5652–5661.

16.

Keshavarz

and Khorram

, A fuzzy bi-criteria transportation problem, Computers & Industrial Engineering 61(4) (2011), 947–957.

17.

Kundu

, Kar

and Maiti

, Fixed charge transportation problem with type-2 fuzzy variables, Information Sciences 255 (2014), 170–186.

18.

Bellman

R.E.

and Zadeh

L.A.

, Decision-making in a fuzzy environment, Management Science 17(4) (1970), B141–B-164.

19.

Werners

, An interactive fuzzy programming system, Fuzzy Sets and Systems 23(1) (1987), 131–147.

20.

Zimmermann

, Fuzzy Set Theory and Its Applications Second, Revised Edition, Springer, 1992.

21.

Lai

and Hwang

, Fuzzy Mathematical Programming: Methods and Applications, Springer, Berlin, 1992.

22.

Jiménez

, Arenas

and Bilbao

, Linear programming with fuzzy parameters: An interactive method resolution, European Journal of Operational Research 177(3) (2007), 1599–1609.

23.

Jiménez

, Ranking fuzzy numbers through the comparison of its expected intervals, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 4(04) (1996), 379–388.

24.

Yager

R.R.

, A procedure for ordering fuzzy subsets of the unit interval, Information Sciences 24(2) (1981), 143–161.

25.

Srinivas

and Deb

, Multi objective optimization using none dominated sorting in genetic algorithms, Evolutionary Computation 2(3) (1994), 221–248.

26.

Goldberg

D.E.

, Genetic algorithms in search, optimization, and machine learning, Addison-wesley Reading Menlo Park, Vol. 412, 1989.

27.

Fonseca

C.M.

and Fleming

P.J.

, Genetic algorithms for multi objective optimization: Formulation discussion and generalization, ICGA 93 (1993), 416–423.

28.

Horn

, Nafpliotis

and Goldberg

D.E.

, A niched Pareto genetic algorithm for multi objective optimization, In Evolutionary Computation, 1994 IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on, 1994, IEEE.

29.

Deb

, et al., A fast and elitist multi objective genetic algorithm: NSGA-II, Evolutionary Computation, IEEE Transactions on 6(2) (2002), 182–197.

30.

Zitzler

and Thiele

, Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, Evolutionary Computation, IEEE Transactions on 3(4) (1999), 257–271.

31.

Metropolis

, et al., Combinatorial minimization, J Chem Phys 21 (1953), 1087–1092.

32.

Kirkpatrick

and Vecchi

, Optimization by simulated annealing, Science 220(4598) (1983), 671–680.

33.

Harrisa

, Mumfordb

C.L.

and Naim

M.M.

, A hybrid multi-objective approach to capacitated facility location with flexible store allocation for green logistics modelling, Transportation Research Part E: Logistics and Transportation Review, Volume 66, 2014, pp. 1–22.

34.

Bandyopadhyay

and Bhattacharya

, Applying modified NSGA-II for bi-objective supply chain problem, J Intell Manuf 24 (2013), 707–716.

35.

Baykasoğlu

and Subulan

, Constrained fuzzy arithmetic approach to fuzzy transportation problems with fuzzy decision variables, Expert Systems with Applications 81 (2017), 193–222.

36.

, Li

, Yu

, Dan

and Zhou

, Multi-depot vehicle routing problem for hazardous materials transportation: A fuzzy bi level programming, Information Sciences 399 (2017), 201–218.

37.

Ebrahimnejad

, A new method for solving fuzzy transportation problem with LR flat fuzzy numbers, Information Sciences 357 (2016), 108–124.

38.

Baidya

, Bera

U.K.