Jurnal Media Teknik & Sistem Industri Vol. 7 (no. 1) (2023) hal. 27 – 38 http://jurnal.unsur.ac.id/JMTSI e-issn: 2581-0561 p-issn: 2581-0529
DOI 10.35194/jmtsi.v7i1.3039
Copyright  ©  ----  THE  AUTHOR(S).This  article  is  distributed  under  a Creative  Commons  Attribution-Share  Alike  4.0 International  license .  Jurnal  Media  Teknik  dan  Sistem  Industri    is  published  by  Industrial  Engineering  of    Universitas Suryakancana

## Perbandingan Savings Algorithm dengan Nearest

## Neighbour dalam Menyelesaikan Russian TSP Instances
Ekra Sanggala 1* , Muhammad Ardhya Bisma 2
1,2 Universitas Logistik & Bisnis Internasional Jl. Sariasih No.54 Bandung
1* ekrasanggala@mail.ru
2 bisma@ulbi.ac.id

## Comparison Savings Algorithm and Nearest Neighbour on Solving Russian TSP Instances
Dikirimkan: 02, 2023.  Diterima: 03, 2023.  Dipublikasikan: 03, 2023.
Abstract—  Travelling  Salesman  Problem  (TSP)  is  the  problem  for  finding  the  shortest  route  starting  from start node then visiting number of nodes exactly once and finally go back to start node. Several heuristics are popular for solving TSP, for example Savings Algorithm and Nearest Neighbour. Performance heuristics on solving  TSP  are  diverse,  so  there  is  need  of  reference  for  choosing  a  heuristic.  Comparing  heuristics  on solving  instance  can  be  a  reference  for  choosing  a  heuristic.  This  paper  will  discuss  about  comparison Savings Algorithm and Nearest Neighbour on Solving Russian TSP Instances. For generating length of route, Savings  Algorithm is better than  Nearest Neighbour, while for generating CPU time, Nearest Neighbour  is better than Savings Algorithm . Keywords — TSP; Heuristic; Savings Algorithm; Nearest Neighbour; Russian TSP Instances
Abstrak—  Travelling  Salesman  Problem ( TSP )  merupakan  permasalahan  penentuan  rute  terpendek  yang diawali dari titik start untuk mengunjungi sekumpulan titik tepat sekali dan diakhiri dengan kembali ke titik start .  Beberapa Heuristik yang  cukup  populer  untuk  menyelesaikan TSP antara  lain Savings  Algorithm dan Nearest  Neighbour .  Kemampuan Heuristik dalam  menyelesaikan TSP berbeda-beda,  sehingga  diperlukan sebuah  acuan  untuk  menentukan Heuristik yang  akan  digunakan.  Membandingkan Heuristik dalam menyelesaikan instance dapat  menjadi  acuan  untuk  pemilihan Heuristik .  Pada paper ini  akan  dibahas mengenai  perbandingan Savings  Algorithm dan Nearest  Neighbour dalam  menyelesaikan Russian  TSP Instances .  Untuk  panjang  rute  yang  dihasilkan,  maka Savings  Algorithm lebih  baik  dibandingkan Nearest Neighbour , sedangkan untuk CPU Time yang dihasilkan, maka Nearest Neighbour lebih baik dibandingkan Savings Algorithm . Kata kunci — TSP; Heuristik ; Savings Algorithm ; Nearest Neighbour ; Russian TSP Instances

