Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.14 No.1 pp.11-21
DOI : https://doi.org/10.7232/iems.2015.14.1.011

Differential Evolution Algorithms Solving a Multi-Objective, Source and Stage Location-Allocation Problem

Thongpoon Thongdee*, Rapeepan Pitakaso
Department of Industrial Engineering, Faculty of Engineering Ubon Ratchathani University, Ubon Ratchathani, Thailand
Corresponding Author, E-mail: tommy.thongdee@gmail.com
January 19, 2014 November 11, 2014 March 13, 2015

ABSTRACT

The purpose of this research is to develop algorithms using the Differential Evolution Algorithm (DE) to solve a multi-objective, sources and stages location-allocation problem. The development process starts from the design of a standard DE, then modifies the recombination process of the DE in order improve the efficiency of the standard DE. The modified algorithm is called modified DE. The proposed algorithms have been tested with one real case study (large size problem) and 2 randomly selected data sets (small and medium size problems). The computational results show that the modified DE gives better solutions and uses less computational time than the standard DE. The proposed heuristics can find solutions 0 to 3.56% different from the optimal solution in small test instances, while differences are 1.4-3.5% higher than that of the lower bound generated by optimization software in medium and large test instances, while using more than 99% less computational time than the optimization software.


초록


    Ubon Ratchathani University

    1.NTRODUCTION

    This research aims to study the multi-objectives, multisources and multi stages location-allocation problem. The problem is to determine the suitable location of ethanol plants. The ethanol plants can use 2 types of raw material (multi sources) which are (1) bagasse and (2) cassava pulp. An ethanol plant can produce ethanol from a single source which is bagasse or cassava pulp or produce it from both sources of raw materials in the same factory. The ethanol plants also have to make a decision about which one of the blending centers they will deliver their produced ethanol to (multi-stages). Initially, Buddadee et al. (2008, 2009) studied the location selection of ethanol plants using bagasse by studying the effect of economic value and environmental impact. It was found that using bagasse is cost effective and helped reduce the environmental impact in terms of reducing greenhouse gas emissions to the atmosphere. Later, Nanthasamroeng et al. (2008) studied the solutions to the problem of selecting the location of an ethanol plant fed with bagasse using a multi-objective approach.

    This research has studied the same problem as Nanthasamroeng et al. (2008), but the form of the problem has been extended to having multi-sources of raw materials, which means it takes into account the source of raw materials used to produce ethanol, whether bagasse or cassava pulp. This problem cannot be solved by optimization software due to the hardness of the problem. When increasing the size of the sources of raw materials and the potential locations to open an ethanol plant, it was found that the software was not able to solve the problem due to memory limitations and the hardness of the problem. Therefore, it is necessary to develop a metaheuristic to help in finding good solutions within an acceptable computational time. Therefore, the contributions of this research are categorized as follows:

    1. We present a mathematical model for the multiobjectives, multi-stages and multi-sources locationallocation problem.

    2. We present a modified differential evolution algorithm which improves on the standard DE in order to enhance the effectiveness of the algorithm.

    The literature review is presented in section 2. Section 3 gives the problem statement. Sections 4 and 5 present the proposed heuristics and the computational results while section 6 is the conclusion of the article.

    2.LITERATURE REVIEW

    Metaheuristics play an important rule in solving many combinatorial optimization problems. There are many metaheuristics that have been successfully used to solve various problems such as Ant Colony Optimization (ACO), Tabu Search (TS), Genetics Algorithm (GA), Particle Swarm Optimization (PSO) and Differential Evolution Algorithm (DE) etc.

    Ant Colony Optimization (ACO) (Doerner et al., 2007), is a methodology that mimics the behavior of an ant colony foraging for food. When determining the food foraging behavior of ants through a numerical analysis, this methodology will give appropriate results for a specific area, but there are limitations of the application in terms of the determination of restrictions. If the function has many Local Optima and they are equal or similar, it may not find the Global Optima, which is similar to the behavior of ants when finding foods in the same quantities in several areas. Many ants will swarm the foods only in the area that has been found first, instead of swarming equally over all food sources, but if it has optimum rounds of searching then it will find the Global Optima. It is therefore a methodology where parameters should be chosen cautiously.

    Tabu Search (TS) (Lin and Kwok, 2006; Drezner et al., 2006; Caballero et al., 2007 and Uno and Katagiri, 2008) is a methodology similar to Simulated Annealing which is a methodology of learning through experience. It applies a better way to find answers by recognizing and protecting the traditional values that are worse in the Tabu List, which will help improve the next round of searching until it reaches the acceptable threshold. However, this methodology relies heavily on the memory of the computer. As a result, it makes the work more complex.

    Particle Swarm Optimization (PSO) (Thongdee and Pitakaso, 2013) is a stochastic based methodology for determining suitability inspired by the behavior of dispersed particles as a group, such as a group of birds that are flying in a flock. PSO consists of a group of particles that are in motion in multiple dimensions, which find solutions based on the actual number of individual particles. The position and velocity vectors are stored in the memory and compared to the neighbor particles, and then the algorithm selects particles with high potential velocity and direction vectors, moving in new directions until arriving at the Global Solution Vector.

    Genetic Algorithms (GAs) (Xu et al., 2008; Doerner et al., 2009; Leung, 2007) are a stochastic based methodology for determining the suitability of a solution with a genetic hypothesis that mimics Natural Evolution, based on the concept of the selection of species by means of natural selection. It can be applied well to numerical analysis in finding solutions that are complex with many variables and conditions

    Differential Evolution (DE) (Medaglia et al., 2009 and Raisanen) is a stochastic based methodology for determining the solution suitability and is random based in Global Search Space. It finds comprehensive solutions with the genetic hypothesis, as in GAs, but it has a distinct advantage as it has less complexity of the methodology and makes more generalizations. It can also use Floating Point Real Numbers in the calculation without the need to convert the decision variables into the binary numeral systems, so that these are the main reasons that make the DE methodology fast and with the robustness to find more answers than other methodologies.

    3.THE PROBLEM STATEMENT

    Since the proposed problem is a new class of location- allocation problem, there are two ways to represent the problem and these are presented below. The general framework of the proposed problem is explained in the case study shown in section 3.1. The mathematical model of the proposed problem is shown in section 3.2.

    3.1.A Case Study of a Bagasse and Cassava Pulp Ethanol Plant in Northeastern Thailand

    Figure 1 shows the framework of the multi-stages, multi-sources location-allocation problem. The problem addressed here aims to find suitable locations for ethanol plants with the lowest operating costs, environmental impact and security risk. These ethanol plants operate using two raw materials which are bagasse and cassava pulp and they need to deliver ethanol to the blending centers.

    16 sugar plants and 46 starch plants in the Northeast have been designated as sources of raw materials which are spread out in different provinces as shown in Figure 2.

    The case study on the location of ethanol plants in the northeastern area of Thailand involves solving for the three objectives as follows; 1) Economic objectives: cost reduction on transportation and plant construction,

    2) Environmental objectives: the reduction of greenhouse gas emissions from all processes of production and transportation and 3) Safety: which aims to minimize the risk for people who live in the transportation area if the leakage happens.

    3.2.Mathematical Models for Selecting the Plant Location

    3.2.1.Decision factors

    Oωij = The bagasse volume transport route (i, j): (Ton)

    OΩtj = The cassava pulp volume transport route (i, j): (Ton)

    ejk = The ethanol volume transport route (j, k): (Liter)

    Hωi = Bagasse volume availability at source i: (Ton)

    HΩt = Cassava pulp volume availability at source t: (Ton)

    3.2.2.Parameters

    i = The number of sugar plants: (Plant)

    j = The number of ethanol plants: (Plant)

    k = The number of tank farms: (Plant)

    t = The number of tapioca flour plants: (Plant)

    m1 = Material price per unit for bagasse: (Baht/Ton)

    m2 = Material price per unit for cassava pulp: (Baht/Ton)

    θ = Material transportation cost per unit: (Baht/km./Ton)

    a = Ethanol transportation cost per unit: (Baht/km./Liter)

    dωij = The distance between bagasse sources and the ethanol plant (i, j): (km.)

    dΩtj = The distance between cassava pulp sources and the ethanol plant (t, j): (km.)

    rjk = The distance between the ethanol plant and tank farms j, k: (km.)

    POTRjk = The population number at risk from the transportation of ethanol ( j, k)

    POFRj = The population number at risk from the ethanol plant ( j)

    FBCj = Additional cost of new ethanol plant, in case of receiving raw material with both bagasse and cassava pulp: (Baht)

    FBj = Additional cost of new ethanol plant, in case of receiving raw material as only bagasse: (Baht)

    FCj = Additional cost of new ethanol plant, in case of receiving raw material as only cassava pulp: (Baht)

    KBCj = Number of maximum raw material transports to ethanol plant, in case of receiving raw material as both bagasse and cassava pulp: (Ton)

    KBj = Number of maximum raw material transport to ethanol plant, in case of receiving raw material as only bagasse: (Ton)

    KCj = Number of maximum raw material transports to ethanol plant, in case of receiving raw material as only cassava pulp: (Ton)

    γ = Emission factor for transportation from(i, j) , (t, j) and ( j, k): (Baht/km./Ton)

    l = Emission factor using diesel for transport from(i, j) , (t, j) and (j, k): (Baht/km./Ton)

    f = Emission factor for chemical substances to produce ethanol: (Baht/Ton)

    g = Emission factor of CO2 from producing ethanol: (Baht/Ton)

    h = Emission factor of CH4 from producing ethanol: (Baht/Ton)

    δ = Emission factor of electricity production to produce ethanol: (Baht/Ton)

    v = Offset emission factor of E10 from producing ethanol to be the Gasohol: (Baht/Ton)

    w = Offset emission factor of Gasoline from producing ethanol to be the Gasohol: (Baht/Ton)

    λ1 = Production efficiency factor for changing raw material to be ethanol from bagasse: (Liter/Ton)

    λ2 = Production efficiency factor for changing raw material to be ethanol from cassava pulp: (Liter/Ton)

    u = Cost of risk per unit: (Bath/Opportunity risk)

    3.2.3.Mathematical Models

    Economic Objectives Minimize

    Minimize m1 × j = 1 J i = 1 I O ij ω y ij + m2 × j = 1 J t = 1 T O tj Ω S tj + j = 1 J i = 1 I θ O ij ω d ij ω y ij + j = 1 J t = 1 T θ O tj Ω d tj Ω S tj + j = 1 J FBC j Q j β + j = 1 J FB j Q j ψ + j = 1 J FC j Q j φ + k = 1 K j = 1 J ae jk r jk x jk

    Environmental Objectives Minimize

    γ + l j = 1 J i = 1 I d ij ω O ij ω y ij + j = 1 J t = 1 T d ij Ω O tj Ω S tj + k = 1 K j = 1 J r jk e jk x jk + f + g + h + δ + v + w j = 1 J i = 1 I O ij ω y ij + j = 1 J i = 1 I O tj Ω S tj

    Social Risk Objectives

    Minimize

    k = 1 K uPOTR jk x jk + j = 1 J μ POFR j Q j β + j = 1 J μ POFR j Q j ψ + j = 1 J μ POFR j Q j φ

    Constraints

    Subject to

    i = 1 I H i ω + t = 1 T H t Ω Q j β KBC j + Q j ψ KB j + Q j φ KC j j
    (1)
    λ 1 i = 1 I H i ω + λ 2 t = 1 T H t Ω k = 1 K e jk j
    (2)
    Q j β + Q j ψ + Q j φ 1 j
    (3)
    Q j β = 1 if ethanol plant j is open for two sources 0 otherwise j
    (4)
    Q j ψ = 1 if ethanol plant j is open for bagasse 0 otherwise j
    (5)
    Q j φ = 1 if ethanol plant j is open for cassava pulp 0 otherwise j
    (6)
    i = 1 I O ij ω y ij = H i ω i
    (7)
    i = 1 I y ij 1 j
    (8)
    y ij = 1 if bagasse from i send material to plant j 0 otherwise j
    (9)
    t = 1 T O tj Ω S tj = H t Ω t
    (10)
    t = 1 T S tj 1 j
    (11)
    S tj = 1 if cassava pulp from t send material to plant j 0 otherwise j
    (12)
    k = 1 K x jk 1 k
    (13)
    x jk = 1 if plant j send ethanol to blending centre k 0 otherwise k
    (14)
    y ij Q j β + Q j ψ i , j
    (15)
    s tj Q j β + Q j φ t , j
    (16)

    The Economic objective is composed of four terms which are: 1) Cost equation of raw materials, which depends on the quantity and price of raw materials; 2) Cost equation of transportation of raw materials, depending on the quantity of raw materials, distance and price per unit of transportation of raw materials; 3) Cost of construction of ethanol plant, which depends on the production capacity per day and 4) Cost equation of transporting ethanol, which is based on the amount of ethanol, distance and the cost per unit of transporting ethanol.

    Environmental objectives refer to the study of Nanthasamroeng et al. (2008) which considers the amount of greenhouse gas emission from the different processes consisting of two main terms: 1) The amount of greenhouse gases caused by transportation and the amount of greenhouse gases arising from the use of diesel fuel in transportation. This term is based on the amount of bagasse, cassava pulp and ethanol which are transported and the distance of transportation and 2) The amount of greenhouse gases resulting from the use of chemicals in the production of ethanol, the greenhouse gas carbon dioxide from the production of ethanol, the amount of greenhouse gas methane from the production of ethanol, the amount of greenhouse gases from electricity production to produce ethanol, compensation of bagasse and cassava pulp to bring it to produce ethanol to be used as Gasohol and the compensation to bring the bagasse and cassava pulp to produce ethanol to be used as Gasohol instead of normal gasoline. This term is mainly based on the amount of bagasse and cassava pulp.

    Social risk objectives are referenced and updated from Nanthasamroeng et al. (2008) and are: 1) It will utilize the number of population which will be affected by a leakage during transportation of ethanol from plants to the tank farm and 2) It will utilize the density of population per unit area around the ethanol plant which would be affected in the event of leakage or explosion of the ethanol production plant.

    Constraints including: (1) The constraint of mass balancing bagasse and cassava pulp which must not be over the requirement of all 3 plants; (2) The constraint of mass balancing ethanol produced from bagasse and cassava pulp is not over the amount of delivered ethanol; (3), (4), (5) and (6) The decision factors for whether the plant shall be established for only bagasse or cassava pulp using only one source, or using both sources of raw material to produce ethanol; (7) is the constraint that is used to ensure that the transported raw material out from node i will not exceed its capacity; (8) Ensure that the bagasse suppliers have to deliver their material to at least 1 ethanol plant; (9) The bagasse suppliers will deliver the bagasse to the ethanol plant or not (zero-one constraint); (10) To ensure that the transported raw material out from node t will not exceed its capacity; En sure that the cassava pulp suppliers have to deliver their material to at least 1 ethanol plant; (12) The cassava pulp supplier will deliver the cassava pulp to the ethanol plant or not; (13) The ethanol plants will deliver the ethanol to at least one blending center; (14) The decision factor that the ethanol plant will deliver the ethanol to the blending center or not and (15) and (16) A specified ethanol plant can receive the raw material from a single source (bagasse or cassava pulp) and two sources (bagasse and cassava pulp)

    4.THE PROPOSED HEURISTICS

    In this section, we will present two algorithms which are (1) standard DE and (2) Modified DE to solve the multi-objectives, multi-stages and multi-sources location- allocation problem.

    4.1.Standard DE

    DE, in general, is composed of 4 main steps which are: (1) Initialization which is used in the first iteration of the algorithm. All parameters are set and some random numbers are initiated; (2) Mutation process which is iteratively used as the first step of the evolution of the algorithm; (3) Recombination process which is the second step of the evolution and (4) Selection process will be used as the last step of the evolution of the proposed heuristic. The pseudo code of these four steps is shown in Figure 3 while the flow chart of the proposed algorithm is shown in Figure 4.

    4.1.1.Initialization

    The researcher has applied the beginning solution process, which is inspired by the Genetic Algorithm (GA), by determining the number of vectors to be equal to the number of potential ethanol plants. The crossing position in a vector will be the parts of sugar plant, starch plant and blending center which are the horizontal cells, while the ethanol plant is the vertical cells.

    When finding the beginning solution of the algorithm, we start from the determination of the initial vector. Then, we generate a random number with values ranging from 0.0-1.0 for each array element in the vector. The vector has dimension of (M2+K)×M1 while M1 = 5 (Number of Ethanol Plants (j)) and M2 = 62 (16 Sugar plants (i) plus 46 Starch plants (t)) and K= 4 (4 Gasohol mixing or blending centers (k)). An example of a vector is shown in Table 1.

    From Table 1 we can get the solution of the problem using the following procedure. First we will assign sugar (plant which generates bagasse) (i) and starch (plants which produce cassava pulp) plants (t) to an ethanol plant (j) by assigning sugar or starch plants (i and t) to ethanol plants (j) that have the highest value in position of vector in a specific row j or t. For example, from Table 1, we can see that sugar plant 1 (i = 1) will deliver their product to ethanol plant 4 (j = 4) due to the highest value in position of row i = 1 is 0.7 which corresponds to j = 4. The same comparison will be executed for all i = 1 to i = 5 thus sugar plants 2, 3, 4 and 5 will deliver their product to ethanol plants 4, 1, 1 and 5 respectively. The starch plant t will use the same procedure to assign it to an ethanol plant j. Therefore, starch plants 1, 2, 3, 4 and 5 deliver their product to ethanol plants 2, 5, 5, 4 and 5 respectively. The assigning of ethano plant j to blending center k uses a different way. Instead of finding the highest value in a row, the highest value in column j (only from k = 1 to k = highest number of k. For example in Table 1k runs from 1 to 4) will be selected. From Table 1, the ethanol plants that are selected to operate are ethanol plants 1, 2, 3, 4 and 5. Ethanol plant 1 will deliver its ethanol to blending center 4 because blending center 4 has value in position equaled to 0.97 which is the highest value among all k (0.54, 0.61, 0.37, 0.97). Ethanol plants 2, 3, 4 and 5 will select to deliver their products to blending centers 4, 3, 2 and 3 respectivel

    4.1.2.Mutation Process

    The mutation process can be executed using formula (17). 3 vectors are randomly selected from all vectors that are generated in each iteration to form a mutant vector.

    V i , g = X r1 , g + F X r2 , g X r3 , g
    (17)

    It is noted that Xr1, Xr2, Xr3 must be different from vector Xi,g . F is a scaling factor which is used to control the degree of difference of two selected vectors. An example of mutant solution is shown in Table 2.

    4.1.3.Recombination Process

    The trial vector Ui,g will be generated from formula (18). The vector will select the position’s value from Xi,g or Vi,g depending on the control parameter Cr (crossover rate) and the random number Uj.

    u j , i , g = v j , i , g , if u j c r or j = j u x j , i , g , otherwise
    (18)

    Eq. (18) explains that when generating the random value of each array value in the vector which lies from 0 to 1, if the value is less than or equal to Cr (Crossover Rate) then select the value in the position of the vector obtained from the mutant vector, otherwise choose the value obtained from the target vector.

    As an example of the calculation, assume that Cr = 0.8, then make a random number such as 0.45, and if we assume that the position of the cell is i1: j1, so we must choose the answer which is 1.01. Similarly to the trial vector, if the position is i1: j3, if making a random number, supposing we get 0.97, so we must choose the number 0.14 as an answer of the trial vector. All the details are shown in Table 3.

    4.1.4.Selection Process

    The selection process is used to select the better vector between the target vector Xi,g and the trial vector Ui,g. The better vector will be selected to be the target vector in the next iteration Xi,g+1. The selection process can be executed using formula (19).

    x i , g + 1 = U i , g , if f U i , g f x i , g x i , g , otherwise
    (19)

    4.2.DE Modified (MODDE)

    Standard DE, as we have explained above, uses a formula (formula (17)) which is found in much literature to generate a mutant vector. It is the only one process out of three processes used in the DE mechanism (mutation, recombination and selection process) that has communication between different vectors. The recombination process is the exchange of values in position between mutant vector and the original target vector, while the selection process is used to select the better between the trial vector and the original target vector to survive for the next iteration. The comparison has been made only in the same vector number (e.g. target vector 1 and trial vector 1). We can see that the communication between vectors has been made only in the mutation process. Three target vectors have been randomly selected. These three target vectors do not use the solution quality of the vectors to guide the selection mechanism. In Modified DE which will be presented here, the best vector among all vectors will be integrated into formula (18) in order to guide the search mechanism of the original DE to a good solution. The new recombination formula is presented in formula (20). Moreover, in modified DE, parameter F and Cr will be designed to be the selfadjusted parameter.

    u j , i , g = X j , i , g if u j C r1 + C r2 X j , i , g best if C r1 u j C r1 + C r2 V j , i , g if u j C r1
    (20)

    where Cr1 and Cr2 are randomly generated (between 0 and 1) and Cr1+Cr2 ≤ 1. For example, we may assume that Cr1 = 0.4, Cr2 = 0.5, and then make random numbers. Assuming that we have uj equal to 0.45. which is greater than Cr1 but less than Cr1+Cr2 (0.9) the value in that position of that vector will be equal to the value in that position of the best vector Xbestj,i,g Both Cr are also set to be auto adjusted. All the details are shown in Table 4.

    In order to execute the self-adjusted parameters (F, Cr1 and Cr2), each of the self-adjusted parameters will be divided into 3 levels. The first level is the medium level. In this level the parameters will use the current best parameters (best F, Cr1 and Cr2) while the second level (high) and the third level (low) will use the current best parameter plus 5% (high group) and minus 5% (low group) respectively. If NP is the number of vectors in each- iteration of the experiment, the self-adjusted parameters (F, Cr1 and Cr2) will be equally divided into 3 groups. Each group of vectors will use high, medium and low levels of the self-adjusted parameters. The current best self-adjusted parameters will be changed to the level of parameters from which the group of vectors generates the best average result among three groups of vectors. Finally, if Cr1+Cr2 is greater than 1, we need to be re-scale to let Cr1+Cr2 be less than or equal to 1.

    5.THE COMPUTATIONAL RESULTS

    In this section, we have two parts of the computational results. In the first part, the proposed algorithms are compared with the result obtained from the optimization software to prove that the proposed heuristics are effective at finding a good solution. In the second part, we will compare the effectiveness of the two proposed heuristics in finding the solution in the case study presented in this article.

    5.1.Comparing the Proposed Heuristics with the Result Generated from LINGO v.11

    The LINGO program cannot solve multi-objec-tive models. The mathematical model shown in section 3.2 is programed in LINGO v.11. In order to let the model be solved, the multi-objectives model is programed in terms of single objectives with multipurposes (social risk, environment impact and economics). Each purpose is determined to have the same importance (equal weight). The algorithms are coded with C++ and run on a PC Intel ® Core™ i5-2467M CPU 1.6GHz. The proposed algorithms are tested with 3 test instances which are small, medium and large test instances. The large test instance (I16-T46-J5-K4) is the test instance which is the case study in the Northeastern part of Thailand. This case study is composed of 16 sugar plants and 46 starch plants, 5 potential ethanol plants and 4 blending centers. Due to it being a large test instance, LINGO v.11 cannot find the optimal solution. Therefore, to compare the proposed algorithms in this instance, the lower bound was obtained from LINGO v.11 within 4 hours 43 mins (Objective Bound).

    The small and medium test instances are smaller versions of the large instance. Some numbers of sugar and starch plants are randomly selected while using the same number of potential ethanol plants and blending centers. The small test instance (I5-T5-J5-K4) is composed of 5 sugar and 5 starch plants. The medium test instance (I10-T26-J5-K4) is composed of 10 sugar and 26 starch plants. The computational results are shown in Table 5.

    From Table 5, in the small test instance, standard DE and modified DE can find a quality solution 1.76% and 0.98% worse than the optimal solution, while being 99.89% faster in computational time.

    In the medium test instance, LINGO v.11 cannot find the optimal solution, thus the objective bound within 2 hours and 41 minutes (the first time that the objective bound is reported in LINGO v.11) is compared with the proposed algorithms. From Table 5, standard DE and modified DE find answers 6.05% and 3.14% away from the lower bound, while using 107.66 and 110.99 seconds to obtain that solution.

    Remark:

    • 1aLingo test by global optimization (runtime 27: 29: 40, hh: mm: ss)

    • 1bLingo test by lower bound (runtime 2: 41: 40, hh: mm: ss)

    • 1cLingo test by lower bound (runtime 4: 43: 08, hh: mm: ss)

    • 2DE test by Dev-C++ Program (2aDE STD, 2bMODDE)

    In the large test instance, the LINGO runtime to find the first objective bound is 4 hours and 43 minutes. The proposed algorithms (standard DE and modified DE) can find a quality solution 4 .75% and 6.38% away from the bound while using only 129.8 and 133.07 seconds to obtain that solution.

    Table 6 shows the results of the case study which was obtained from the modified DE while Figure 5 shows the map of transportation route of the result obtained from the algorithm.

    5.2.Comparing the Effectiveness of the Two Proposed Heuristics

    In general, when dealing with multi-objective problems, the pareto front technique is often used to compare the effectiveness of the algorithm. Since it is impossible to have only one answer to give the best of all objectives simultaneously for multi-objective problems, the group of the ideal answers to this problem is the answer that is not dominated when compared to all the answers. That solution can be obtained by means of the Pareto which is the principle of “Pareto Domination.”

    This research has used the Pareto technique as well, by determining weights for each objective. The weight obtained has come randomly in each round of calculations. This is the principle to approach the process of domination until getting various solutions. The results of the Pareto are shown in Figures 6, 7 and 8.

    Referring to Figures 6, 7 and 8 for each loop of the experiments with multi-objectives, the algorithms have assigned a random weight equal to the number of objectives. For example, if we have 3 objectives in the case study, the algorithm will choose a random weight to three values (w1, w2, w3). Then, these three values will be re-calculated such as w’1 = w1/(w1+w2+w3). The values which are obtained from the calculation will be multiplied with the objective functions, such as the objective number 1 (f’1 = w’1*f1). This principle will result in getting various solutions for multi objectives problem.

    Comparing the standard DE and modified DE in finding the Pareto Front: (1) The average number of pareto-optimal solution (ANP) and (2) average ratio of pareto-optimal solutions (ARP) are used to reveal the effectiveness of the proposed algorithms to solve the case study. N is the number of iterations in one experiment. n1, n2, …, nk is the number of pareto-optimal solutions found in the kth experiment and K is the total number of experiments. Therefore, the ANP and ARP can be calculated by using formulas (21) and (22).

    ANP = n 1 + n 2 + n 3 + ... + n k K
    (21)
    ANP = n 1 N + n 2 N + n 3 N + ... + n k N K
    (22)

    The results of ANP and ARP are shown in Table 7. From Table 7, we will see that the Modified DE outperforms standard DE in order to find better number for ANP and ARP. Modified DE can find an average number of pareto-optimal solutions at 83.2 solutions while standard DE can find 74.7 solutions. Comparing ARP, modified DE has an average ratio equal to 0.416 which is higher than that of standard DE which has a ratio equal to 0.3735.

    6.CONCLUSIONS

    In this article we present the mathematical model for the multi-stages, multi-sources and multi-objectives location-allocation problem. The case study which is used here is composed of 16 sugar and 46 starch plants, 5 potential ethanol plants and 4 blending centers. Another 2 test instances are selected from the case study.

    We presented differential evolution and modified differential evolution algorithms to solve this problem and compared our algorithm with the optimal solution or the objective bound obtained from LINGO v.11 depending on the size of the test instances.

    In the modified DE, the new recombination formula (equation 20) has been proposed. The computational result in all test instances shows that the proposed algorithms can find solutions 0.98% to 1.76% away from the optimal solution (small test instance) while it can find 3.14 % to 8.32 % worse than the objective bound generated by LINGO v.11 (medium and large instances). The computational time used to obtain this solution is 99.22% to 99.89% lower than that of the optimization software.

    We also compared the efficiency of standard DE and modified DE to find the ANP and ARP. From the computational result we can see that modified DE outperforms standard DE in finding better solutions in both key performance measures (ANP and ARP).

    Figure

    IEMS-14-11_F1.gif

    The supply chain of the Ethanol production for mixing to produce gasohol.

    IEMS-14-11_F2.gif

    Location of Sugar plants, Starch plants, Ethanol Plant and the Gasohol mixing plant in North- Eastern Thailand.

    IEMS-14-11_F3.gif

    Pseudo code for the DE algorithm.

    IEMS-14-11_F4.gif

    Development Flow Chart for DE algorithm.

    IEMS-14-11_F5.gif

    The routing of raw material transportation to Ethanol plant, and from the plant to Tank farm.

    IEMS-14-11_F6.gif

    Show the Pareto front for multi-objectives.

    IEMS-14-11_F7.gif

    Show the Pareto front comparing between economics and social risk.

    Show the Pareto front comparing between economics and environmental impact.

    Table

    The beginning solution of the DE algorithm

    The mutation solution of the DE algorithm

    The recombination solution of the DE algorithm

    The recombination solution of the MODDE algorithm

    The comparison of performance between LINGO 11.0 and DE algorithm

    Selection location of Ethanol plant produced from Bagasse and Cassava pulp

    ANP and ARP of the proposed algorithms

    Exp.No=Experiment Number, #iteration=Number of Iterations. #Pareto = number of Pareto fronts found during the experiment. Ratio= (#Pareto)/(#iteration).

    REFERENCES

    1. Buddadee B , Wirojanagud W , Watts D.J , Pitakaso R (2008) The development of multi-objective optimization model for excess bagasse utilization: A case study for Thailand , Environmental Impact Assessment Review, Vol.28 (6) ; pp.380-391
    2. Buddadee B , Wirojanagud W , Techarungpaisan P , Pitakaso R (2009) Environmental system optimization of excess bagassse utilization for sugar mills in the Northeastern of Thailand , Thai Environmental Engineering Journal, Vol.24 (2) ; pp.1-13
    3. Caballero R.M , Gonzalez F.M , Guerrero J.M , Paralera C (2007) Solving a multiobjective location routing problem with a metaheuristic based on tabu search application to a real case in Andalusia , Eur. J. Oper. Res, Vol.177; pp.1751-1763
    4. Doerner K.F , Gutjahr W.J , Nolz P.C (2009) Multi-criteria location planning for public facilities in tsunami-prone coastal areas , OR Spectrum, Vol.31 (3) ; pp.651-678
    5. Doerner K , Focke A , Gutjahr W.J (2007) Multicriteria tour planning for mobile healthcare facilities in a developing country , Eur. J. Oper. Res, Vol.179; pp.1078-1096
    6. Drezner T , Drezner Z , Salhi S (2006) A multi-objective heuristic approach for the casualty collection points location problem , J. Oper. Res. Soc, Vol.57; pp.727-734
    7. Leung S.C.H (2007) A non-linear goal programming model and solution method for the multi-objective trip distribution problem in transportation engineering , Optim. Eng, Vol.8; pp.277-298
    8. Lin C.K.Y , Kwok R.C.W (2006) Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data , Eur. J. Oper. Res, Vol.175 (3 ) ; pp.1833- 1849
    9. Medaglia A.L , Villegas J.G , Rodriguez-Coca D.M (2009) Hybrid bi-objective evolutionary algorithms for the design of a hospital waste management network , J. Heuristics, Vol.15; pp.153-176
    10. Nanthasamroeng N , Pitakaso R , Buddadee B (2008) A multi objectives model for multi-echelon location problem: Application in ethanol plant location analysis in Thailand,
    11. Thongdee T , Pitakaso R (2012) Solving a multiobjective, source and stage location-allocation problem: a case study of a bagasse and cassava pulp ethanol plant in northeastern Thailand , KKU Res. J, Vol.17 (1) ; pp.71-87
    12. Thongdee T , Pitakaso R (2013) Solving a Multi- Objective, Source and Stage Location-Allocation Problem Using DE-PSO, pp.584-589
    13. Uno T , Katagiri H (2008) Single- and multiobjective defensive location problems on a network , Eur. J. Oper. Res, Vol.188; pp.76-84
    14. Xu J , Liu Q , Wang R (2008) A class of multi-objective supply chain networks optimal model under random fuzzy environment and its application to the industry of Chinese liquor , Inform. Sci, Vol.178; pp.2022-2043