- Email: [email protected]

Int. J. Production Economics 98 (2005) 251–261 www.elsevier.com/locate/ijpe

Recent network design techniques using evolutionary algorithms Mitsuo Gena,, Anup Kumarb, Jong Ryul Kimc a

Graduate School of Information, Production and Systems, Waseda University, Kitakyushu, 808-0135, Japan b Computer Engineering and Computer Science, University of Louisville, Louisville, KY 40292, USA c Graduate School of Management, KAIST, 207-43, Seoul, Republic of Korea Available online 25 March 2005

Abstract As social systems based on computer networks are more complicated, the optimization problems in network systems have been drawing the attention of many related researchers. Recently, genetic algorithms (GAs) have achieved a great advancement in related research ﬁelds, such as combinatorial optimization, multiobjective optimization, and so on. In this paper, we consider hybrid GAs (called spanning tree-based GAs) for difﬁcult-to-solve network design problems inherent in industrial engineering and computer communication networks, such as degree-constrained minimum spanning tree problems, capacitated minimum spanning tree problems, ﬁxed charge transportation problems, network topological design problems, and so on. r 2005 Published by Elsevier B.V. Keywords: Genetic algorithm (GA); Network design; Minimum spanning tree; Fixed charge transportation

1. Introduction Genetic algorithms (GAs) are one of the most powerful and broadly applicable stochastic search and optimization techniques and have achieved great advancement in related research ﬁelds, such as network optimization, combinatorial optimization, multi-objective optimization, and so on. And Corresponding author. Tel.: +81 284 62 0605;

fax: +81 284 64 1071. E-mail address: [email protected] (M. Gen). 0925-5273/$ - see front matter r 2005 Published by Elsevier B.V. doi:10.1016/j.ijpe.2004.05.026

GAs have received a great deal of attention about their ability as optimization techniques for many real-world problems (Gen and Cheng, 1997, 2000). In the past few years, the GA community has also turned much of its attention toward the optimization problems of the industrial engineering/operations research world (Gen et al., 2001). This paper is intended as a text covering the central aspects of GAs and their applications to difﬁcult-to-solve network design problems inherent in industrial engineering and computer communication network systems. Especially, these network design

ARTICLE IN PRESS 252

M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

problems for various network systems have drawn the attention of many related researchers, such as network designers, network analysts, network administrators accordingly, as the scale of communication network is getting larger and larger. The following major topics of this research will be summarized as follows:

Degree-constrained minimum spanning tree problem (MST) Capacitated minimum spanning tree problem Fixed charge transportation problem Bicriteria Local Area Network (LAN) topological design.

Also, we present some computational results, in order to ascertain the possibility of hybrid GA approaches as the optimization technique for network design problems, such as degree-constrained MST problems, capacitated MST problems, ﬁxed charge transportation problems, network topology design problems, and so on.

2. Degree-constrained Minimum Spanning Tree Problem The MST problem has a venerable history in combinatorial optimization and computer science. Given a ﬁnite connected graph, the MST problem is to ﬁnd a minimum cost subgraph spanning all vertices (Gen et al., 1998b). The degree-constrained MST problem, denoted as dc-MST, is an extended formulation of the MST problem. The dc-MST problem may arise for instance when designing a communication networks; a degree constraint limits the vulnerability in case of a dropped crossing. So the dc-MST is a more realistic representative of the practical problem than the MST in this situation. However, to ﬁnd the solution of the dc-MST problem, it is difﬁcult to directly apply the ﬁne polynomial time algorithms such as Dijkstra’s, Kruskal’s, Prim’s, and Sollin’s. We consider a connected undirected graph G ¼ ðV ; EÞ; where V ¼ f1; 2; . . . ; ng is a ﬁnite set of vertices representing terminals or telecommunication stations, etc., and E ¼ fði; jÞji; j 2 V g is a ﬁnite

set of edges representing connections between these terminals or stations. Each edge has an associated positive real number denoted with W ¼ fw12 ; w13 ; . . . ; wðn 1Þn g representing distance, cost and so on. We deﬁne the following binary decision variables: 1 if edge ði; jÞ is selected; xij ¼ (1) 0 otherwise for all edges ði; jÞ 2 E: Then a spanning tree of graph G can be expressed by the vector x. Let T be the set of all such vectors corresponding to spanning tree in graph G; the well-known MST problem can be formulated as ( ) n 1 X n X min zðxÞ ¼ wij xij jx 2 T . (2) i¼1 j¼iþ1