## I. P ENDAHULUAN
Sebuah  perusahaan  agar  dapat  menjadi kompetitif  harus  mendesain,  memproduksi  dan mendistribusikan  produk  dan  jasanya  dengan mempertimbangkan waktu pengiriman dan peningkatan kualitas [1]. Penentuan rute pengiriman  produk  dan  jasa  merupakan  suatu  hal yang  sangat  penting  karena  sangat  membantu dalam  penghematan biaya  pengiriman  dan penghematan  waktu  pengiriman  [2]. Travelling
Salesman  Problem merupakan  salah  satu  masalah penentuan rute yang paling penting dalam  logistik [3]. Travelling Salesman Problem ( TSP ) merupakan permasalahan penentuan rute terpendek yang  diawali  dari  titik start untuk  mengunjungi sekumpulan  titik  tepat  sekali  dan  diakhiri  dengan kembali  ke  titik start . TSP ini  termasuk  ke  dalam Non-Deterministic Polynomial-Time Hard Problems ( NP-Hard  Problems ),  dimana  jika  titik yang  harus  dikunjungi  berjumlah  banyak,  maka
untuk  mendapatkan  rute  terpendeknya  diperlukan waktu  yang  sangat  lama.  Sebagai  contoh  jika terdapat 50 titik yang harus dikunjungi maka akan terdapat  50!  (3,04140932017134  x  10 64 )  alternatif rute,  dengan  alternatif  rute  sebanyak  ini  tentunya akan  memerlukan  waktu  yang  sangat  lama  untuk mendapatkan rute terbaiknya, sekalipun perhitungannya  menggunakan  super  komputer tercanggih [4].
Pada  beberapa  dekade  terakhir  ini,  pada manajemen  pendistribusian  produk,  telah  terjadi peningkatan  penggunaan  metode-metode  optimasi berdasarkan  teknik-teknik Operations  Research dan Mathematical  Programming .  Pada  aplikasi dunia  nyata,  di  Amerika  Utara  dan  Eropa penggunaan  metode-metode  optimasi  ini  telah berhasil  menghemat  biaya  transportasi  sebanyak 5%  sampai  dengan  20%.  Salah  satu  faktor keberhasilan  ini  adalah  karena  ditemukannya algoritma-algoritma  yang  mampu  memberikan solusi  yang  baik  dengan  lama  waktu  perhitungan yang wajar [5].
Algoritma yang perhitungannya cepat walaupun  “hanya”  menghasilkan  solusi  yang mendekati  optimal,  merupakan  opsi  yang  sangat baik untuk menyelesaikan TSP [6]. Algoritma jenis ini  dikenal  dengan  sebutan Heuristik .  “ Heuristik ” merupakan  sebuah  kata  dari  bahasa  Yunani  yang berarti  “menemukan”  atau  “mengeksplorasi”. Heuristik disebut  sebagai approximate techniques . Tujuan  utama  dari Heuristik adalah  untuk membangun  sebuah  model  optimasi  yang  mudah dipahami  dan  mampu  memberikan  solusi  yang baik dalam waktu perhitungan yang wajar [7].
Beberapa Heuristik yang cukup populer untuk menyelesaikan TSP antara lain [8]:
1. Savings Algorithm
2. Nearest Neighbour
3. Nearest Insertion
4. Christofides Heuristics
5. Minimum Spanning Tree Heuristic Dikarenakan prinsip dasar kerja dari Heuristik adalah “mengeksplorasi”, maka kemampuan setiap Heuristik dalam menyelesaikan TSP berbeda-beda, suatu Heuristik mungkin baik dalam menyelesaikan TSP  X tapi  mungkin  kurang  baik dalam  menyelesaikan TSP  Y ,  sedangkan Heuristik lainnya mungkin kurang baik dalam menyelesaikan TSP  X tapi  mungkin  baik  dalam menyelesaikan TSP  Y .  Dengan  demikian  tidak dapat  ditentukan Heuristik mana  yang  merupakan Heuristik yang  terbaik,  yang  dapat  dilakukan adalah  menguji Heuristik pada  beberapa TSP , sehingga hasil pengujiannya dapat dijadikan acuan dalam  memilih Heuristik untuk  menyelesaikan TSP . Savings  Algorithm dan Nearest  Neighbour merupakan Heuristik yang populer untuk menyelesaikan TSP .  Pada paper ini  akan  dibahas
mengenai  perbandingan  kedua Heuristik tersebut dalam menyelesaikan Russian TSP Instances . Dua kriteria  penting  yang  dinilai  adalah  solusi  yang dihasilkan dan waktu perhitungan ( CPU Time ) [9].

## II. M ETODOLOGI P ENELITIAN
Savings Algorithm ditemukan oleh Clarke dan Wright pada tahun 1964, prinsip dasar dari Savings Algorithm adalah  penghematan  ( Savings )  jarak tempuh yang diperoleh berdasarkan penggabungan dua  rute,  gambaran  mengenai  penggabungan tersebut dapat dilihat pada gambar 1, di mana titik 0 merupakan depot [10].

