Available online at www.sciencedirect.com
Computers & Operations Research 32 (2005) 2785-2800

www.elsevier.com/locate/dsw
A tabu search algorithm for the routing andcapacity assignment problem in computer networks
Jian Shena>*, Fuyong Xua, Peng Zhengb
aSchool of Information Science and Engineering, Lanzhou University, Lanzhou 730000, PR China bDepartment of Electrical and Computer Engineering, University of California, Irvine, CA 92697, USA
Abstract
A tabu search metaheuristic algorithm for a classical routing andcapacity assignment (CFA) problem in computer networks is presentedin this paper. Computational experiments across a variety of networks are reported. The results show that the proposedtabu search algorithm is both effective andefficient in finding goodsolutions of the CFA problem comparedwith the traditional Lagrangean relaxation andsubgradient optimization technique. Extensive tests are made in order to choose the best values of the parameters for tabu search algorithm.
© 2004 Elsevier Ltd. All rights reserved.
Keywords: Computer networks; Routing andcapacity assignment; Combinatorial optimization; Tabu search
1. Introduction
Network design is a fundamental problem with a large scope of applications that have given rise to many different models and solution approaches [1,2]. The general network design problem involves the minimization of a cost objective function over a lot of design variables, such as link capacities, flow assignment, network topology, node locations, message priority discipline. The joint problem of routing andcapacity assignment, also known as the capacity andflow assignment (CFA) problem, is a special issue of the general network design problem.
The CFA problem was first considered by Gerla in his thesis [3]. Fratta et al. [4] proposed a model to minimize mean network delay in the case of general bifurcated routing and linear design costs, allowing the application of the low deviation algorithm to solve the corresponding convex multicommodity flow problem. Ng and Hoang [5] examineda special case of the routing
"Corresponding author. Tel.: +86-931-8263681; fax: +86-931-8897029. E-mail address: jian..shen@163.com (J. Shen).
andcapacity assignment problem in which a m-M/M/1 queuing structure is usedto model parallel transmission lines. They formulatedthe problem using continuous link capacity variables, andused the flow deviation methodfor solution. LeBlanc andSimmons [6] formulatedthe routing andcapacity assignment problem using continuous link capacity variables andsuggesteda new convex delay function different from the traditional M/M/1. Gavish and Neuman [7] proposeda model to jointly minimize the delay andcapacity costs in the case of nonbifurcatedrouting anddiscrete capacity functions. The model was solved using a Lagrangean relaxation procedure. Gavish and Altinkemer [8] extended the work in [7] by considering all possible routes for every communicating node pair. They included cut constraints that are redundant in the original problem to improve the lower bounds and proposedan interesting heuristic to generate a feasible solution. Amiri andPirkul [9] developed a new mixedinteger nonlinear programming formulation for the CFA problem using Lagrangean relaxation andsubgradient optimization techniques anda two phases heuristic solution procedure to obtain lower bounds as well as feasible solutions. The model overcame the shortcoming of previous methods. The results were comparedto those reportedin [8]. Amiri [10] presenteda new mathematical programming model that includes a constraint that sets an upper limit on the average link queuing delay in the network, and considered all possible routes for every communicating node pair. Amiri andPirkul [11] developed the model in [10] with multi-busy-hour traffic conditions. Mahey et al. [12] considered discrete capacities and the cost function combines the installation cost with a measure of the quality of service (Qos) of the resulting network for a given traffic, andproposeda mixedinteger nonlinear model of the joint capacity andlow assignment problem solvedby a generalizedBenders decomposition method. Queiroz and Jr. [13] proposeda heuristic methodfor the continuous capacity andlow assignment problem by rephrasing the problem in the context of concave programming andbringing an alternative formulation of the projectedpairwise multicommodity low polyhedron. The key idea is to use local minima to deine concavity cuts, thus avoiding cycling and an explicit enumeration of the vertices.
Several authors incorporatedreliability constraints into the CFA problem. Monma andSheng [14] presenteda global network design andanalysis model to analyze network performance in low-cost backbone packet-switchednetworks. Lim [15] proposedan optimal procedure for minimizing the total link cost of the common channel signaling network under joint performance and reliability constraints. Al-Rumaih et al. [16] proposed a methodology for network topology design considering the problems of single link andnode failures tolerances. Their methodis basedon systematic topo-logical modiications of an initial network constructed without reliability requirements but for which the link capacities satisfy a set of link andpath performance requirements. ChamberlandandSanso [17] presented a model to take failures into account in the CFA problem. The model provides a way to evaluate a trade-of between increasing capacity and lower performance in the event of failures. Two diferent algorithms, corresponding to two diferent levels of parallelism, were proposed and implemented.
The previous methods, however, are all traditional mathematical programming techniques with high complex computation process. The results generatedby these methods are local optimal solutions insteadof global optimal ones.
In recent years, a new tabu search (TS) metaheuristic algorithm has been quickly developed. It was introduced by Glover [18-20], andsuccessfully appliedto solve the problems, such as graph coloring [21], traveling salesman problem [22], low shop sequencing [23], job shop scheduling [24], andmany other combinatorial optimization problems [25,26]. In the area of telecommunications, Laguna andGlover [27] discussed the development of a TS method for the bandwidth packing problem. Costamagna et al. [28] presenteda TS algorithm for topological optimization of broadband communication networks. ChamberlandandSanso [29] presenteda tabu search algorithm for topo-logical expansion of multiple-ring metropolitan area networks. Berger et al. [30] applieda TS for a network loading problem with multiple facilities. Shyur and Wen [31] developed a simple TS for optimizing the system of virtual paths in an ATM network. Youngho et al. [32] developed an efective TS procedure to provide tight upper bounds for a iber routing problem arising from the design of optical transport networks.
The achieved success of TS in all applications is due to its implementation as problem-oriented. For each implementation, it needs particular deinitions of structural elements and parameters. In order to study the performance of TS, a simple TS algorithm for the classical CFA problem is proposed in this paper. The performances of the algorithm are comparedwith the traditional techniques, and extensive tests are made to determine appropriate parameter values for the TS algorithm.
The remainder of the paper is organized as follows. In Section 2, the CFA problem is formulated. Section 3 describes the TS algorithm for the CFA problem. The results of computational experiments are presentedin Section 4. Finally we conclude and suggest further research in Section 5.
2. Problem formulation
The classical routing andcapacity assignment problem can be describedas follows: given a basic topology anda requirement matrix, how to simultaneously select link capacities androutes usedby nodes in the network in order to ensure an acceptable performance level at a minimum cost [7-9]. This problem is a complex nonlinear programming which has many restrainedconditions andit is known to be NP-completeness [33-36].
In order to formulate the classical CFA problem, we make the same assumptions used in [7-9]. It is assumedthat the network topology, the queuing andcapacity cost structure, andthe traic requirements between every pair of communicating nodes are given. We also assume that nodes have ininite bufers to store messages waiting for transmission on the links, that the arrival process of message to the network follows a Poisson distribution and that message lengths follow an exponential distribution. We further assume that the propagation delay in the links is negligible, that there is no message processing delay at the nodes, and there is only a single class of service for each communicating node pair. Under these assumptions, the computer network is modeled as a network of independent M/M/1 queue [37,38] in which links are treatedas servers with service rates proportional to the link capacities. The customers are messages whose waiting areas are the network nodes.
We use the following notation:
Z: the total cost,
I: the set of communicating origin-destination pairs in the network,
L: the total number of links in the network,
R: the set of candidate routes,
Sp: the set of candidate route for p, p e I. We assume that Sp D Sq = </> for p = q,
V/i: the average message length [bits/message],
&ri: an indicator function, taking 1 if link l is usedin route r, andO otherwise,
Xr: the message arrival rate [messages/s] of the unique origin-destination pair associated with route r, r e R,
If: the index set of link types available for link l, l e L,
Fl: the average bit rate [bits/s] on link l,
Qik: the capacity [bps] of line type k, k e Il,
Slk: the setup cost [$/month] of line type k, k e Il,
mlk: the distance cost[$/month/mile] of line type k, k e Il,
Clk: the variable cost [$/month/bits/s] of line type k, k e Il,
D: unit cost of delay [$/month/message],
G: fixedcost multiplier,
V: variable cost multiplier,
dl: the distance for link l,
decision variable, which is 1 if route r is selectedfor message routing, andO otherwise,
ylk: a decision variable, which is 1 if link type k is assignedto link l, andO otherwise.
The CFA problem can now be formulatedas follows:
Z = min < Y]D ^--— + G V(slkylk + drmlk) + V V ClkFlyl^ (1)
\ k€Il k€Il )
subject to
Fl = - ^ XrbrlXr 6 ^ Qlkylk   (Vl e L); (2)
Y^Xr = 1   (Vp e 77); (3)
r€S?
£ ylk = 1   (Vl e L); (4)
k €Il
Xr = 0,1(Vr e R); (5)
ylk = 0,1(Vk e Il,le L). (6)
The objective function is to minimize the total cost of network given by expression in Eq. (1). The first term of the objective function indicates the total cost of delay. The second term refers to the total fixedcost computedas the sum of the initial setup cost andthe distance cost. The third term is the variable cost associatedwith the links in the network. The constraint (2) guarantees the feasibility of the flow on each link in terms of the capacity assignedto it. The constraints (3) and (4) guarantee that only one route for each origin-destination pair and only one line type is chosen for each link, respectively.
3. Tabu search for the CFA
Tabu search is a procedure using ideas from artiicial intelligence, which guides local search methods to overcome local optimality andobtain optimal or near optimal solutions for hardcom-binatorial optimization problems. Starting from an initial solution, the methodexplores the solution space by moving from a solution to the best solution in the neighborhoodat each iteration. This allows the methodto escape from a local optimum andexplore other regions of the search space, but the quality of the solution may deteriorate from one iteration to the next, which distinct TS form the classical local search methods. To avoid cycling, a specially designed memory mechanism, known as the tabu list, is usedto store previously visitedsolutions or certain attributes of them, which will not be reversedfor a certain number of iterations. In particular, the status of a tabu move can be overruledandmake accessible right away if a certain aspiration criterion is met. For a more comprehensive description of TS, readers can refer to Ref. [25].
Since the TS is comparedwith the traditional techniques in this paper, we propose a simple TS algorithm for the CFA problem, and the fundamental components of the procedure are speciied in the following.
3.1. Solution representation
To a communicating origin-destination node pair p, p e I, there are |Sp| candidate routes, among which one andonly one is selectedto route the corresponding traffic. Using an integral variable rp to represent the index number of the route, we will get |I| such variables all together, each representing a certain route for a node pair. A route vector r = (r0,r1,^,r|I|_1) can be obtainedif we put all the |I| variables together, for 0 6 rp 6 |Sp| — 1. To a link l, l eL, there are candidate capacity types, among which only one is assignedto a line. Using an integral variable cl to represent the index number of the capacity types. We will get |L| such variable all together, each representing a capacity type for a line. A capacity vector c = (c0,c1,^C|L|_1) can be obtainedif we put all the |L| variables together, for 0 6 cl 6 |Il| — 1. It is natural for us to use these two vectors to represent a solution of the CFA.
3.2. Initial solution
Usually there are advantages to starting from an initial solution that is of high quality. We study the following methods for the CFA problem.
3.2.1. Initial route selection
We use four route methods as follows:
The random route method (RRM): Each time before the TS procedure starts, a program is used to generate H random integers, which lie in the interval [0, |Sp| — 1]. Let components of the route vector r equal those random numerals respectively, so an initial route solution could be attained.
The shortest route method (SRM): For each communicating node pair, select the shortest route from its candidate route set to carry the corresponding traic.
The minimum hops method (MHM): The hop of a route is defined as the number of nodes (or links) it traverses. This method is to select the one with the minimum hops from the candidate route set for each communicating node pair.

