(PDF) yujor96.pdf

Yugoslav J ournal of Operations Research 6 0996J. Number 1, 41 -54 THE CHAIN·INTERCHANGE HEURISTIC lIIETHOD ' Ne nad MLAD ENOVIC GA'RAlJ and Ecole d,w Hs utee Et udes Commerciele... University otMontrest. Mon treat. Canada. 113 T I V6 J ose A. MORENO a nd J . Marcos MORENO -VEGA Depsrtmonto de Bstad/sties , I. 0. y Computocion Univereided de La La{:lllla, Spein Abst r act: This paper describes a new Tabu search-like technique for solvi ng combinatorial optimization problems . The cham -interchange move is introduced .• which is an extension of the well -known I -interchange move . Ins tead of Interchanging one solu tion att r ibu te t hat is in the solution .....ith one that is not, four att ributes an' interc hanged . In t hat way the Tabu sea rch recency-based me mory is eas ily obtained, i.e., t he poss ib ility of getti ng out of the local optimu m trap can be ac h ieved without addit io nal efforts . Some location-allocation problema t hat cou ld be solved by t he same chain-interchange algorithm by on ly cha nging the objective function are HEitE'<! . Moreover. most of the problems list ed arc suggested for the first time to be solved by Tabu search me thod ( TS). Computer results arc reported. Keywords: Heuristics, loca tion. Tabu search. chain Interchange . 1. INTRODUCTI ON A new local search heuristic C hain-in terchan ge method for sol vi ng co mbinatorial optimization problems is proposed. It could be seen as a Tabu sea rc h me t hod adapted for a large class of problems, as well as an extended interchange heuris t ic. TS was int r oduced by Glove r (1 986) and indepe ndently by Ha nse n (19B6 ) (u nder t he name Steepest A scent Mildest Descent) as a mete-heurist ic designed to J;l't 11 global optimum to combinatorial opti mization problems. TS belongs to a class of J Wor k on this paper was initia lized during a visit of the first aut hor to La Laguna University . 42 N. Mladenovic!, J .A.Moreno, J .M Moreno-Vega I The Cham-Interchange Heuristic Method Local S earch Heurist ic Methods, or more specifically to a class of Descent -Ascent Methods (Hansen and Jaumard (l990)).The major components include a short-term memory process which is the core component of the search procedure, an intermediate memory process for regional ly intensifying the search, and a long -term memory process for globally diversifying the search . The sho rt-tenn memory process is implemented through a set of tabu conditions and the associated aspiration criteria. The idea is to prevent cycling in the descent-ascent process by avoiding reversal or repetition of previously visited solut ions . Intermediate and long-tenn memory processes are perfonned by restricting the search in a special subregion and by inducing the search in a new subregion of the solut ion space. TS has already been applied to an increasingly wide spect rum of problems. For a survey of a variety of successful applications, see Glover (1980, 1990 ) a nd Glover and Laguna(l994). For each particular problem researchers developed neighbourhood structu res, short-ter m, inter mediate and long-term memory processes in order to build a few TS rules in exist ing local search heuristic methods. We have the opposite purpose in this paper; find a class of optimi zation problems that could be soloed usi ng the same T S memory processes , i.e., t he same data st ructu re . Our work is based on the fact t hat there are many more opti mization problem s that cou ld be solved by TS t han data st ruct ures developed to solve them in an efficient way . Thus our method applies to a large class of combinatorial problems , and for each problem just t he subroutine evaluati ng the objective function value has to be changed. The method proposed in this paper is an extended. Interchange heuristic. Instead of interchanging two variables (attributes) in order to generate the neighbourhood of a cu rrent solut ion, we interchange the pos it ions of four variables. This simple extension of well known descent local search I -interchange methods all ows us to obtain the following properties: (i) move at each iteration to the best neighbouring solutio n , even if it is not better than the current solution (to avoid a local optimum t rap); (ii) introduce two waiting (tabu) lists (to prevent cycling). Lists consist of variables waiting to go out of the solution and to go into the solution respectively, Hence, we save t ime and memory by storing not the tabu solutions themselves, but one of t heir attributes; (iii) bring into the sol ution that variable wh ich has been out of the solution for the longest time (to induce the search in a new region of t he solution space.). Problem-specific knowledge now can be easily embedded in t he algorithm, or, any existing desce nt heurist ic method of t he Interchange type can be extended, using the same data st ructure . We shall illustrate ou r method on some discrete locati on-allocation proble ms . The paper is organized as follows. In the next section we formu late t he p -faci lity locat ion-al locat ion problem and give a list of some models t hat could be solved with our method by only changing the objective function. Ou r list of applications is meant to be illustrative, not exhaustive . In Section 3 we explain the rules of ou r Chain-Interchange (CO algorithm within the Tabu search (T S) framework . Computer experi ence is reported in Section 4. Sect ion 5 concludes the paper. 2. THE p -FACILITY LOCATION-ALLOCATION P ROBLEM The Location-Allocatio n (LA) problem consist of finding the best selection of N Mlade novit . J A MoM.'no. J .M. MOM.'no-Vega I The Chain-Interchange I teunsne Method 43 points to npe n facilities at them and th e way to serve th e users . The objective cost function to be minimized depends on t he relat ive s it uation of the facility points and the demand points. In a wide class of relevant location-allocation prohlems, every alternative solution consists of a fixed numbe r, say p , of facility points to he opened and t hen the optimal way t o serve t he U S(' r1' . For every set of p facility poi nts. the optimal allocat ion of users to the facility poin ts gives t he optimal cost . T hen t he problem consists of find ing the set of p facility points t hat minim izes the corresponding cost . These are t he p -facility location-allocation problems where the feasible sol ut ions are the sets of p facility poi nts a nd the objective functio n ra nges from simplest to those com puted by solving a n alloca t ion problem (see Brandeau a nd Chiu (1989». In order to formal ise discrete LA models, we con sider set L of m potential location points, set D of n demand points and m-en matrix with the costs c(x ,u ) of a ttending a user at 1.1 from a facility at x, v x E L, 'rIu E D. Every alternative solution is given by the set X of location points chosen for the facilities and the allocation of every demand point 1.1 E U to the facility point A (u ) E X that se rves eve ry use r a t 1.1 : The objecti ve function t o be mini mized depends on t he loca t ions X and t he allocations AU . For directly-all ocated models the objective cost function is monotone and every user at 1.1 ifl allocated to the facility point A (u ) such that c( A(u), 1.1 ) S c(x, 1.1 ), 'r/ x E X . The n t he solu tion space for these problems is S = {S . X I X ｾ L}. On the othe r hand . for any LA problem, given the allocation AU of the users, t he loca tion of the facilit ies is g1VE"n by X = AW). So the solution space can be considered to be S = {S = A I A : D -+ L }. Another way to give t he allocations consists of providing the partition of t he de mand po int se t in the points all ocat ed to eve ry facility po int , i.c., by giving U (x ) = {u E D : A (u ) '" x}, V x e X . However, in order for describe the search procedure for these problems, it is convenient t o use all the it ems rela ted with the solution ; i.e., the locations given by X . the a lloca t ions give n by A (. ) and the part it ion given by U (.) . In a ny implementation we can use a ny of t hem to perfo rm a ny step since X = A (lJ) and U (x )" A - 1(x ), v x , T herefore, we can use t he solution space: ｓ ］ｻ ｓ ］ Ｈ ｘ Ｌ ａ Ｌｕ ＩＯ ｘ ｾ ｌＬ A :D -+X, U : X-+2 D wit h A (u ) ., x iffu e U( x) } T he p -faci lity problem is a directly-allocated LA problem wit h solution space: s. {S o X I X .. LoIXI= p} T hen the object ive fun ction charncteriz ea the proble m . A list of t hese problems is give n in Brandea u and Chiu (1989). We selected 10 of them. T his list is meant to be illustra t ive, not exhaustive. All of the m a re directly allocated LA pro blems, ie., the object ive cost function depends on the best allocation for every user. So me of these problems are announced as maxi miz ation proble ms in the literature, but they a rc all formulated here by object ive fun ctions to be min imised . • 44 N. Mladenovic, JAMoreno, .1.M. Moreno-Vega I The Chain-Interchange Heuristic Method Let c(X,ul = min c(r ,u). ..x L T he p -median problem . The objective fun ction is the average of the allocation costs. 2. The p -center probl em . The object ive fun ction is the maximum of the allocation costs. 3. The balanced p -centdian problem . The objective fun ction is t he su m of the objective fun ctions of the p -median and the p -center problems. 4. T h e median p -center problem . The median p -center problem consists of finding t he opti mal solut ions of the p -center problem with min imu m average allocat ion costs. The objective function is also a linear combination of the objective functions of the p- median and p -center problem s. It can be defined by where a 2: max fl ( X ), For instance a = max d r , U). XEL .uaJ 5. T he p -capture problem . This problem consists of maximizing the am ount of dem and captu red by p facility points. We assume that the amount of demand of every user capt ured by competi tors is inversely proportional to the corresponding cost. The object ive fun cti on of thep-capture problem is: fsl X ) = I elY ,u) , uaJ c(Y,u )+c( X , u ) where Y represents locations t he competitors already estabilished 6. The p-covering problem . The opti mal solut ions of t he p -covering prob lem maximize t he amou nt of users within a distance r . The objective function is: !.I X )= I!u e U'el X , u» rll· 7. T he p -equtty problem. The opt imal solution s are those minimizing the differen ce bet ween the objective function s of the p-center and p-median problems . The object ive fun ctions is: N. Mladennvie, J .A.:\loreno , J .l\I. :\1or't-'no-Vega I T hE' Chain-In terc hange t t eu neuc Method 45 8. The p -anticenter problem . The opti mal solutions are those maximi zing the minimum of the allocation costs. The objecti\"f.' funct ion is: f8( X ) = max - c( X, u) .dJ 9. The p -mean problem . The objective funct ion IS t he average of squared allocat ion costs. 10. The p -tou-mcdlan peohlcm . The objective fun ction is the average of logarithm ofthe all ocat ion costs. (rc(Xl = lUl l Ilo< dX , uJ. • ,u 3. CHAIN-INTERCHANGE HE URISTI C METHOD Mos t of t he classica l heuri st ic sea rch proced ures a ppearing in the literature to be applied to location -allocation problems can he described using moves (or neighbour hood st r uct u res). &1.' Cooper (1964 ), Ha ndle r and Mirchnndani (979 ). Jacobsen (1983), Kue hn and Ha mbur ger (1963 ), Maranzana 0 964 l, Moreno et al. (199 1), Teitz and. Bart (1968) etc. This is formalised below . 3.1. Search moves for LA problems Let (S,n be the solution space a nd the object ive funct ion of a combi na to rial problem . A heuristic search procedure cons ists of a st rat egy to apply a se r ies of sea rc h moves. The sea rc h moves are operations to obtain a solution S e S s ta rting from another solution T e S . For a location-allocation problem, let S "" (X, A, V ) be the cu rrent solut ion "riven by t he loca t ions X , the allocations A and the partition V . T he usual elementary moves for locat ion -alloca ti on problems are the follow ing: • Reallocation of demand point u to facility point x . Take x e X und e e t/ wit b ｖ Ｈ ａ Ｈ ｵ ﾻｾｻｵｽ -c Ｎ - DoA (u ) _ x . • Opening of a facility point at x to serve demand point u , Take r e Xund e e D ...vith ｖＨ ａ ＨｵＩ Ｉｾｻｵｽ -c Ｎ - Do A(u ) 4- x . .46 N. Mladenovic!, J .A.Moreno, J .M. Moreno-Vega / The Chai n-Intercha nge Heuristic Method • Closing of the facility center att endi ng demand point u . - Take x e X a nd U e U(x ) wit h U(A (u » = {u} . - Do A (u ) .... x. • Translation of t he facility point at x to y . - Take xe X a nd Y fl X. - Do A {u ) .... y for vu e U (x ). The elementary moves only modi fy one item of the solution . Reallocat ion, Opening and Closing moves only modify the allocat ion of a demand point, so t he closed and opened facility center corresponds to singleton dema nd sets. A translation move only modifies the location of a facility point. The set of feasible solutions of a directly-allocated locat ion- allocat ion problem is S = {S z X I X ｾ L }. Let X be the current solution, t hen t he usual elementary moves for these proble ms are: • Addition. - Takex fl X a nd do X s-, X u {x }. • Elimination. - T ake x e X and do X .... X \ {%} . Finally, the set of feasi ble solutions of a p -facility location-allocati on proble m is S = {S '" X I X ｾ L : IXI ::: p} . Then the usual elementary move for these probl ems is: • Subtitution. - Take % E X andy fl X and do X .... (X \ {%})u {y }. Given a set of (elementary) moves. solut ion T is a neighbour of solut ion S if there is a move that produces T from S . The neighbourhood N (S ) of solut ion S is the set of neighbours of S . The ne ighbourhood st ruct ure is very important for the success of a search procedure. From elementary moves, one can define multiple or combined moves. 3.2. Chain-interchange moves A common property of R eallocation . Opening a nd Closing on the one hand and S ubstit ution moves on the other is that they all interchange pos it ions of some ent it ies (varia bles ) that belong t o the solut ion with some t hat are not in the solut ion. If the solution is represented by pairs (%, u ). % E L, u E D (or by edges of an associated graph). then reall ocati on . opening a nd closing moves mean that one ed ge is moved out of the, solut ion a nd a not her one goes in it. On the ot her hand, if the solut ion is re presented as a su bset of L(X l;; L then a n interc ha nge move is a su bstit ut ion move: one facility (ve rtex of associated graph ) goes in X. another goes out . N. Mledenovic, J ,A.Moreoo. .J M. Moreno-Vega I The Chai n-In te rch ange lI..urtstic Method 47 We s hall now int rod uce a new chrun-interehnruse move . This move could 1x1 obtained as lin extension of reallocation, ope ning, closing and subst it ution moves: if dements that s hould be inter-changed from one step to another are edges (.r,u ) of associated graph. we ha ve chain -reallocation , chai n-opening or clunn -elcs mg m OVC8 ; if suc h elemen ts a re facilities x E X. then a cbain -eubetuution move is obtai ned . We s hall describe in detail only the chai n-subst it ut ion move and give a pseudo-code for it in the next subsect ion . Analogous results hold for chain-realloca t ion . chai n-opening a nd chain-closing. Let us divide a set of facility points L into four disjointed subsets X I' TI , X 2 and T 2 , s uch that: x = X l U TI. Xl n TI =0 . IX I = p Ｑ ｾ ｜ｘ = X ZUT2• X 2 nT2 =0. !L \ X I = m - p , with IXII = p - I I . !TIl = t l .IX21= m - p - t 2 and ]T2! = re. Sets T1 a nd T2 are two tabu lists with card inalit ies t l a nd t z respectively. Then the chain-substi t ution move is as follows: • C h ain·s u b s ti t u tio n move. Take .r(l4< t E X I . X, Il E X z • X · E TI and ｘ ｾ E T2. Do the following: X, ｾ Ｈ ｘ Ｌ ｉｻ ｸ ｾ Ｌ }l U{x'}; TI .- (TI \ { x' })U{ X IIl }; ｘ Ｒ ｾ Ｈｘ Ｒ ｉｻ ｸ ＬＢ }lU{ x"}; ｔ Ｒ ｾ ｔＨ Ｒ ｘｻｉ Ｂ ｽ ｬｕ ｻ X O" ' }· As the result of the above fou r moves we obtain one substi t ut ion move. i.e.• W(- take .roul E X and XIIl E X and get X +- (X \ { .roul } )U { .rill }. The question is why do we need four ins tead of only one s ubst it ut ion move ? By taking out facility point .r....t from X , t;; X, not from X • we force some facility points to he part of the solution for a ce rtai n number of st eps, even if excl udi ng them fr om the solution wou ld produce a better solu t ion . By implementing T 1 a nd T2 as order lists and if x ' E T1 is chosen in f IFO (First In First Out) ma nner. the n each facili ty should stay in the solution for t, =1 I T, it erations . In t hat way at most t ,+ 1 ascent moves a re allowed in t he aee rch process (if the current solut ion is a local mi nim um ). T he sa me holds for facility poi nt x" • i.c.• before it ｾＨｊ ･ ｳ out from T 2 • it is forced t o be out of the soluti on for t 2 iterations. Let us ernphas izo this fact in the following Pro perty. Property I IAOt the lengths of tabu lists T 1 and T 2 be t J ami t z reepectwety. The sequence of solutio ns X ,. i = 1.2•... obtained by successnie implementation of the cha in- substit ution moues abaoe under the FIFO rule in T , and T 2• has a period of length u C!: t l + t 2 + 2. Proof. The seque nce Xu i = I .2•... could 'get into a loop' (a cycle of numbers that is repeated endlessly) only if the same solut ion X is obtained after u steps . \'rle s hal l show that (1 C!: t l ... t 2 ... 2 . Indeed . he minimum number of ite rat ions facility Ｎｲ ｾ Ｌ E Xl needs in orde r to belong to X, again is tl'" t2 '" 2 : one s te p to go out from X 1h ite- 48 N. Mladenovic, J .A}.foreno, .I.M. Moreno-vega I The Chain-Inte rehan ga Heuns uc ｾ ｉｻＢｴｨ ｯ､ ra tions being in T 2 because of the FIFO rule. at least one step in X2 and /1 s teps in T I • It is easy t o see that all other facilities that leave the solut ion after ｘ ｾ ｉ ｾ Ｏ could be in T I • thus. in the solution. _ To cha nge the positrons of two elements with indices out and in in some ordered set xU . it is necessary to perform 3 ope ra t ions: xx : :: x(out) ; x(out) : :: x (in ); x(in ) : :: xx, Note that for four changes we need only 5 operat ions (k and 1 are indices of the firs t entities introduced in tabu lists T I and T 2 respective ly): C b atn -su b s t tt u t to n -m ove (out. k. i c . L, x ) xr : '" x (out); x (out ) : '" x(k); r (k) : = din); r (in ): = x(l); r(i) : = xx . Note also that two important TS steps are perfo rmed with only these five stateme nts: (i) move to a new current solut ion ; Iii) update tabu list. 3 .3 . Algorithm Let the number of demand Ifixed l points n. the number of facility points m and the number of new facilities p be given . Let us assume t hat we a re able to calculate t he objective funct ion value /IX) if solution X !;; L is known . T hese are all the input data we need. Output values of the chain-substitution procedure a re : best found solut ion X <>P/ : { xoP/ (j ). j : l •. · ·· . P }andfoP/ ={(X oP/ )' Chain-suhstituti on (m , n. P. f opt. xopt (. » . S tep 1. Paramete rs of the meth.!::!d - t lo/2 : lengths of the tabu lists 1j and T 2 ; - nbmax: t he maximum number of iterations between 2 improvements; - nlong : number of times a long term memory process .....i ll be used (i . e.. how many times t he procedure will be restarted in a n unexplored area of solution space) Step 2. ｾ Let x(j ). j = 1, .. .• m be the set of facility locat ion points L in some order. The first p of elements of r (] ). j : 1•.. .., m represents the solution. - Find a n initial ordering of array x (j ). j = 1. _... • m. { Obtained at random. (i.e.• a random permutation of 1. .. . m ) or by any heuri st ic method (for example by a greedy heuristic ).} - Put xnp, ( j ) : = r{j ). j = 1•...• m ; fop, : '" { (xoP/ ); { X<>pf(j ) : = x (j I. j '" I, ... , P represen t s the incumbent solu tion - (best solut ion fou nd so far )} N, Mlndr-novic, .J.AMorpno, J .M. Moreno-Vega I The Chain-Interchange ncunsnc Ml'thod 49 - nbiter : = 0; { cu rrent iterat ion } - besti ter : = 0; { iteration when the best solution has boen found } - enll : = 1'; cnt 2 : = m ; { init ial values for counters in two tabu lis ts } - d () : : O; )= I, ... , m; { Long - term memory array d {j ),J =I , ... , m . represent the iteration number when variable J left the solution the last time. } Step ,1. Divers ificati on loop. (or It - I to n /ong do Step 4. • ot search , whil e (nbu er - besnter < k , nbmax ) do nbuer : = nbiter + I ; S tep4.I. F jnd..1.h e best soluti on in the neil;hh2w:hood - Generate a se t of neighbour sol ut ions .V(,x }; - choose non tabu solution x' nptimizinz ( ove r N ix ); I x' () differs from x (j ) in only two in dices ou t and In ) - check if there is a tabu solut ion better than {opl {a spi r ation lew!); in that case, Xopt : = .r. Around (m, n , p. t I, t2, x , t ', xapt, (opt , out, In ). Step 4.2, Kl'fP t he best incu mbent sol ution iC ir: < (opt ) then {opt : = ( ' ; xopt (out l : = x (m ); bestuer : » nbiter, e"diC·• Strp 4,3 . ll1.>date long · te rm memory d (x (out )l :- nbuer; Step 4.4. Move to t he new solut ion a nd ｜ｬ ｍｄＭ ｫＮ ｙｬ ｾ C h a in - s u b s t itution - move tout, cnll,m, cnt2, r ); ('nt l : = clIt l - I; If <Cnt l = p - tl ) then cnt l : '" p; (· " d iC; cnt2 : = cnt 2 - I; if (cn/ 2 = m - (2 ) then cnt 2 : .. m ; ('ndiC; endwhile Step 5. Piycrs ificllt joll { Br ing: int o t he sol ution variable j ' that has been out fur the lo ngest t ime, I . c. , - fi nd t he minimum or d(j ), J == P + I, . " , m, and - exchange its position wit h one fr om T, . } J O: :Ea rwnin{ d tj ).j ==p+ I , ... , m }; XX" : == x(p );x(p ) : =. r (j" ); x (j") : = xx; endfor h . Obviously, the complexity of one iteration or the descent-ascent search (S tep 41 depends on the complexity or the procedure Around (S tep 4.1.) s ince C hain- s u bsrl t u t fo n -m o ve is O ( 1), We shall now give a pseudo-rode for the greedy or stet'< 50 N. Mludenovie, JAMoreno, J .M. Moreno-Vega I The Ehai n-Interchange Heuristic Method pest descent mildest ascent (Ha nsen (1986)) version of the algorit hm , i .e., a vers ion t hat explores the complet e neighbour hood consisting of p (m - p ) solut ions. T hen modifications in order to get defferent versions are obvious: (i) partial greedy - take one facility out of t he soluti on at random and exchange it with al l m - p facilit ies t ha t do not be long to the curre nt solution; (ii) anxious search - e nume rate all neighbourhood solutions u ntil the first improvement ; (iii) random search • take u (a parame ter) nei ghbourhood solut ions at random: (iv) random walk • take one neighbour hood solut ion at random , etc. Note that for the random wal k algorit hm we need no tabu lists Itl ::. t 2 : 0 ), since the probability of cycling is al most o. A similar conclus ion holds for ra ndom sea rch. Note also that l -sabstitutw n move (wit h al l versions mentioned above) can in fact be viewed as a special case of ou r chain-interchange move, where the para meters t 1 '" ITII and t 2 '" IT2 1 are set at zero. The detailed pseudo-code of Around follows . Arou n d {m, n, p, t l , ra. x, f", (op/. ' xopt ,out.in ) [" := big ; fo r i = I to P { Enumerate candidates that go out of the solution} jj : = x(i); for k '" p + 1 to m { Enumerate candidates that go into the solution} x(i ) : : x( k); { Interchange facilities } { : '" {( x ); { Find objective function in x } if (i ｾ p - t l and k s: m - (2 ) then { Keep the best non tabu solution} if (( c [" J then r := ( ;out :: itin :» k ; endif e lse { Aspiration criterion } if (( < (opt ) then (opt : = ( ; out :'" i; in :'" k ; x oP/(out) :: x (i n ); eodif; eodif: e n d fa r h j x (i ) : '" ii . end for i ; The Around procedure employs a simple type of as pira tion cr iterion. consisting o f re movi ng a tabu stat us from a t ri al move when it yields a solut ion be tter t han the best obtai ned so far « opt ). Then it becomes both, the new cu rrent and new incumbent solut ion. 3.4. Extensions In the framework of TS bot h inte nsifica ti on and di versi fication of t he sea rch are performed using so - called long . term me mory function . It has been not- N. Mladenovie, J A Mort>no, J .:\I, Moreno-vega I The Cham-Interchan ge Heuristic ｾｬ､ｨ ｵ､ :il ed t hat search with memory has many more cha nces to visit unexplored regi ons of tf-e solut ion space t han ra ndo m mult istart sea rch. Moreover, mult ist a rt implcmentution suffers from 'cont ru l-Iimlt catastrophe (see Boese , Kahng and Muddu ＨｬＹｾ ｈ ﾻ Ｉ when the problem size grows la rge. In Boese , Kahng and Mudd u (994) it is shown t hat usually in combinatorial probl ems. V {'!'Y good solu tions a re located near other good solut io ns . That result m ay explai n why Simu la ted a n nealing, tabu search and other descent-ascen t local search heur istics ha ve been so successful in practice. But these also explain .....hy TS hass been successful even without usin g the long-term me mory function ( M'C Glo\'l'r a nd Laguna 1994 & 3.4. for s uch a pplica t ions). However; there arc easy ways to imple-m ent TS long -t er m memor ies in nur algorith m. One possihility has al ready been e xplained in steps 4.:1. and 5 of the . algorithm : dj r epresents the last iteration number when facility point) Iutt ri buto of t he solu tion) has been in the solut ion (S um and McKt>O....'11 (1993 1). Note that o nly o ne o pe ration in each iteration is m..eeded to update sequence d) (St ep 4 31. An other pos.eibrhty is to introduce frequen cy-based-memory (Glow r and Laguna (1994 Jl in the cha in- intercha nge method . I...t r ) represe nt counts of the number of occ ur re nces of a facility point ) in t he soluti on in previous it r-rations . Whe n improvement with loca l search is no longer possible, intensification a nd diversification cou ld be performed usin g array r j tin Step 5 of the a lgorithm ) in so me of the following .....ays: Table 1 : Results for 47 European Cities: m oxit» 10000, nlong = I , I J = I , 12""3 Obiecnve function val ue 'l> deviation CPU Time (sec) ｉｾ RW l -int CS I RW l -int CS I HW l -int CS 28;11 28711 29938 287 11 0.00 4 .27 0.00 9 .00 0.36 2.47 10 17677 17845 18474 .17677 0.95 4.51 0.00 5 .M 0.4 2 1.55 15 12749 12918 12749 12749 1.33 0 .00 0 .00 4 47 0.73 1.29 20 9328 9762 9fJ57 9328 4 .65 3.53 0.00 :l96 0.75 1.!5 25 6561 6908 6920 6621 529 5.47 0 .9 1 368 053 1.06 30 44 55 4705 4530 4455 5.61 1.68 0.00 3.50 0.59 0.98 • Intensification by Setect tc n . Take p largest elements from rJ and put cor respond ing facilit ies into t he "lew solut ion. Among them , put correspo ndi ng facilities into the new t hat co rr espond to t 1 largest members of r) in T 1 : • Uiversification by Nega tive Selection. Bring into the so lut ion p facilities with cor respo nding P s ma lles t vulues of arruy r) (o r dJ ) , etc. 4. COMPUTATIONAL EXPERI ENCE T wo sets of experi ments .....ere conducted for the p-median prob le m only . The 52 N . Mlade novie, JAMoreno, J .M. ｾｦ ｯｲ･ｮＭｖｧ｡ ｬ The Cham-Interchange Heuristic ｾ ｴ･ｨ ｯ､ fir st one examined road distances between 47 important European cities (Moreno. Garcia and Moreno-Vega (1994» ; the second one used t he Ruspini (1970) data for 75 fixed points, which is widely referenced in classification or clu steri ng' t heory. Wit hout 105 5 of gen erality, in all testi ng it is assu med th at a set of potential faciliti es is equal to a set of customers (L =-D, m =-n ). We reported in Moreno, Moreno and Mladenovic (1994 ) a comparison of Tabu search. Simulating An nealing and Genetic Algorithms in solving the p -med ian problem . It was s hown that the Tabu search method gives better results than bot h the Simulating Ann ealing and Gen etic Algorithm . Here we compare the res ults of our Chai n-Substit ution method (CS) ....rith another two well -known methods: the Random Walk (RW) algorithm (wi t h local improvem ent of the solutio n ) and descent I-I ntercbange (l -Int}. In the Random Walk algori t hm both, the facility that goes out and t hat goes in are chosen at random. The new solut ion determines the partit ion of the set of customers into p groups. Local imp rovement cons ists of solving separate ly p l -fecility problems. i.e., the best center for each given set of customers is found. We obtain t he I· Interchange met hod as a special case of our Chain-Interchange met hod by setting param eters t 1 and t z to zero (tabu lists are empty). RW and CS terminate when a given maximum number of iteratio ns maxit is reached , while l -Int stops naturally (whe n t here is no better solution in the neighbourhood of a cu rrent solution ). The res ults for the 47 European cities problem are given in Table 1. p represents the number of new facilities and Z" PI t he exact minimu m value (Klose (1994 » . The next columns contain the objective fu ncti on val ues, % deviation calculated relative to Z" PI and CPU times for all methods compared. Ta bl e 2 : Results for Ruspini data: marit=- 25000, nlong = 1, t l =l. t2=3 Objective fun ction value % deviat ion CPU T ime tsect z RW l -int CS R\V l -int CS RW l -int CS 4- I. 779 ,68 512.81 779.68 5 15.14 796.44 5 12.8 1 779,68 5 12.81 o.00 0.45 2.15 0.00 0 ,00 0,00 49 .57 29 .5 1 1.68 3.52 14.09 8.67 15 389.98 390.28 393.83 393,83 0.08 0.99 0 ,99 22 .75 5.45 7.12 2. 314.10 3 18.66 315.05 3 15.05 1.45 0.30 0.30 19.20 6.90 6.83 25 252.43 263.50 257 .45 255.80 4.39 1.99 1.33 17.12 6.11 5.97 30 199 .41 2 14.28 208 .56 207.37 7.45 4.59 3.99 15.79 5 68 5.40 35 159.90 169 .88 166 .48 163 .10 6.24 4.11 2.00 14.93 5.07 4.98 4. 127.63 139.56 132.46 128,62 9.35 3.78 0. 77 14.30 4.74 4 62 The results for Ruspin i data are summari zed in Table 2. using the same format as T able 1. T he Chain-Substitution (CS) algorit hm out-performs both l -I nt and RW while using smaller CPU times. I 5. CONCLUSIONS The I- Interchange (swap) move was s uccessfully applied to a large class of combinatori al problems, but it did not allow escaping fr om local optima traps. We suggest a simple extens ion of this move , chain-in tercha nge move, that allows us to obtai n an efficient descen t-ascent local search heurist ic of the Tabu search type. The list of the implementation s of Ltnterchange. and thus chai n -interchange moves is very large. Even the simplex method for linear programming a nd some con- ca ve minimization met hods are of t ha t type: one variable goes out of the busis, another goes in . On the ot her hand, the same problem could ha ve different interchange st rat egies, i.e., di fferent data. st ruct ures coul d he developed to solve t he snrne problem b)' t he using interc hange method. For example, in dircctly-ullocuted LA probl e ms t lu- same solution can be represented as a subset of vertices (Iocnnona] as well WI a subset of edges (a lloca t ions) of so me graph . Obviously, the sot of neighbourhood solution s obtained by all pa.sesible interchanges in both cases is not HlP same . This fact eoulrl Iirmt a general a pproach in which problem-specific knowledge is ignored . In ｴｨｩｾ paper we suggested some "middle" approach : recogn ize a class of problems wit h eimilnr properties , stich t ha t the sa me data st r uct ure (the sa me I1l".'orithm l mil)' be applied. W{,lIddrl'!'" ed our a ttention to loca tion-allocation problems which huve similar problem-specifi c k now ledge . To solve them we developed a version of the chain-interchangr- method , the cha in-substitution algorithm . Future work on t his "mid dle" ap proach wit h the cbain.interchanee methods co ul d be deve loped in four direct ion s: (iJ enlarge the class of problems t hat could be solved efficie nt ly with the cha in-eubeutution a lgor ithm proposed in & 3,;) of this paper (by on ly changing the subrout ine that eva lua tes objective function). a nd compare r esul ts with other gooQ heur istics (for each particular problem ), TI.('St' could be for e xample p -clu ster problems, n-dlsperslon problems. simple plant location problems. q uadra tic knapsack proble ms. concave minimization problems etc., {iil to solve ｬ｡ｲｾＧＮ instances of L\ problems extend the basic ve rsion of the chasn-subetuuuan algorithm usinJ: some hybri ds o r other kn own idl'(t.'l fro m TS; (iii) develope data structures that a llow implementation (If ot he r versio n of the chnin-interch nn ge method suc h as chain- reallocation , cha in -opening, cha in -closing etc, a nd compare results with the chain- substitution a lgor ithm; (iv ) in this pa per we propose a t -chein -intcrche a ge method. Obvi ously it cou ld be generalized to a k -cbain -intercharuie algo rit hm . Then it becomes 8 hybrid of t he Varia ble Neighbou rhood Algo rithm (l'o1Iadt'novlc (1995) and TS. Acknowledgment . Thi s work was pa rtly supported b)' project number 911237 of the Gobi erno Autonomo rip Canurlas. Spa in. The fir st a ut ho r was al so s upported by the Offi ce of Naval Research gra nt N000 14·92.J· 119-1 , Canada . REFERENCES III Brandeau. M,L., and Chiu , 58. "An overv iew of rep resentative problems in locat ion research", Managf'mt'llt &/f'ItN' 35 (1989) 6 45·674. 121 Boese , D.K., Kahog, B.A. , and ｾｉ ｵ ､ ｵ Ｌ S " KA new adapt ive multi-start tec hnique for combmatoricl global optimiza tions", OperollOM ｒ ｦＧ Ｎｾｯ Ｂｨ utters 16 (1994 l 101-113 131 Cooper. L., "Heuristic met hods for locat ion-allocation problems", SIAM Rf'I!It'U' 6 096-1 1 37-53 . 1' 1 Glove r, F., "Fu t ure paths for integer progmm r mug and links to uruftcal intelligence", Comput. & Ope r . Rt's . 5 ( I!JH6 l 533·549 . 15) Glover, F., "Tabu search Part J". ORSAJ. Computing I (l9H9 J 190-206 161 Glover, F'.• "Tabu search Part W. ORSA J . Computing 2 11990 ) 4-32. PI Glover. F'.• and Laguna. M.• "Tabu search", in C. Rt>P\'('!l(I'd.l, M odr rn ｬｉ ｦＧ ｬｉ ｮ Ｕｴ ｬ ｾ Tf'C'hmqllr. for Combinatonal Problt'mJf (e ha ptr r 3), Oxford, Blackwell. 1994. Annal. of OperatlOfts R esearcti 41 0993 13-28 . N. Mladenovit, J.AMoreno., J .M. Moreno-Vega I The Chain-Interchange Heuristic Method (8) Handler, G.Y., and Mirchandan i, P .B., Location on Networks, MIT P ress . 19 79. (9) Hansen, P., "The steepest ascent mildest descen t heuristic for comb inato rial programming", P rese n ted at t he Congress on Numerical Methods in Combinatorial Optimiz.alion , Capri , ltaly, 1986. [IOJ Hansen, P., and J a umard, 8. , "Algorit h ms for t he maximum satisfiability problem", Cnmputing 44 (l990) 279-303. {1I ] J acobse n, S .K., "Heuristic for the capacitated plant location model", E.J.O.R . 12 (983) 253-26 1. (12) Klose, A., "A comparison betwee n the Erlenkot ter algorithm and a branch and bound a lgorit hm based on eubgr adien t optimization to so lve the uncapacitated facility location problem", OR Proceeding , Spri nge r, 1994, 335-339. [13J Kuehn, A.A., a nd Ha mburge r M.J., "A heuristic program for locating warehouses", Management &ience 9 (1963) 643-666 . [14) Maranzana, F.E., "On the location of supply points to minimize transportation costs", OperatUJM Resrarch Quarterly 12 (1964) 138-139 . (15) Mladenovit , N., "Variable ne igh bourhood algorithm - a new mete-heuristic for comb inatorial opti mization ", Optim ization days , Montreal, May 10-12, 1995, pp-22. (16) Moreno, J.A. , Moreno-Vega, J ., and Mladenovit , N., "Tabu sea rch and simulated an nealing in p-median problem", CORS '94 - Optimization days , May 29 - June I, 1994, pp- 125 . (17) Moreno, J.A. , Garcia, R.L., and Moreno-Vega, JA , "A parallel genetic algorithm for the discrete p-median problem", Studies in Locational Analysis , 7 (199 4) 131-14 1. (18) Moreno, J.A. , Rodriguez, C., and J imenez, N., "Heu rist ic cluster algorithm for the multiple fa cility location-al location problem", Revue de Automatique, In fonnatique et de Recherche OperatUJnelie 25 (199 1) 97- 107 . [19 ) Ruspini, E.I-I., "Numerical methods for fuzzy clustering", Informat ion &iences 2 (l970) 3 19-350. 1201 Sum, M., and McKeown, '"Tabu search applied to the ge neral Ilxed charge problem", Annals of Operations Reuarch 41 (1993 ) 405-420. (2 1) Teitz, 10.1_8. , and Bart, P., "Heu ristic methods for estimating the generalized vertex median ora weighted graph", Operations Research 16 (1968) 955-961.