## Gambar 1: Contoh Penggabungan 2 rute [10].
Pada  gambar  1(a)  terlihat  bahwa  titik  i  dan titik j  dilayani  oleh  rute  yang  berbeda.  Pada gambar  1(b)  diperlihatkan  bahwa  titik  i  dan  titik j dilayani  oleh  rute  yang  sama.  Dapat  diketahui jarak  tempuh D a pada gambar 1(a)  adalah sebagai berikut ini [11]:
D a = d 0i + d i0 + d 0j + d j0 (1)
Sedangkan  untuk  jarak  tempuh D b pada gambar  1(b)  dapat  diketahui  sebagai  berikut  ini [11]:
D b = d 0i + d ij + d j0 (2)
Nilai Savings diperoleh dengan mengurangkan jarak tempuh D a dengan jarak tempuh D b , sehingga diperoleh  persamaan  nilai Savings S ij berikut  ini [11]:
S ij = D a – D b = d i0 + d 0j - d ij (3)
Pada Savings  Algorithm ,  langkah  pertama yang  harus  dilakukan  adalah  menghitung Savings untuk  setiap  pasangan  titik.  Kemudian  nilai-nilai Savings yang telah diperoleh, diurutkan mulai dari Savings terbesar  sampai  ke Savings terkecil. Pembentukan  rute  dilakukan  dengan  memasukkan ke  dalam  rute  terlebih  dahulu  pasangan-pasangan titik yang memiliki nilai Savings lebih tinggi [11]. Nearest  Neighbour mungkin  merupakan Heuristik yang  paling  sederhana  dan  paling mudah.  Prinsip  dasar  dari Nearest  Neighbour adalah  mengunjungi  titik  terdekat  yang  belum dikunjungi.  Langkah-langkah  dalam Nearest Neighbour kurang lebih seperti berikut ini [6]:
1. Tentukan titik Start .
2. Kunjungi  titik  terdekat  yang  belum dikunjungi.
3. Apa  masih  ada  titik  yang  belum terkunjungi?  Jika  masih  ada,  ulangi  ke langkah kedua.
4. Kembali ke titik Start . Russian  TSP  Instances merupakan  sepuluh TSP yang  dibuat  oleh  penulis  berdasarkan  sejarah Russia dan  tempat-tempat  di Russia . Diharapkan TSP  Instances ini  dapat  menjadi  “tempat”  para peneliti  untuk  menjalankan  algoritma  yang digunakannya.  Sepuluh TSP yang  terdapat  di Russian TSP Instances adalah sebagai berikut ini:
1. AK-47-TSP
Memperingati senjata AK-47 yang ditemukan oleh Mikhail Kalashnikov .
2. Gagarin-108-TSP Memperingati Yuri  Gagarin sebagai manusia pertama yang melakukan perjalanan ke luar angkasa dan mengorbit selamat 108 menit.
3. Mendeleev-101-TSP Memperingati Dmitri  Mendeleev sebagai
penemu  sistem  periodik.  Unsur  dengan nomor atom 101 diberi nama Mendelevium untuk
mengenang
Mendeleev . 4. Petersburg-182-TSP Terdiri  dari  182  area  berpenduduk  di wilayah Saint Petersburg . 5. Popov-250-TSP
Memperingati Alexander  Popov sebagai penemu  radio.  Pada  tanggal  24  Maret 1896, dia berhasil mentransmisikan sinyal radio sejauh 250 meter.
6. Russia-10-Nodes-TSP
Terdiri dari 10 kota berpenduduk terbanyak di Russia . 7. Russia-20-Nodes-TSP Terdiri dari 20 kota berpenduduk terbanyak di Russia . 8. Siege-of-Leningrad-872-TSP Memperingati
872
hari blokade
Leningrad saat perang dunia kedua. 9. World-Cup-Stadium-12-TSP
Memperingati World Cup 2018 di Russia . Sebanyak  12  stadion  digunakan  pada World Cup tersebut.
10. Yashin-270-TSP
Memperingati Lev  Yashin sebagai  kiper terhebat  dalam  sejarah  sepakbola.  Dia berhasil mendapatkan lebih dari 270 clean sheets dalam karirnya.
Data  koordinat  dan  jumlah  penduduk  untuk membuat Russian  TSP  Instances bersumber  dari https://www.geonames.org [12]. Pada Russian TSP Instances ,  untuk  menghitung  jarak  antar  titik
digunakan Haversine  Formula ,  yang  hasilnya dibulatkan  keatas  sampai  nilai  satuan  terdekat. Bagi  para  pembaca  yang  membutuhkan file dari
Russian TSP Instances dapat langsung menghubungi penulis melalui e-mail . Haversine  Formula merupakan  persamaan yang digunakan untuk menghitung jarak antara dua titik di Bumi, bentuk persamaannya adalah seperti berikut ini [13]:
𝑎 = 𝑠𝑖𝑛 2 ( 𝛥𝜙 2 ) + cos 𝜙 1 . cos 𝜙 2 . 𝑠𝑖𝑛 2 ( 𝛥𝜆 2 ) (4) 𝑐 = 2 . 𝑎𝑡𝑎𝑛2 [√𝑎, √(1 − 𝑎) ] (5) 𝑑 = 𝑅 . 𝑐 (6)
ϕ1  : Latitude titik pertama.
ϕ2  : Latitude titik kedua.
λ1  : Longitude titik pertama.
λ2  : Longitude titik kedua. Δϕ  : ϕ1 – ϕ2 Δλ  : λ1 – λ2
R : Radius Bumi (6371 Km).
Langkah-langkah  pada  penelitian  ini  dapat digambarkan  dengan  menggunakan flowchart seperti berikut ini:
Gambar 2: Flowchart langkah-langkah penelitian
Untuk  membantu  menyelesaikan  seluruh perhitungan  digunakan  perangkat  lunak GNU Octave . GNU  Octave merupakan  alat  multifungsi untuk  melakukan  analisis  numerik.  Berbagai  alat bantu  yang  tersedia  di  dalam GNU  Octave adalah sebagai berikut ini [14]:
1. Sekumpulan function untuk  menyelesaikan berbagai masalah.
2. Bahasa pemrograman yang dapat digunakan untuk mengembangkan kemampuan GNU Octave . 3. Berbagai fasilitas untuk melakukan
plotting . Nama GNU  Octave diambil  dari  seorang  ahli kimia  yang  bernama  Octave  Levenspiel. GNU Octave ini merupakan proyek resmi dari GNU dan lisensi source code berada di bawah GNU General Public  License ( GPL ),  sehingga  siapa  pun  boleh menggunakannya untuk berbagai tujuan [15].