Fig. 1. The structure of tabu list.
The longest route method (LRM): For each communicating node pair, select the longest route from its candidate route set to carry the corresponding traffic.
3.2.2. Initial capacity assignment
Many methods can also be applied to the capacity assignment. In this paper, we only adopt the best capacity assignment method. If the routes of all communicating node pairs have been selected, the flow of each link is also decided. In the candidate capacity set, there must be a best candidate capacity value that can make the total cost of network is the minimum. We can findthese capacity values, andassign to the links.
3.3. Move definition
Two kinds of moves are defined only to route solution, i.e., M+ andM_. The former can lead to a tentative solution rt = rc + ei, andthe latter, rt = rc — ei. For ei is an identical vector and rt and rc represent the trial solution andthe current solution, respectively. Obviously, those two moves satisfy the 'completeness' condition, i.e., any solution, wherever it lies in the solution space, can be reachedfrom another solution through certain number of such moves.
3.4. Tabu list
A list (Fig. 1) is usedto form the tabu list. Each unit in the list consists of two parts, i.e., the index number of the communicating node pair, which ranges from 0 to \II\ — 1, andthe operations imposedon it, which is representedby either 0 or 1, where 0 refers to M+ and1toM_. For example, a unit containing (10,0) means that the move is prohibitedif it leads to rt = rc + e10. The tabu list operates as first-in-first-out (FIFO) stacks. During the search procedure, a new tabu move is addedat the endof the list andthe oldest move is removedfrom the headof the list.
The length of the list is tabu list size (Tmax). The tabu list size represents the number of iterations that a move remains tabu, preventing the search from cycling. When the tabu list is short, tabu moves are allow to be reversedafter few iterations, which makes the search emphasize intensiication. If the tabu list is long, many moves are tabu andthe search is forcedinto areas that were not yet visited, which makes the search focus on diversiication. Thus the size of the tabu list should depend on the size andthe characteristics of the problem suggestedby Glover [25]. In the experiments, we investigate various values of the tabu list sizes.
3.5. Neighborhood search strategy
The neighborhoodsearch strategy specifies which move in the neighborhoodis chosen at each iteration. It is of great importance for the solution quality andthe search efficiency. The following three methods are tested.
The best method (BM): Generate andevaluate all solutions in the neighborhoodof the current solution. Choose the move yielding the solution with the best objection function value as the next move. Note that if the move is tabu, the best non-tabu move is selected.
The first method (FM): Generate sequentially the set of solutions in the neighborhoodof the current solution. Choose the first move identified as yielding a solution with the improved objective function value. If no improving move exists, select the best non-tabu move.
The sample method (SM): Under the conditions where the neighborhood size is very large, it is time-consuming to search the whole neighborhood. The sample method randomly generates a neighborhoodsubset of the current solution. All solutions in this subset are obtainedandevaluated, andthe move yielding the best objective function value is chosen as the next move. If the move is tabu, the best non-tabu move in the subset is selected.
3.6. Aspiration criterion
Comparedwith the constraining effect of tabu restrictions, aspiration criteria make the search process free. An aspiration criterion is designed to overrule tabu status and make a candidate move in tabu status admissible. In this article, the following aspiration criterion is used: if a move gives a better objective function value than the best foundso far, then it can be taken as the next move in spite of its tabu status.
3.7. Stopping criterion
Many stopping criteria can be developed depending on the nature of the problem being studied. The most common criterion, which is employedin this paper, is a maximum number of iterations.
3.8. Objective function
The objective function of the CFA problem is given in Eq. (1). However, in many cases, it is diicult to seek a feasible solution or it will take considerable time to seek such one, which satisies the constraints mentionedabove. So we redefine the objective function for the CFA problem as follows:
'( F, 1       1
/ex      ^*e/i - Fi ieL ieL - reR kei,
Z = <   ^ keii keii J
C
— Qikyik otherwise,
- reR keii (7)
where, C is a large, positive constant, which is 1 x 105 in this paper. By doing so, we can transfer the constrainedoptimization problem into an equivalent non-constrainedproblem, which is convenient in practice.
3.9. Tabu search procedure
Based on the previous discussion, we present a TS procedure for the CFA problem.
Step 1. Initialization: Generate an initial solution (r0, c0) according to the selected initial method, and calculate the total cost Z(r0, c0); Initialize the current solution (rc, cc) andthe best solution (rb, Cb) by setting (rc = r0, cc = c0) and(rb = r0, q, = r0), respectively; initialize the tuning parameters.
Step 2. Neighborhoodsearch (SM):
(1) Generate a neighborhoodsubset M, andall solutions in M are obtained.
(2) Evaluate solutions: Let (rtb,ctb) be the best solution for Z(rtb,ctb) is minimum in M.
If the move (rc — rtb) is not tabu, andZ(rtb, ctb) < Z(rb, cb), go to (3); otherwise go to (4).
If the move is tabu, but corresponding Z passes the aspiration criterion, i.e. Z(rtb, ctb) < Z(rb, cb), go to (3); otherwise let (rtb,ctb) be the solution for Z(rtb,ctb) is the nearest minimum in M, repeat this step.
(3) Renew the best solution: Set (rb = rtb, cb = ctb) andZ(rb,cb) = Z(rtb,ctb).
(4) Move: Set (rc = rtb, cc = ctb).
(5) Modify the tabu list: Put the opposite move into the tabu list and remove the oldest move in it.
Step 3. Check stopping criterion: If the stopping criterion is satisied, go to step 4; otherwise go to step 2.
Step 4. Stop andreport the results.
4. Computational results
We studied the four topologies shown in Figs. 2-5, viz. ARPA, OCT, USA andRING. These networks along with traffic parameters andcost structure are similar to those testedin [7-9]. In all four networks each node communicates with every other node. In the ARPA network there were 420 communicating node pairs with 4 messages per second being sent along the chosen route. The corresponding values were 650 andl for OCT, and 650 and4 for USA, and 992 andl for RING. The set of candidate routes was obtained using a modiied shortest path algorithm previously, and 5 routes were chosen for every communicating node pair. The diferent capacities used in the base case andtheir corresponding cost components are presentedin Table 1. The algorithm was coded in C language andrun on a PC with Pentium III-866 MHz CPU.
Table 2 shows the results with diferent message lengths. In order to compare the efectiveness of our procedure with the traditional method, we also report the results obtained by Amiri and Pirkul [9]. The unit cost of delay is assumed to be $2000 per month per message for the base case. Both ixedandvariable cost multipliers are equal to 1. Computational results indicate that both delay cost andoverall cost decrease comparedwith the results in [9]. The lower delay cost, the shorter

