Int ern at i onal  Journ al of  El e ctrical  an d  Co mput er  En gin eeri ng   (IJ E C E)   Vo l.   8 , No .   6 ,  Decem ber   201 8,   pp. 4 713~ 4723   IS S N: 20 88 - 8708 ,  DOI: 10 .11 591/ ijece . v8 i 6 . pp 4713 - 47 23          4713       Journ al h om e page :  http: // ia es core .c om/ journa ls /i ndex. ph p/IJECE   Hybrid  Genetic  Algo rithms  an d Si mulated Ann ea lin g fo r  Mul ti - trip  Vehicl e  R ou ting Pro blem  w it h Time W ind o w s       Ama li a  K art i ka   Ariy an i 1 ,  Wayan Fi rd aus M ahmud y 2 , Yusu f  Pri yo  Anggod o 3   1,2 Dep ar t m ent   of   Inform at ic s ,  Fa c ulty   of   Com puter Sci en ce,  Br awi jay a   Univer sit y ,   Indone sia   3 Data   Sc ie nt ist, I lmuone  Data, In donesia       Art ic le  In f o     ABSTR A CT   Art ic le  history:   Re cei ved   Ma r 28 , 201 8   Re vised  Ju l  13 ,  201 8   Accepte d  J ul  27 , 2 01 8       Vehic l e  routi ng  proble m   with  ti m e  windows  (V RP TW)  is  one  of  NP - har d   proble m .   Multi - tri p  is  appr oa c h  to  solve  the  VRP TW  tha t  looki ng  tri p   sche duli ng  for  g et s  best  result.  E ven  though  the r e  are   var ious  al g orit hm s  for  the   probl em,  there  is  opportunit y  to  impr ove  th e  exi sting  al gori th m s  in  orde r  gai ning  a  b et t er  result .   In  th is  re sea rch ,   g enetic   al gorit m   is  h y br idi z ed  with  sim ula te d  annea li ng  al gori tm  to  solve  the   proble m .   Gene tic   al gorit m   is   emplo y ed  to  exp lore   global  sea rc h  are a  and  sim ula te d  ann ea l ing  is  emp lo y e d   to  expl o it   lo ca l   sea rch   area.   Four  combinat ion  t y p es  of  genetic   al g orit hm   and   sim ula te d  anneal ing  (GA - SA )  are  te st ed  to   get   th e  b est  soluti on.   Th e   computat ion al   e xper iment  show s  tha t  GA - SA 1  and  GA - SA 4  ca n  produc ed   the   m ost  opti m al   fit n ess  ave ra ge  val ues  with  ea ch  v al ue  was   1. 0888  and   1. 0887 .   How ever   GA - SA 4  ca n  found  the   best  f itness   chr om osome  faste r  tha n   GA - SA 1.   Ke yw or d:   Gen et ic  al gorithm   Hybr i d  al gorithm   Mult i - trip    Rou ti ng  pro blem   Si m ulate d  an ne al ing  al gorith m   Copyright   ©   201 8   Instit ut e  o f  Ad vanc ed   Engi n ee r ing  and  S cienc e .    Al l   rights re serv ed .   Corres pond in g  Aut h or :   Wayan  Fir dau s  Mahm ud y ,    Faculty  of Com pu te r  Scie nc e,   Bra wij ay a  U niv e rsity ,   Vetera n  Roa d,  Ma la ng ,  Indo ne sia .   Em a il :  wayanfm @u b. ac.id       1.   INTROD U CTION     The  gr ow t h  of  the  nu m ber   of  tourist s  in  tourist   destinat ion s  l ocated  in   Ba nyuw a ngi,   East   Java ,   Ind on esi a,  is  increasi ng   as  th e  infr ast ru ct ure  i m pr ov em ents  by  the  gove r nm ent.  W it h  t he  increa sin g  nu m be r   of   visit s,  the re  are  s om e  pr oblem s  fo r  t ourist s  com ing   f ro m   ou t  of  to wn   or   from   abr oa d.   So m e  of   them   fin d  it  diff ic ult  to  determ ine  wh ic h  sigh ts  to  visit   with  the  tim e  l i m i t  they   hav e  set   du e  to  lim ited  acce ss  to  av ai la ble  inf or m at ion .  T hey  can   not  de ci de  the   trip  base d  on  their   tim e  lim it   wi th  m ini m u m   c os t  a nd  ar rive   to  th e   destinat io n  on  op e ning  hours  [1 ] .  That  pro ble m   us ually   cal le d  as   sche duli ng  pr ob le m .  Schedulin g  pro bl e m   is  to  m ake  a  sche du le   to   visit   to ur   places  that  t otal  tim e  of   th e  sche du le   is  ba la nced   unde r  m any  con trai ns  [2 ].   Sche du li ng   pr ob le m   is  com plex  pr ob le m   becau se  t o  ge t  best  s olu ti on  m us t  be  balan ci ng   al l ocati on  the  visit   that  to  pass  al l   co ntrains .  T he   m a in  f ocu s   of   sche duli ng  is  to  m ini m iz e  the  total   durati on  of  the  visit   [ 3].  I n  add it io n,  the  de la y  of  sche du li ng   durin g  ch ang e   the   pa rt  is  ve ry  im po rtant  becau se   ge t  in flue nce   the   tota   durati on  of  t he   sche du li ng  [ 4] .  The  researc h  f oc us   to   get  m axi m u m   so lu ti on   with  hav i ng  m ini m u m   c os t  as  low  as possible .  The  t ourist  m us t  ha ve  a  sc he du le   tri p.   T o  s ol ve  this  pro ble m   need s  a  ce rtai n  m od el .  Anggo do  et   al   [1 ]   had   fi nish e d  this   pro blem   with  sa m e  data.  It  ca n  so lve  t he  pro bl e m   with  veh i cl e  routing   pro ble m   appr oach.  Veh i cl e routin g pro blem  is p ro ce dure  for sol ving  sche du li ng  pro blem  in  veh ic l e r ou te .   Veh ic le   routin g  prob le m   with  ti m e  wind ows  is  a   com bin at ion  sc hedul e  visit ing  m any   places  wit h  tim e  con strai ne d  ser vice  pro visio n  [ 5].  V RPT W   is  us e d  to  fi nd   op ti m al   ro ute  of   veh ic le   w hich   le ave  a   centrali zed  de po t.  T he  s olu t ion   of   r oute   ge ts  fr om   geog raphical ly   disp erse d  c us tom ers.   Fi nd i ng   ve hicle  sche du li ng  an d  routing   plan  a nd   m ini m iz ing  total   ro ute  distance  are  the  focus  of  the  probl e m   [6 ] .  VRPT W  is   us e d  in  lo gisti cs  m anu factur i ng   with  the  c om plexit y  pr obl e m .  As  m any  as  co ns trai n  m akes  the  pro ble m   as  diff ic ult  as.  In  fact,  to  so lve  VRPT W   pro ble m   is   easy   wh en  just  hav i ng  on e  de pot  an d  few   nodes  but  th e   pro blem   wil l  beco m e  co m plex  w he n  ha ving   m any  depots  and   node s.  I n  add it io n,   the  pro blem   will   be   m or e  Evaluation Warning : The document was created with Spire.PDF for Python.
                         IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  8 , N o.   6 ,  Dece m ber  2 01 8   :    4713   -   4723   4714   com plex  wh e n  be  f ound  the  fl exible  pat h  [7 ] .   Ba sed  on  that,   VRPT W   is  a  non - determ insti c  po ly nom inal - tim e   hard  ( HP - ha r d)  prob le m   [6 ] .  P rev i ou s  resea rc h  that  pr opos e d  A nggo do   et   al   [1 ]   ha ve  co nst rain  day  of   tr ip  the   tourist .  Eve ry  finish in g  the  tri p  on  once  day  the  tourist   m us t  go   bac k  to  th e  ho te l  or   ce ntr al iz ed  depot.  I n  this   stud y,  the  t ourist  will   visit   fo r   m any  days  so   the  pro blem   has  m a ny  trips.  It  is  cal le d  m ul ti - trip  VRPT W   that   diff e re nce  pro blem   with  on l y  VRPT W .  M ulti - trip  VRPT W   m akes  pro blem   to  be  com plex  becau se   on ly  VRPT W wit hout m ulti - trip ju st nee d on e  leave a nd go bac k t o  the  cent rali zed  depot.   Most resea rch e rs  ha ve bee n  gr ow i ng   i nterest  to u se c om bin a ti on  a nd   de velop i ng   he ur ist ic s algorit hm  to  so lve  VR PT W   pro blem .  T he  hybri d  he ur ist ic   al go rithm   gets  ver y  str ong  searc hing  an d  the  so luti on  qu al it y  of   m et ho d  is  high  [8 ] .  Ge ose iri  &  Gh a nnadpo ur   [ 5]  propose d  goal   appr oach   to  s olv e  ro utin g  pro blem ,  bu il di ng   a nd  im ple m ented  ge netic   al gorith m   (G A)   t o  so l ve  the  pr ob le m .  Re centl y,  m any  researchers  us e d  gen et ic   al gorithm   to  so lve  the  prob le m .  Ur sa ni  et   al   [9 ]   us e d  ge ne ti c  al go rithm   in  routin g  prob le m   fr am ewo r k.   G eneti c  al go rit hm   can  get  m ax im u m   so lutio n  for  S olo m on   benchm ark  prob le m ,  research  pro blem ,  and   E - Com m erce  Supp li er   [ 7],  [ 10 ] ,   [ 11 ] .   H oweve r,  ge netic   al gorithm   has  wea kness  i n  local   searchi ng  s olu t ion .   S olv i ng  th e  r ob le m   m us t  i m pr ove  to   ef f ect ive  an d  ef fici ent  searc hing   m axi m u m   so luti on.   Wang  et   al   [1 2]  propose d  com bin at ion   ge netic   al go rith m   with  par ti cle  swar m   op ti m ition .  T he  f ocus  of   Gen et ic   al gorithm   find s  glob al   so luti on  a nd   pa rtic le   swarm   op tim iz a ti on   sea rch  local   so luti on.   It  is  balanc e   and  ex cel le nce   but  need i ng  m or e  tim e  fo r   co m pu ta ti on.  Im pr ov i ng  cr osso ver  ge netic   al gorithm   us e   cy cl ic  sh ift  cr os s ov e r   with  hill - cl i m bing  m echan ism   to  gen erate  a  child  in  init ia li zi ton   proses  [ 13 ] .  It  is  go od   m od el   to  so l ve  t he  prob le m   bu t  this   m od el   j ust   th e  f ocu s   f or  sea rch i ng  local   a r ea  beca us e  c rosso ver   m od ific at ion  m akes ch a nge  fo c us  s earc h  a r ea.   Ba sed  on   it ,  w e  nee d  m od el   to  s olv e  w hich  balance  t o  sea r ch  s olu ti on  a nd  fa st  com pu ta ti on .  In  fact,  gen et ic   al gorit hm   sh ow s  on e   m od el   can  to  get  m axi m u m   so luti on  with  f ocus  in  gl ob al   search .  Pr e vi ou sly ,  gen et ic   al go rithm   had   c ou l d  i m ple m entat ion   in  this  ca se  [ 1] .  Ma ny  proce dures  do  to  get   good  l ocal  sea rch.  I n  this  stud y,   ad di ng   c om bin at ion   one  he ur ist ic   m et ho d  w hich   fo c us   i n  local   searchi ng.  Cr osso ver   m od ific at ion  is  no t  done  be cause  ca n  cha ng e  f ocu s   g e ne ti c  al go rithm   from   glo bal  se arch   t o  local   s earch .  Ma hm ud y  [ 14 ] ,   i m pr oved  sim ulate d  an neali ng   (SA)  f or   r ou ti ng  pr ob le m   gets  the  best  so luti on  and   fast  com pu ta ti on.   Si m ulate d  an ne al ing   fo c us   on  local   sea rc h,  w hen   us i ng  la rg e  data  sim ulate d  a nn eal i ng  te nds   to   ge t  poor   so luti on.  In   t his  researc h,   we  pro po se  ne w  c om bin at ion   m od el   of  ge netic   al gorithm   and   si m ulate d  ann e al in g  (GA - SA)  to   sol ve  the  pro blem .  The  pro po s ed  m et ho d  will   te st  with  oth e r  m od el   [ 15 ] .  Fo c us   this  rese arch   i s   bu il di ng  new  com bin at ion  of  ge n et ic   al gorithm   and  sim ulate d  ann eal in g  an d  com par e  al l   G A - S A   com bin at ion  t o get m axi m u m  so luti on.       2.   RELATE D  W ORK   Pr e visious  res earch  a bout  r ou ti ng  prob le m   hav e  done  to  get  m axi m um   so luti on .  I t  is  no t  ne w   pro blem   ho we ver  ve ry  intere sti ng   t o  fi nd  t he  m od el   w hic h  s olv i ng  in  m any  co ndit ion s .  T he  sam e  data  ha d  been  fi nish e d  by  A nggo do  [ 1],  it   was   fi nis hed  usi ng  genet ic   al go rithm .  It  propose d  one - c ut - po i nt  cr os s ove r   and   reciprocal   exch a ng e  m utati on   to  get  the  so l ution.  to   get  m axi m u m   so luti on  it   was  us ed  per m utat ion   m od el   fo r   ch ro m os om e.  Pre vious  st ud ie s ,  G A  ca n  so l ve  routin g  prob le m   [9 ] .  T hat  stu dy  pro po s e d  com bin at ion   m uta ti on   ope r at or   a nd  rec om bin at ion   ope rator  f or   t he  gen et ic s  al gor itm   op erato r.   In   t hat  pro blem ,  chr om os o m e  rep re sentat ion   was  us e d  pe rm utatio n  m od el .  G A   was  us e d  to  s olv e  r outi ng   pro ble m   with  m any  co nst rains  i.e .  vehi cl e  with  li m ited  ca pacit y,  de po t  c onstrai ns,  an d  ti m e  windows   co ns trai ns  [ 5].  that  researc h  got  m axi m u m   resu lt   beca us e  th e  m ai n  fo c us   w as  the  te ch niqu es  gen et ic   al go rithm   that  us ed  be st  cost - best  r oute   crosso ve r,   se qu e nce  best  m utati on ,   an d  pe rm utati on   m o del  f or   c hrom os om e  represe ntati on.   Ba sed  on  previ so us  stu dies, GA  is goo d  m eth od  t o  fi nd  so l ution  in g lo bal search i ng  an d  t he  best  ch r om os om e   represe ntati on   for ro ute  prob l e m  is p erm ut at ion  m od el .   Rou ti ng  pro blem   will   get  m axi m u m   so luti on   wh e n  have  m eth od  wh ic h  balance  to  fin d  s ol ution .   It  is   fo c us   on  gl ob a l  and   l ocal  sear ch.   GA  can  do  fin ding  s olu ti on  in  global  sea rch,  so  nee ding   m e tho d  ca n  find   i n  local   search .  Ma hm ud y  [1 4]   prosese d  i m prov e d  sim ulated   an neali ng  to   so lve  r outi ng   pro blem .  It  go t  go od   so luti on  with  fast  com pu ta tio n.  Com bin at ion   GA   a nd   S A  will   get  best  so luti on   whic h  rather   tha n  othe r   m et ho d.   G A  do  fi nd i ng   s ol ution   in   f ocus  gl ob al   sea rc h  an d  S A  do  fin ding  s olu ti on  in  f ocus   local   sear ch.   T o  get  bette r  s olu t ion   will   be  us e d  ada ptive  c hrom os e  [5 ] .  It  is   good  m et ho d  howe ver   to  ne ed  one’ s  proce dure  to   com bin at ion   G A  &  SA.  Faty anosa  et   al   [ 15 ]   had   finis hed  hybri d  GA  an d  SA   t o  s olv e  be nch m ark s  f unct ion .  In   that  resea rc h  us e d  exte n de d  interm ediat e  cro ss over  a nd  rando m   m utatio n  f or   operato r  G A.   I n  this  s tud y,   we  will   us e  hy br id  GASA  wh ic h  pro pose d  by  Faty an osa .  oth e r  tha n  that,  will   pro posed  proc ed ur e  hybri d  GASA  and c om par e w it h  Fat ya no sa ’s GAS A  m et ho d.         Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Hyb ri d Ge netic  Alg or it hms  and Si mu l ated A nn e alin g  fo r   . .. ( Ama li a K ar ti ka  Ariy an i )   4715   3.   DESCRIPTI ON OF THE   PROBLE M   Veh ic le   Ro uting   P r ob le m   wi th  Ti m e  W in dows  (V RP T W)   is  on e  of   the   m os t  stud ie d  VRP  issues .   The  c oncept   of   VRPT W  i s  th e  de velo pm ent  of  VRP  pro bl e m s  with  t he  a dd it io n  of  new  co ns trai nts  th at   is  a   tim e  wind ows.   Thu s ,  the  se rvi ce  of   each  c ust om er  m us t  be  sta rted   an d  te r m inate d  base d  on   t he  tim e  wi ndow s   that  ha ve  bee n  determ ined.   I f   the  ve hicle   di stribu te s  up  be fore  the  c us t om er' s  window s   tim e,  it   is  su bj ect   to   the  wait in g  poi nts,  wh il e  the  distrib ution  ve hicle   that  com es  after  th e  cus tom er ' s  windows  ti m e  exp ires,   th e n  it  is su bject  t o pen al ty  poi nts  [16].    The  pur pose  of  VRP T W ' s  op ti m iz ation   pro blem   is  to  determ ine  the  shortest   dista nce  route  to   m ini m iz e  trave l  cost  a nd  the  nu m ber   of  ve hi cl es  without  breaki ng  the  ti m e  windows  a nd  ve hicle   ca pa ci ty .   The  j ou rn ey   st ar ts  from   a  sing le   de pot  then  go e s  to  eac h  of  the  scat te re d  custom ers.   T he   distrib utio n  veh ic le   m us t  reach  th e  cust om er' s  place  betwee n  the  c us tom er's  tim e  windows.   The   total   weig ht  of  th e  good s   trans ported  s houl d  not  excee d  the  capaci ty   of   the  veh ic le .   Veh i cl es  that  hav e  finish e d  visit ing   the  cu stom er   node  m us t  return  to  the  init ia l  dep ot  withi n  the  prede fin ed  tim e  wind ows  de pot  [17].   Mult i - Trip  V ehicl e  Rou ti ng  P r ob l e m   (MT - VRP )   is  one  of  the   dev el op m ent  of  cl assic   VRP   pro blem s  in  wh ic h  a  ve hicle   travels  on   m ulti ple  routes  within  a  c ertai n  tim e  fr am e  [1 8].  T he  MT - VRP  is  a  s pecial   veh ic le   route  issue  where  each   veh ic le   ca n  s er ve  m or e  tha n  one  tri p  wh e re  e ach  tri p  sta rts   f ro m   the  de pot,  passes   seve ral  custom ers  an d  en ds   up  in  t he  depot   an d  the   total   c us tom er  dem a nd  sho uld   not  exceed   cap aci ty   [19].  Mult i - Trip  VRPT W  app li es   MT - VRP  conc ept but the re is  addit ion   of ti m e lim it  o f  wi ndows in  it .   In   t his  stu dy,   hybri dizat io n  of   ge netic   al gorithm   and   s i m ulate d  ann e al ing   is  us ed   to  so l ve  the   pro blem   of   Mult i - Trip  Ve hicle   Rou ti ng  P rob lem   with  Ti m e   W in dows  w hich  is  ab out  sch edu li ng  to uri st  rout e   in Bany uw a ngi R ege ncy. T here are se ve ral c onditi ons that l i m i t t he  stu dy.   a.   Ther e  are  19 t ourist  data an d 1 4 ho te l  data  use d  in  this  resea rch   b.   Trips  are se t f or  3 days an d oc cup y  only  1   ho te l as de po t   c.   Trav el  is  ass um ed  us i ng the  car a nd road  cond it io ns  sm oo t hly   d.   The ro und t rip   tim e is assum e d  to  b e  the  sam e   e.   Ti m e w indo ws  tourist s start at  05.00 - 19.00   f.   Fit ness value  de rive d  f r om  tot al  trav el  ti m e a nd total  to ur ist   at tract ion  ca n be  visit ed w it hi n  3 days   g.   The  m or e to uri st o bj ect s a nd t he  le ss t rav el  ti m e required wi ll  r esult i n g rea te r  fitness  v al ue   h.   Penalty   value   is  the  total   va lue  of  vio la ti on  a gainst  ti m e   wind ow s   to uri st  obj ect   an d  tim e  wind ows   tourist s       4.   ALGO RITH M USED   4.1.   Genetic  Algor ithm   Gen e ti c  Algor it h m   is  on e   of  searc h  a nd  optim iz at ion   al gorithm s  base d  on  natur al   s el ect ion   a nd  gen et ic   m echan ism s  that  hav e  bee n  de velop e d  as  eff ect ive  op ti m iz ati on   a ppro a ches   to  so lve  co m plex  pro blem s [ 20 ] . G eneti c alg or i thm  ap pr oac h ca n  hel p  fin d  a  g oo d  so l ut ion   for  com plex  m at hem atical  p ro blem s  su c h  as   the   V RP  pro blem   [21].  Mult i - T rip   Pr oble m s  VRP T W   is   a  c om bin at or ia l  optim iz at ion   prob le m   by   form ing   the  app r opriat e  repre pen ta ti on  so l ution   that  will   get  op tim al   so luti on   in  the  us e  of   ge netic   al gorithm   for  M ult i - Trip   VRPT W  pro blem .  In   t his  stud y,   we   use   proce dure   of   ge netic   al gori thm   that  is  show n  i n    Figure  1 [1 ] .       Init iali za t ion  p ar amete r  GA   GA   (stopping  co ndit ion)   {   Cal culat ing  fi tnes s of  chr om osom e   //   doing   rep rodu ct ion   to  g et ne w  chr om osom e   Cross over   using   One - Cut - Point  C ross over   Mutat ion   using  Resiproc a l  Ex ch ange   Mut at ion   Sele c ti on  using   Repl a ce m ent Sel ec t ion   }     Figure  1 .   Proce dure  of g e netic  algorit hm       4.1.1.  Ch r om osom  Repre sen tation   In   case  a bout  VRPT W,   c hro m os o m e  is  an  encode  of   de sti nations   perm uta ti on   that  are  visit ed  by  tourist .  Usi ng   per m utati on   w il l  include  al l  of   t ourism   destinat ion s  s o  ge netic   al goritm   can  sea rch   optim u m   so luti on.  Ch rom os o m  r epr ese ntati on  c an  b e   seen i n  Fi gure  2.     Evaluation Warning : The document was created with Spire.PDF for Python.
                         IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  8 , N o.   6 ,  Dece m ber  2 01 8   :    4713   -   4723   4716       Figure  2 .   Ch rom os o m e rep res entat ion       Af te r   getti ng  t he  c hrom os ome   res ults,  ne xt  ste p  is  to   cal cu la te   the  fitness   value   of  the   c hrom os om e   that  has   bee n  f or m ed.   T he  fitness  cal c ulati on b egi ns   as   if  it   inserts   a h otel i nd e x  on  a  c hrom os om e.  In   t he  first  gen e  of   the  c hrom os om e  inser te d  the  ind e x   of  the  sel ect ed  ho te l,  f or  exa m ple  the  ind ex   of   the  sel ect ed  hote l   is  4,   t hen   t he  hote l  ind e x  4  is  inserted   at   the  beg i nn i ng  of  t he  c hrom os ome .  O nce  th e  ho te l  ind ex   is  ins erted,   the  ne xt  ste p  is  to  insert  the  tourist   obj ect   gen e  one  by  one  on  the  ch r om os o m e,  if  the  total   du rati on  of  the  tourist   visit   ha s  excee ded  14. 45   t he n  the  i nse rtion   of  the  hote l  ind e x  4  ret urns.   A fter  the   insertio n  of   t he   ho te l  ind e x  the   proc ess  of  e nterin g  the  ret urn  to uri st  ge ne  is  done  with  the  sa m e  pr oce ss  unti l  the  day  lim it   is  e ntere d.   I n  thi s  stud y  it   is  assum ed  that  the  trip  is  done  within  3  days  so   that  the  pr oc ess  of   e nterin g  the  chrom os om e  gen e  is  done  i n  3  trips .  I f  the  proces s  of  enter ing   the  ge ne  ha s  been   c om plete d,   the n  the  end   of   the chr om os ome  is re - inse rt ed  the  hotel   in dex 4.   The  cal culat io n  of  fitne ss  va lue  is  influ e nc ed  by  the  pa ra m et ers  of   tra ve l  tim e  ( ti me ),  penalty ,  an d  nu m ber   of   t ourist  destinat io ns  that  can   be  visit ed.   In   t he  tim e  par am e ter   the  gr eat e r  t he  value  of  ti m e,  the   sm a ll er  the  fitness  value   obt ai ned   so   eq uat ion   1  is   use d  di vid ed   by   1  +  tim e,  the  ad diti on   of  value  1  in  th e   tim e  par a m et e r  is  us ed  t o  avo i d  infi nity   value  if  there  i s  an  occ urrenc e  of   ti m e   value  equ al   to  0.  In   the   increasin g  pe na lt y  par am et er  pen al ty   val ue  will   reduce  th e   fitness  value   s o  th at   t he  pen a lt y  equ at ion  is  us e d  m ul ti plied b y t he value  - 1 f or  the p e nalty  v al ue  to  b e  m inu s,  if the re is  no penalt y t hen  t he penalt y val ue  e qu a l   to  0.   I n  the  pa ram et er  of   the   nu m ber   of   at t racti on s ,  the  le ss  num ber   of   visit ed  to ur ist   sit es  will   red uc e  the  value  of   fitnes s  so   that  the  va lue  of   t he  nu m ber   of   to ur ist   at tract ion s  di vi ded   by  the  nu m ber   of   ideal   tourist  at tract ion   that  can  be  visit ed  within  3  days  as  m any  as  10   at tract ion s  [ 1].   In   this  stu dy  Eq uation  1  sho ws  th e   functi on  to  cal culat e  the  fitn ess  value .   T he   exam ple  of   c hrom os om e’s  fitness  cal cula ti on   can  be  se en  in    Table  1.      =   1   1 +  + (    − 1 ) +                 10 ,       ( 1 )       Table  1 .   C hro m os o m e’s  Fit ne ss Cal culat ion   Ch romos o m e   Path   No d e   Starting   Ti m e   Tr av el  Ti m e   Arr iv e  Ti m e   Ear liest   Ti m e   W aitin g   Ti m e   Start   Visit  Du ration   Fin ish   Latest  Ti m e   Pen alty   1   4 ,8   5 :0 0   2 :0 6   7 :0 6   5 :0 0   0 :0 0   7 :0 6   3 :0 0   1 0 :0 6   1 9 :0 0   0 :0 0   8 ,17   1 0 :0 6   1 :1 2   1 1 :1 8   8 :0 0   0 :0 0   1 1 :1 8   3 :0 0   1 4 :1 8   1 7 :0 0   0 :0 0   1 7 ,1   1 4 :1 8   1 :3 2   1 5 :5 0   5 :0 0   0 :0 0   1 5 :5 0   3 :0 0   1 8 :5 0   1 7 :0 0   1 :5 0   1 ,4   1 8 :5 0   2 :2 1   2 1 :1 1   5 :0 0   0 :0 0   2 1 :1 1   0 :0 0   2 1 :1 1   1 9 :0 0   2 :1 1   2   4 ,12   1 :0 0   0 :3 7   1 :3 7   5 :0 0   3 :2 3   5 :0 0   3 :0 0   8 :0 0   1 9 :0 0   0 :0 0   1 2 ,2   8 :0 0   2 :0 2   1 0 :0 2   5 :0 0   0 :0 0   1 0 :0 2   3 :0 0   1 3 :0 2   1 9 :0 0   0 :0 0   2 ,3   1 3 :0 2   1 :0 2   1 4 :0 4   5 :0 0   0 :0 0   1 4 :0 4   3 :0 0   1 7 :0 4   1 7 :0 0   0 :0 4   3 ,4   1 7 :0 4   2 :5 7   2 0 :0 1   5 :0 0   0 :0 0   2 0 :0 1   0 :0 0   2 0 :0 1   1 9 :0 0   1 :0 1   3   4 ,14   5 :0 0   0 :4 0   5 :4 0   8 :0 0   2 :2 0   8 :0 0   3 :0 0   1 1 :0 0   1 9 :0 0   0 :0 0   1 4 ,10   1 1 :0 0   2 :1 9   1 3 :1 9   5 :0 0   0 :0 0   1 3 :1 9   3 :0 0   1 6 :1 9   1 9 :0 0   0 :0 0   1 0 ,4   1 6 :1 9   2 :1 7   1 8 :3 6   5 :0 0   0 :0 0   1 8 :3 6   0 :0 0   1 8 :3 6   1 9 :0 0   0 :0 0   Total   1 9 :0 5     5 :0 6   f itn ess   - 4 .21 0 1       Af te r  g et ti ng t he result  of tra vel tim e and p e nalty , f it ness  is cal culat ed by  us in g  E quat ion  2 .        =   1   1 + 19 . 05 + ( 5 . 06   − 1 ) +   8 10             (2)      =   − 4 . 2101     4.12.  Cro s sove r   In  this  stu dy ,   cro ss over  pr oce ss  us es  one - c ut   po int  cr os s ov e r   [22].  The  nu m ber   of   of f spring  ob ta ine d  from   crosso ver   ra te   x  pops ize .   In   t his  m et ho d,  the  c ut  point  value  will   be  ge ner at e d  ra ndom ly   with  a  range  of   values  0 to  c hrom os om e leng th - 1.       Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Hyb ri d Ge netic  Alg or it hms  and Si mu l ated A nn e alin g  fo r   . .. ( Ama li a K ar ti ka  Ariy an i )   4717   4.1.3.  Mut at io n   M utati on   proc ess  us i ng  Re ci procal  E xchan ge  M utati on   [ 22 ] .   The   num ber  of  offs pr in g  m utati ons   resu lt s  f r om   m uta ti on  r ate  x  pops ize .  In   t he   process  of   m utati on   the  firs t  ste p  is  to  sel ect   1  ind i vidu al   at   rand om .  In   the   Re ci procal  Ex change  M utati on  m et ho d,   2  r andom ly   sel ected   in de xes  will   be  sel ect ed  w it h  a  range  of  0 - c hrom os om e   le ng th - 1  a nd e xch a nge  bo t h values   of the selec te d  gen e  in dex.     4.1.4.  Sele ctio n   At  the  sel ect io n  ste p,  the   m eth od  t o  be  us ed   is  Re placem ent  Sele ct ion   bec ause  ca n  getti ng  m axi m u m   so luti on  [ 1] .  T he  pr i nciple  of  the  rep la cem ent  sel ect ion  operator  is  th at   if  the   off sprin g  re producti on  has  a   fitness  value   gr ea te r   tha n  t he  par e nt  the n  offs pr i ng  wil l  rep la ce  t he  par e nt  Offspri ng  obta ine d  from   the   m uta ti on   proce ss  will   rep la ce  the  par e nt  if  t he  offs pr i ng   ha s  gr eat er  fitne ss  than  the  pa r ent,  if  the  cros so ve r   process  that  ha s 2   pa ren t s , th e n  sel ect ed  1 pa ren t  with t he  lo west f it ne ss  va lue   [ 23] , [2 4] .     4.2.   Simula ted A nnea ling   Si m ulate d  an ne al ing   ( SA)  c on sist s  of   optim izing   the  “ m el t ing ”  pr oc ess  with  the  appr opriat e  tem per at ur e ,  then   lo wer i ng   the  te m per at ure  slow ly   un ti l  it   "fr eeze s"  a nd  no  furthe r  process  [ 25 ] .  At  t he   beg i nn i ng   of   the  process ,  the   m et a l  will  be  heated.  T he n,   the  tem per at ur e   is  lower ed  slo wly  to  avo id  cr acki ng   to  m ini m iz e  the  ene rg y  us e d  [26].  S A' s  flo w  ca n  helps   G A' s  ind i vidual  to  get   co nver ge nce  t o  a  m inim u m   global  [27].  T he  highe r  the  tem per at ure  an d  the   lowe r  th e  value  of  the   so luti on,  the  gr eat er  the  c ha nce  of   receivin g  a  les s tha n op ti m al   so luti on  [28].  Figure  3  s hows  pro ce dure  of s i m ulate d  an nea li ng   wh ic h  is  use d.       Init iali za t ion  p ar amete r  SA   SA   (stopping  co ndit ion)   {   If  (t  ≥   final  te m per at ur e  {   d 1 = fit n ess (c hro m oso m e)   S n = Crea t ing  Nei ghborhood  Solut ion  using Scr amble  Mut at ion   d 2 = fit n ess (S n )   If  (d <  d 1 )   {   Init ial  α = r andom [0, 1]   Init ial  p = Probabi li t y   If  (α   <  p )  {   S = S n   }   }  el se   {   S = S n   }   }   }     Figure  2 .   Proc udure   of   sim ul at ed  an neali ng       Wh e re  S   is   m a xim u m   chr omoso m e  w hich  i s  get  from   resul t  of   G A.   d 1   a nd  d 2   a re  fit ness   of  S   a nd  S n .   S n   is  ne w   chrom os om e  fr om   Neigh bor hood  scram ble  m uta ti on   proce ss  and   resu lt   s olu ti on  of  SA   i s  S .  Pro bab il ty   value  in S A  is  ge ner a te d  usi ng  E qu a ti on   3 .       =   1 ( 2 − 1 ) 1                   ( 3 )     4.2.1.  Neig hb or hood Searc h   In  this  st ud y,   SA   will   ge ne r at e  neih bor hood  s olu ti on  by   us i ng  Sc ram ble  Muta ti on  [ 27] .  At  this  op e rato r  two  r andom ly  sel ected   points  are  s el ect ed  and   s w it ch  the  chrom os om e  po sit ion  between   tw o  po i nts  rand om l y   fo r  e xam ple sh ow i n  Fi gure  4 .         Evaluation Warning : The document was created with Spire.PDF for Python.
                         IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  8 , N o.   6 ,  Dece m ber  2 01 8   :    4713   -   4723   4718       Figure  3 .   Scra m ble  m utatio n process       4.3.   Hy brid  Gene t ic  A lg orithm   an d  Simula te d Anne aling   Ba sed  on  goodne ss  an d  we akn e ss  each  al gorithm ,  com b inati on   gen et ic   al gorithm   and   sim ulate d   ann eal in g  will   furn is h  weakn ess  each  al gori thm .  Ho we ver,   nee ding  one  c om bin at ion   to  get  m axi m u m   resu lt .   GA - S A1  is  proses ed  m et hod  in  t his  stu dy,  wh il e  GA - SA2,   G A - SA3 ,  a nd  G A - S A4  are  c om par is on     m et ho d [ 15 ] .     4.3.1.  GA - S A1   Com bin at ion   GA - S A1  is  sta rted  by  i niti al i zat ion   G A  para m et er.  The   se cond   proce ss  i s  r unning   S A   with  init ia l  so luti on   us in g  ch r om os om e  with   best  dan   worst   fitness.  It  is  stop   un ti l  it erati on   m axi m u m   i n  G A.   Pseudoc ode  of  GA - S A1 can  be seen  in  Fig ure  5.       Init iali za t ion  p ar amete r  GA - SA   GA   (stopping  co ndit ion)   {   // running   GA   proc ess   S = chr om osom e  with  best   fit n ess  of  GA   SA   (stopping  co ndit ion)   {   S = chr om osom e  with  best   fit n ess  of  GA   // running   SA   proc ess   }   S = chr om osom e  with  wors t  fi tne s s of  GA   SA   (stopping  co ndit ion)   {   S = chr om osom e  with  best   fit n ess  of  GA   // running   SA   proc ess   }   }     Figure  4 .   GA - SA1  process       4.3.2.  GA - S A2   GA - S A2   proc ess  sta rts  by  ru nnin g  G A   first  un ti l  st opping  co ndit ion ,  the n  S A   pr oce ss  is    execu te d  [15].  In  S A  process,   the  num ber   of   popula ti ons  use d  is   obta ine d  base d  on  rand om   rate  of  the   best  ind ivi du al s . P s eudoc od e  of  G A - S A 2  ca n be  seen i n  Fi gure  6.       I nit iali za t ion  p ar amete r  GA - SA   GA   (stopping  co ndit ion)   {   // running   GA   proc ess   }   Chrom oso m e = sele c t  (r andom ra t e,   GA   chr om osom e)   SA   (stopping  co ndit ion)   {   // running   SA   proc ess   }     Figure  5 .   GA - SA2  process         Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Hyb ri d Ge netic  Alg or it hms  and Si mu l ated A nn e alin g  fo r   . .. ( Ama li a K ar ti ka  Ariy an i )   4719   4.3.3.  GA - S A3   GA - S A3   proce ss  sta rts  by  runn i ng   S A  al go rithm   first  un ti l  stop pi ng   c onditi on ,  the n  G A  process  is   execu te d  [ 15] .  In   GA   proces s ,  the  num ber   of  popula ti ons  use d  is  obta ine d  based   on  ra nd om   rate  of   the  best  ind ivi du al s . P s eudoc od e  of  G A - S A 3  ca n be  seen i n  Fi gu re  7.       Init iali za t ion  p ar amete r  GA - SA   SA   (stopping  co ndit ion)   {   // running   SA   proc ess   }   Chrom oso m e = sele c t  (r andom ra t e,   GA   chr om osom e)   GA   (stopping  co ndit ion)   {   // running   GA   proc ess   }     Figure  6 .   GA - SA3  process       4.3.4.  GA - S A4   GA - S A2   proce ss  sta rts  by  runn i ng   GA   fi rst  fo r  ge ne rati ons,  then  S A  pro cess  is  execu te d  an d  afte r   SA   pr ocess  is  com plete d  it   w il l  ru n  G A  agai n.   A fter G A  process  on  the  fi r st  it erati on   is  com plete d,   ind i vidual  is  ta ken   as  m uch   as  ra ndom   rate  of   the  best  ind i vi du al   t o  be   processe d  by  SA .  Af te r  S A  process  is  c omplet ed ,   it   will  ta ke  th e  ind ivid ual  as  m uch   as  the  ran dom   rate  of   the  best  in div id ual  from   the  SA   proces s  to  be   processe d  bac k  by  G A  [15].  The  recurre nce   will   stop  after   stoppin g  c ondi ti on   is  f ound.   Pseu doco de  of  G A - SA4 ca n be see n  in  Fig ure  8.       Init iali za t ion  p ar amete r  GA - SA   W hil e  (Stopping   Condit ion )  {   If  (GA   condition )  {   GA ()  {   // running   GA   proc ess   }   }   If  (SA   condition )  {   SA ()  {   // running   SA   proc ess   }   }   Chrom oso m e = sele c t  (r andomrat e ,   chr om osom e)   }     Figure  7 .   GA - SA4  process       5.   E X PERI MEN TAL RES UL T AND  DI SCUSSI ON   5.1.   Experim en ta l  Scenari o   The  e xp e rim ental   scenario   wi ll   be  done  by  c om par ing   fitne ss  res ults  ge ne rated  f r om   eac h  al gorith m   ie   GA ,  S A,   G A - S A 1,   GA - S A2,  G A - SA3,  and   GA - S A 4.   In   the  GA - S A 2,   G A - S A3,  an d  G A - SA4  al gorithm s,   a  ran dom   par am et er  of   0.1 - 1  is  us ed  to  sel ect   the  nu m ber   of   ind i viduals  ra ndom ly  to  be  pr oces sed  f ur t he r.   I n  GA - S A2,  if  th e  rando m   rate  us e d  is  0. 1  t he n  only   10 %  of   the  ov e rall   GA  popu la ti on  wil l  be  re - op ti m ized   by  SA   [ 15] .  To  know   t he  m os t  op tim al   ran dom   rate,  it   will   be  te ste d  ra ndom   rate  par am et ers  in  ad van ce  s o  i t  can  be  known  ra ndom   rate  valu e  that  can  pro du ce   the  m os t  optim al   fitness  value .  T he  pa ram et ers  us ed   in  this   exp e rim ent can  be se en  in  Ta bl e 2 .       Tab le   2 .   E cpe rim ent Par am et e rs   Para m eters   Valu e   GA   Po p u latio n  Size   400   Maxi m u m  Gene rat io n   800   cros so v er  rate   0 .3   m u t atio n  r ate     0 .1   Evaluation Warning : The document was created with Spire.PDF for Python.
                         IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  8 , N o.   6 ,  Dece m ber  2 01 8   :    4713   -   4723   4720   Tab le   2 .   E cpe rim ent Par am et e rs   Para m eters   Valu e   SA   in itial te m p e rature   0 .9   co o lin g  r ate   0 .9   n ew so lu tio n  acc ep tan ce  p rob ab ility  co ef f ic ien t   200       The  ex per im ents  will   be  carried  out  with  th e  sa m e  env iro nm ent  us ing   J ava  pro gr am m ing   la ngua ge   and   c om pu ta tio n   ti m e   fo r  ea ch  al gorithm   f or   60  seco nds   and   will   be  r epeate d  10  ti m es   to  pr oduc e  a  fair  com par ison.     5.2.   Result  and  Di scussion   The  first  e xp e r i m ent  is  con du ct ed  to  determ ine  the  optim a l  ran dom   rate.  The  res ult  of   r andom   rate   par am et er  te st  can  be   seen  i n  Table  3 - 5.   Ta bl e  3  sho ws  that   rand om   rate  0. 8  yi el ds   the  hig he st  avera ge  f it ness   value   of  1.0 323.  I n  Ta ble  4,  the  highest  fi tness  a v era ge   is  obta ined   w hen  the   ra ndom   rate  is  1  w hich   is  1.087 2.   I n  Ta bl e 5 , t he hig hes t avera ge fit nes s v al ue  is  ob ta i ned whe n  the  ra ndom  r at e is 0 .5   w hich  is  1.0886.       Table   3 .   GA - S A2’s  Ra ndom  Rat e Result   ra n d o m  ra te   Fitn ess  Value   Fitn ess   Av erage   Iter atio n   1   2   3   4   5   6   7   8   9   10   0 .1   1 .08 9 4   1 .00 6 7   1 .00 8 5   1 .00 6 4   1 .00 8 5   1 .00 9 3   1 .00 6 4   1 .01 0 1   1 .00 4 9   1 .00 8 5   1 .01 5 9   0 .2   1 .00 9 4   1 .00 9 4   0 .99 8 5   1 .00 5 9   1 .08 1 2   0 .99 8 8   1 .00 9 3   0 .99 8 8   1 .00 9 3   1 .08 9 1   1 .02 1 0   0 .3   1 .00 8 5   1 .08 9 1   1 .00 6 4   1 .00 7 4   1 .00 5 0   1 .00 9 3   1 .00 9 6   1 .00 9 3   1 .08 1 2   1 .00 8 5   1 .02 3 4   0 .4   1 .00 9 3   1 .00 5 9   1 .00 9 6   1 .00 9 3   0 .99 5 6   1 .00 6 0   1 .00 9 6   1 .08 9 7   1 .08 9 7   1 .00 9 3   1 .02 3 4   0 .5   1 .00 9 3   1 .00 9 4   1 .00 5 3   1 .00 4 9   1 .00 9 3   1 .00 5 2   1 .01 0 1   1 .01 0 1   1 .00 6 4   1 .01 0 1   1 .00 8 0   0 .6   1 .00 9 6   1 .00 6 0   1 .00 5 3   1 .00 9 3   1 .00 8 0   1 .01 0 1   1 .00 9 3   1 .01 0 1   0 .99 8 2   1 .00 5 9   1 .00 7 2   0 .7   1 .01 0 1   1 .01 0 1   1 .00 5 4   1 .00 8 5   1 .00 9 4   1 .00 9 4   1 .00 5 4   1 .00 7 4   1 .00 9 6   1 .00 8 0   1 .00 8 3   0 .8   1 .00 9 4   1 .00 7 4   1 .00 6 4   1 .08 6 8   1 .00 9 6   1 .08 9 1   1 .00 9 6   1 .00 6 7   1 .08 8 3   1 .00 9 4   1 .03 2 3   0 .9   1 .00 7 4   1 .00 8 5   1 .09 0 0   1 .01 0 1   1 .00 9 3   1 .01 0 1   1 .00 9 4   1 .00 5 2   1 .01 0 1   1 .00 6 4   1 .01 6 7   1   0 .99 8 5   1 .00 9 4   1 .00 9 4   1 .00 5 3   1 .00 5 2   1 .00 5 0   1 .00 5 4   1 .01 0 1   1 .08 8 0   1 .00 8 5   1 .01 4 5       Table  4 .   GA - S A3’s  Ra ndom  Rat e Result   ra n d o m  ra te   Fitn ess  Value   Fitn ess   Av erage   Iter atio n   1   2   3   4   5   6   7   8   9   10   0 .1   0 .99 9 1   0 .99 5 9   0 .99 8 6   1 .00 4 7   0 .98 8 5   0 .76 6 2   1 .00 9 4   0 .99 7 3   1 .00 5 7   0 .99 8 4   0 .97 6 4   0 .2   0 .88 1 6   1 .00 9 3   0 .99 7 8   0 .99 8 3   1 .00 8 5   1 .08 2 7   0 .76 1 5   0 .85 5 1   0 .85 7 3   1 .08 8 8   0 .95 4 1   0 .3   1 .00 5 3   0 .88 0 3   0 .81 8 2   0 .86 9 6   0 .86 9 4   0 .85 7 1   1 .00 4 5   0 .86 1 3   0 .76 2 3   1 .00 6 2   0 .89 3 4   0 .4   1 .08 9 1   0 .80 0 0   0 .86 4 8   0 .67 0 6   1 .00 6 7   0 .86 0 9   0 .99 6 5   1 .00 6 4   1 .00 9 6   0 .86 1 4   0 .91 6 6   0 .5   0 .78 3 3   0 .77 3 9   1 .00 5 4   0 .86 4 4   1 .00 4 6   0 .86 5 8   0 .86 1 7   1 .00 5 7   1 .00 4 3   0 .85 8 3   0 .90 2 7   0 .6   1 .08 6 4   1 .00 6 7   0 .78 0 0   1 .00 5 3   0 .76 6 2   0 .78 7 6   0 .76 9 4   1 .00 7 6   0 .86 8 8   1 .00 9 3   0 .90 8 7   0 .7   0 .88 9 9   0 .86 6 4   0 .84 0 2   1 .00 8 0   0 .87 9 6   0 .88 1 0   1 .00 6 4   1 .00 5 2   0 .85 5 4   0 .87 0 2   0 .91 0 2   0 .8   1 .00 6 0   0 .86 4 9   1 .00 6 4   0 .91 5 3   0 .86 5 5   0 .87 5 1   1 .00 8 2   0 .85 4 3   0 .86 9 9   0 .86 6 1   0 .91 3 2   0 .9   0 .86 9 4   0 .95 7 0   1 .00 4 9   0 .96 5 4   0 .86 1 9   0 .99 9 3   0 .96 0 4   0 .86 6 6   0 .88 1 6   0 .87 0 0   0 .92 3 7   1   1 .08 8 8   1 .08 6 7   1 .09 0 0   1 .08 8 8   1 .08 6 7   1 .08 6 8   1 .08 6 6   1 .08 6 7   1 .08 8 8   1 .08 2 2   1 .08 7 2       Table  5 .   GA - S A3’s  Ra ndom  Rat e Result   ra n d o m  ra te   Fitn ess  Value   Fitn ess   Av erage   Iter atio n   1   2   3   4   5   6   7   8   9   10   0 .1   1 .09   1 .08 1 2   1 .08 1 2   1 .08 6 8   1 .08 8 8   1 .08 8 8   1 .08 6 7   1 .08 8 8   1 .08 8 3   1 .08 8 8   1 .08 6 9   0 .2   1 .08 6 7   1 .08 6 8   1 .08 6 8   1 .08 8 8   1 .09   1 .08 8 3   1 .08 8 8   1 .08 2 6   1 .08 8 8   1 .09   1 .08 7 8   0 .3   1 .08 8 4   1 .09   1 .08 8 8   1 .08 9 7   1 .08 6 7   1 .08 8 4   1 .08 6 7   1 .08 9 1   1 .08 1 2   1 .08 6 7   1 .08 7 6   0 .4   1 .08 6 8   1 .08 6 7   1 .08 9 7   1 .08 6 8   1 .09   1 .08 6 7   1 .08 8 8   1 .08 6 7   1 .08 6 8   1 .08 9 4   1 .08 7 8   0 .5   1 .08 8 4   1 .08 9 7   1 .08 6 8   1 .08 9 7   1 .08 6 7   1 .08 6 8   1 .08 9 7   1 .09   1 .08 9 4   1 .08 9 4   1 .08 8 6   0 .6   1 .08 6 7   1 .08 6 8   1 .08 8 8   1 .08 8 8   1 .08 6 8   1 .08 6 8   1 .08 6 4   1 .08 9 4   1 .08 8 8   1 .08 9 7   1 .08 7 9   0 .7   1 .08 6 8   1 .08 8 4   1 .09   1 .08 6 8   1 .08 6 4   1 .08 9 4   1 .08 8 8   1 .08 9 4   1 .09   1 .08 6 7   1 .08 8 3   0 .8   1 .08 6 8   1 .08 8 8   1 .08 9 4   1 .08 1 2   1 .08 6 8   1 .08 9 4   1 .08 8 8   1 .08 1 2   1 .08 8   1 .08 6 8   1 .08 6 7   0 .9   1 .08 6 8   1 .08 9 4   1 .08 9 7   1 .08 6 8   1 .08 9 7   1 .08 8 8   1 .09   1 .08 8 8   1 .08 6 8   1 .08 9 7   1 .08 8 6   1   1 .08 9 4   1 .09   1 .08 6 7   1 .08 8 4   1 .08 6 8   1 .08 6 7   1 .08 8 8   1 .08 6 7   1 .08 9 4   1 .08 6 7   1 .08 7 9       Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       Hyb ri d Ge netic  Alg or it hms  and Si mu l ated A nn e alin g  fo r   . .. ( Ama li a K ar ti ka  Ariy an i )   4721   The  ne xt  ex pe rim ent  is  to  com par e  the   fitness  res ults  of  eac h  al gorithm   us in g  GA  an d  S A   par am et ers  an d t he  ra ndom  r at e p aram et ers  th at  h ave  b ee n  te ste d  pre viously . Testin g  is  done 10  ti m es o n ea ch   al gorithm . Th e  co m par iso n of t he  al go rithm   can  be  see n  i n Table   6.   T he  first  te st  w as  perform ed  on   a  gen et ic   al gorithm .  Af te r  te sti ng   10  tim es ,  the  aver a ge  fi tness  sco re   of   1.038 4  was   ob ta ine d.   T he   second  ex pe rim ent  was  perf or m ed  on   the  si m ulate d  anneal ing   al gorith m   and  pro du ce d  a n  a ver a ge  fitness   of  1.077 2.  T he  t hird  te st   was  perf or m ed  on  the   G A - SA1  hybri diza ti on   a nd   ge ne rated   an  a ver a ge  fitness  of   1. 0888.   I n  GA - S A2  te st,  the  a ver a ge  fitn ess  gai n  is  1.0 135.  I n  the   G A - S A 4  te st  the  aver a ge   fitness  gain  of   1.0 124  a nd  the  G A - SA4  t est   ob ta ine d  t he   aver a ge  fitne ss  value   of  1.0 86 3.   Fr om  the six t h t est  o f  t he  al gorithm , th e b est   aver a ge fit ness  v al ue  is  gen e r at ed  by t he GA - SA1.   Figure  9  s how s  the  fitness  re su lt s  obta ine d  by  each   al gorit hm   within  1  m inu te .  The   cha r t  sh ows   that  us es  of  the  sim ulate d  a nn eal in g  al gorit hm   ca n  sig nifica n tl y  increase  t he  fit ness  value   bec ause  e  t he  al go rithm   eff ect ively   ex plo it s  local   se arch   a rea,  pro vid in g  a n  op port un it y  to  fin d  the  best  fitness  fa ste r.   F r om   all   al gorithm s  te st ed  in  this  rese arch,  G A - S A 1  and   GA - S A4  al go rithm   can  produce  the  m os t  op tim al  f it ness   a m on g  ot her  a lgorit hm s,  bu t  GA - S A4  ca n  f ind   t he  best  fitness  c hrom os om e  fo r   26   sec ond  faster   tha n  G A - SA1  that  requi res  39  seco nd  to  fin d  the  be st  fitness  ch ro m osom e.  ho we ver,  GA - S A4   is  st il l  of te n  stuck  on   it s  local  searc h w hile G A - SA1 c an fin d  the   opti m u m  p oin t eve n  th ough it  ta ke s a lit tl e lon ge r.       Table  6 .   Re s ult Com par iso n o f  Al gorithm   Iter atio n   Alg o rith m   GA   SA   GA - SA1   GA - SA2   GA - SA3   GA - SA4   1   1 .09 0 0   1 .08 1 6   1 .08 8 4   1 .00 8 5   1 .08 9 1   1 .08 6 7   2   1 .01 0 1   1 .08 7 6   1 .08 6 8   1 .00 9 3   1 .08 6 6   1 .08 6 8   3   1 .08 8 8   1 .08 1 6   1 .09 0 0   1 .00 6 4   1 .08 9 1   1 .08 9 4   4   0 .99 8 2   1 .08 6 7   1 .08 9 4   1 .00 9 4   1 .08 6 7   1 .09 0 0   5   1 .00 6 0   1 .08 6 8   1 .08 6 8   1 .00 6 7   1 .08 6 7   1 .08 9 4   6   1 .00 9 4   1 .08 1 2   1 .08 9 4   1 .00 5 7   1 .08 9 7   1 .08 6 8   7   1 .08 8 3   1 .08 6 8   1 .08 9 4   1 .09 0 0   1 .08 2 2   1 .08 9 7   8   1 .00 5 4   1 .00 6 4   1 .09 0 0   1 .00 5 4   1 .09 0 0   1 .08 8 4   9   1 .08 9 1   1 .08 6 8   1 .08 9 7   1 .00 4 7   1 .08 8 8   1 .08 9 7   10   0 .99 8 4   1 .08 6 7   1 .08 8 4   1 .09 0 0   1 .08 9 1   1 .08 9 7   Fitn ess   Av erage   1 .03 8 4   1 .07 7 2   1 .08 8 8   1 .02 3 6   1 .08 7 8   1 .08 8 7   Fitn ess   Mini m u m   0 .99 8 2   1 .00 6 4   1 .08 6 8   1 .00 4 7   1 .08 2 2   1 .08 6 7   Fitn ess   Maxi m u m   1 .09 0 0   1 .08 7 6   1 .09 0 0   1 .09 0 0   1 .09 0 0   1 .09 0 0           Figure  8 .   Com par is on Result       6.   CONCL U S ION   This  st ud y  c om par es  the  fitness  valu es  ge ner at e d  by  ge netic   al gorith m   and   sim ulated   a nneal ing  al gorithm   and   four   it s  hy br i di zat ion   m od el s.  From   the  sixth  te st  of   the  al gorithm ,  the  best  ave rag e  fitness   value  is  ge ner a te d  by  the   G A - SA1.  Howe ver,  the  rati o  o f  fitness  values  ge ner at e d  by  G A - SA1  a nd  G A - SA4   can  be  sai d  to  be  cl os e  to get her   s o  that  bot h  G A - SA1  an d  G A - SA4  ca n  pro duce  the  m os t  op tim al  aver a ge  Evaluation Warning : The document was created with Spire.PDF for Python.
                         IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  8 , N o.   6 ,  Dece m ber  2 01 8   :    4713   -   4723   4722   fitness  val ues   bu t  GA - S A4   c an  fin d  the  be st  fitness  ch rom os o m e  faster  than  G A - S A1.  Determ inati on   of   popul at ion  nu m ber   of  ge net ic   al gorithm   t o  be  optim iz e d  a gain   by  sim ula te d  an nea li ng   al gorithm   ca n  influ e nce  al go rithm   sp eed  in   find i ng   best  resu lt .  I n  GA - SA1,  popula ti on s  re - optim ized   by  the  sim ulate d  ann eal in g  al go rithm   are  j us t  the  best  a nd   worst  fitness  ch r o m os o m es,  bu t  in  GA - S A 4,   th e  popu la ti on  is   10 %   of   the  popula ti on   with  the  be st  chr om os om es,  the  m or e  chrom os om es  op tim iz ed  by  the  si m uated  ann eal ing  al gorithm ,  the  faster  the  c ha nc e  of   t he  al gori thm   to  fin d  the   m os t  op ti m al   f it ness.   F uth e r  r esearch ,  to n ee d s  K - Me ans for clu s te ring no des  th at  can  im pr ove  co m pu ta ti on ti m e [30].       REFERE NCE S    [1]   Y.  P.  Anggodo,  et   al.,  "O pti m a ti on  of  Multi - T r ip  Vehic l e  Rout ing  Problem  with  Ti m e  W indows  using  Gene ti c  Algorit hm , "  Jou rnal  of  En vi ron mental   En gineering  and  Sustain able   Te chnol ogy ,   vol .   3 ,   no.   2,   pp.   92 - 97,   Nov   2016.   [2]   X,  Ji  and  K.  Yao,   “ Unce rt ai n  Projec t  Sch edul i ng  Problem  with  Resourc e  Co nstrai nts, ”  Jour nal  of  Intelli g e nt  Manufac turing ,   vol.   28 ,   issue  3,   pp.   575 - 580 ,   Oc t   2014.   [3]   C.   Verbe ec k ,   e t  al. ,   “ A  Meta heu risti c  Solu ti o n  A pproa ch  for   The  Ti m e - Constrai n ed  Proje ct   Sch e duli ng  Problem, ”   OR  Spectrum ,   v ol  39,   issue  2 ,   pp .   353 - 371 ,   Mar   2 016.   [4]   S.  Sundar,   e t  al . ,   “ A  Hy brid   Artif ic i al   Be e  Colon y  Algorit hm   for  T he  Job - Shop  Schedul ing  Probl em  with  No - W ai t   Constrai nt , ”  So ft Computing ,   vol .   12,   issue  5 ,   pp .   1193 - 1202,   Mar   2017.   [5]   K.  Ghos ei ri  and  S.  F.  Ghanna dp our. ,   “ Multi - Obj ec t ive   Vehi cle  R outi ng  Problem  with  Ti m e  W ind ows   Us ing  Goal   Program m ing  and  Gene t ic Algori thm,”   App lied  S oft   Computing ,   v ol.   10 ,   issue  4,   Sep  2010.   [6]   Y.  Bai,  et   al . ,   “ S tudy   of   Multi - V e hic l e  Rou ti ng  Proble m  wit h   Time   Window, ”  tw el f th  Inte rnat ional   S y m posium   on  Opera ti ons R ese arc h  and it s App li c at ions  in engi nee ring ,   te chno l og y   and  m an agem ent   (ISO RA), 2015.   [7]   K.  Heng,  et  al.,   “Appli cation  of   Rout e   Flex ib il i ty  in  Data - Star ve d   Ve h ic l e  Rou ti ng   Proble m  wi th  T ime  Windows,”.   IEE E   Congress  on  Evol u ti onar y   Com puta ti on  (C EC),   2016 .   [8]   R.   Chun y u  and  W .   Xiaobo.,  “R ese arch  on   Multi - Ve h ic l e  and   M ult i - Depot   V ehic le   Rout ing   Prob le m  wi th  Time   Windows  for  El ectronic  Comm ere , ”.   Int ern atio nal   Conf ere n ce  on  Artifi ci a l  Inte lligen ce   and   Com puta ti onal  Inte lligen ce,   201 0.     [9]   Z.   Urs ani ,   et   al . ,   “ Loc al ized  Gene tic  Algorit hm   for  Vehic le   Rout ing  Problem  wit h  Ti m e  W indow s,  “ Appl ie d  Soft  Computing ,   vo l.  11,   issue   8,   pp.   5 375 - 5390,   De c  2 011.   [10]   S.  Kara ka ti c   an d  V.  Podgorel e c. ,   “ A  Surve y   o f  Gene tic  Algor it hm s  for  Solving  Multi   Depo t   Vehic l e  Rout in g  Problem,”   Appl i ed  Sof t  Computi ng ,   vol .   27 ,   pp .   5 19 - 532,   Feb   201 5.   [11]   S.  N.  Kum ar  and  R.   Panneers elvam . ,   “ A  Ti m e - Depe ndent   Veh i cl e  Rou ti ng  Pro ble m   with  Ti m e   W indows  for  E - Com m erc e  Supplie r  Si te   Pi ckups  Us ing  Gene tic  Algorit hm , ”  In telli gen t  Informati on  Manage ment ,   vol.   7 ,   no .   4,   pp .   181 - 194,   Jul   201 5.   [12]   Y.  W ang,   et   al . ,   “ Two - Ec he lo n  Logi stic s  Distribut ion  Regi on   Parti ti oning  Pr oble m   Based  on  Hy br id  Sw arm  Optimiza ti o n - Ge net i c  Algor i thm, ”  E xpe rt   Syste ms   wit h   Applicatio ns ,   vol  42 ,   issue  12,   Jul 20 15 .   [13]   D.  M.  Pierre   an d  N.  Za kar i a.,  “ Stocha stic   Par ti a lly   Op ti m iz ed  C y c lic  Shift  Cross over   for  Multi - Objec t ive   Gene t ic  Algorit hm s  for  The   Vehi cl e  Ro uti ng  Problem  with  Ti m e - W indo ws , ”  Appl i ed  Sof t  Computing ,   vol .   52,   pp.   863 - 87 6,   Mar  2017.   [14]   W .   F.  Mahm udy . ,   “ Im prove d  Sim ula te d  Anne al ing  for  Opt imization  of  Vehi cl e  Rou ti ng  Pro ble m   with  Ti m e  W indows (VRP TW),”   Kurs or ,   v ol.   7 ,   no .   3 ,   pp .   1 09 - 116,   2017 .   [15]   T.   N.  Fat y a nosa,   et   al.,  “ H y brid  Gene tic  Algorit h m   and  Sim ula te d  Annea li ng  for  Functi on  Optimi za t ion, ”  Journa l   of  Information   Technol og y  and   C omputer  Scienc e .   Vol .   1 ,   No.   2,   p p.   82 - 97 . 1   [16]   O.  Bahri . ,   “ Multi - Obje ct iv e  Optimiat ion  of  Vehic l e  Routi ng  Problem  with  unce rtaint y :  An  Approac h  Based  on   Pos sibil ity   Th e o r y , ”  2012 .   <  h tt p :/ /www . la rod ec. com/download/ f il e/ f id/ 543 >  [Ac ce ss   on  Janu ar y   25  2017]   [17]   S.  W .   Li n,   e t  al.   “ Vehic le   Rout in g  Problems   with  Ti m e  W indows  Us ing  Sim ula te d  Annea li ng , ”  Sys te ms ,   Man,   and   Cybe rnet ic s ,   pp.   645 - 650,   Jul   201 7.   [18]   N.  W assan,   et   al .   “ The   Multi ple  Tri p  Vehic le   R outi ng  Problem  with  Bac khaul s:   For m ula ti on  an d  a  Two - Le ve l   Vari able  Ne ighb orhood  Sear ch , ”   Computer  &   Op erati ons R ese arc h ,   vol .   78 ,   pp .   45 4 - 467,   Feb   2017 .   [19]   Y.  Yang  and  L .   Ta ng. ,   “A  Filt er - and - fan  Appr oach  to  th e  Mul ti - Tr ip  Ve hi cl e  Rout ing  Probl e m,”   Inte rna t ional   Confer ence  on   L ogisti cs  S y s te m s a nd  In telli g ent   Mana gement,  vo l.   3 ,   pp .   1713 - 17 17,   Jan   2010.   [20]   Y.  Y.  Zha ng,   e t  al . ,   “ Optimal  Re servoir  Operation  Us ing  a  Hybrid  Simulat ed  Anne ali ng  A lgorit hm - Gene t i c   Al gorithm, ”   Internat ion al   Confer enc e  on  Bio - Inspire d  Com puti n g:  The ori es  and   Applic ations,   p p.   454 - 458,   Nov   2010.   [21]   B.   Minocha ,   e t   al . ,   “Solvi ng  Ve hi cl e  Rou ti ng   and  Sche duli n g  Proble ms   usi ng  Hybrid  Gen et i c  Al gorithm”.  Inte rna ti ona l  Co nfe ren c e  on   E le c troni cs  Com puter T e chnol og y ,   2 011,   pp .   189 - 19 3.   [22]   V.  N.  W ij a y an in grum   and  W .   F.  Mahm udy . ,   “ Op ti m iz ation  of  Shi p’s  Route   Sched uli ng  Us ing  Gene tic  Algorit hm , ”  Indone sian  Journal  of  El ectric a l   Engi nee ring  an d  Computer  Sci enc e   ( IJE ECS) ,  vol .  2,   no.   1,   p p.   180 - 186,   Apr  2016.   [23]   W .   F.  Mah m udy ,   et   al. ,   “ Rea l  Coded  Gene tic  Algorit hm s  for  Solving  Flexi ble   Job - Shop  Schedul ing  Problem  –   Part   I:  Model ing,”,  A dvanc ed   Mat eria ls R ese arch ,   vo l .  701,   pp.   359 - 36 3,   Ma y   2013.   [24]   W .   F.  Mah m udy ,   et   al. ,   “ Rea l  Coded  Gene tic  Algorit hm s  for  Solving  Flexi ble   Job - Shop  Schedu li ng  Problem  –   Part   II:  Optimiz at ion , ”  Ad vanced  Mat erial s R ese arch,   vol .  701 ,   pp .   364 - 369,   Ma y   2013.   Evaluation Warning : The document was created with Spire.PDF for Python.