## III. H ASIL P ENELITIAN
Agar Russian  TSP  Instances dapat  digunakan maka disimpan dalam file bertipe text yang disusun secara  terstruktur  sehingga  dapat  dibaca  dengan baik oleh GNU Octave .
Instance
Russia-10-Nodes_TSP akan digunakan  sebagai  contoh  pengerjaan.  Berikut  ini merupakan contoh penggunaan Haversine Formula dalam  menghitung  jarak  antara  dua  titik di Bumi:
Moscow (Lat: 55,75222; Long: 37,61556) St.Petersburg (Lat:59,93863; Long: 30,31413)
𝑎 = 𝑠𝑖𝑛 2 ( 𝛥𝜙 2 ) + cos 𝜙 1 .  cos 𝜙 2 .  𝑠𝑖𝑛 2 ( 𝛥𝜆 2 )
𝑎 = 0,002477
𝑐 = 2 . 𝑎𝑡𝑎𝑛2 [√0,002477, √0,998761 ] 𝑐 = 0,099581
𝑑 = 6371 . 0,099581 𝑑 = 634,4309  ≈ 635 𝑘𝑚
Pada  Tabel  I  dapat  dilihat  jarak  antar  titik berdasarkan hasil perhitungan Haversine Formula .
T ABEL I J ARAK A NTAR T ITIK (K M )
Berikut  ini  merupakan  contoh  perhitungan nilai Savings :
S ij = d i0 + d 0j - d ij S 23 = d 21 + d 13 – d 23 S 23 = 635 + 2812 –3105 S 23 = 342 Km
Pada  tabel  II  dapat  dilihat  nilai Savings antar titik.  Dapat  diketahui  bahwa  nilai Savings antara titik 3 dan 7 merupakan  yang tertinggi  yaitu 4438 Km, maka titik 3 dan 7 dimasukkan ke dalam rute dan  dikunjungi  secara  berurutan.  Nilai Savings tertinggi  kedua  adalah  antara  titik  7  dan  10  yaitu 2972 Km, maka titik 10 dimasukkan ke dalam rute dan  dikunjungi  setelah  titik  7.  Cara  ini  terus diulang hingga seluruh titik masuk ke dalam rute.
T ABEL II N ILAI S AVINGS A NTAR T ITIK (K M )
Pada  Tabel  III  dapat  dilihat  panjang  rute  dan CPU Time yang dihasilkan dari Savings Algorithm untuk  setiap instance .  Untuk  rute  yang  dihasilkan dari Savings  Algorithm dapat  dilihat  pada lampiran.
T ABEL III P ANJANG R UTE D AN C PU T IME Y ANG D IHASILKAN DARI S AVINGS A LGORITHM
Nearest  Neighbour menentukan  titik  yang dikunjungi  berdasarkan  titik  terdekat  yang  belum dikunjungi.  Dimulai  dari  depot  yaitu  titik  1, diketahui  titik  terdekat  yang  belum  dikunjungi adalah titik 5, kemudian dari titik 5 diketahui titik terdekat yang belum dikunjungi adalah titik 8, cara ini terus diulang hingga seluruh titik dikunjungi.
Pada  Tabel  IV  dapat  dilihat  panjang  rute  dan CPU Time yang dihasilkan dari Nearest Neighbour untuk  setiap instance .  Untuk  rute  yang  dihasilkan dari Nearest  Neighbour dapat  dilihat  pada lampiran.
T ABEL I V P ANJANG R UTE D AN C PU T IME Y ANG D IHASILKAN DARI N EAREST N EIGHBOUR IV. P EMBAHASAN
Untuk menghitung nilai perbandingan panjang rute digunakan persamaan berikut ini:
𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 = 𝑅𝑢𝑡𝑒 𝑆𝐴−𝑅𝑢𝑡𝑒 𝑁𝑁 𝑅𝑢𝑡𝑒 𝑆𝐴 (7)
Rute SA : Panjang Rute dari Savings Algorithm . Rute NN : Panjang Rute dari Nearest Neighbour .
Untuk contoh perhitungan, digunakan instance AK-47-TSP ,  maka  perhitungannya  seperti  berikut ini:
𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 = 23861 − 27803 23861