Fig. 2. The topology of ARPA network.
Fig. 3. The topology of OCT network.

Fig. 4. The topology of USA network.

Table 1
Link capacity set andits cost components
Capacity	Setup cost	Distance cost	Variable cost	
(bps)	($/month)	($/month/mile)	($/month/bps)	
4,800	650	0.4	0.360	
9,600	750	0.5	0.252	
19,200	850	2.1	0.126	
50,000	850	4.2	0.030	
108,000	2,400	4.2	0.024	
230,000	1,300	21.0	0.020	
460,000	1,300	60.0	0.017	
response time to users. That is to say, our proposedTS algorithm obtainedthe minimum total cost andthe better quality of service at the same time. We also noticedthat the solutions are slightly improvedin ARPA network. With the increasing of the network scale, the results have a significant improvement. In OCT network the total cost reduced67%. In USA network it is 59%, and61% in RING. It can be concluded from these results that TS is effective in solving the CFA problem, and superior in large scale networks.
In order to implement the proposed algorithm efectively, the properties of the key tabu parameters are examined.
Fig. 6 shows the results with different methods used to generate the initial solution. It can be seen that the initial solution has a significant effect on the results. The solutions of SRM andMHM are superior to those of RRM andLRM. There is slight difference between SRM andMHM. This can be attributedto the fact that MHM is usedto select the route with the minimum hops or links, as a result, the overall traffic in each link is lighter, andthe total cost is lower comparedwith other
Fig. 5. The topology of RING network.
J. Shen et al. / Computers & Operations Research 32 (2005) 2785-2800 2795
Table 2
Computational results with different message lengths
	Message	Our method			Methodin	[9]				
	length										
	
	Total	Delay	FixedVariable	Upper	Lower	Delay	FixedVariable	
		cost	cost	cost	cost	boundboundcost	cost	cost	
	200	180,920	36,184	113,980	30,756	185,565	176,513	38,999	118,634	27,932	
	300	234,638	49,274	140,783	44,581	245,740	235,370	54,134	152,107	39,499	