In some real-world problems, the degree of each vertex in a tree is not always arbitrary, where the degree means the number of edges connected to a vertex. Narula and Ho ﬁrst proposed this problem in designing electrical circuits: connect n terminals with the minimum amount of wire, where the number of wires incident to terminal k can be at most a given value (Narula and Ho, 1980). It means that there is a degree constraint on each vertex such that, at each vertex vk ; the corresponding degree value d k is at most a given value bk : Then the problem is formulated as the following form: ( n 1 X n X min zðxÞ ¼ wij xij jd k pbk ; i¼1 j¼iþ1

)

i; j; k 2 V ; x 2 T .

ð3Þ

The above MST problem with degree constraints is denoted as the degree-constrained MST problem. For convenience, we only consider the degree constraint bk ¼ b for all k 2 V : As there are no effective polynomial-time algorithms for this problem, it is necessary to develop a new approach to meet the requirements of some network optimization problems in engineering design. Lately, Zhou and Gen (1997a, b)

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

proposed a new approach to solve the dc-MST problem by using GA with Pru¨fer number encoding which is suitable to encode the spanning tree with degree constraints (Zhou and Gen, 1997a, b). Also, they introduced a mixed strategy in the selection operation, which is really more suitable for this combinatorial optimization problem. Also, Zhou and Gen proposed a new tree encoding for the dc-MST problem, which is called degree-based permutation encoding, in order to overcome defects of Pru¨fer number encoding (Zhou and Gen, 2003).

253

It is not hard to verify that the following formulation is a valid integer programming representation for the centralized network design problem: min

zðxÞ ¼

n 1 X n X i¼1

s:t:

n 1 X n X i¼1

(4)

xij ¼ n 1,

(5)

j¼2

X X i2S

cij xij

j¼2

xij pjSj lðSÞ,

(6)

j2S j41

3. Capacitated Minimum Spanning Tree Problem A centralized network is a network where all communication is to and from a single site. In such networks, terminals are connected directly to the central site. Some multipoint lines are used, where groups of terminals share a tree to the center and each multipoint line is linked to the central site by one link only. This problem is formulated as the Capacitated Minimum Spanning Tree (c-MST) problem in the combinatorial optimization literature (Hall, 1996). The c-MST problem has been shown to be NP-hard by Papadimitriou (1978). So far, there are no effective algorithms to solve this problem. In this Section, we formulate the centralized network design problem as a zero–one integer program. This particular formulation was ﬁrst expressed by Gavish (1982). Considering a complete, undirected graph G ¼ ðV ; EÞ; we let V ¼ f1; 2; . . . ; ng be the set of nodes representing the terminals and denote the central site, or ‘‘root’’ node, as node 1, and let E ¼ fði; jÞji; j 2 V g be the set of edges representing all possible telecommunication wiring. For a subset of nodes Sð V Þ we deﬁne EðSÞ ¼ fði; jÞji; j 2 Sg to be the edges whose endpoints are both in S. Let cij be the (ﬁxed) cost of including edge (i, j) in the solution, and suppose that di represents the demand at each node i 2 V ; where by convention the demand of the root node d 1 ¼ 0: We also use d(S), S V ; to denote the sum of the demands of the nodes of S. The subtree capacity is denoted by k:

S V \f1g; X X

jSjX2, xij pjUj 1,

(7)

i2U j2U j41

U V ; jUjX2; f1g 2 U, xij ¼ 0 or 1, i ¼ 1; 2; . . . ; n 1;

(8) j ¼ 2; 3; . . . ; n.

Equality (5) is true of all spanning trees: a tree with n nodes must have n 1 edges. Inequalities (6) are some of the standard rank inequalities for spanning trees: if more than |U| 1 edges connect the nodes of a subset U, then that set of edges must contain a cycle. The parameter lðSÞ in (6) refers to the bin-packing number of the set S, namely, the number of bins of size k needed to pack the nodes of items of size di for all i 2 S: These constraints are similar to Eq. (7), except that they reﬂect the capacity constraint: if the set S does not contain the root node, then the nodes of S must be contained in at least lðSÞ different subtrees off of the root. In the case that the demands of all non-root nodes are 1, inequalities (6) can be expressed more simply as XX jSj xij pjSj , k i2S j2S j41