## 𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 =   −16,5207%
Nilai Perbandingan -16,5207% berarti panjang rute yang dihasilkan dari Nearest Neighbour lebih panjang  16,5207%  dibandingkan  panjang  rute yang dihasilkan dari Savings Algorithm . Untuk  menghitung  nilai  perbandingan CPU Time digunakan persamaan berikut ini:
𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 = 𝐶𝑃𝑈 𝑆𝐴−𝐶𝑃𝑈 𝑁𝑁 𝐶𝑃𝑈 𝑆𝐴 (8)
CPU SA : CPU Time dari Savings Algorithm . CPU NN : CPU Time dari Nearest Neighbour .
Untuk contoh perhitungan, digunakan instance AK-47-TSP ,  maka  perhitungannya  seperti  berikut ini:
𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 = 0,2652 − 0,078
0,2652
𝑁𝑖𝑙𝑎𝑖 𝑃𝑒𝑟𝑏𝑎𝑛𝑑𝑖𝑛𝑔𝑎𝑛 =  70,5882%
Nilai  Perbandingan  70,5882%  berarti CPU  Time yang  dihasilkan  dari Nearest  Neighbour lebih cepat  70,5882%  dibandingkan CPU  Time yang dihasilkan dari Savings Algorithm .
Pada  Tabel  V  dapat  dilihat  perbandingan panjang  rute  dan CPU  Time yang  dihasilkan  dari Savings  Algorithm dengan  panjang  rute  dan CPU Time yang dihasilkan dari Nearest Neighbour . Panjang  rute  yang  dihasilkan  maka Savings Algorithm lebih  baik  dibandingkan Nearest Neighbour karena  panjang  rute  yang  dihasilkan dari Savings Algorithm lebih pendek dibandingkan panjang  rute  yang  dihasilkan  dari Nearest Neighbour .  Sedangkan  untuk CPU  Time yang dihasilkan,  maka Nearest  Neighbour lebih  baik dibandingkan Savings Algorithm karena CPU Time yang  dihasilkan  dari Nearest  Neighbour lebih cepat  dibandingkan CPU  Time yang  dihasilkan dari Savings Algorithm .
T ABEL V P ERBANDINGAN P ANJANG R UTE DAN C PU T IME YANG D IHASILKAN D ARI S AVINGS A LGORITHM DENGAN N EAREST N EIGHBOUR V. K ESIMPULAN

## V. K ESIMPULAN
Savings  Algorithm dan Nearest  Neighbour mampu  menyelesaikan Russian  TSP  Instances dengan  lama  waktu  perhitungan  yang  wajar.  Jika dalam  penentuan  rute,  yang  diprioritaskan  adalah rute  yang  lebih  pendek  maka  dapat  digunakan Savings  Algorithm ,  tetapi  jika  dalam  penentuan rute,  yang  diprioritaskan  adalah CPU  Time yang lebih  cepat  maka  dapat  digunakan Nearest Neighbour .  Agar  dapat  diketahui  lebih  lanjut mengenai  kehandalan Savings  Algorithm dan Nearest  Neighbour dalam  menyelesaikan TSP , maka  perlu  dilakukan  pengujian  lebih  lanjut  pada instance yang berbeda.