ARPA	400	308,129	71,785	185,145	51,199	308,637	298,361	72,326	185,137	51,174	
	500	341,427	75,900	204,084	61,443	377,433	362,662	82,298	232,511	62,624	
	600	400,613	92,535	232,368	75,710	445,902	429,600	110,657	233,658	71,587	
	300	163,912	28,999	113,354	21,559	406,239	393,967	90,573	244,334	71,332	
	400	185,123	36,505	121,104	27,514	544,644	520,221	133,759	320,930	89,955	
OCT	500	208,139	47,788	126,805	33,546	672,487	647,417	154,419	409,684	108,384	
	600	238,648	55,912	143,119	39,617	819,884	778,427	144,641	548,571	126,672	
	300	159,010	31,630	107,587	19,793	362,652	345,934	91,666	210,655	60,331	
	400	183,768	41,909	116,325	25,534	451,957	435,920	107,071	270,166	74,720	
USA	500	206,892	45,354	132,852	28,686	551,778	530,605	130,260	329,318	92,200	
	600	236,411	46,239	156,697	33,475	649,871	628,804	141,256	403,471	105,144	
	300	211,946	44,807	139,315	27,842	464,817	436,100	98,906	285,735	80,176	
RING	400	248,614	57,585	156,429	34,600	571,185	550,219	133,858	335,183	102,144	
	500	280,602	53,695	186,975	39,932	697,968	663,173	155,114	418,662	124,192	
	600	306,929	56,494	205,034	45,401	811,630	778,604	168,312	499,155	144,163	