S V \f1g; jSjX2,

ð9Þ

ARTICLE IN PRESS 254

M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

since items of unit size can always be packed in djSj=ke bins or subtrees. Up to now, all heuristic algorithms for this problem are only focused on how to deal with the constraints to make the problem simpler to solve. On the approach of cutting plane algorithms (Gouveia, 1995) or branch–bound algorithms (Malik and Yu, 1993), the network topology of the c-MST problem are usually neglected. As a result, it results in the exponential explosion of constraints. Recently, Zhou and Gen proposed a GA approach using a tree-based genetic representation to encode the candidate solution of the cMST problem (Zhou and Gen, 1997c). This treebased encoding representation guarantees that the candidate solutions are always feasible solutions of the problem to be solved, and its locality property makes the evolutionary process more efﬁcient. Altiparmak et al. combined a tree-based encoding representation with FLC for solving communication network design problem (Altiparmak et al., 2004).

4. Fixed Charge Transportation Problem Many practical transportation and distribution problems such as the minimum cost network from (transshipment) problem with ﬁxed charge in logistics can be formulated as the Fixed-Charge Transportation Problem (fc-TP). For instance, in a transportation problem, a ﬁxed cost may be incurred for each shipment between a given plant and a given consumer and a facility of a plant or warehouse may result in a ﬁxed amount on investment. The fc-TP problem is much more difﬁcult to solve due to the presence of ﬁxed costs, which cause discontinuities in the objective function. The transportation problem (TP) as a logistics planning is the prime meaning given to logistics. It seeks the determination of a minimum cost (or time) transportation plan for a homogeneous commodity from a number of plants to a number of consumers. It requires the speciﬁcation of the level of supply at each plant, the amount of demand at each consumer, and the transportation cost from each plant to each consumer. The goal is to allocate the supply available at each plant so as

to optimize a criterion while satisfying the demand at each consumer. Many scholars have since reﬁned and extended the basic TP model (Syarif et al., 2002; Zhou et al., 2002; Gen and Syarif, 2003; Syarif and Gen, 2003). The usual objective function is to minimize the total transportation cost or weighted distance, or to minimize the total proﬁt contribution from the allocation (Gen and Cheng, 1997, 2000). It is one of the simplest combinatorial problems involving constraints. This transportation problem with given m plants and n consumers can be formulated as follows: min

f ðxÞ ¼

m P n P

f ij ðxÞ

i¼1 j¼1

s:t:

n P

xij pai ;

i ¼ 1; 2; . . . ; m;

xij Xbj ;

j ¼ 1; 2; . . . ; n;

j¼1 m P i¼1

xij X0;

8 i; j;

where x ¼ ½xij is the unknown quantity to be transported from plant i to consumer j, f ij ðxÞ is the objective function of shipping one unit from plant i to consumer j in which f ij ðxÞ ¼ cij xij will be a cost function if it is linear, ai is the number of units available at plant i, and bj is the number of units demanded at consumer j. As an extension of the linear TP, there is fc-TP. This problem arises when the ﬁxed costs occur in establishing transport route between a plant and a customer. TP is a special case of fc-TP of the equal ﬁxed costs with zero for all routes. The objective function of fc-TP usually is stated as f ðxÞ ¼

m X n X

ðf ij ðxÞ þ d ij gðxij ÞÞ

i¼1 j¼1

with gðxij Þ ¼