## R EFERENSI
[1] A.  Yalaoui,  H.  Chehade,  F.  Yalaoui  and  L.  Amodeo,
Optimization of Logistics , ISTE, London, 2012.
[2] D.  Waters, Logistics  An  Introduction  to  Supply  Chain
Management , Palgrave Macmillan, New York, 2003.
[3] N. Labadie, C. Prins and C. Prodhon, Metaheuristics for
Vehicle Routing Problems , ISTE, London, 2016.
[4] D.L. Applegate, R.E. Bixby, V. Chvatal and W.J. Cook, The  Traveling  Salesman  Problem  A  Computational
Study , Princeton University Press, New Jersey, 2006.
[5] P.  Toth  and  D.  Vigo, The  Vehicle  Routing  Problem , SIAM, Philadelphia, 2002.
[6] C.  Nilsson, Heuristics  for  The  Traveling  Salesman
Problem , Linkoping University.
[7] K.  Kumar,  D.  Zindani  and  J.  Paulo  Davim, Metaheuristics Optimizing Engineering Problems
Through Heuristic Techniques , CRC Press, USA, 2020.
[8] M.  Chiarandini, Construction  Heuristics  for  Traveling
Salesman  Problem ,  University  of  Southern,  Denmark
2020.
[9] K. Arora, S. Agarwal and R. Tanwar, Solving TSP using
Genetic  Algorithm  and  Nearest  Neighbour  Algorithm and their Comparison , International Journal of Scientific &  Engineering  Research,  Volume  7,  Issue  1,  January 2016.
[10] J.  Lysgaard, Clarke  &  Wright’s  Savings  Algorithm , Department  of  Management  Science  and  Logistics,  The Aarhus School of Business, Sep. 2007.
[11] H.  Paessens, The  Savings  Algorithm  fot  The  Vehicle Routing  Problem ,  European  Journal  of  Operational
Research 34, North-Holland, 1988. [12] https://download.geonames.org/export
[13] B.  Idrizi, Necessity  for  Geometric  Corrections  of
Distances  in  Web  and  Mobile  Maps ,  International
Conference on Cartography and GIS, Bulgaria, 2020.
[14] A.  Quarteroni  and  F.  Saleri, Scientific  Computing  with MATLAB and Octave Second Edition , Springer, 2006.
[15] J.S.  Hansen, GNU  Octave  Beginner’s  Guide ,  PACKT, Birmingham, 2011.
L AMPIRAN 1
Rute yang Dihasilkan dari Savings Algorithm

