TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 15, No. 2, August 201 5, pp. 390 ~  396   DOI: 10.115 9 1 /telkomni ka. v 15i2.830 1        390     Re cei v ed Ap ril 23, 2015; Revi sed  Jul y  5 2015; Accept ed Jul y  20, 2 015   Heuristic Approaches t o  Solve Travelin g Salesman  Problem      Malik Muneeb Abid 1 *, Iqbal Muhamma d 2   1 School of T r ansportati on a n d  Log istics, South w est  Jia o T ong Un iversit y , Che ngd u, Chi n a, 6100 31   2 School of Infor m ation Sci enc es and T e chno log y ,  South w e s t JiaoT ong Uni v ersit y , Ch en g du, Chi n a .  *Corres p o n id n g  author, e-ma i l : malik.mun ee b.abi d@h o tmai l.com      A b st r a ct   T h is pa per  pro v ides th e surv ey of the  he uri s ti cs soluti on  a ppro a ches  for  the travel in g s a les m an   prob le m (T SP). T SP is easy to understa nd, h o w e ver, it is  very difficult to solve. Due to co mp lexity i n volv e d   w i th exact sol u tion a ppr oach e s  it is h a rd to s o lve T SP w i thi n  feasi b l e  ti me . T hat ’ s  w h y  di fferent he uristi cs   are g e n e ral l y a ppli e d  to so lve  T SP. Heuristic s  to so lv e  T SP are  pr ese n ted here  w i th deta i l ed alg o rith ms. A t   the end, co mp ariso n  a m on g selecte d   ap pro a ches sh ow s the efficie n cy of appro a ches i n  terms of soluti o n   qua lity an d time consu m ed to  solve T SP.     Ke y w ords : T SP, heuristics, survey, NP-har d         Copy right  ©  2015 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  The com puta t ional compl e xity  theory make s  it  po ssible  to valid ate the  co ncepts  of  “ea s y” a nd “h ard ”  problem s an d the di stinction  a m on g them. Probl ems  can  be f o rmally  classi fied  based on th ei r co mplexity and if a pr obl em stri ctly be long s to the fa mily of NP-h ard o r  compl e te   probl em s, we kno w  in  a d vance that  there i s   little  ch an ce  of finding  an  efficient  and  ex act  algorith m  to   solve it. The  algorith m  fo r su ch  a p r o b lem ha s a n  executio n time bu rstin g   fo r   increa sing problem si ze s,  and  in   majo rity ca se s is  not feasi b le f o r mo st p r a c tical pu rp ose s .  Comp uters a r e playing eve r y effective ro le in so lving  different com p lex probl em s but the mat t er   of fact is th at some  proble m s a r e fun d a m entally  ha rd er to  solve. A l though, fo r some p r obl em s it  is po ssi ble to  develop inte lligent algo rithms that  sol v e the probl e m s expe ditio u sly, howeve r , it  seem s  sub s tantially hard  even in som e  cases im poss ible to come up with any solution [24].  Daven d ra [13 ]  defined TSP as, “Given  a set of  citie s  of different distan ce s a w ay from  each othe r, a nd the obj ecti ve of TSP is to find t he sh ortest p a th fo r a sale spe r son to visit every  city exactly o n ce  an d  return ba ck to  the  ori g in  city”.  TSP is  an i m portant  ap plied p r obl em  with   many fasci na ting variants;  like theoretical math e m a t ics, co mpute r  sci en ce, NP hard probl em,  combi nato r ial  optimizatio n  and o peration re se ar ch  [25]. TSP is cl assified  as  symmet r ic,  asymmet r ic a nd multiple T SP based on  the distan ce  and directio n betwe en two  cities in a gra p h   (Figu r e 1 ) . If distan ce be tween two ci ties is  same  in each di rection it is  symmetri c  wi th  undirecte d  na ture othe rwi s e it is asymm e tric.         Figure 1. Cla ssifi cation of  TSP      TSP ca n b e   solved  by u s i ng o p timal al gorit hm s  (e.g ., IP formulati on),  however, these   solutio n s are comp utationa lly  infeasibl e  and  it  i s   alm o st impo ssible  to gen erate   optimal  soluti on   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Heu r isti c App r oa che s  to Solve T r a v elin g Salesm an  Problem  (Mal ik Mune eb Ab id)    391 within  re aso n able tim e . Fo r thi s   rea s o n   heuri s tics are  used  to  solv e TSP. Thi s   pape r  provid es  a  survey of different ap proa che s  u s ed to  solve the TS P heuri s ticall y.      1.1. Illustration of TSP  The  co re o b j e ctive of TSP  is to  minimi ze the  total t r a v eling cost  of obje c t a r ou n d  tours.  In ord e r to  u nderstan d TS P, let us expl ore th e  given  belo w  exam ple. Figu re  2  sho w s the  ro ad   distan ce b e twee n the three town s i.e. ABC and a d d i tionally assu me that a sal e sp erson, wh ose  busi n e ss i s  t o  sell s l ubri c ant items to   different  com panie s  lo cate d in the s e th ree  citie s , m u st  travel (startin g from  home ) . Here the d e c imal  valu es  near the lin e  edge s in th e  diagram a r e t h e   driving dis t anc e s  between the c i ties .  In this    exa m ple, we  are assumi ng  that we h a ve a   symmetri c  T SP i.e.  the cost in going f r om A to B is  the same a s  the cost in g o ing from B to   A    but in asymm e tric TSP the co st coul d no t be the same  betwee n  the two point s.  In the given situation, one  que stion ari s es  in mind th at how many  TSP tours co uld be?   The  gen eral   answe r to  thi s  q u e s tion  is,  for th e  com p lete g r a ph  with  n  vertice s , the  num be r of   different TSP route s  wo uld  be Equation  (1).       !             ( 1 )       Figure 2. A 4 city TSP prob lem       Let us calcula t e the chea pe st t our by wo rking o n  abov e Figure 2 .    HABCH 8 2 + 1 40 +9 0+ 5 2 = 3 64  HACB H 8 2 + 1 02 +9 0+ 6 9 = 3 43  HCAB H 52 +10 2 +140 +6 9=3 6 3     Thus, g o ing from H to A, th en to C, then  to B and then  back H could  be the best choice.    1.2. Related  Wor k   In literature  TSP is used  in two forms:  i) combi n atorial optimi z ation versio n and ii)  deci s io n version. In first v e rsi on it i s  u s ed to  find a  minimum  Hamiltonian  cy cle a nd in l a ter   versio n to ch eck the existe nce of smalle r gra ph.   Theo retical compute r  scie nce  and  op e r ation s  resea r ch,  both fiel ds of  co mbi natorial   optimizatio n  contai ns TSP .  In this probl em, set of  cities a r e give n  with their  dist ances to fin d   the   sho r test rout e to each  city without visiting a ci ty twice. In 1930,  it was first formul ated a s  a   mathemati c al  model a nd a pplied to  so  many area s  to find their  op timal solutio n s  e.g., Clu s te ring   of array of data [1], Hand ling of a warehou se m a te rials [2] a nd  cry s tal struct ure a nalysi s   [3].  Re sou r ce co nstrai ned  sch edulin g pro b lem with agg regate dea dli ne also  solv ed with TSP [4].  Re sea r che s  [5, 6] took o r i enteeri ng a n d  pri z e  colle ction pro b lem s  as  spe c ial  case s of resou r ce  con s trai ned  TSP. One of the best  kno w n an d mo re  compl e x co mbinato r ial p r oble m  is Ve hicle   routing  p r obl e m , to dete r mi ne the  o r de r  of vehicl e fo r  cu stome r s se rving from fle e t of vehi cle s , is  being solved by  TSP  [7].  TSP is ea sy to unde rsta n d  but it’s real ly diffi cult to solve it. In 1 972, Ri ch ard  M. Karp  sho w e d  that  it is  NP-com plete to  solv e Ham iltonia n  cy cle p r o b l e m, whi c h  e x plains t he  NP- hard n e ss  of TSP. This ca n be ju dge d that ho w mu ch co mputatio nal difficulty i s  attached to  find  the optim al ro ute [9]. With  the p a ssa ge  o f  time TSP i s   getting m o re   and  more  so phisti c ated  a nd  solving in stan ce s are la rg er now. A brief view of TSP mileston es i s  given belo w  in Table 1.   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 15, No. 2, August 2015 :  390 –  396   392 Table 1. Sum m ary of the Mileston es a c hi eved in TSP (12)  Year   Research Tea m   Size of Ins t anc e   1954   G. Dantzig, R.  F u lkerson,  and S.  Johnson [14]   49 cities  1971   M. Held and R.M .  Karp [15]   64 cities  1975   P.M. Camerini, L .  Fratta,  and F. M a ffioli [16]  67 cities  1977   M. Grötschel [17]   120 cities  1980   H. Cro w der a nd  M.W. Padberg [1 8]  318 cities  1987   M. Padberg a nd  G. Rinaldi [19]   532 cities  1987   M. Grötschel and  O. Holland [20]   666 cities  1987   M. Padberg a nd  G. Rinaldi [19]   2,392 cities  1994   D. Applegate, R.  Bixb y ,  V. C h vátal, and W. Cook [2 1]  7,397 cities  1998   D. Applegate, R.  Bixb y ,  V. C h vátal, and W. Cook [2 2]  13,509 cities  2001   D. Applegate, R.  Bixb y ,  V. C h vátal, and W. Cook [2 3]  15,112 cities  2006   D. Applegate, R.  Bixb y ,  V. C h vátal, W. Cook,   and K. Helsgaun  [23]  24,978 cities      This pap er i s  o r ga nized  as foll ows:  Next  sectio n  provid es th e alg o rithm   details of  sele cted heu ristic sol u tion s  for  TSP. After  that all of these te chni que s a r e  analyzed a nd  comp ared for solution q uali t y and time consumed fo r  different probl em data.   At last co ncl u si o n s  and future di rection s  are prese n ted.       2. Heuris tic Solution Tec hniques   There a r e va riou s h euri s ti cs and  ap prox imate solut i on ap proa ch es,  which h a d  bee n   devise d  duri n g last de ca d e s, to find so lution wi thin  reasona ble time and  with 2-3 % optima lity  gap [8]. T h e r e a r e  num e r ou s a p p r oa che s   used t o  solve TSP  sh own in  li terature. So me   importa nt an d mo stly used a pproa ch es  are  enli s t ed h e re  with  their  appli c ation al gorith m s.   Variabl es for  these al gorithms are illustrated in Table  2.      Table 2. Illust ration of Vari able s   Descrip tion  Variable   Initial solution pr ovided b y  the us er    S  Objective function value  z  The best solution  S*  Cities in TSP (Nodes in  transporta tion net w o rk)   i, j  Population P  Gene rations G  Gene ration count er    N g en   Initial temperatur e   T  Cooling factor    r  Number of  times the tempera t ure  T  is decreased   ITEM P   Maximum numbe r of ne w  solution s to be accepted at each temper at ure  NLI M IT   Maximum numbe r of solutions evaluated at each te mperatu r e    NO VER  Gain par ameter   L      2.1.  Brute Forc e  Metho d    Algorithm for  TSP using Brute-force me t hod contain s   the followin g  step s:    Algorithm 1: TSP using Brute Force Me thod   Step 1: calcul ate the total numbe r of tours (w he re citie s  rep r e s e n t the numbe r of node s).   Step 2: draw  and list all the  possible tou r s.  Step 3: calcul ate the distan ce of ea ch to ur.   Step 4: choo se the sho r test  tour; this is the optimal so lution.    2.2. Greedy   Appr oach    Gree dy app ro ach  solve s  TSP by using t he five steps,  given in Algorithm 2.        Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Heu r isti c App r oa che s  to Solve T r a v elin g Salesm an  Problem  (Mal ik Mune eb Ab id)    393 Algorithm 2:  TSP using G r eedy Approa ch   Step1: Look  at all the arcs with minimu m distan ce.   Step 2: Choo se the  n  chea pest arcs  Step 3: List the distan ce of  arcs  starting f r om the mini mum dista n ce to maximum distan ce.   Step 4: Dra w  and che ck if it forms a Ham iltonian cy cle.   Step 5: If ste p  4 forms a  Hamiltonian  cycle than  we h a ve an optim al solutio n ; write down the  tour of the op timal solution  and calculate  their distan ce.    2.3.  Near es t Neig hbor He uristic   Algorithm 3 shows the met hodol ogy to solv e TSP by  Nea r e s t Neig hbor  Heu r i s tic.    Algorithm 3:  TSP using Neare s t Nei g h bor Heu r isti c  Step 1: Pick any starting n ode.   Step 2: Look  at all the arcs coming o u t of  the starting  node that hav e not been vi sited an d  cho o se the n e xt close s t no de.  Step 3: Repe at the pro c ess until all t he node s have b een visited at  least on ce.   Step 4: Check and  see if a ll node s are v i sited. If so  re turn to the sta r ting point wh ich give s us a   tour.   Step 5: Dra w  and write do wn the tour, a nd cal c ul ate the dista n ce o f  the tour.    2.4.  Bran ch and  Bound M e th od  Bran ch  and  b ound  techniq ue i s   comm o n ly  used  opti m ization  tech nique. F o rm u l ation of  TSP by using  bran ch an d b ound te chni q ue is given in  Algorithm 4.     Algorithm 4: TSP using Branch and Bo und Metho d   Step 1: Choo se a sta r t nod e.  Step 2: Set b ound to a very large value,  let’s say infin i ty.  Step 3: Choo se the chea p e st  arc bet we en the cu rren t and unvis ite d  node a nd a dd the dista n c e  to the current  distan ce an d  repeat while  the curre n t distan ce is le ss than the bou nd.  Step 4: If current distan ce i s  less than b ound, then  we are do ne   Step 5: Add up the distan ce and bo und  w ill be eq ual to the cu rre nt distan ce.   Step 6: Repe at step 5 until  all the arcs h a ve been  cov e red.     2.5.  2-Op t Algori t hm   For n no de s in the TSP proble m , the 2-Opt algo rith m con s ist s  of the steps  sh own in   Algorithm 5.     Algorithm 5: TSP using 2 - Opt Algorithm   Step 1:   Let S be the initial solution  provide d  by the user  and z its  objec tive func tion value. Set S*= s ,  z*=z, i=1 and  j=i+1=2.  Step 2:   Con s id er the  excha nge results in a sol u tion S that  has objective fun c tion value  z’ <z*,  set z* =z’  and S*=S’. If j<n re peat ste p  2; otherwi se set i=i + 1 an d j=i+1. If i<n, repeat  step 2 ;  otherwi se g o   to step 3.  Step 3:   If S ≠ S*, s e t S = S*, z = z * , i=1, j= i+ 1= 2 and go to s t ep  2. Otherwise, output S* as the best solutio n   and termi nate  the pro c ess.     2.6.  Greedy  2-Op t Algorithm    The g r ee dy 2-Opt  algo rithm is  a vari ant of  2-opt  algorith m . It con s i s ts of t he ste p s  s h ow n  in  Algo r i th m 6 .     Algorithm 6:  TSP using   G r eedy 2-O p t Algorithm   Step 1:   Let S be the initial solution  provide d  by the user  and z its  objec tive func tion value. Set S*= s ,  z*=z, i=1 and  j=i+1=2.  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 15, No. 2, August 2015 :  390 –  396   394 Step 2:   Tran sp ose Node i and  No de j, i<j. Com pare the  re su l t ing obje c tive function valu e z with z*. If  z  ≥ z* a nd j<n, set j=j+1 a nd repeat st e p  2; Otherwise go  to step 3.  Step 3:   If z < z * , set S*= S , z * =z , i= 1,  j= i+ 1= 2 and  go to s t ep 2. If z   ≥  z* and   j=n, set i=i + 1,  j=j+1 a nd re p eat step 2. Otherwi se, outp u t S* as the best sol u tion a nd termin ate  the pro c e ss.     2.7.  Gene tic Alg o rithm   This al go rith m is ba se d  on ge netics. The Ge net ic Algo rithm  works a s  shown in   Algorithm 7.     Algorithm 7: TSP using   G enetic Algo rit h m  Step 0:   Obtain the m a ximum num ber of individ uals in the p o pulation P an d the maximu m numbe r of  gene ration s  G from the user, gene rate  P solution s for the first gen eration’ s po p u lation ra ndo mly,  and re presen t each solutio n  as a st ring.  Set generatio n cou n ter N g en =1.   Step 1:   Determine th e fitness of e a ch  solutio n  in  the cu rre nt gene ration’ s  popul ation an d record the  string that ha s t he be st fitness.  Step 2:   Gene rate sol u tions for the  next generation’s p opulati on as follo ws:  1. Retain 0.1 P  of the solutions  with t he best fitness in  the previou s  popul ation.   2. Gene rate 0 . 89P solution s via mating, and   3. Select 0.01 P solution s from the previo us po pulatio n  rando mly an d mutate the m .  Step 3:   Update N g en = N g en + 1 . If N g en   ≤  G, go to Step 1. Otherwise sto p .    2.8.  Simulated Annealing (SA)   Statistical m e ch ani cs i s  t he ba si c id e a  of si mulate d ann ealin g  (SA). Analo g y  of the   behavio r of physi cal sy stems in  the  heat bath i s  main motivation of SA. Solution sta t e is  rep r e s ente d   by the tem p e r ature. Initiating  with  a n  in itial tempe r at ure,  algo rith m move s to   the   next temperat ure until it rea c he s a fro z en  state.     Algorithm 8:  TSP using Si mulated Ann ealing   Step 0: Set  S  = initial feasi b le sol u tion  Step 1: Repe at step 2  NOVER  times or until the number of succe s sful ne w sol u tions i s  equ al to  NLIMIT  Step 2: Pick a pair of ma chine s  ran dom ly and excha nge their p o si tions.   Step 3: Set  T =  rT  an d  ITEMP =  ITEMP +  1 . If  ITEMP  <= 1 00, go to  step 1; otherwise stop.     2.9. Neur al  Net w ork   In  th is  pr oc ess  a t  ea ch  pr oc es s i n g   s t e p   a  c i ty  is surv eyed. On  co mplete ite r ation visit s   all cities in a  pre s et order.   First of all a node  i s  sele cted from ran d o mly from the network an d a   gain pa ramet e r is u s ed to  attain the result and qua lit y if solution.  Algorithm 9 shows the wo rking   mech ani sm o f  neural net work.     Algorithm 9:  TSP using ne ural net wo rk  Step 1. Find the nod e j c  which is  closed t o  city i.  Step 2. Move node j c  and its neig hbo rs o n  the ring toward s city i.  The dista n ce each nod e wil l  move is determin ed by  a function f (L,  n), whe r e n i s  the distan ce  measured alo ng the loop b e twee n nod e s  j and j c .  n =inf (j- j c (m od N),  j c - j (mod N ))  Every node j is moved fro m  current po siti on to a new o ne.  The fun c tion f is defined to  be   f(L,n)=sqrt(1/2)*exp (-n 2 /G 2 )  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Heu r isti c App r oa che s  to Solve T r a v elin g Salesm an  Problem  (Mal ik Mune eb Ab id)    395 3. Discussio n s   Previou s  se ction demo n st rates th e different metho dologi es to  solve NP -ha r d TSP  probl em app roximately. Although, different te chniq u e s had b een  devised p r e v iously, but,  all  available te chniqu es a r e  not efficient in term s  of solution time  and qu ality.  Comp ari s o n  by  Mare dia  [10] sho w s  that Neare s t Ne ig h bor  heu risti c   works  well  bu t it is not  su re that it will  g i ve   us  solution s  good a s  b r ut e force. Moreover, g r eed y appro a ch i s  not a g o o d  app roximat i on  techni que  for TSP. Co mp arison  of Bra n ch  an d  bou nd te chni que  with  brute f o rce m e thod  is  presented in  Figure 3 (data extrac ted from Maredia [ 10]). SA algorit hm obtains has ability to find   the goo d qua lity final solutions  by mech anism  of  gra dually goin g  from o ne  solu tion to the ne xt.  The mai n  differen c e  of SA from the  2-o p t is that  the l o cal  optimiza t ion algo rithm  is often  re stri ct   their  sea r ch f o r the  optim al sol u tion in  a  downhill  di re ction which m ean th at the i n itial solution  is  cha nge d only  if it re sults in  a d e crea se  i n  the  obje c tive fun c tion val u e .  However ,  it is   s h own by   Kim et al. [11] that 2-opt al gor ithm  wo rks well  wh en the problem  si ze is l e ss tha n  50 citie s . F o r  comp ari s o n  o f  the app roa c hes  we  are referri ng to d a t a Kim et al. [11]. Data  extracted f r om Ki m  et al. [11] is plotted in Figu re 4 an d 5, a c cordi ng to result s it is ob vious that the  solution of T S P  usin g the  neu ral n e two r k o u tperfo rms th an all  other a ppro a che s  fo r all  pro b lem  sizes.  Ho wev e r,  if we  compa r e the  time  co nsum ed  to  so lve the  pro b le ms, it i s   ea sy  to re alize that  neu ral  net wo rk  approa ch i s  takin g  mu ch  more time  a s   comp ared  to  others. Ge net ic alg o rithm  h a s b een  used  for   many optimi z ation p r oble m s; ho weve r, the u s e  of  ge netic al go rith m for TSP h a s  di sadva n ta ges   of prematu r e  conve r ge nce and p oor  local  sea r ch  capa bility. These di sad v antage s ca n be   overcome by  adaptation  of other effici ent wo rk in g  algorith m s e. g., artificial immune  syst ems  [13].        Figure 3. Co mpari s o n  of Bran ch an d Bound Te ch niq ue with Brute  Force Metho d             Figure 4. Len gth Comp ari s on of TSP  Heu r isti cs   Figure 5.   Time Comparis on of TSP Heuris tics       Advantage s  of these h e u r istics  app ro ach e s  are th at they are  simple  an d  easy to   unde rsta nd. These req u ire  le ss  p r og ra mming and   storage  requi rements a nd  prod uce m u ltiple   s o lutions wit h  in less  time [ 26]. Howe ver, he uri s tics lo cal  imp r o v ements in  h euri s tics  can  be  sou r ce of lack in glob al prosp e ctive of obje c tive function.   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 15, No. 2, August 2015 :  390 –  396   396 4. Conclusio n  and Re co mmendation s  This p ape r p r ovide s  the  survey of dif f erent  he uri s tics u s e d  to solve TSP. First, an   example of T SP is pre s ent ed to give the idea of  TS P. This su rve y  is limited to some  sele ct ed  approa che s   becau se it is not possibl e  to cove r  all approa che s   here. So, onl y most relev ant  approa che s   are di scusse d here. Altho ugh a num be r of heuri s tics had b een  devise d  however;  some  are effi cient with  re spect to time and some a r e outpe rformi ng in sol u tion  quality. Future  work will consider  th e formulation  of heuri s tics to  solve t he TSP  in a  reasonable time  with bench  mark pro b lem  data of mile stone s prese n ted in Table  1.      Referen ces   [1]  La w l er EL,  Le nstra JK, Rin n o o y  AHG, Sh mo y s   DB. T he T r aveling S a l e sman Pr obl e m . Chich e ster:   John W i l e y .  1 9 85.   [2]  Ratliff HD,  Ro sentha l AS.  O r der-Picki ng  in  a  Recta ngu la r W a reh ouse:  A So lva b le   Case  for th e   T r avelin g Sal e sma n  Prob le m .  PDRC Re port Series N o . 81- 10. 198 1.   [3]  Bland RE, Shallcross DF.  L a rge T r av el ing  Sales m an  Probl e m  Arisi ng  from Ex peri m e n ts in X-r a y   Crystallo gra p h y : a Prelimin ar y Report on C o mp utatio n.  T e chnic a l Re port No. 730. 1 987.    [4]  Miller, Pek n y   J. Exact Soluti on of Larg e  A s y mmetric T r avelin g Sal e sm an Prob lems.  Scienc e 25 1.   199 1: 754- 761.   [5]  Balas E. T he Prize Col l ecti ng  T r aveling Sal e sman Prob lem.   Netw orks 19.  198 9: 621- 636.   [6]  Golde n  BL, Le v y  L, Vohr a R. T he Orienteeri ng Prob lem.  N a val R e searc h  Log istics 34.  1 987: 30 7-3 18.   [7]  Christofi des N.  Vehicl e Ro utin g, in T he T r ave lin g Sa lesma n  Probl em. In: La w l er, Le nstra, Rino o y  Ka n   and Shm o ys.  Editors . John W i le y .   198 5: 431- 448.   [8]  Reg o  C, Gamboa D, Glover F ,  Osterman C.  T r av eling sal e s m an pro b lem h euristics: le adi ng metho d s ,   implem entati o n s  and lat e st ad vances.  Euro p ean Jo urn a l of  Operatio nal  Re search . 20 11;  211( 3): 427- 441.   [9]  Cook W .  History of the T SP.  The T r aveli ng S a lesm an Prob l e m.  Georgia T e ch. 200 9.    [10] Maredi a  A. His tor y ,  A nal ys is, and   Implem ent atio n  of T r aveli ng S a lesm an   Probl em (T SP) an d R e l a ted   Probl ems. T h esis. Dep a rtment of  Comp u t er and Math ematica l  Scie nces Un iversit y  of Ho uston - Do w n t o w n . 20 10.   [11]  Kim IB, Shim IJ, Z hang M. C o mparis on  of T SP Algor ithms, Project for Mode ls in F a ci lities Pl an nin g   and Mater i als  Han d li ng. 19 98 .  [12] http:// w w w . mat h .u w a ter l oo.c a /tsp/histor y / mi le stone.html (ass essed o n  08- 0 6 -20 15).   [13]  Dave ndra D.   T r avelin g Salesm an Prob le m, T heor y  and Ap plic atio ns. IN T E CH ope n acce s s   pub lish e rs. 201 0.     [14]  Dantzi g G, F u l k erson  R, Joh n s on S. So luti on  of a l a rg e-scal e  travel in g-sal e sman pr ob lem.   Operati ons   Research 2.  19 54: 393- 41 0.  [15]  Held M, Karp RM.  T he traveling-salesm an problem and minimum spanning trees: part II.  Ma th em a t i c al  Progra m mi ng 1.   1971: 6- 25.   [16]  Cameri ni PM, F r atta L, Maffi oli F .  On impro v i ng re la xati on  methods b y  m odifi ed gra d i e n t  techniqu es.   Mathe m atic al Progra m mi ng Study  3.  197 5:   26-3 4 .  [17]  Grötschel M, P adb erg M. O n   the s y mmetric   traveli ng s a les m an  prob lem: t heor y  an d c o m putatio n. In:   R. He nn, B. K o rte, W Oettli.  Editors .  Lectu re N o tes i n  Ec onom ics a n d   Mathematic al  S y stems  15 7 .   Sprin ger, Berli n . 1977: 1 05-1 15.   [18]  Cro w d e r H, Pa dber g MW . Sol v ing l a rg e-scal e  s y mm etric travell i n g  sal e s m an pr obl ems  to optima lit y.   Mana ge me nt Scienc e 26.   19 8 0 : 495-5 09.   [19]  Padb erg M, Ri nal di G. Optimizatio n  of a 5 3 2 -c it y  s y mm etric traveli ng s a l e sman  prob le m b y   branc h   and cut.  Opera t ions Res earch  Letters 6.  198 7: 1-7.  [20]  Grötschel M, Holl an d O. A cutting pl an e  al gorithm for mi nimum p e rfect 2-matchin g s.  Co mp uting 39 .   198 7: 327- 344.   [21]  Appl egat e D, Bixb y R, Chv á ta l V, Cook W .  F i ndin g  cuts i n  the T SP (A  prelim in ar y  r e p o rt).  DIMAC S   T e chnic a l Re p o rt.  1995: 95- 0 5 .  [22]  Appl egat e D, Bixb y R, Co o k   W ,  Chvátal  V. On the soluti on of trav elin g sa lesma n  pro b lems .   Rhei nisc he F r i edric h-W ilh elm s -Univers ität Bonn. 19 98.   [23]  Appl egat e D,  Bixb y R, Chvát a l V, Cook W .  T he  T r aveling  Salesm an Pro b lem: A Comp utation a l Stud y.    Princeto n, Ne w  Jerse y , USA:  Princeto n Univ ersit y  Press. 2 006.   [24]  F a tma A, Karkor y  A, A Abud almol a . Imple m ent atio n of Heuristics for  Solvi ng T r avell i ng Sa lesma n   Probl em Usin g  Nearest Ne ig hbo ur an d Min i mum Spa nni n g  T r ee Algorith m s.  Internation a l Jour nal of   Mathe m atic al, Co mp utation a l,  Natural a nd P h ysical E ngi ne erin g.  201 3; 7(10).  [25] http://en. w i k i p e d ia.or g / w iki/T r avelli ng _sal esm an_ prob lem (a ssessed o n  08- 06-2 015).   [26]  T u rban E. Decision su pp ort and e x p e rt s y ste m . Macmillan s e ries i n  inform ation s y stem. 1 990.       Evaluation Warning : The document was created with Spire.PDF for Python.