Fig. 6. Results with diferent initial solution methods (RING).
methods. Because in most cases, fewer hops means shorter distance and vice versa, the difference between MHM andSRM is negligible. The results indicate that the goodinitial solution should be selectedto improve the quality of solutions while using TS. For the CFA problem, the initial solution shouldbe generatedby MHM or SRM, which is usedfor the rest of the study.

Fig. 7. Results with different neighborhood search strategies (RING).
Fig. 8. CPU times with different neighborhood search strategies (RING).
Figs. 7 and 8 show the effects andthe CPU times with different neighborhoodsearch strategies. We observe that the neighborhoodsearch strategy make a significant impact on the performance of TS procedures, particularly when the neighborhoodsize is large. BM, in most cases, can yieldbetter solutions, but with most computation time. The solutions obtainedby SM are very close to those by BM, with lest CPU times. FM spends less CPU times than BM, but it leads to worse results in each case, making it unsuitable for the TS procedure. Considering the solution quality and efficiency at the same time, we can draw a conclusion that SM shouldbe selectedwith higher priority when using TS. Only in circumstances where the size of neighborhoodis small or time is not so critical, can BM be applied.
When SM is used, how to select the neighborhood sample size is another important problem. The results with different neighborhood sample sizes are given in Fig. 9. Obviously, if the sample size is too small, the algorithm couldnot finda goodsolution. When the sample size is equal to 50 (about

Fig. 9. Results with different neighborhood sample sizes (RING).
Fig. 10. Results with different tabu list sizes (RING).
5% of the whole neighborhood), the algorithm arrives in an optimal solution. With the increase of the size, the solutions have a slight improvement but pay more computational efforts. Therefore, 5% of the neighborhoodshouldbe selectedas a subset in practice.
The results andthe CPU times with different tabu list sizes are reportedin Figs. 10 and 11, respectively. It is observedthat the tabu list with a size of 7 that proposedby Glover [25] is also suitable for the CFA problem. When the tabu list size is small (< 7), the algorithm visits the same sequence of solutions over andover again, andends up in a local optimum. When it is large (> 7), the results have slight improvement with the increase of the tabu list size, but at the expense of more computation time. So it is reasonable to select 7 as the tabu list size for the CFA problem.
In addition, the average number of iterations and the average CPU time for both our method andthe methodproposedby Amiri andPirkul [9] are summarizedin Table 3. Evidently, our TS