## L AMPIRAN
2
Rute yang Dihasilkan dari Nearest Neighbour
L AMPIRAN 3
Listing Program Savings Algorithm
clc; clear; cd ("Instances (Original)"); INSTANCES=readdir("."); cd (".."); global DISTANCE; for i=3:size(INSTANCES,1) INSTANCE=char(INSTANCES(i)) INSTANCE=INSTANCE(1,1:length(INSTANCE)-4); START_FINISH_NODE=1; %cd ("Instances (Converted)"); %SAVINGS=load(strcat(INSTANCE,"_Savings.txt")); %cd (".."); cd ("Instances (Converted)"); START_TIME=cputime; DISTANCE=load(strcat(INSTANCE,"_Distance.txt")); cd ("..");
%SAVINGS INDEX_SAVINGS=0; for j=2:size(DISTANCE,1) for k=j+1:size(DISTANCE,1) if j!=k INDEX_SAVINGS=INDEX_SAVINGS+1; SAVINGS(INDEX_SAVINGS,:)=[j k DISTANCE(j,1)+DISTANCE(1,k)-DISTANCE(j,k)]; endif endfor endfor
SORTED_SAVINGS=[(1:size(SAVINGS,1))' sortrows(SAVINGS,-3)]; clear('SAVINGS');
%INDIVIDUAL SAVINGS ALGORITHM %INSERT NODE BASED ON HIGHEST SAVINGS INDIVIDUAL_SAVINGS_ALGORITHM=SORTED_SAVINGS(1,2:3); SORTED_SAVINGS(1,5)=1;
while size(find(SORTED_SAVINGS(:,5)==0),1)>0 %SAVINGS_COMPETITION k=0; if size(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),1)>0 k=k+1; SAVINGS_COMPETITION(k,1:4)=...
[SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,1))(1,1),1:4)]; endif
if size(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,3)==INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),1)>0 k=k+1; SAVINGS_COMPETITION(k,1:4)=...
[SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,3)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,1))(1,1),1:4)]; endif
if size(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVI DUAL_SAVINGS_ALGORITHM,2))),1)>0 k=k+1;
SAVINGS_COMPETITION(k,1:4)=...
[SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2)))(1,1),1:4)]; endif
if size(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,3)==INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVI DUAL_SAVINGS_ALGORITHM,2))),1)>0 k=k+1; SAVINGS_COMPETITION(k,1:4)=...
[SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,3)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2)))(1,1),1:4)]; endif
%CANDIDATE NODE CANDIDATE_NODE=sortrows(SAVINGS_COMPETITION,-4)(1,1:3); clear('SAVINGS_COMPETITION');
%INSERT NODE BASED ON CANDIDATE NODE if INDIVIDUAL_SAVINGS_ALGORITHM(1,1)==CANDIDATE_NODE(1,2) INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY=INDIVIDUAL_SAVINGS_ALGORITHM; clear('INDIVIDUAL_SAVINGS_ALGORITHM'); INDIVIDUAL_SAVINGS_ALGORITHM(1,1)=CANDIDATE_NODE(1,3);
INDIVIDUAL_SAVINGS_ALGORITHM(1,2:size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2)+1)=INDIVIDUAL_SAVI NGS_ALGORITHM_DUMMY; ELIMINATED_NODE=CANDIDATE_NODE(1,2); elseif INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))==CANDIDATE_NODE(1,2) INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY=INDIVIDUAL_SAVINGS_ALGORITHM; clear('INDIVIDUAL_SAVINGS_ALGORITHM');
INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2)+1)=CANDIDATE_NODE(1 ,3);
INDIVIDUAL_SAVINGS_ALGORITHM(1,1:size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2))=INDIVIDUAL_SAVING S_ALGORITHM_DUMMY; ELIMINATED_NODE=CANDIDATE_NODE(1,2); elseif INDIVIDUAL_SAVINGS_ALGORITHM(1,1)==CANDIDATE_NODE(1,3) INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY=INDIVIDUAL_SAVINGS_ALGORITHM; clear('INDIVIDUAL_SAVINGS_ALGORITHM'); INDIVIDUAL_SAVINGS_ALGORITHM(1,1)=CANDIDATE_NODE(1,2);
INDIVIDUAL_SAVINGS_ALGORITHM(1,2:size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2)+1)=INDIVIDUAL_SAVI NGS_ALGORITHM_DUMMY; ELIMINATED_NODE=CANDIDATE_NODE(1,3); elseif INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))==CANDIDATE_NODE(1,3) INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY=INDIVIDUAL_SAVINGS_ALGORITHM; clear('INDIVIDUAL_SAVINGS_ALGORITHM');
INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2)+1)=CANDIDATE_NODE(1 ,2);
INDIVIDUAL_SAVINGS_ALGORITHM(1,1:size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2))=INDIVIDUAL_SAVING S_ALGORITHM_DUMMY; ELIMINATED_NODE=CANDIDATE_NODE(1,3); endif clear('INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY'); SORTED_SAVINGS(CANDIDATE_NODE(1,1),5)=1; clear('CANDIDATE_NODE'); %ELIMINATED NODE
SORTED_SAVINGS(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVING S(:,5)==0),:)(:,2)==ELIMINATED_NODE),1),5)=1;
SORTED_SAVINGS(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVING S(:,5)==0),:)(:,3)==ELIMINATED_NODE),1),5)=1;
clear('ELIMINATED_NODE');
%ELIMINATED SAVINGS BASED ON MOST LEFT NODE AND MOST RIGHT NODE if size(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)= =INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_S AVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),:)(:,3)==INDIVIDUAL_SAVIN GS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))),1),1)>0 INDEX_SORTED_SAVINGS=...
SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,1)),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVI NGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),:)(:,3)==INDIVIDUAL_SAVINGS_ ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))),1); else INDEX_SORTED_SAVINGS=...
SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==IN DIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))),:)(find(SORTED_SAVINGS(find(SORT ED_SAVINGS(:,5)==0),:)(find(SORTED_SAVINGS(find(SORTED_SAVINGS(:,5)==0),:)(:,2)==INDIVIDUAL_SAVINGS_ALGOR ITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2))),:)(:,3)==INDIVIDUAL_SAVINGS_ALGORITHM(1,1)),1); endif
SORTED_SAVINGS(INDEX_SORTED_SAVINGS,5)=1; endwhile
%INSERT START FINISH NODE INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY=INDIVIDUAL_SAVINGS_ALGORITHM; clear('INDIVIDUAL_SAVINGS_ALGORITHM'); INDIVIDUAL_SAVINGS_ALGORITHM(1,1)=START_FINISH_NODE;
INDIVIDUAL_SAVINGS_ALGORITHM(1,2:size(INDIVIDUAL_SAVINGS_ALGORITHM_DUMMY,2)+1)=INDIVIDUAL_SAVI NGS_ALGORITHM_DUMMY; INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2)+1)=START_FINISH_NODE;
%cd ("Instances (Converted)"); %DISTANCE=load(strcat(INSTANCE,"_Distance.txt")); %cd (".."); INDIVIDUAL_SAVINGS_ALGORITHM(1,size(INDIVIDUAL_SAVINGS_ALGORITHM,2)+1)=... FUNCTION_LENGTH(INDIVIDUAL_SAVINGS_ALGORITHM(1,1:size(INDIVIDUAL_SAVINGS_ALGORITHM,2))); clear('DISTANCE'); cd ("Instances (Result)"); dlmwrite(strcat(INSTANCE,"_Savings_Algorithm.txt"),INDIVIDUAL_SAVINGS_ALGORITHM,"delimiter","\t");
FINISH_TIME=cputime;
LENGTH_TIME=FINISH_TIME-START_TIME dlmwrite(strcat(INSTANCE,"_Savings_Algorithm_CPUTIME.txt"),LENGTH_TIME,"delimiter","\t"); cd (".."); clear('SORTED_SAVINGS'); endfor