(

1 0

if xij 40; otherwise;

where dij is the given ﬁxed costs. For the transportation of the multicommodity, we can also easily model the multicommodity transportation model and solve it by solving subproblems of the original problem.

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

Also, two objective functions of the bicriteria fcTP problems with given m plants and n consumers can be described as min

f 1 ðxÞ ¼

m X n X

ðf ij ðxÞ þ d ij gij ðxÞÞ,

i¼1 j¼1

min

f 2 ðxÞ ¼

m X n X

tij ðxÞ,

i¼1 j¼1

( with

gij ðxÞ ¼

1

if xij 40;

0

otherwise;

where tij (x) can be viewed as a function of delivery time in which it is in the form tij ðxÞ ¼ tij xij where tij is per unit delivery time from plant i to consumer j. Gen and Li proposed the Spanning Tree-based Genetic Algorithms (st-GA) to solve Multicriteria Transportation Problem (m-TP) in which the Pru¨fer number encoding is adopted to represent a special data structure in solution characterized as a transportation graph (Li and Gen, 1997, 1998; Gen and Li, 1998; Gen et al., 2000a; Li and Gen, 2000). They also designed crossover and mutation operations based on the tree encoding to generate feasible solutions in the evolutionary process. st-GA can ﬁnd the Pareto optimal solutions for the m-TP problem in criterion space. The numerical experiments show the effectiveness and efﬁciency of st-GA than the matrix-based encoding GAs. Further, Gen and Li proposed the Spanning Tree-based Hybrid Genetic Algorithms (st-hGA) to solve the fc-TP problem in which we utilize the reduced cost for optimality test of a feasible solution and hybridize to the genetic algorithm to avoid degeneration of the evolutionary process (Gen et al., 2000b). The mixed strategy combined ðm þ lÞ-selection and roulette wheel selection is used in st-hGA. Lately, Gen and Li developed the evolutionary approach based on GA for solving bicriteria fc-TP problems (Li et al., 1999; Gen et al., 2000c).

255

consist of several LAN segments connected together via bridges. The use of these transparent bridges requires loop-free paths between LAN segments. Therefore, only spanning tree topologies can be used as active LANs conﬁgurations when designing a computer network system. We consider LANs that connect n service centers and m users. For example, we assume that we want to design LANs as shown in Fig. 1. We deﬁne the n n service center topology matrix X1 which represents the connected appearance of service centers. An element x1ij represents whether the centers i and j are connected. We further assume that LANs are partitioned into n segments (service centers). The users are distributed over those n service centers. The n m clustering matrix X2 speciﬁes which user belongs to which center. An element x1ij means whether user j belongs to center i. We deﬁne the n ðn þ mÞ matrix X called the spanning tree matrix ([X1 X2]). The M/M/1 model (Bertsekas and Gallager, 1992) is used to describe a single cluster (LAN segment) behavior. Then we can formulate the bicriteria LAN topology design problem as the following nonlinear 0–1 programming model: " # n n X n X 1 X d i ðXÞ min þ b f ðXÞ , G i¼1 C i d i ðXÞ i¼1 j¼1 ij ij (10) min

n 1 X n X

w1ij x1ij þ

n X m X

i¼1 j¼iþ1

w2ij x2ij

12

11

17

9 4

2

8

18

1

10

14

22

5

16 6

In computer networking, LAN are commonly used as the communication infrastructure that meets the demands of the users in the local environment. The computer networks typically

23

13

7

5. Bicriteria LAN Topological Design

(11)

i¼1 j¼1

19

3

21 20

15 : service center,

: user

centers: {1, 2, 3, 4, 5} users: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

Fig. 1. The sample LANs architecture.

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

256

s:t:

m X

x2ij ogi ;

i ¼ 1; 2; . . . ; n,

(12)

j¼1 n X

x2ij ¼ 1;

j ¼ 1; 2; . . . ; m,

(13)

i¼1

d i ðXÞoC i ;

i ¼ 1; 2; . . . ; n,

(14)

where G is the total offered trafﬁc, d i is the total trafﬁc at center i, f ij is total trafﬁc through link ðk; lÞ; Ci is the trafﬁc capacity of center i, bij is the delay per bit due to the link between centers i and j, gi is the maximum number which is capable of connecting to center i, w1ij is the weight of the link between centers i and j, and w2ij is the weight of the link between center i and user j. Gen et al. (1998a) introduced the st-GA for solving the bicriteria LAN topological design problem which is minimizing the connecting cost and the average networks message delay (Kim et al., 1998, 1999; Gen et al., 1998a). They show computational experiments with two LAN design problems to demonstrate the effectiveness of the st-GA in which the registered Pareto optimal solutions technique was used to get nondominated solutions and the compromise solution among Pareto solutions was shown by using the TOPSIS method (Gen and Cheng, 1997; Hwang and Yoon, 1981). Gen et al. also proposed a heuristic algorithm based on GA for designing the reliable multiplexed network topology with ﬁber-optic cable (Kim and Gen, 1999).

6.1. Degree-constrained minimum spanning tree Here, we introduce the results of GAs proposed by Zhou and Gen (1997a, b), Gen and Cheng (1997). The numerical example was given by Savelsbergh and Volgenant (1985) who solved it using heuristic algorithm denoted as edge exchanges and the optimal solution is 2256. It is a 9vertex undirected complete graph. The parameters for the GAs approach are set as follows: population size pop_size ¼ 50; crossover probability pc ¼ 0:5; mutation probability pm ¼ 0:01; maximum generation max_gen ¼ 500; the constrained degree value for all vertices b ¼ 3; and run by 30 times. By GAs approach, the optimal solution 2256 can be reached at most times. Fig. 2 illustrates that the proposed GAs approach combined with the evolution strategy in selection has a better mechanism to reach the optimal solution than that with roulette wheel selection. The former gets the optimal solution 20 times in 30 run times while the latter only has 2 times in 30 run times. These results show that the evolution strategy in selection is really more suitable than the roulette wheel selection for the combinatorial optimization problems like dc-MST. In further testing the proposed GAs approach on the dc-MST problem, ﬁve randomly generated numerical examples with 10 to 50 vertices were tested. The weights deﬁned on each edge are integers which are randomly generated and uniformly distributed over [10,100]. All parameters for the GA are set as before and the constrained

2550

mixed selection strategy roulette wheel selection

2500

6. Numerical examples fitness

We consider some computational results, in order to ascertain the possibility of hybrid GA as the optimization technique for network design problems, such as degree-constrained minimum spanning tree problems, capacitated minimum spanning tree problems, ﬁxed charge transportation problems, network topology design problems, and so on.

2450 2400 2350 2300 2250 2200 0

5

10

20 15 random trials

25

Fig. 2. Solutions compared with two GAs selections.

30

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

257

Table 1 Comparison between results by the GA and their LB Problem size (vertices)

10 20 30 40 50

LB (without dc)

GA (with dc)

Percentage GA to LB

min. val

degree value

min. val

degree value

117 233 316 419 513

5(2) 4(2) 4(4) 7(3) 6(4)

123 237 327 449 554

3 3 3 3 3

5.13% 1.72% 4.48% 7.16% 7.99%

min. val: minimal value, dc: degree constraint.

degree value is b ¼ 3: Here we do not try to ﬁnd the optimal solution as the problem scale is a little larger. Compared with their lower bounds (LB) which can be directly obtained by the MST algorithm without considering the degree constraint, the results by GAs approach are within less than 8% of their lower bounds as shown in Table 1. The ﬁgures in parentheses in the table are the number of vertices violating the degree constraint. If we arbitrarily modify those vertices violating the degree constraint, the results are always worse than those obtained by the GAs approach. Therefore, it shows that GAs approach has ﬁne mechanism on operation in a simple way and to some extent can meet the requirements from the practical engineering design. 6.2. Capacitated minimum spanning tree We also represent the results of GA proposed by Zhou and Gen (1997c). We present a numerical example given by Gavish (1982). The example consists of a CMST problem with 16 nodes, a unit trafﬁc between each node and node 1, and a capacity restriction k ¼ 5: The cost matrix for the example is presented by Zhou and Gen (1997c). The parameters for the proposed EC approach are set as follows: population size pop_size ¼ 200; mutation probabilities for exchange and inversion operations are pm ¼ 0:2 and pm ¼ 1:0; maximum generation max_gen ¼ 500; and run by 20 times, respectively. Gavish adopted an augmented lagrangian-based algorithm to solve this problem and got the optimal solution 8526 (Gavish, 1982).

central site

1 multipoint line 1

11

multipoint line 3

4

7

14

9

15 multipoint line 2

10

5

13 6 3

16

8

12 2

Fig. 3. The optimal solution of the CMST (cost ¼ 8526).

By the proposed EC, we also got the optimal solution 8526 and its corresponding topology of a tree. Fig. 3 illustrates the result. 6.3. Fixed charge transportation We describe the results of st-GA suggested by Gen and Li (1998) and Li and Gen (1997, 1998). The proposed spanning tree-based GA was implemented in C language and run on an HP 9000 Model 715/100 workstation under the UNIX operating system. Solution quality, evaluates the performance of the procedure. In order to compare GA with other approaches, test problems are taken from literature (Sun et al., 1998) which are produced by the generator NETGEN from Klingman et al. (1974) and modiﬁed by Barr et al. (1981).

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

258

The computational results with three problem sizes are used, and denoted by m n; these are 5 10, 10 10 and 10 20. The total supply (demand) for different problem sizes is given in Table 2. The ranges of integer ﬁxed costs for different types of test problems are given Table 3. The unit variable costs in all test problems are integers ranging from 3 to 8. Table 4 shows the comparison results with stGA and m-GA on three test problems with problem types. The coded algorithm was run by 10 times with given parameters, mutation rate 0.4, crossover rate 0.2, maximum generation 2000 and population size. For the different size problems, the given population sizes were different as 200 for 5 10, 300 for 10 10 and 400 for 10 20. For the m-GA, probabilities of the genetic operators were Table 2 Total supply (demand) for different problem sizes Problem size

Total supply

5 10 10 10 10 20

5000 10000 15000

Table 3 Ranges of integer ﬁxed costs for different types of test problems Problem type

Range of ﬁxed costs

A B C

Lower limit

Upper limit

50 100 200

200 400 800

given as 0.2 for mutation, and 0.4 for crossover, which were known as better parameter settings. If the solution obtained by either m-GA or st-GA is best, the percentage is 100, and if it is near best, the percentage is less than 100. The solution quality is used as the following deﬁnition. Solution quality ¼

best solution 100. obtained solution

The number of problems for which the best solution was found by GAs, m-GA or st-GA, out of a total of 10 trials, is given in the columns labeled ‘‘Freq.’’. As shown in the computational results in Table 4, st-GA found the best solution more times than the m-GA. Also in the comparison of the solution quality for fcTP, st-GA has a higher probability of evolving an optimal solution or a near-optimal solution than m-GA. On the CPU time, the spanning tree-based GA takes shorter CPU time than the matrix-based GA. Especially, in large-scale problems (this case is a 10 20 problem), the CPU time by the st-GA has not great difference than by the m-GA. Along with increase of the problem size, st-GA requires more than time to generate the feasible chromosomes in the initialization, because the feasibility of the chromosome is not easy to satisfy. Certainly, if we increase the population size for m-GA, it may be found that the optimal solution in the encoding space where the ﬁxed cost has smaller integers (as A type), but it will take exceedingly longer CPU time. st-GA incorporated speciﬁc knowledge of these kinds of network problems. The spanning tree encoding requires the encoding memory to be very

Table 4 Comparison of solution qualities for two GA approaches Problem

m-GA

st-GA

Size

Type

Worst

Average

Best

Freq.

Worst

Average

Best

Freq.

5 10

A B C A B A

90.80 88.87 85.41 99.62 99.72 94.85

95.06 92.86 86.99 99.86 99.85 95.93

98.73 94.01 90.82 100.00 100.00 97.62

0 0 0 4 3 0

98.49 97.78 98.31 99.42 99.61 98.11

99.12 99.03 99.83 99.77 99.74 99.25

100.00 100.00 100.00 100.00 100.00 100.00

2 2 9 2 3 2

10 10 10 20

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

The Pareto optimal solutions were found after several experiments, as illustrated in Fig. 4. The obtained solutions is formed in Pareto frontier. From the result, we can see the spanning treebased GA approach has a good performance on the bicriteria LAN topology design problem. Here the TOPSIS method proposed by Yoon and Hwang (1981) is used in order to determine the best compromise solution among Pareto solutions. TOPSIS stands for technique for order preference by similarity to ideal solution, which is based upon the concept that the chosen alternative should have the shortest distance from the positive ideal solution and the farthest from the negative ideal solution. The detailed information about TOPSIS can be found in references (Gen and Cheng, 1997; Hwang and Yoon, 1981). So, in Fig. 5, we represent the best compromised solution for the Pareto solutions of Fig. 4, using TOPSIS method. The chromosome of the best compromise solution in Fig. 5 is

less than that of matrix encoding. Compared with m-GA and st-GA, st-GA not only found higher quality solutions but also took less computing time on this practical ﬁxed charge transportation problem. Therefore, as a genetic approach the spanning tree-based GA is more effective and efﬁcient in solving the large-scale ﬁxed charge transportation problem. 6.4. Bicriteria LAN design Let us consider a bicriteria LAN topology design problem using the st-GA proposed by Kim et al. (1999) and Gen et al. (1998). 0.26

0.21 Message Delay

259

0.16

½6355664152334152532242112646556124 0.11

with 1614 connection cost and 0.09935 message delay.

0.06 0.01 1450 1500 1550 1600 1650 1700 1750 1800 1850 1900 1950 Connection Cost

7. Conclusion In this paper, we summarized about hybrid GA (also called spanning tree-based GA) approaches

Fig. 4. Pareto solutions.

22 24

16

21

14

25

20

15

23

10

2

18

1 27

34

30

31

29

3

5

28

17 8

4 19

35

36

13

32 26

9

33

6 12

7 11

: user : service center, centers: {1, 2, 3, 4, 5, 6} users: {7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36} Fig. 5. The best compromise solution for Pareto solutions.

ARTICLE IN PRESS 260

M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261

for several optimal network design problems, such as degree-constrained minimum spanning tree problems, capacitated minimum spanning tree problems, ﬁxed charge transportation problems, and bicriteria LAN topological design problems. Further, we can see the potential of GA approach as one of optimization techniques for network design problems.

Acknowledgements This research was supported by the International Scientiﬁc Research Program, the Grant-inAid for Scientiﬁc Researches (No. 07045032: 1995.4-1998.3; No. 10044173: 1998.4-2001.3) by the Ministry of Education, Science and Culture, the Japanese Government. The research was partly supported by Waseda University Grant for Special Research Projects. References Altiparmak, F., Gen, M., Dengiz, B., Smith, A.E., 2004. A genetic algorithm with fuzzy logic controller for design of communication networks. IEEJ Transactions on Electronics, Information and Systems 124 (10), 1979–1985. Barr, R.S., Glover, R.S., Klingman, D., 1981. A new optimization method for large scale ﬁxed charge transportation problems. Operation Research 29 (3), 448–463. Bertsekas, D., Gallager, R., 1992. Data Networks, second ed. Prentice-Hall, New Jersey. Gavish, B., 1982. Topological design of centralized computer networks-formulation and algorithms. Networks 12, 355–377. Gen, M., Cheng, R., 1997. Genetic Algorithms and Engineering Design. Wiley, New York. Gen, M., Cheng, R., 2000. Genetic Algorithms and Engineering Optimization. Wiley, New York. Gen, M., Li, Y., 1998. Solving multiobjective transportation problem by spanning tree-based genetic algorithm. In: Parmee, I. (Ed.), Adaptive Computing in Design and Manufacture. Springer, New York, pp. 98–108. Gen, M., Choi, J., Ida, K., 2000a. Improved genetic algorithm for general transportation problem. Artiﬁcial Life and Robotics 4, 96–102. Gen, M., Li, Y., Ida, K., 2000b. Spanning tree-based genetic algorithm for bicriteria ﬁxed charge transportation problem. Journal of Japan Society for Fuzzy Theory and Systems 12 (2), 295–303. Gen, M., Ida, K., Kim, J.R., 1998a. A spanning tree-based genetic algorithm for bicriteria topological network design.

Proceedings of 1998 IEEE International Conference on Evolutionary Computing, pp. 15–20. Gen, M., Zhou, G., Takayama, M., 1998b. A comparative study on tree encodings on spanning tree problems. Proceedings of 1998 IEEE International Conference on Evolutionary Computing, pp. 33–38. Gen, M., Cheng, R., Oren, S.S., 2001. Network design techniques using adapted genetic algorithms. Advances in Engineering Software 32 (9), 731–744. Gen, M., Syarif, A., 2003. Multi-stage supply chain network by hybrid genetic algorithms with fuzzy logic controller. In: Verdegay, J.L. (Ed.), Fuzzy Sets based Heuristics for Optimization. Springer, New York, pp. 181–196. Gouveia, L., 1995. A 2n constraint formulation for the capacitated spanning tree problem. Operations Research 43 (1), 130–141. Hall, L., 1996. Experience with a cutting plane algorithm for the capacitated minimal spanning tree problem. INFORMS Journal on Computing 8 (3), 219–234. Hwang, C., Yoon, K., 1981. Multiple Attribute Decision Making: Methods and Applications. Springer, Berlin. Kim, J.R., Gen, M., 1999. A spanning tree-based genetic algorithm for reliable multiplexed network topology design. Proceedings of the Fourth International Symposium on Artiﬁcial Life and Robotics 2, 460–463. Kim, J.R., Gen, M., Ida, K., 1998. A GA for bicriteria LAN topology design problem. Proceedings of the Second International Conference on Engineering Design and Automation, Aug. 9–12, Maui, Hawaii. Kim, J.R., Gen, M., Ida, K., 1999. Bicriteria network design using spanning tree-based genetic algorithm. Artiﬁcial Life and Robotics 3, 65–72. Klingman, D., Naoier, A., Stutz, J., Netgen, J., 1974. A program for generating large scale capacitated assignment, Transportation and Minimum Cost Flow Networks. Management Science 20 (5), 814–822. Li, Y., Gen, M., 1997. Spanning tree-based genetic algorithm for bicriteria transportation problem with fuzzy coefﬁcients. Australian Journal of Intelligent Information Processing Systems 4 (3/4), 220–229. Li, Y., Gen, M., 1998. Spanning tree-based genetic algorithm for solving bicriteria transportation problem. Journal of Japan Society for Fuzzy Theory and Systems 10 (5), 888–898. Li, Y., Gen, M., Ida, K., 1999. A genetic algorithm for bicriteria ﬁxed charge transportation problem. Proceedings of the Fourth International Symposium on Artiﬁcial Life and Robotics 2, 456–459. Li, Y., Gen, M., 2000. Spanning tree-based genetic algorithm for solving bicriteria transportation problem. Journal of Japan Society for Fuzzy Theory and Systems 10 (5), 501–513. Malik, K., Yu, G., 1993. A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23, 525–532. Narula, S.C., Ho, C.A., 1980. Degree-constrained minimum spanning tree. Computers and Operations Research 7, 239–249.

ARTICLE IN PRESS M. Gen et al. / Int. J. Production Economics 98 (2005) 251–261 Papadimitriou, C.H., 1978. The complexity of the capacitated tree problem. Networks 8, 217–230. Syarif, A., Yun, Y.S., Gen, M., 2002. Study on multi-stage logistics chain network: a spanning tree-based genetic algorithm approach. Computer and Industrial Engineering 43 (1–2), 299–314. Syarif, A., Gen, M., 2003. Solving exclusive side constrained transportation problem by using a hybrid spanning treebased genetic algorithm. Journal of Intelligent Manufacturing 14 (3/4), 389–399. Savelsbergh, M., Volgenant, T., 1985. Edge exchanges in the degree-constrained spanning tree problem. Computers and Operations Research 12 (4), 341–348. Sun, M., Aronson, J.E., Mckeown, P.G., Drinka, D., 1998. A tabu search heuristic procedure for the ﬁxed charge transportation problem. European Journal of Operational Research 106, 441–456.

261

Zhou, G., Gen, M., 1997a. Approach to degree-constrained minimum spanning tree problem using genetic algorithm. Engineering Design and Automation 3 (2), 157–165. Zhou, G., Gen, M., 1997b. A note on genetic algorithm approach to the degree-constrained spanning tree problems. Networks 30, 105–109. Zhou, G., Gen, M., 1997c. A centralized network design problem with genetic algorithm approach. In: Yao, X., Gen, M., Tujimura, Y., Mckey, R.J. (Eds.), Proceedings of the Australia–Japan Joint Workshop on Intelligent and Evolutionary Systems, pp. 35–45. Zhou, G., Hokey, M., Gen, M., 2002. The balanced allocation of customers to multiple distribution centers in the supply chain network: a genetic algorithm approach. Computer and Industrial Engineering 43 (1–2), 251–261. Zhou, G., Gen, M., 2003. A genetic algorithm approach on tree-like telecommunication network design problem. Journal of the Operational Research Society 54 (3), 248–254.