Fig. 11. CPU times with different tabu list sizes (RING).
Table 3
Average number of iterations andCPU times
algorithm is able to converge very quickly to an optimal solution. The optimal solution couldbe foundat the average iteration 90, which is approximately 3 times less than the methodin [9]. It is needto point out that the solution methoddescribedin [9] was written in Pascal andrun on IBM-3081D. Taking machine differences into account, our method is still faster than the traditional techniques. These further illustrate the high efficiency of the TS method.
5. Conclusions
In this paper, a tabu search metaheuristic algorithm is proposedfor the classical CFA problem in computer networks. Better results are obtainedcomparedwith the traditional techniques, so the high effectiveness of the TS methodis further verified. Extensive computational experiments show that appropriate parameters will greatly improve the efectiveness andeiciency of the TS procedure. These results are also helpful to the other sophisticated performance optimization problems in computer networks.

	Our method	Method in [9]	

	Number of	Total CPU	Number of	Total CPU	

	iterations	(S)	iterations	(S)	
ARPA	60	0.36	300	590	
OCT	70	0.63	291	1363	
USA	110	0.64	285	1920	
RING	120	0.64	300	3120	
In future research work, the performance of the TS method will be further studied. Advanced intensification anddiversification strategies [39], andparallel, reactive andhybridTS methods [40-42] shouldbe appliedto improve the quality of the solutions. In addition, we will apply the TS methodto some new optimization problems arising in computer networks, for instance, the weight setting problem in OSPF routing [43], etc.
References
[1] Minoux M. Network synthesis and optimum network design problems: models, solution methods and applications.
Networks 1989;19:313-60. [2] Ahuja V. Design andanalysis of computer communication networks. New York: McGraw-Hill; 1982. [3] Gerla M. The design of store-and-forward networks for computer communications. Ph.D. thesis, University of
California, Los Angeles, 1973. [4] Fratta L, Gerla M, Kleinrock L. The flow deviation method: an approach to store-and-forward communications
network design. Networks 1973;3:97-133. [5] Ng T, Hoang D. Joint optimization of capacity andflow assignment in a packet-switchedcommunications network.
IEEE Transactions on Communications 1987;35(2):202-9. [6] LeBlanc L, Simmons R. Continuous models for capacity design of large packet-switched telecommunication networks.
ORSA Journal on Computing 1989;1:271-86. [7] Gavish B, Neuman I. A system for routing andcapacity assignment in computer communication networks. IEEE
Transactions on Communications 1989;37(4):360-6. [8] Gavish B, Altinkemer K. Backbone network design tools with economic tradeofs. ORSA Journal on Computing
1990;2:226-52.
[9] Amiri A, Pirkul H. Routing andcapacity assignment in backbone communication networks. Computers & Operations Research 1997;24(3):275-87.
[10] Amiri A. A system for the design of packet-switched communication networks with economic tradeofs. Computer
Communications 1998;21:1670-8. [11] Amiri A, Pirkul H. Routing andcapacity assignment in backbone communication networks under time varying traffic
conditions. European Journal of Operational Research 1999;117:15-29. [12] Mahey P, Benchakroun A, Boyer F. Capacity andlow assignment of data networks by generalizedBenders
decomposition. Journal of Global Optimization 2001;20:173-93. [13] Queiroz M, Jr. CH. A heuristic for the continuous capacity andflow assignment. European Journal of Operational
Research 2003;146:444-59.
[14] Monma C, Sheng D. Backbone network design and performance analysis: a methodology for packet switching
networks. IEEE Journal on SelectedAreas in Communications 1986;4(6):946-65. [15] Lim Y. Minimum-cost dimensioning model for common channel signaling networks under joint performance and
reliability constraints. IEEE Journal on SelectedAreas in Communications 1990;8(9):1658-66. [16] Al-Rumaih A, Ahmed R, Bakry S, Al-Dhelaan A. A methodology for network topology design with link and node
failures tolerance. International Journal of Network Management 1995;6(1):42-64. [17] ChamberlandS, Sanso B. Sequential andparallel approaches to incorporate reliability in the synthesis of computer
networks. Journal of Network andSystems Management 1997;5(2):131-57. [18] Glover F. Future paths for integer programming andlinks to artificial intelligence. Computers & Operations Research
1986;19:533-49.
[19] Glover F. Tabu search-part I. ORSA Journal on Computing 1989;1(3):190-206.
[20] Glover F. Tabu search-part II. ORSA Journal on Computing 1990;2(1):4-32.
[21] Hertz A, Werra D. Using tabu search techniques for graph coloring. Computing 1987;39:345-51.
[22] Malck M, Guruswamy M, Pandya M. Serial andparallel simulatedannealing andtabu search algorithms for the
traveling salesman problem. Annals of Operations Research 1989;21:59-84. [23] Barnses J, Laguna M. Solving the multiple-machine weightedlow time problem using tabu search. IIE Transactions
1993;25:121-8.
[24] Dell'Amico M, Trubian M. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research 1993;41:231-52.
[25] Glover F, Laguna M. Tabu search. Dordrecht: Kluwer Academic Publishers; 1997.
[26] Osman IH, Laporte G. Metaheuristics: a bibliography. Annals of Operations Research 1996;63:513-623.
[27] Laguna M, Glover F. Bandwidth packing: a tabu search approach. Management Science 1993;39(4):492-500.
[28] Costamagna E, Fanni A, Giacinto G. A tabu search algorithm for the optimization of telecommunication networks.
European Journal of Operational Research 1998;106(2-3):357-72. [29] ChamberlandS,  Sanso  B.  Topological expansion of multiple-ring metropolitan area networks. Networks
2000;36(4):210-24.
[30] Berger D, Gendron B, et al. Tabu search for a network loading problem with multiple facilities. Journal of Heuristics
2000;6:253-67.
[31] Shyur CC, Wen UP. Optimizing the system of virtual paths by tabu search. European Journal of Operational Research 2001;129:650-62.
[32] Youngho L, Junghee H, Kugchang K. A iber routing problem in designing optical transport networks with wavelength
division multiplexed systems. Photonic Network Communications 2003;5(3):247-57. [33] Gavish B, Hantler SL. An algorithm for optimal route selection in SNA networks. IEEE Transactions on
Communications 1983;31(10):1154-61. [34] Narasimhan S, Pirkul H, De P. Route selection in backbone data communication networks. Computer Networks and
ISDN Systems 1988;15:121-33. [35] Gavish B, Pirkul H. Eicient algorithms for solving multiconstraint zero-one knapsack problems to optimality.
Mathematical Programming 1985;31:78-105. [36] Garey MR, Johnson DS. Computers andintractability : a guide to the theory of NP-completeness. San Francisco:
Freeman; 1979.
[37] Kleinrock L. Communication nets : stochastic message low anddelay. New York: Dover; 1964. [38] Kleinrock L. Queueing systems, vols. 1-2. New York : Wiley-Interscience; 1975-1976.
[39] Dell'Amico M, Lodi A, Maffioli F. Solution of the cumulative assignment problem with a well-structured tabu search
method. Journal of Heuristics 1999;5:123-43. [40] Battiti R, Tecchiolli G. The reactive tabu search. ORSA Journal on Computing 1994;6(2):126-40. [41] Crainic TG, Gendreau M. Cooperative parallel tabu search for capacitated network design. Journal of Heuristics
2002;8:601-27.
[42] Trafalis T, Kasap S. A novel metaheuristics approach for continuous global optimization. Journal of Global Optimization 2002;23:171-90.
[43] Ericsson M, Resende MGC, Pardalos PM. A genetic algorithm for the weight setting problem in OSPF routing. Journal of Combinatorial Optimization 2002;6:299-333.