## L AMPIRAN
4
Listing Program Nearest Neighbour
clc; clear; %INSTANCES DIRECTORY cd ("Instances (Original)"); INSTANCES=readdir("."); cd (".."); global DISTANCE; for i=3:size(INSTANCES,1) INSTANCE=char(INSTANCES(i))(1,1:size(char(INSTANCES(i)),2)-4) %INSTANCES (CONVERTED) DIRECTORY cd ("Instances (Converted)"); START_TIME=cputime; DISTANCE=load(strcat(INSTANCE,"_Distance.txt")); cd ("..");
%INDIVIDUAL NEAREST NEIGHBOUR DISTANCE_DUMMY=DISTANCE; j=1; START_FINISH_PLACE=1; NEXT_PLACE=START_FINISH_PLACE; INDIVIDUAL_NEAREST_NEIGHBOUR(1,j)=NEXT_PLACE; for j=2:size(DISTANCE,2) [DISTANCE_DUMMY_SORT, PLACE_NUMBER_DUMMY_SORT]=sort(DISTANCE_DUMMY(NEXT_PLACE,:)); NEXT_PLACE=PLACE_NUMBER_DUMMY_SORT(1,2); INDIVIDUAL_NEAREST_NEIGHBOUR(1,j)=NEXT_PLACE; DISTANCE_DUMMY(INDIVIDUAL_NEAREST_NEIGHBOUR(1,j-1),:)=999999999; DISTANCE_DUMMY(:,INDIVIDUAL_NEAREST_NEIGHBOUR(1,j-1))=999999999; endfor j=j+1; NEXT_PLACE=START_FINISH_PLACE; INDIVIDUAL_NEAREST_NEIGHBOUR(1,j)=NEXT_PLACE; INDIVIDUAL_NEAREST_NEIGHBOUR(1,size(INDIVIDUAL_NEAREST_NEIGHBOUR,2)+1)=... FUNCTION_LENGTH(INDIVIDUAL_NEAREST_NEIGHBOUR(1,1:size(INDIVIDUAL_NEAREST_NEIGHBOUR,2)));
%SOLUTIONS NEAREST NEIGHBOUR DIRECTORY cd ("Instances (Result)"); dlmwrite(strcat(INSTANCE,"_Nearest_Neighbour.txt"),INDIVIDUAL_NEAREST_NEIGHBOUR,"delimiter","\t");
FINISH_TIME=cputime;
LENGTH_TIME=FINISH_TIME-START_TIME dlmwrite(strcat(INSTANCE,"_Nearest_Neighbour_CPUTIME.txt"),LENGTH_TIME,"delimiter","\t"); cd (".."); clear('DISTANCE'); clear('INDIVIDUAL_NEAREST_NEIGHBOUR'); endfor