laporan akhir penelitian unggulan its dana its 2020 · 2020. 11. 30. · i laporan akhir penelitian...

i

LAPORAN AKHIR

PENELITIAN UNGGULAN ITS

DANA ITS 2020

Pengembangan Model Traveling Salesman Problem & Vehicle Routing

Problem dan Algoritma Generik Berbasis Hyper-heuristics Untuk

Menyelesaikan Permasalahan Optimasi Operasi dan Penjadwalan Public

Transport di Kota Surabaya dalam Kerangka Kerja Intelligent Transport

Systems

Tim Peneliti :

Ahmad Muklason, S.Kom., M.Sc., Ph.D. (Departemen Sistem Informasi/FT-EIC/ITS)

Dra. Nuri Wahyuningsih, M.Kes. (Departemen Sains Aktuaria/FSAD/ITS)

Raras Tyasnurita, S.Kom., M.BA, Ph.D. (Departemen Sistem Informasi/FT-EIC/ITS)

Retno Aulia Vinarti, S.Kom., M.Kom, Ph.D. (Departemen Sistem Informasi/FT-EIC/ITS)

DIREKTORAT RISET DAN PENGABDIAN KEPADA MASYARAKAT

INSTITUT TEKNOLOGI SEPULUH NOPEMBER

SURABAYA

2020

Sesuai Surat Perjanjian Pelaksanaan Penelitian No: 800/PKS/ITS/2020

i

Daftar Isi

Daftar Isi .......................................................................................................................................................... i

Daftar Tabel .................................................................................................................................................... ii

Daftar Gambar ............................................................................................................................................... iv

Daftar Lampiran .............................................................................................................................................. v

BAB I RINGKASAN ..................................................................................................................................... 1

BAB II HASIL PENELITIAN ........................................................................................................................ 2

BAB VI HASIL DAN PEMBAHASAN ........................................................................................................ 2

4.1 Data Uji Coba .................................................................................................................................. 2

4.2 Lingkungan Uji Coba ........................................................................................................................ 2

4.3 Hasil Solusi Awal.............................................................................................................................. 3

4.4 Hasil Uji Coba Algoritma Artificial Bee Colony ...................................................................................... 8

4.4.1. Uji Coba Parameter Limit ............................................................................................................. 8

4.4.2. Uji Coba Parameter FoodSource ................................................................................................. 10

4.4.2. Uji Coba Jumlah Iterasi ............................................................................................................... 11

4.4.3. Uji Coba Low Level Heuristik .................................................................................................... 12

4.4.3. Hasil Solusi Akhir ....................................................................................................................... 14

4.5 Performa Algoritma Artificial Bee Colony ..................................................................................... 19

4.5.1 Perbandingan dengan Solusi Awal ........................................................................................... 19

4.5.2 Perbandingan dengan Algoritma Nearest Neighbour ................................................................... 20

4.5.3 Perbandingan dengan Algoritma Genetik .................................................................................... 20

4.5.4 Perbandingan dengan Algoritma Simulated Annealing ............................................................... 24

BAB III STATUS LUARAN ........................................................................................................................ 28

BAB IV KENDALA PELAKSANAAN PENELITIAN .............................................................................. 30

BAB V RENCANA TINDAK LANJUT PENELITIAN .............................................................................. 31

BAB VI DAFTAR PUSTAKA ..................................................................................................................... 32

BAB VII LAMPIRAN .................................................................................................................................. 33

LAMPIRAN 1 Tabel Daftar Luaran ............................................................................................................. 34

ii

Daftar Tabel

Tabel 4. 1 Spesifikasi Perangkat Keras ............................................................................................................ 2

Tabel 4. 2 Spesifikasi Perangkat Lunak............................................................................................................ 2

Tabel 4. 3 Hasil Solusi Awal ............................................................................................................................. 3

Tabel 4. 4 Hasil Solusi Akhir........................................................................................................................... 14

iii

Tabel 4.1 Spesifikasi Perangkat Keras 2

Tabel 4.2 Spesifikasi Perangkat Lunak ............................................................. Error! Bookmark not defined.

Tabel 3 Status Luaran .................................................................................................................................... 28

iv

Daftar Gambar

Gambar 4. 1 Uji Coba Parameter Limit pada Dataset 6 .................................................................................. 9

Gambar 4. 2 Uji Coba Parameter Limit pada Dataset 11 ................................................................................ 9

Gambar 4. 3 Uji Coba Parameter Limit pada Dataset 14 ................................................................................ 9

Gambar 4. 4 Uji Coba Parameter FoodSource pada Dataset 6 ..................................................................... 10

Gambar 4.5 Gambar 4. 5 Uji Coba Parameter FoodSource pada Dataset 11 ............................................... 10

Gambar 4. 6 Uji Coba Parameter FoodSource pada Dataset 14 ................................................................... 11

Gambar 4. 7 Running Time Parameter FoodSource ..................................................................................... 11

Gambar 4. 8 Uji Coba Jumlah Iterasi pada Dataset 6 .................................................................................... 11

Gambar 4. 9 Uji Coba Jumlah Iterasi pada Dataset 11 .................................................................................. 12

Gambar 4. 10 Uji Coba Jumlah Iterasi pada Dataset 14 ................................................................................ 12

Gambar 4. 11 Uji Coba LLH pada Dataset 6 .................................................................................................. 13

Gambar 4. 12 Uji Coba LLH pada Dataset 11 ................................................................................................ 13

Gambar 4. 13 Uji Coba LLH pada Dataset 14 ................................................................................................ 13

Gambar 4. 14 Perbandingan Solusi Awal dan Solusi Akhir ........................................................................... 19

Gambar 4. 15 ................................................................................................................................................. 20

Gambar 4. 16 Perbandingan Algoritma ABC dan NN .................................................................................... 20

Gambar 4. 17 Perbandingan Algoritma ABC dan GA .................................................................................... 21

Gambar 4. 18 Perbandingan Algoritma ABC dan GA .................................................................................... 21

Gambar 4. 19 Box Plot Dataset 1 dan 2 ........................................................................................................ 22




Gambar 4. 23 Box Plot Dataset 9 dan 10 ...................................................................................................... 23

Gambar 4. 24 Box Plot Dataset 11 dan 12 .................................................................................................... 23


Gambar 4. 26 Perbandingan Algoritma ABC dan SA ..................................................................................... 24

Gambar 4. 27 Perbandingan Algoritma ABC dan SA ..................................................................................... 25




Gambar 4. 31 Box Plot Dataset 9 dan 10 ...................................................................................................... 26



v

Daftar Lampiran

1. Paper Publikasi

1

BAB I RINGKASAN

Kemacetan lalu lintas adalah masalah umum di kota-kota besar di seluruh kota besar. Selain dengan

penyediaan moda transportasi masal yang bagus, untuk mengatasi masalah kemacetan diperlukan

sistem manajemen transportasi yang bagus juga. Penelitian ini bertujuan untuk mengembangkan

model Traveling Salesman Problem (TSP) dan Vehicle Routing Problem (VRP) untuk memodelkan

permasalahan manajemen transportasi di kota Surabaya, khususnya yang berkaitan dengan optimasi

operasional dan penjadwalan moda transportasi umum masal terintegrasi yang direncanakan akan

dibangun di kota Surabaya. Selain pembuatan model, untuk menyelesaiakan model permasalahan,

dalam penelitian ini akan diusulkan algoritma generik dengan menggunakan pendekatan hyper-

heuristics. Dari sisi keilmuwan, kontribusi ilmiah yang diharapkan dari penelitian ini adalah

diperolehnya data set dan pengembangan model baru untuk TSP dan VRP yang telah dibuktikan

sebagai permasalahan yang Non-deterministic Polynomial (NP), i.e. NP-hard, dimana belum

diketahui adanya algoritma esak yang mempu menyelesaikan dalam waktu polynomial. Data set

dan model baru ini diharapkan dapat mendorong penelitian algoritma lebih lanjut oleh peneliti

lainya khususnya di bidang kecerdasan buatan dan riset operasi. Dari sisi manfaat praktis, luaran

dari penelitian ini diharapkan dapat menghasilkan piranti lunak cerdas yang dapat membantu dalam

manajemen transportasi masal terintegrasi dalam kerangka kerja Intelligent Transport System (ITS)

di kota-kota besar di Indonesia, khususnya di kota Surabaya.

Kata Kunci: Traveling Salesman Problem, Vehicle Routing Problem, Intelligent Transport

System, Hyper-heuristics

2

Ringkasan penelitian berisi latar belakang penelitian,tujuan dan tahapan metode

penelitian, luaran yang ditargetkan, kata kunci

BAB II HASIL PENELITIAN

BAB VI

HASIL DAN PEMBAHASAN

Pada bab ini akan menjelaskan mengenai hasil uji coba dan analisis terhadap hasil solusi yang

diperoleh dari implementasi Algoritma ABC dan perbandingannya dengan beberapa algoritma

lain seperti NN, GA dan SA.

4.1 Data Uji Coba

Data yang digunakan sebagai uji coba adalah dataset TSP dari Traveling Salesman Competition

(TSC) 2.0 yang digunakan langsung dalam penelitian tugas ini.

4.2 Lingkungan Uji Coba

Pada subbab Lingkungan Uji Coba ini akan menjelaskan terkait lingkungan pengujian dalam

melakukan implementasi penelitian terkait optimasi rute rencana perjalanan dengan pesawat pada

studi kasus TSC 2.0. Spesifikasi perangkat keras yang digunakan dalam implementasi ditunjukkan

pada Error! Reference source not found..

Tabel 4. 1 Spesifikasi Perangkat Keras

Perangkat Keras Spesifikasi

Jenis Laptop Dell Inspiron 7559

Processor Intel(R) Core(TM) i7-6700HQ 2.6GHz

RAM 16 GB

Hard Disk Drive 1000 GB

Untuk spesifikasi perangkat lunak yang digunakan dalam pengerjaan penelitian ini ditunjukkan

pada Error! Reference source not found..

Tabel 4. 2 Spesifikasi Perangkat Lunak

Perangkat Lunak Fungsi

Windows 10 64 bit Sistem Operasi

Netbeans 8.2 Implementasi Algoritma

Microsoft Excel 2016 Pengolahan Hasil Uji Coba

Microsoft Word 2016 Penulisan Laporan

3

4.3 Hasil Solusi Awal

Pembuatan solusi awal dilakukan dengan cara menentukan secara acak urutan tur kota dari daftar

kota yang telah dilakukan seleksi sebelumnya. Jika ditemukan solusi yang tidak layak maka urutan

kota akan kembali diacak hingga ditemukan solusi yang layak. Tabel 4.3 menunjukan solusi yang

dihasilkan pada solusi awal beserta biaya yang dibutuhkan.

Tabel 4. 3 Hasil Solusi Awal

Dataset Solusi

1 AB0-AB5-AB3-AB6-AB8-AB1-AB4-AB9-AB2-AB7-AB0 (8609)

2 EBJ-NBP-OMG-NCA-NUJ-OHT-GSM-EFZ-QKK-SSC-TKT (1498)

3 GDN-IEG-WE2-ZC1-LB1-KJ1-LD1-DL1-RZE-SZY-SA2-KRK-MZ1-GDN

(17818)

4 GDN-PVK-BTS-VCE-CDG-NYO-SXF-GLA-TSR-KBP-KIV-LUX-TGD-HEL-

MLA-SPU-ERZ-DUB-TRD-ANR-VNO-LIS-AMS-INN-PRG-SKP-BEG-LJU-

TIA-BCN-BUD-GVA-VAR-MHP-SJJ-AKT-TLL-RIX-CPH-VOZ-GDN (52623)

5 RCF-QNY-YMJ-EIF-QNL-MUD-EGM-EQP-GSW-AON-LQP-BPA-JAQ-PSS-

HGY-SQZ-JLM-WYX-SZR-MGY-LDS-SMM-PIG-MWT-IXY-JRJ-CLQ-RZA-

GMM-UUZ-KLW-GMU-FED-FIE-EHO-FNO-LZS-JSF-MLL-FWF-AVC-UCF-

QUZ-BBZ-MWE-LGI-RCF (5157)

6 VHK-RNK-IFS-LGF-DBD-CZA-YMG-IXR-UGD-BML-IKC-UDQ-PYW-JSP-

BCT-YCE-DUK-NKE-RXB-CPQ-TXU-XEH-GCC-UXA-QEZ-UXC-QIU-WJI-

URB-BJW-YQK-BSK-UNM-GYZ-LFE-WYU-IXJ-MXV-WBF-HPO-CJF-CTQ-

UAX-ZML-QLA-ZVF-NOZ-RSE-TPR-EFU-ZZY-PFG-UWL-BYT-EUV-PJI-

AFF-MUF-KIS-LNP-IXQ-IWR-UHR-EXJ-VTQ-DQJ-KKE-ASN-LWM-NTJ-

UYZ-QXW-AJK-BHK-FPD-CCR-SAN-IEI-OTN-CUV-XSR-RLV-AWR-RNS-

FVJ-YHH-UDY-LTN-CWC-WTV-VDG-YUT-ZVP-VKQ-GCX-LDS-VHK

(12625)

7 AHG-FAY-FFF-GWN-FWO-COH-GUT-DVS-FKV-GAR-DAU-DIZ-BBW-HFU-

FDV-EIH-BPW-EFY-BTY-GSL-DNK-EPQ-DDV-HCP-BSP-BZT-ECE-CTU-

BHB-BXV-CWC-DWI-ETU-DKV-HAP-DIB-ERX-FCD-FOS-ARO-AMR-BAQ-

AZS-BKI-FRJ-BNK-GMM-BWF-GRU-FIO-FJO-FRW-DPO-DHV-CRI-HAF-

BUF-BAJ-FJA-DER-BZH-FOE-FXP-FHS-BRF-DSM-FMZ-EZG-ATB-AEN-

AKZ-GWJ-ALX-ALM-DUH-IVN-IDG-NIZ-JGW-KLS-INT-HWB-KXF-KON-

MYY-IBM-JHC-MDX-IRN-HUV-MGM-MQY-JBB-JOQ-JOO-IOM-IRE-HMD-

4

Dataset Solusi

KXI-LHG-KKA-LID-JUZ-JQD-HID-LBK-IIH-LPA-KMH-MCH-LUI-KPR-NFB-

LSE-LYI-ITE-HXU-JWN-MOR-KYK-MRT-LAL-HTJ-LIR-JLI-NCU-MAS-LAA-

HFX-KXN-MIJ-HRV-HVV-JUG-MLJ-KXM-LZD-ICN-HGD-LJA-NFL-HON-

IWU-KLO-MED-JMP-NAD-MAZ-MON-LOU-AHG (89234)

8 AEW-HIX-QZU-WLL-ZZP-VNJ-WFU-ANZ-WKK-MYZ-RUP-RLE-WPH-DSR-

VVA-GSC-VZK-WCD-BIN-YED-AOY-RLT-QHR-INI-IVF-OPC-CUU-VFT-

VXE-JZU-UJW-JRX-RWM-EQV-PAV-TKC-GPI-JSR-AUJ-BZR-PFI-VDU-RYJ-

ETH-DWQ-RHQ-LAZ-JQI-ASF-URK-DDZ-XMD-VDQ-LTI-ULD-XGM-IHK-

ECS-IID-IDB-LRL-JJY-NBR-FWA-CJM-RJM-RRT-JIM-JBJ-JAH-KBN-EHZ-

JCY-TBS-CLA-XRW-NOR-BFZ-ZNG-SED-LNC-GRH-LTF-XSY-PUW-DCY-

XSF-BJG-TQN-JRT-FGF-PRO-IUN-HMM-EBK-XLT-UYS-MVV-EOG-OAE-

CKW-AUO-SXJ-CZJ-BCU-NVV-ROM-IPE-FYA-RAA-WUL-PEU-BYB-MSW-

ZNF-FMC-NZN-PUG-QRL-PJS-LII-ZCX-EGV-WRL-CAA-GKF-BGU-FCP-JBS-

IYZ-OBE-DSN-HIN-ILI-TRJ-AFH-NPF-JHO-BQL-EBY-MYR-DNZ-DCB-EOW-

KIC-BNL-FCJ-PDI-HTD-LRU-QMS-MMN-JFU-AME-OOM-OTQ-NRS-BAB-

ALA-HNP-RWO-JQL-CHK-OVC-JKB-MAE-OLQ-BKB-IHD-PCD-LKE-CGR-

OXH-HPZ-RAR-PNH-GHI-DRO-AKF-FAO-EXV-LTP-KIW-BMD-QBR-PEP-

BLJ-PDY-QXU-MFT-PFU-FKP-NPT-MRE-OVD-EOB-EBC-BPY-DVQ-CSW-

AEW (17434)

9 GVT-PFD-CPU-IQC-NRL-DLZ-AXR-FTC-URP-IUH-PSE-WSO-KKO-DJT-

MRH-JXA-XXF-VMN-VIW-PWO-IMC-RGA-IUU-IRH-WWJ-WSD-QGZ-AWV-

KXR-KLB-SOX-EYQ-DHJ-TQQ-OQL-RUK-XSQ-YRN-JDF-QTU-PYJ-BSZ-

YEK-OBM-LVV-NJX-BBM-BNC-SEW-PSG-BLW-IZD-JNF-UHQ-DPL-MZN-

TKY-FNL-YSI-ODA-SPU-EGT-AEY-FKS-SAW-STR-SAT-GJO-OBN-XSV-

ZJX-VGF-UGR-TWU-JGV-VKO-UFP-XXV-KRI-JQS-WAZ-IML-IAM-FMI-

ZID-MUL-NRE-YDX-GER-YKY-LHE-ZHS-VEH-BQX-OXU-JPK-KUL-WTB-

LMK-SPH-SIY-ZEA-MRO-ZUV-AHR-PSS-SZE-HPH-QJV-LOC-WQP-AHC-

TMZ-UZF-EYO-MVE-XXJ-EUJ-DQF-LDA-XIW-FNQ-NDJ-UCN-CYU-QRP-

TSX-WMZ-NVG-ZWM-HHM-LSE-LSC-ZNU-XPE-ALC-SWH-RDM-LBR-JVS-

NTM-XGD-ZLZ-NMF-VCI-GRI-PCH-TMW-FWU-GPH-HAQ-VWB-UHZ-TXQ-

ZZO-JAK-OXE-UOY-UZH-UCQ-HAC-REH-VIQ-MLK-BXV-TVP-XMH-IJS-

JOF-PZZ-UDV-IFZ-PAM-XIG-AEH-ERN-VVL-RBN-PQM-XEJ-VSK-VAK-

5

Dataset Solusi

JXV-LUA-BYN-QNV-AXO-NGB-HVC-HJJ-CEA-CAB-YQL-VGR-JLO-NUO-

RZK-DHD-XNA-PUN-RGB-MGK-JPI-SGB-ZTN-JAV-JIV-JBA-BUC-MPH-

OKB-QNA-XOS-EJK-GSQ-AOL-UEI-PTC-BCI-OLW-KKQ-STB-NZQ-RZB-

QBQ-HDY-RPW-JJD-FAK-RSX-EAG-JLS-ICU-NJH-TAE-VLS-UCR-QBZ-

BRA-VDX-HVP-HSZ-JSU-VLV-VUC-JUJ-LJS-BRC-UMH-CAK-GVT

(290733)

10 ECB-OGF-FGT-DSH-SVY-JAP-EVX-UZO-IFL-AAB-CUQ-JRK-DRM-NAP-

RQS-QYW-EWE-ZRU-THY-URM-LRY-OQY-SRK-IPX-PWL-STD-LKC-MTV-

EAK-NLU-JTU-ICJ-IYX-DRK-LNF-PGR-XXY-BHJ-IVY-KPX-MHI-OJE-SIV-

XUA-YEO-XGY-SVT-KAM-FSJ-ABP-JGZ-TUJ-ZDE-OEU-APJ-IWD-LRJ-ZEV-

TBG-NMV-AJI-EGP-TPR-DEN-XJE-TRO-RYW-LBS-INX-FCD-FAB-MOM-

THP-CJU-GSW-XWU-ZVN-NVJ-KLG-SHI-YOO-NWT-PZG-TGN-TNQ-URW-

TIP-CSH-BHR-SPH-FCV-BFP-EMG-GCP-CHH-ZZW-VRY-WMZ-CHW-AKB-

SCB-AGL-DSZ-LTS-KNJ-UUG-BKB-YWI-UXZ-KFW-VBB-DLU-ERR-AXT-

QQA-FJQ-QPO-JKP-MFH-VJP-LNS-SNZ-ETP-RAX-IUM-UPC-HMD-YQZ-

ISW-OLW-EVC-VON-URG-TIK-BCB-ZJA-AQG-RFP-XGF-UYA-RXJ-ZAZ-

CQJ-ESC-EXW-GEH-IUK-LFN-RFS-JZK-ZUN-JEH-CNB-KJC-NPL-BSS-JVK-

BOT-LTO-URO-KXM-LXL-CZK-NRS-GER-OQV-HLC-DTO-GFW-YPU-AIN-

VWD-CSW-LMG-EJV-WCD-RVW-GLQ-JQC-TFG-KCX-VKI-BUF-BQK-EBZ-

NPJ-XPD-AYM-ODK-VEE-VJR-HFK-ZCY-EIN-NTI-OTR-PDB-OQC-NPM-

LMY-KWU-EOL-UIA-ASE-JCY-RMN-AHQ-BNO-BTQ-UZM-KWE-IJZ-UJN-

KCM-EDC-RWT-WRM-XCA-GLV-QDZ-ZZZ-SPA-XFD-EPP-SLM-UKX-FZB-

OXB-YEC-IIK-YRB-DDD-JGU-HZM-BOU-YMC-NHG-YJV-CCB-FJI-TKS-

KXQ-BHN-FXQ-EXJ-JDU-KNS-ZIS-WNB-PHT-ACC-OLV-UYZ-QHU-AQO-

HTF-WFD-VUW-UVD-YME-QLI-GFY-YHM-DEU-GFO-XOV-ICO-HDZ-WTU-

QVC-KOR-XRB-YOV-DDL-WGN-ZSZ-LME-ZIU-QNP-YMJ-GJZ-VQC-LOR-

STM-MRZ-ZXF-LEL-QYH-MFM-SZR-ZBE-YMX-HFW-JIE-LQV-GUO-CLG-

NEU-QWG-TNI-ECB (374530)

11

LIJ-FOG-QWO-LVG-NUJ-EHR-ZQV-HLV-UYV-MGY-FKW-NJQ-TSY-NOP-

TNZ-YFT-MYB-QZQ-JWL-KHM-YKW-PNA-HMT-FWB-OIU-UJA-IZX-CPP-

LMS-FIT-AEB-WAC-FKQ-GAB-BEJ-SZD-HIE-THB-NMK-LIR-JTA-XEX-JCP-

OFQ-CJM-IWT-ZHV-QAL-DIW-VRO-JOY-NTW-MBV-YYU-NGN-LTQ-RMH-

6

Dataset Solusi

NRY-LRM-GAM-CUM-OGM-LUF-RYP-MRN-KPI-FTD-JBN-HCI-UHG-YLW-

EOW-DGR-KYX-TXN-ZKG-VYA-CAW-TTY-KRL-JNL-OYX-NQM-HJQ-BXF-

CIB-CHM-PTG-JFR-SRK-TAH-NKW-LRU-JMS-ELA-VYK-AUD-ZTL-QRB-

TBR-BKY-NPJ-QSA-BPL-LGM-FTW-DEE-VXG-IUM-BKR-MBQ-WHV-EKP-

QDL-EGG-IKX-CQT-QEX-KYF-KIB-NTG-NFQ-DJI-RIK-CXO-EDC-DTD-

MFB-IGC-SVT-CLS-LQH-XBL-EIV-LOM-KIP-MWP-PHY-NDU-LSW-PKP-

SXJ-GGK-DPA-BLH-JZN-QDG-SPS-BUC-PND-LIJ (94610)

12 PJE-YMP-ABC-DFY-NIK-SKJ-AVL-OLX-MYC-GPQ-XIA-NCM-KPQ-UMJ-

NUU-LNP-BCC-TZF-ADH-TPT-OYK-GUI-FDO-NXV-TOT-PLU-LRD-MQY-

NPB-XGF-GHP-RRM-XPW-RNM-MKS-ULP-GDP-KWC-KBN-MPH-RFV-

FQA-KGS-CDF-QNT-MTH-YRE-RLV-CNF-RWG-HKN-HZT-JTJ-SUN-JCH-

GRI-ODY-QRB-QIP-OXT-FNT-WVR-HBC-KQX-YBA-BFK-GOF-WMT-WQT-

IHU-OWP-NTP-UBM-FLG-HUU-JOY-ARK-FWL-ZHE-HPQ-SKB-PJV-JTO-

VRQ-TLJ-MYZ-MNJ-OQD-JLG-NZM-FSR-LKD-CZB-OUH-LEX-KYY-TAR-

DKL-QPQ-YRT-FXQ-RHH-ZLQ-VKQ-LVK-NIU-KLC-IWJ-JEQ-OHN-BAP-

AXD-BPA-NSB-SBF-XZK-RDI-OZM-ISX-SFS-WGV-LNJ-KNP-MXX-NFZ-

XPH-JJR-DUF-NXG-VNU-PFI-SWO-MFA-VSR-GYD-AVW-MXC-UHU-KEF-

MCD-BQP-JPR-OAM-QTI-EFD-ILA-HQT-HER-XJI-DMM-SCI-DID-LTM-LZB-

JOK-AWL-MUP-ZNO-NVC-HQK-SXO-AEF-OMN-GJY-GYX-FBT-RAG-TBX-

MIS-BPT-IWP-EDL-CKH-JOX-EZN-SDL-TTB-NHH-DUV-FKK-GQE-PIL-HJC-

FDM-GSF-UTP-EKV-ISQ-RCF-MWL-NSX-ASV-NEJ-KSN-OPN-KIB-DFV-

IGO-KFV-EVS-PJE (147314)

13 GKU-KZA-YWT-GXK-YTF-LQC-BDZ-DCO-YNN-UDG-UHC-THJ-IZY-TGW-

KQA-TLG-RVW-DLH-ITH-ZPU-LLY-EMY-HFS-OEE-UTM-OXW-TVO-SQP-

OCL-SEF-RXQ-BYN-IZA-IUF-IKD-FFA-XMH-LGT-GOH-WPW-AVW-WJL-

NTW-PLE-AMW-YXE-DAH-AOJ-DIY-BEB-ONM-CFT-SAN-MGJ-FIO-ACC-

VMY-AWP-TDN-PLK-DFV-KFW-BYM-UXF-IZT-WPR-OEH-WHN-SAU-SOL-

RZM-ZIB-IQS-SBY-WDX-VMW-VZY-PNF-WBE-QUE-TBP-TPX-XMX-NUY-

VCP-SHN-NOI-EPN-PYX-MOE-RFW-DOO-GRX-UOW-GDN-SRS-RZS-FSI-

EUV-OOK-HIA-GSM-PEF-FFX-IUB-SYL-UKA-CJZ-XME-WOS-INI-CSO-

YWL-HGS-BQF-YGY-MYF-GKJ-PEG-FCA-PUT-UOU-OFL-TAC-REB-AOH-

GWD-TXU-HML-JJB-OIK-OFW-SDY-NIF-ZEZ-AIV-AVI-YPG-DEB-YWH-

7

Dataset Solusi

QRD-CTG-NEO-LXH-PGC-OTS-SXE-JCC-OGV-BSH-UQP-BMD-IVS-SHH-

VKU-EPV-LIS-AON-AHQ-NYB-DUX-BJT-JCJ-GAR-TIP-NLU-SSF-TWD-KSY-

KPN-RYO-WTP-AHE-OUQ-TUU-NYM-NZH-GSI-GCB-NCV-ACA-AEL-NLW-

HTM-CYT-KKI-BZR-LWI-YSL-VEZ-CZD-DLP-GLT-AAM-LCQ-UQD-DSJ-

LZQ-GCK-FPL-JBZ-WZA-RYT-SIQ-TGS-VZT-CKA-VLA-OEG-FMJ-CKZ-

VPY-SQK-RUA-KKY-DYS-DJY-TNL-IHK-OAB-LZZ-VSE-IOA-XRE-EWE-

LZM-MPZ-SWU-DCH-GJX-OIR-AVF-XJS-NSG-GMA-XNA-LEB-AQC-RJJ-

UAW-GQJ-UPM-SNU-FTZ-WOZ-AUF-POB-VOV-UFC-QNF-GKU (184021)

14 IXG-OXF-JFR-VZA-LYR-RDO-EPH-ZLA-RZZ-APY-CFT-QQE-WUC-LKS-

FPG-KQO-HDB-BFF-HOH-PMQ-HHR-KII-IZC-MER-SRE-SOM-FMC-MXN-

IMH-SYY-XGR-JRF-UIE-NXW-RTP-KDT-NHX-ONX-KPC-OEX-CNY-QCY-

IJJ-PGB-OYJ-IES-FGX-GUO-KBC-WEC-GSD-SJO-XIH-CDN-EAJ-HKP-RGA-

SRB-JOK-VRH-QLD-FDC-OXB-QTS-TOG-PNS-ZPD-JPW-ZGD-QQM-NWX-

BAH-HKT-MWZ-SSN-IKW-IFX-NZZ-SZB-ZIT-AZZ-HIM-ZAH-QYJ-ZPQ-

RUR-NNS-MMT-FLC-FIC-ZOS-VMZ-PAB-WCQ-DMI-ZZV-RLF-AGQ-ZTD-

IAV-GZG-NNJ-PPL-ZBA-WCY-OGN-WEN-QVV-CKL-NVF-EKB-IPC-ILP-

DZU-QPR-QNQ-FON-FXG-HYF-MMR-NGK-BRR-VMP-KJN-XDP-DRK-YZU-

WLK-TIL-MXD-DYS-DLU-JTI-FGK-YDC-XDS-EBK-PSK-PMI-WZV-EDF-

UVX-GCZ-QEM-EJY-SJH-QTT-ZYZ-TKN-YAH-YBJ-FSO-ODX-HHA-TNR-

IJS-NAW-DQK-ZHK-OUO-GXR-QSS-KXT-SDF-EXL-LWD-AOB-LMA-WNQ-

JSE-OOW-QSX-MFF-JVE-OXU-XJK-CEA-UFE-PTG-CCK-TPF-EVD-XZU-

BCJ-UPE-JNH-YDZ-HLT-AAL-VQA-EXG-XJQ-JWW-AAJ-THL-IZW-JAK-

EWQ-RUB-MIZ-JSN-END-FQX-USH-QHL-JRO-JEI-SJX-ORA-ZTM-AUQ-

KXF-KUA-DBP-AZP-MYJ-HFT-ITG-MCB-YAF-LXM-CWL-GZZ-IER-BNB-

YLV-LCC-RLV-OST-HVE-UDG-FES-DWY-EVS-IVF-PZF-SIQ-IBE-GIU-KEU-

ZUJ-SGD-DEI-NRF-OON-OYM-FSE-TKP-EWS-DOB-BOW-OQQ-GIT-PQK-

SWR-VRY-JTW-DUB-DAX-FBV-OFE-HXK-QJO-SLF-MCY-FKP-YHQ-HXV-

CEF-JDF-PWL-VTF-QID-XMU-TVT-CFH-JKA-RDM-GTW-WBK-ZAW-MQW-

JQA-SVV-ULV-YFC-AOL-WGF-XTR-AKF-BPO-KEV-PXB-IPU-EKJ-MTA-

GAL-OUL-HMF-GQV-IXG (230839)

8

4.4 Hasil Uji Coba Algoritma Artificial Bee Colony

Algoritma ABC digunakan untuk mengoptimasi solusi dari solusi awal yang telah dihasilkan.

Terdapat tiga parameter yang akan berpengaruh pada solusi akhir yaitu parameter limit, foodSource

dan jumlah iterasi yang akan dilakukan.

Untuk menghasilkan solusi yang lebih baik maka dilakukan pencarian nilai parameter yang optimal

dengan melakukan beberapa uji coba terhadap dataset 1, 6, 11 dan 14. Dataset tersebut dipilih

karena dataset tersebut mewakili karakter dari beberapa dataset lainnya.

Nilai parameter yang akan digunakan berdasarkan pada percobaan yang dilakukan oleh penulis

sebelumnya. Percobaan dilakukan dengan memulai dari nilai parameter terkecil. Setelah itu nilai

parameter akan dikali dua atau tiga kali lipat dan dibandingkan hasilnya. Hal tersebut akan

dilakukan terus menerus sampai ditemukan nilai parameter yang mendekati nilai terbaik.

Hasil dari percobaan tersebut menghasilkan nilai parameter limit 5000, foodSource 8 dan jumlah

iterasi 500.000.000. Angka ini akan menjadi dasar pada uji coba parameter berikutnya. Dari hasil

nilai parameter diatas dataset 1 selalu menghasilkan hasil yang paling optimal, sehingga dataset 1

tidak akan digunakan untuk uji coba berikutnya. Ujicoba akan dilakukan sebelas kali pada setiap

dataset. Hasil akhir akan diambil dari nilai terbaik yang didapatkan dalam pengujian ini.

W

4.4.1. Uji Coba Parameter Limit

Pada uji coba ini dilakukan percobaan dengan menguji parameter limit dengan nilai 10000, 25000,

50000 dan 75000. Nilai limit yang terlalu kecil menyebabkan terlalu seringnya masuk ke tahapan

scout bee yang menyebakan akan menghasilkan solusi yang buruk. Terlalu besar nilai limit akan

menyembakan jarangnya terjadi tahapan scout bee yang menghasilkan kurangnya eksplorasi

terhadap solusi [17].

Pada dataset 6, nilai 10000 menghasilkan solusi yang lebih baik daripada ketiga nilai parameter

lainnya. Selengkapnya dapat dilihat pada gambar 4.1.

9

Gambar 4. 1 Uji Coba Parameter Limit pada Dataset 6

Pada dataset 11, nilai 25000 menghasilkan solusi yang lebih baik daripada ketiga nilai parameter

lainnya. Selengkapnya dapat dilihat pada gambar 4.2.

Pada dataset 14, nilai parameter 50000 menghasilkan solusi yang lebih baik daripada ketiga nilai

parameter lainnya. Selengkapnya dapat dilihat pada gambar 4.3.

Dari ketiga hasil uji coba diatas, nilai parameter 25000 akan digunakan untuk menghasilkan nilai

solusi akhir karena menghasilkan hasil yang lebih baik secara keseluruhan.



10

4.4.2. Uji Coba Parameter FoodSource

Pada uji coba ini dilakukan percobaan dengan menguji parameter foodsource dengan nilai 4, 8 dan

12. Sebenarnya parameter ini tidak terlalu perlu untuk cari nilai terbaiknya, karena algoritma ABC

mampu menjaga kualitas solusinya diberbagai nilai foodSource [17].

Pada dataset 6, nilai parameter 12 menghasilkan hasil yang lebih baik. Selengkapnya dapat dilihat

pada gambar 4.4.

Gambar 4. 4 Uji Coba Parameter FoodSource pada Dataset 6

Pada dataset 11, nilai parameter 8 menghasilkan hasil yang lebih baik dari dua nilai lainnya.

Selengkapnya dapat dilihat pada gambar 4.5.

Gambar 4.5 Gambar 4. 5 Uji Coba Parameter FoodSource pada Dataset 11

Pada dataset 14, nilai parameter 12 menghasilkan solusi yang lebih baik daripada kedua nilai

parameter lainnya. Selengkapnya dapat dilihat pada gambar 4.4.

11

Gambar 4. 6 Uji Coba Parameter FoodSource pada Dataset 14

Dari hasil uji coba ini, nilai 12 menghasilkan nilai yang lebih baik secara keseluruhan. Namun

perbedaan antara nilai 4, 8 dan 12 hanya berkisar 1-2%. Jika dilihat dari running time, nilai

parameter 4 menjadi yang terbaik di ketiga dataset. Selengkapnya dapat dilihat pada gamba 4.7.

Berdasarkan pertimbangan running time dan selisih nilai solusinya, maka nilai foodSource 4 akan

digunakan untuk mencari solusi akhir.

Gambar 4. 7 Running Time Parameter FoodSource

4.4.2. Uji Coba Jumlah Iterasi

Pada uji coba ini akan menggunakan tiga iterasi yang berbeda yaitu 100.000.000, 250.000.000 dan

500.000.000. Pada dataset 6 jumlah iterasi 500.000.000 menghasilkan solusi yang lebih baik

daripada kedua jumlah iterasi lainnya. Selengkapnya dapat dilihat pada gambar 4.8.

Gambar 4. 8 Uji Coba Jumlah Iterasi pada Dataset 6

Pada dataset 11 jumlah iterasi 500.000.000 menghasilkan solusi yang lebih baik daripada kedua

jumlah iterasi parameter lainnya. Selengkapnya dapat dilihat pada gambar 4.9.

12

Pada dataset 14 jumlah iterasi 500.000.000 menghasilkan solusi yang lebih baik daripada kedua

jumlah iterasi lainnya. Selengkapnya dapat dilihat pada gambar 4.10. Dari hasil uji coba diatas,

jumlah iterasi 500.000.000 menghasilkan solusi yang lebih baik dari ketiga dataset yang diuji

coba. Sehingga jumlah iterasi 500.000.000 akan digunakan dalam pencarian solusi akhir.



4.4.3. Uji Coba Low Level Heuristik

Pada uji coba ini akan menggunakan empat jenis low level heuristic (LLH) yang berbeda yaitu

swap 2 kota, swap 3 kota, swap 4 kota dan kombinasi swap 3 dan 4 kota. LLH swap memiliki

peluang yang lebih besar untuk menghasilkan solusi yang lebih baik dibandingkan move, shuffle

dan crossover karena ada perbedaan biaya dari kota a menuju b setiap harinya.

Pada dataset 6, swap 4 kota menghasilkan solusi yang sedikit lebih baik dari swap 3 kota dan

swap 3 & 4 kota. Selengkapnya dapat dilihat pada gambar 4.11.

13

Gambar 4. 11 Uji Coba LLH pada Dataset 6

Pada dataset 11, swap 3 & 4 kota menghasilkan solusi yang sedikit lebih baik dari swap 3 kota

dan swap 4 kota. Selengkapnya dapat dilihat pada gambar 4.12.


Pada dataset 6, swap 3 kota menghasilkan solusi yang sedikit lebih baik dari swap 4 kota dan

swap 3 & 4 kota. Selengkapnya dapat dilihat pada gambar 4.13.


Pada hasil uji coba ini, swap 3, swap 4 dan swap 3 & 4 kota cukup berimbang. Sedangkan pada

swap 2 kota menghasilkan hasil yang lebih buruk dari 3 LLH lainnya. Perbedaan pada nilai solusi

terkecil dan terbesar dapat diakibatkan perbedaan nilai solusi awal dan penggunaan random,

sehingga pemilihan LLH terbaik akan menggunakan nilai rata-ratanya. Berdasarkan nilai rata-rata,

swap 3 & 4 menghasilkan hasil yang lebih baik sehingga swap 3 & 4 akan digunakan dalam

mencari solusi akhir.

14

4.4.3. Hasil Solusi Akhir

Setelah menemukan nilai parameter yang tepat lewat percobaan pada subbab sebelumnya, maka

algoritma ABC dijalankan pada seluruh dataset untuk mendapatkan solusi akhir yang hasilnya

dapat dilihat pada tabel 4.4.

Tabel 4. 4 Hasil Solusi Akhir

Dataset Solusi

1 AB0-AB7-AB4-AB9-AB1-AB6-AB2-AB8-AB3-AB5-AB0 (1396)

2 EBJ-NBP-OMG-NCA-NUJ-OHT-GSM-EFZ-QKK-SSC-TKT (1498)

3 GDN-OSZ-KJ1-WE1-IEG-WRO-KTW-KRK-RZE-LB1-LD3-WMI-SZY-GDN

(8530)

4 GDN-VNO-RIX-TLL-KUO-BLE-OSL-CPH-SXF-LUX-ANR-EIN-GLA-DUB-

OPO-SDR-BOD-GVA-INN-VCE-LJU-ZAG-SJJ-SKP-SOF-IAS-KIV-ODS-ROV-

ADF-AKT-ATH-MLA-TIA-TGD-BEG-BRQ-BUD-KSC-BQT-GDN (16447)

5 RCF-EQP-MGY-BPA-JRJ-RZA-FWF-AON-LDS-UUZ-CLQ-MWT-FIE-WYX-

PSS-JLM-QNL-IXY-BBZ-GMU-KLW-QNY-GMM-GSW-JSF-FNO-HGY-YMJ-

EGM-LGI-MLL-AVC-MUD-SMM-FED-QUZ-SQZ-PIG-SZR-JAQ-EIF-EHO-

UCF-LQP-LZS-MWE-RCF (833)

6 VHK-RNK-BCT-LDS-EFU-ZML-GCC-IXJ-FPD-KIS-CCR-QLA-UWL-URB-

IXR-XEH-FVJ-KKE-PJI-CTQ-QEZ-CUV-WTV-PFG-UXA-RXB-EUV-VKQ-

YHH-AFF-ZZY-DUK-YMG-IFS-ZVP-ZVF-UNM-NOZ-RNS-YCE-WBF-LTN-

LNP-BYT-ASN-IWR-SAN-IEI-UYZ-UXC-CPQ-GYZ-TXU-MXV-WJI-DQJ-

HPO-AWR-VTQ-CWC-BSK-BHK-UDY-IKC-UGD-RSE-LGF-MUF-UHR-NTJ-

TPR-WYU-CJF-QXW-XSR-OTN-CZA-LWM-BML-YUT-QIU-VDG-YQK-

IXQ-AJK-UAX-NKE-DBD-EXJ-BJW-PYW-JSP-LFE-GCX-UDQ-RLV-VHK

(3233)

7 AHG-DHV-DVS-DER-DPO-FKV-BNK-FOE-ETU-BHB-FOS-HFU-FRW-

GWN-BZT-BBW-CWC-AZS-BAJ-ECE-HAP-BWF-ALX-GUT-BSP-BZH-FXP-

GSL-DKV-FWO-DDV-ARO-EPQ-DAU-ATB-GAR-FAY-BRF-FFF-DNK-FDV-

DSM-DIB-CRI-GRU-BUF-FJO-EIH-GMM-FMZ-HCP-BAQ-BPW-HAF-DWI-

ALM-BXV-DUH-FIO-FHS-EFY-FRJ-AMR-FCD-DIZ-FJA-COH-ERX-CTU-

GWJ-EZG-BKI-BTY-AEN-AKZ-HFX-LUI-IVN-IDG-KMH-HXU-HVV-JHC-

ICN-JGW-MIJ-LAA-KLS-MLJ-JWN-LPA-JUG-IRN-HGD-MDX-MAS-ITE-

HRV-NFL-HTJ-KXI-JOQ-NCU-LOU-MGM-LIR-HON-LID-LJA-KON-LZD-

15

Dataset Solusi

NFB-IRE-IOM-JBB-JQD-HUV-MYY-JOO-MON-KXF-KKA-LBK-LYI-MOR-

NIZ-HWB-HMD-JMP-KXM-KLO-MED-IIH-KYK-LAL-IWU-LHG-HID-KPR-

MCH-IBM-MQY-MAZ-KXN-INT-NAD-JUZ-MRT-JLI-LSE-AHG (32854)

8 AEW-IDB-ZMT-FCJ-OAE-FMC-VCO-AOY-CJT-OBE-PDI-DCB-OVD-ZZP-

AZF-OLQ-XGM-IYZ-WCD-BPY-XLY-VDU-YSB-BQL-PEU-JFU-VGV-SVS-

MSW-OIO-EOW-BYB-NFP-NPT-IHD-FWA-NPF-BAB-TZP-HIX-CSW-RVM-

ETH-NRS-DWQ-WUE-BIN-RWB-PDY-BKB-EOB-MFT-KIC-QQS-DNZ-SVZ-

QRL-TKC-JRT-OPC-QCW-LRU-DCY-CGR-PUG-HMM-IVF-IUN-DRO-RAA-

VFT-WFU-MVV-RWZ-AKF-ILI-OTQ-BNL-OOM-JQL-JKB-ULO-CAA-MYZ-

JIM-FAO-QMS-BLJ-PJS-GPI-PEP-RJM-LNC-OXH-NOR-ROM-ASD-JAH-

DSR-YHH-LAZ-EQV-HTD-BMD-CUU-GSC-EHZ-INI-GRH-KBN-IPE-MMN-

AUJ-EXV-RWM-ZNG-JCY-PDX-NZN-NVV-SRY-WJA-TQN-LTP-RAR-LTU-

WPH-FGF-FYA-RZG-KIW-IXO-VNJ-ASF-HPZ-EOG-HGV-QBR-PFI-PUW-

WCS-PNH-TBS-VVA-BFZ-EBC-CKW-JLS-DVQ-CJM-PCD-CHK-ECS-IID-

EBY-VRF-VDQ-ALA-FKP-CZJ-MYR-PRN-DUA-UGL-DSN-MAE-BCU-QUI-

MRE-AFH-QXU-LRL-RYJ-PFU-QZU-AME-JHO-HNP-OCB-LKE-JRX-JZU-

HKD-WKK-USB-GHI-WCU-LII-EBK-JSR-CQP-VXE-RRT-PRO-TNH-VEP-

GCF-OVC-HIN-AUO-AEW (6226)

9 GVT-NUO-PUN-RBN-ZHS-VDX-YSI-QBQ-FTC-UZF-XPE-JAV-TMW-JPK-

TWU-LUA-AXO-NJH-JUJ-JLS-LJS-IJS-PQM-XXV-JNF-KRI-UHQ-OBN-EGT-

SAW-SAT-JPI-CAB-JQS-PSS-TXQ-IUU-DJT-XGD-WMZ-TSX-AWV-YEK-

VLS-BSZ-IAM-RSX-QBZ-TAE-LBR-VIQ-JVS-UCQ-OXE-GJO-NTM-EYO-

UHZ-ZUV-TKY-CEA-MZN-NRE-SIY-ZEA-EJK-DPL-HVC-SOX-EUJ-DQF-

SZE-OBM-JXV-XSV-BYN-SPH-XXJ-VUC-DHJ-IQC-BQX-HPH-NGB-VGF-

BRC-HAC-SWH-VGR-JOF-XEJ-TQQ-XMH-UOY-UZH-RZB-REH-YDX-

AHR-DLZ-RGA-STR-GER-AXR-VVL-ERN-YRN-MVE-NRL-BXV-WWJ-

VKO-IML-CYU-WAZ-UCN-JJD-ZLZ-QTU-NMF-UCR-SPU-PSE-QGZ-KXR-

WSO-QRP-FAK-WSD-IUH-VCI-GSQ-PWO-IRH-FMI-ZZO-NVG-FKS-JDF-

PYJ-GRI-VIW-FNL-KKO-IMC-AEY-JAK-VMN-EAG-IZD-UMH-XXF-SGB-

RDM-RPW-MRO-FNQ-BCI-ZJX-XIW-TVP-VSK-HJJ-UFP-YQL-LDA-ICU-

NDJ-VAK-OQL-PCH-SEW-VWB-HHM-AOL-KKQ-BLW-LSE-GPH-VLV-

QNV-LSC-AEH-UGR-UEI-HSZ-NJX-TMZ-STB-HVP-OLW-BUC-EYQ-PTC-

16

Dataset Solusi

LMK-LVV-JSU-RUK-KLB-XSQ-URP-UDV-LOC-CAK-WTB-QJV-YKY-JGV-

LHE-RZK-XNA-XOS-QNA-PZZ-MPH-KUL-ZID-ZNU-WQP-PAM-AHC-OKB-

ODA-ZWM-BNC-XIG-OXU-HAQ-PSG-FWU-MLK-NZQ-BBM-ZTN-MUL-

ALC-JBA-IFZ-JIV-MGK-VEH-JLO-BRA-HDY-DHD-CPU-PFD-JXA-RGB-

MRH-GVT (82096)

10 ECB-DSH-BNO-VRY-JIE-JQC-FZB-ISW-PDB-ZXF-YHM-GFO-PHT-BHN-

RAX-VBB-CSW-FCD-UYA-EWE-NHG-OEU-LTO-YEC-XWU-XJE-ZIS-DEU-

GEH-IUM-XFD-TNQ-OLW-WMZ-OJE-EIN-IIK-NVJ-AJI-KJC-AIN-QWG-

XUA-CHW-LXL-WCD-ERR-CSH-TRO-YOO-XRB-FJI-LOR-QLI-WNB-ACC-

TKS-YJV-AGL-CUQ-DRK-NPM-UXZ-NWT-RYW-URW-JGZ-AQG-ZEV-

DSZ-NEU-SCB-STD-NAP-HZM-SPH-ZCY-GFW-YOV-VQC-DDL-URO-OQC-

JZK-UIA-BUF-UVD-JTU-TUJ-IWD-ICO-HDZ-KXQ-RVW-ZJA-TPR-JGU-

ESC-NMV-OTR-BHR-KOR-TBG-HLC-MTV-IYX-CQJ-EDC-VKI-VWD-MFM-

AXT-EOL-NLU-BOT-UUG-KCX-JEH-UZM-TIP-EBZ-XXY-FJQ-CLG-XGY-

MOM-SPA-EMG-CJU-NPJ-IVY-SZR-YME-NRS-LKC-URG-BTQ-QQA-KAM-

FCV-EJV-LME-ZZW-RMN-BCB-LBS-SRK-YMX-HFW-GSW-LMY-BSS-

CHH-FAB-YMC-XCA-HFK-MFH-SHI-QYH-RFP-NPL-KFW-PGR-KWU-IPX-

TGN-AHQ-RWT-THP-EPP-TFG-DLU-SLM-KCM-GLV-JCY-YEO-AQO-SVY-

QDZ-RXJ-ZIU-ZBE-QNP-GJZ-QHU-ZVN-MHI-EVC-JVK-ZUN-YQZ-VJR-

IFL-LRJ-STM-JRK-BHJ-UJN-MRZ-YMJ-FXQ-EXJ-ETP-OQV-UZO-OGF-

ASE-DEN-LNS-BQK-SVT-THY-IJZ-VJP-GER-QPO-KWE-YWI-WTU-OLV-

GCP-LMG-APJ-GUO-URM-BFP-HMD-LQV-WFD-KNJ-ICJ-CZK-KXM-JKP-

VEE-QYW-DTO-ZAZ-LFN-TIK-KNS-DDD-OQY-EGP-LTS-LEL-ZSZ-AYM-

ABP-LNF-BKB-NTI-JAP-KLG-XOV-XGF-AAB-ZRU-GLQ-FSJ-TNI-ODK-

HTF-VUW-YPU-RQS-AKB-ZDE-FGT-VON-SIV-WGN-QVC-KPX-OXB-EAK-

BOU-INX-XPD-WRM-PZG-PWL-ZZZ-LRY-UKX-CNB-UPC-IUK-YRB-CCB-

EXW-RFS-EVX-SNZ-DRM-GFY-UYZ-JDU-ECB (57977)

11

LIJ-SLQ-FOG-HIE-DIW-RMH-FKL-HMT-NNZ-CQT-NUJ-HLV-YUT-DGR-

JNL-LTQ-EIV-QAL-LQH-BKR-VRD-LRM-NFQ-JRW-IGC-QWO-TXN-SZD-

GAM-CXO-BEJ-PHY-OFQ-KIP-DEE-PXN-DPA-DJI-ZPF-NRY-JTA-FKW-

GAB-MFB-LSW-TBR-MWP-SXJ-EOW-PNA-BPL-NQM-NPJ-WHV-OYX-

17

Dataset Solusi

KHM-ELA-PRW-IZX-TZY-NTW-UOA-FWB-AEB-QDL-UZS-BUC-QZQ-NJQ-

RIK-MTM-JZN-FKN-TNZ-MYB-CJM-KYF-NGN-CPP-DTD-JFR-KIB-LGM-

UJA-LVG-DZD-TAH-SRK-BLH-IWT-XBL-ZTL-FTW-SVT-UHI-TTY-NOP-

RYP-IKX-OIU-AUD-VAH-FKQ-KPI-IUM-LOM-LIR-CUM-QSA-CAW-ZEX-

PND-XEX-NTG-EGG-MBQ-CIB-OGM-PKP-EDC-CHM-MBV-LRU-JWL-

LSU-CLS-HYM-EKP-MGY-MRN-JCP-NDU-HFR-FIT-BXF-LMS-KRL-HCI-

AOU-HJQ-LUF-GGK-SPS-IWF-QDG-XJU-JBN-PTG-JUT-LSX-LIJ (58642)

12 PJE-GPQ-GJZ-DKL-SDL-SKJ-LEX-MKS-RNM-DMM-FXQ-KLY-ARK-RAG-

OPN-KGS-GRI-YRT-NUU-OBN-BFK-GYX-OHN-NEJ-NXV-UMJ-GOF-KEF-

HBE-QNT-OZM-ADH-BQP-BCC-SBF-DUV-PLU-AEF-NIK-CNZ-HQT-MYZ-

OUH-NVC-CKH-UTG-TPT-OXT-DFV-JTJ-SFS-TAR-MXC-EFD-GDP-WMN-

NXG-MXX-YBA-OQD-ABC-LKD-PIL-PSS-FKK-JJR-HUU-GQE-UDS-PFI-

FBT-FNT-MWL-JGC-GSF-ODY-ONZ-GUI-ZWI-BPA-VSR-CDF-TZF-YHK-

RFV-RLV-QTT-OYK-NHH-VNU-RCF-ISQ-FDO-NIU-SKB-QTI-TTB-OLX-

EKV-XIA-UBM-IHU-ASV-KPQ-XAL-DUF-HKN-HWC-EZN-SXO-LRD-KFV-

KYY-KLC-MPH-CWO-GJY-MFA-JOK-MCD-RWG-EVS-JLG-GYD-JTO-CZB-

OAM-ZNO-QPQ-SAN-RDI-DFY-RRM-KSN-WGV-RHH-JEQ-FDM-LNP-NTP-

HJC-IGO-HBC-JCH-HQK-PJV-YDW-LZB-KWC-HZT-AWL-NPB-MYC-NSB-

KNP-KIB-ISX-OWP-AXD-FLG-MTH-MNJ-QRB-IWJ-XGF-IWP-ILA-TLJ-

NSX-SCI-SDS-JOX-EDL-MIS-EIH-DID-FWL-HER-QIP-NFZ-TBX-TYV-

MQY-LNJ-ZAA-SWO-AVW-FSR-NZM-CNF-OMN-SUN-KBN-BAP-BPT-

HPQ-AVL-JOY-VRQ-MUP-PJE (83560)

13 GKU-NYM-BDZ-CSO-GJX-PLE-ACA-AVW-AHE-PNF-SAU-FIO-FTZ-VKU-

FSI-LZM-LIS-KZA-MPZ-DAH-SQK-EMY-IUF-MOE-UKA-CTG-IUB-GCB-

TDN-UTM-BSH-YWL-TUU-NLU-SEF-NUY-TBP-SOL-DJY-ZUO-MYF-NSG-

TVO-SHN-HTM-SNU-PYX-DYS-PGC-XMX-UDG-LFD-WHN-AWP-WPR-

IZA-IVS-RVW-TIP-GMA-ZTR-BYN-DUX-LZQ-SWU-BEB-YPG-REB-OAB-

JBZ-IZT-VMY-AAM-LWI-DAK-FPL-YTF-JCJ-BQF-KPN-UOW-OIR-GRX-

CZD-GKJ-GAR-TXU-OIK-UQP-VZT-QUE-GCK-GQJ-VMW-OXW-CYT-

XMH-BMD-SLY-AHQ-BJT-CFT-YTJ-IZY-HIA-THJ-GSX-LEB-NLW-AIV-

AOJ-KQA-GOH-ITH-LGT-POB-PLK-EPN-RYO-NOI-FFA-WOZ-XJS-OFL-

YWH-AEL-VZY-SRS-SBY-IOA-XUR-CJZ-PUT-WBE-MGJ-SYL-NIF-GWD-

18

Dataset Solusi

XRE-DLP-OUQ-WPW-VPY-GSI-HFS-RUA-NLM-VCP-TGS-UQD-XME-OCL-

BZR-INI-TLG-OEH-FCA-TGW-DCO-FMJ-HML-ACC-AVF-RFW-KKI-KFW-

VSE-PGF-EUV-IKD-SAN-AQC-BYM-DOO-NTW-KSY-UOU-NZH-NEO-

CKA-SHH-WTP-RZM-UPM-JJC-IHK-JCC-PEF-WDX-GXK-TNL-OTS-LXH-

RJJ-OEE-DCH-UHC-AUF-LQC-SQP-SSF-OGV-LLY-SDY-SOF-QNF-DSJ-

RXQ-GSM-VOV-JJB-ONM-SXE-HGS-XNA-IQS-AVI-AMW-FFX-UFC-AON-

EWE-KKY-GLT-GDN-WJL-ZMS-VLA-OOK-EPV-RYT-DFV-LZZ-DIY-SIQ-

OFW-CKZ-NYB-NCV-TPX-OEG-RZS-TAC-WOS-AOH-VEZ-DLH-UAW-

TWD-DEB-GKU (138227)

14 IXG-AAJ-ZIT-SLF-ZLA-BNB-MMT-TIL-SYY-NVF-XDS-HVE-ZAH-BAH-

DQK-KII-OXB-LXM-ZAW-FKP-QQE-QQM-AKF-DYS-RDM-NHX-FON-

OST-MMR-PGB-YDZ-FGX-HDB-LWD-FDC-CCK-EKJ-WLK-DOB-PMI-

OOW-IES-YFC-NXW-NNJ-HMF-HKT-JEI-ZZV-SVV-TOG-PAB-KDT-EKB-

VMZ-PNS-JSN-EXG-XDP-WGF-XZU-YBJ-QTT-EVD-QCY-JTI-WEN-OFE-

QPR-QYJ-QHL-IZW-GCZ-FXG-DMI-GIU-HXV-KUA-DZU-QSS-VZA-QID-

QVV-RLF-ONX-IPC-EWS-EAJ-OUO-HKP-SDF-CEF-JQA-OEX-HXK-THL-

IVF-KXF-APY-TKP-QEM-BRR-FLC-GSD-ZBA-AUQ-AAL-IAV-ZHK-RTP-

BOW-OGN-MYJ-PXB-HOH-VMP-BFF-PZF-GTW-JVE-GUO-SJX-MWZ-

MQW-GZG-WZV-SJH-JTW-NGK-IZC-JRF-CNY-AOB-RDO-XTR-DAX-RZZ-

PMQ-GXR-DEI-OYM-SRE-ZOS-PPL-AGQ-HYF-JNH-KEU-TPF-IER-DLU-

LCC-FSO-SIQ-ZTD-SZB-PSK-FSE-QNQ-MCB-JKA-SSN-LYR-FGK-MER-

END-EXL-CDN-OXU-DWY-SOM-DBP-QSX-RUR-DUB-NRF-ORA-VQA-

JAK-FMC-MXN-KBC-PQK-IJJ-HLT-ITG-YAH-TKN-JFR-EVS-GQV-RUB-

NNS-IPU-NWX-UFE-KPC-MIZ-EJY-OYJ-MCY-VTF-RLV-BCJ-IMH-GIT-

WCY-CEA-JSE-CWL-GZZ-SRB-IJS-JOK-SGD-ZTM-YLV-NZZ-IBE-PWL-

UDG-EPH-AZZ-JDF-KEV-SWR-HHR-IFX-XGR-IKW-FPG-AOL-TVT-KJN-

MXD-KXT-HHA-VRH-ULV-ZPQ-EWQ-ODX-WEC-LMA-NAW-TNR-CFH-

MTA-JPW-WBK-UIE-EBK-JWW-MFF-ZPD-WCQ-ILP-LKS-WNQ-UVX-BPO-

KQO-PTG-USH-JRO-YDC-YZU-YHQ-OUL-RGA-CKL-HFT-VRY-ZYZ-XMU-

OON-XJQ-OQQ-QLD-QJO-FBV-DRK-HIM-GAL-OXF-WUC-QTS-ZGD-YAF-

EDF-FIC-UPE-FQX-XIH-ZUJ-XJK-CFT-FES-AZP-SJO-IXG (144815)

19

4.5 Performa Algoritma Artificial Bee Colony

Untuk bisa mengetahui apakah hasil solusi akhir dengan menggunakan algoritma ABC bagus atau

tidak, maka perlu dilakukan beberapa perbandingan dari hasil solusi akhir. Perbandingan pertama

akan dilakukan dengan hasil dari solusi awal. Setelah itu akan dilanjutkan dengan

membandingkan dengan algoritma lainnya (GA, NN, SA). Parameter dan jumlah iterasi pada

masing-masing algoritma pembanding telah diatur agar menghasilkan solusi optimal dengan

running time yang mirip dengan running time algoritma ABC.

4.5.1 Perbandingan dengan Solusi Awal

Perbandingan dengan solusi awal dilakukan untuk melihat seberapa besar penghematan yang bisa

dilakukan setelah dilakukan optimasi dengan algoritma ABC. Hasil perbandingan dapat dilihat

pada gambar 4.14.

Berdasarkan perbandingan dengan solusi awal, algoritma ABC dapat menghemat biaya perjalanan

dengan rata-rata 56,1% darihasil yang dihasilkan solusi awal. Algoritma ABC hanya

menghasilkan solusi yang sama pada dataset 2 karena hasil pada solusi awal sudah merupakan

hasil yang teroptimal.

Pada dataset buatan, algoritma ABC mampu menghasilkan hasil yang sangat baik dengan

menghasilkan solusi lebih baik diatas 50%. Terdapat tiga dataset yang mampu menghasilkan

solusi lebih lebih baik diatas 80%. Namun pada dataset berdasarkan data real, peningkatan solusi

hanya berkisar 20 sampai 40%.

Gambar 4. 14 Perbandingan Solusi Awal dan Solusi Akhir

20

4.5.2 Perbandingan dengan Algoritma Nearest Neighbour

Pada dataset 1-5 algoritma ABC menghasilkan hasil yang lebih baik pada 7 dataset. Sedangkan

pada dataset 2 menghasilkan hasil yang sama dengan algoritma NN dikarenakan dataset 2

memang hanya memiliki satu solusi.

Algoritma ABC mampu menghasilkan solusi yang jauh lebih baik dari algoritma NN dengan

penghematan biaya perjalanan sebesar 73% pada dataset 1, 52% pada dataset 3, 72% pada dataset

4 dan 66% pada dataset 5. Selengkapnya dapat dilihat pada gambar 4.15.

Gambar 4. 15

Pada dataset 6-14 algoritma NN hanya dapat menghasilkan solusi yang layak pada dataset 10.

Pada dataset tersebut algoritma ABC menghasilkan solusi yang lebih baik dengan penghematan

biaya perjalanan sebesar 85%. Selengkapnya dapat dilihat pada gambar 4.14.

4.5.3 Perbandingan dengan Algoritma Genetik

Pada dataset 1-8 algoritma ABC menghasilkan hasil yang lebih baik pada 7 dataset. Sedangkan

pada dataset 2 menghasilkan hasil yang sama dengan algoritma GA dikarenakan dataset 2

memang hanya memiliki satu solusi.

Perbedaan cukup besar terlihat pada dataset 4 dan 5. Algoritma ABC mampu menghasilkan solusi

yang lebih baik dari algoritma GA dengan penghematan biaya perjalanan sebesar

Gambar 4. 16 Perbandingan Algoritma ABC dan NN

21

49,5% pada dataset 4 dan 73% pada dataset 5. Selengkapnya dapat dilihat pada gambar 4.17.

Pada dataset 9-14 algoritma ABC menghasilkan hasil yang lebih baik pada 5 dataset tersebut.

Perbedaan cukup besar terlihat pada dataset 9 dan 10 dan 14. Algoritma ABC mampu

menghasilkan solusi yang lebih baik dari algoritma GA dengan penghematan biaya perjalanan

sebesar 34% pada dataset 9, 47% pada dataset 10 dan 29% pada dataset 14. Selengkapnya dapat

dilihat pada gambar 4.18.

Perbandingan dapat dilihat lebih detail pada setiap dataset dengan menggunakan box plot. Pada

dataset 1 baik persebaran data maupun hasil solusi, algoritma GA menghasilkan hasil yang lebih

buruk.

Sementara untuk dataset 2 hasil antara kedua algoritma sama persis diakibatkan dari solusi awal

yang mampu menghasilkan hasil terbaik pada dataset tersebut. Selengkapnya dapat dilihat pada

gambar 4.19

Gambar 4. 17 Perbandingan Algoritma ABC dan GA

Gambar 4. 18 Perbandingan Algoritma ABC dan GA

Selanjutnya pada dataset 3 dan 4, algoritma ABC menghasilkan hasil yang lebih baik dari segi

persebaran data dan juga hasil solusinya. Pada dataset 4 algoritma ABC mampu menghasilkan

solusi baik dengan persentase sebesar 50%. Selengkapnya dapat dilihat pada gambar 4.20.

22

Gambar 4. 19 Box Plot Dataset 1 dan 2


Pada dataset 5 dan 6, algoritma ABC tetap unggul baik dari segi persebaran maupun hasil solusi.

Perbedaan yang cukup besar terdapat pada dataset 5 dimana algoritma ABC mampu menghasilkan

solusi lebih baik dengan persentase sebesar 73%. Selengkapnya dapat dilihat pada gambar 4.21.


Pada dataset 7 dan 8 algoritma ABC tetap menghasilkan hasil yang lebih baik. Selengkapnya

dapat dilihat pada gambar 4.22.

23


Pada dataset 9 dan 10 algoritma ABC masih tetap menghasilkan hasil yang lebih baik dari segi

persebaran data maupun hasil solusi. Selengkapnya dapat dilihat pada gambar 4.23.


Selanjutnya pada dataset 11 dan 12 algoritma ABC tetap menghasilkan hasil ynag lebih baik. Pada

persebaran data algoritma ABC menghasilkan hasil yang lebih baik dengan persebaran data yang

lebih kecil. Sedangkan untuk hasil solusi perbedaan hanya berkisar 10-15%. Selengkapnya dapat

dilihat pada gambar 4.24.


Pada dataset 13 dan 14 persebaran data tidak terlalu berbeda jauh antara kedua algoritma. Namun

pada hasil solusinya algoritma ABC menghasilkan hasil yang lebih baik terutama pada dataset 14.


24


Berdasarkan beberapa penjelasan diatas, dapat disimpulkan algoritma ABC menghasilkan hasil

yang jauh lebih baik daripada algoritma GA.

4.5.4 Perbandingan dengan Algoritma Simulated Annealing

Pada dataset 1-8 algoritma hanya menghasilkan hasil lebih baik pada dataset 4. Pada dataset 2

kedua algoritma menghasilkan hasil yang sama. Pada 6 dataset lainny algoritma SA menghasilkan

hasil yang lebih baik.

Perbedaan cukup besar terlihat pada dataset 8. Algoritma SA mampu menghasilkan solusi yang

lebih baik dari algoritma ABC dengan penghematan biaya perjalanan sebesar 41%. Selengkapnya


Gambar 4. 26 Perbandingan Algoritma ABC dan SA

Pada dataset 9-14 algoritma SA menghasilkan hasil yang lebih baik pada 5 dataset tersebut.


25

Gambar 4. 27 Perbandingan Algoritma ABC dan SA

Untuk lebih detailnya akan dilihat setiap dataset dengan menggunakan box plot. Dataset 1 dan 2

mengasilkan hasil yang sama persis sehingga tidak dibuatkan grafik box plotnya.

Untuk dataset 3 algoritma ABC menghasilkan persebaran solusi yang lebih baik dan untuk nilai

solusi tidak ada perbedaan besar antara kedua algoritma.

Untuk dataset 4 algoritma SA menghasilkan persebaran solusi yang lebih baik. Sedangkan

algoritma ABC unggul pada hasil solusi. Selengkapnya dapat dilihat pada gambar 4.28.


Untuk dataset 5 dan 6 algoritma ABC menghasilkan hasil persebaran data yang lebih baik.

Sedangkan untuk nilai solusi algoritma SA menghasilkan hasil yang lebih baik pada dataset 4.


Untuk dataset 7 dan 8 persebaran nilai solusi cenderung sama dan untuk hasil solusi algoritma SA

menghasilkan hasil yang lebih baik. Selengkapnya dapat dilihat pada gambar 4.30.

Pada dataset 9 algoritma SA menghasilkan hasil yang lebih baik dengan pada persebaran nilai solusi

dan nilai solusi.

26



Sedangkan untuk dataset 10 algoritma SA menghasilkan nilai solusi yang lebih baik tetapi untuk

persebaran nilai solusinya lebih buruk daripada algoritma ABC. Selengkapnya dapat dilihat pada

gambar 4.31.


Pada dataset 11 dan 12 algoritma ABC menghasilkan persebaran nilai solusi yang lebih baik.

Sedangkan untuk nilai solusinya algoritma SA menghasilkan nilai yang lebih baik. Selengkapnya


27


Pada dataset 13 algoritma ABC menghasilkan persebaran nilai solusi yang lebih baik. Namun untuk

nilai solusinya algoritma SA yang menghasilkan hasil lebih baik.

Pada dataset 14 algoritma SA menghasilkan persebaran dan nilai solusi yang sedikit lebih baik dari

algoritma ABC. Selengkapnya dapat dilihat pada gambar 4.33.


Berdasarkan beberapa penjelasan diatas, algoritma SA menghasilkan hasil yang lebih baik daripada

algoritma ABC dengan menghasilkan hasil yang lebih baik pada 11 dataset. Algoritma ABC

menghasilkan hasil yang lebih baik pada persebaran data. Namun hal tersebut tidak dapat membuat

algoritma ABC menghasilkan performa yang lebih baik.

28

BAB III STATUS LUARAN

Tabel 1 Status Luaran

No Nama Luaran Status

1 Seminar Internasional Terindeks Scopus: IEEE

ECTI-Con Thailand

Published

2 Seminar Internasional Terindeks Scopus: IEEE

CENIM, Indonesia

Presented

2 Jurnal Q1 Persiapan

30

BAB IV KENDALA PELAKSANAAN PENELITIAN

Adapun kendala dalam pelaksanaan penelitian ini adalah:

1. Kesulitan mendapatkan data kepadatan lalu lintas yang real time di kota Surabaya.

2. Kondisi pandemic covid19 menjadi kendala untuk melakukan kunjungan ke dinas

perhubungan kota Surabaya.

3. Data transportasi di Kota Surabaya belum ada yang berupa data real time yang diambil

secara otomatis dengan menggunakan perangkat Internet of Thing

4. Public transport di kota Surabaya bisa berhenti dimana saja sepanjang perjalanan

seharusnya hanya bisa berhenti di halte yang ditentukan saja.

31

BAB V RENCANA TINDAK LANJUT PENELITIAN

Rencana selanjutnya dari penelitian ini adalah:

1. Mengembangkan model matematis permasalahan Traveling Thief Problem (TTP ) untuk

menyelesaikan permasalahan pada manajemen pengangkutan sampah berdasarkan data

yang didapatkan sekaligus mengembangkan algoritma hyper-heuristics untuk

menyelesaikan model baru tersebut.

2. Memodelkan permasalahan penjadwalan public transport ke dalam bentuk Urban Transit

Route Problem (UTRP )

3. Mengimpplemtasi algoritma Modified Particle Swarm Optimization (MPSO) ke dalam

kerangka kerja hyper-heuristik

4. Menyelesaiakan permasalahan UTRP dengan pendekatakan hyper-heuristik dan algoritma

MPSO

5. Membandingkan peforma yang dihasilkan pendekatan hyper-heuristik dan algoritma

MPSO dengan metode lainnya dalam menyelesaikan permasalahan penjadwalan public

transport

6. Penulisan Artikel Jurnal

32

BAB VI DAFTAR PUSTAKA

[1] Kruskal, Joseph B. "On the shortest spanning subtree of a graph and the traveling salesman

problem." Proceedings of the American Mathematical society 7.1 (1956): 48-50.

[2] E. K. Burke and Y. Bykov, "The late acceptance Hill-Climbing heuristic," European Journal of

Operational Research, no. 258, pp. 70-78, 2017.

[3] J. M. Sussman, Perspectives on Intelligent Transportation Systems (ITS). New York:

Springer-Verlag, 2005.

[4] D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, "The Problem," in The Traveling

Salesman Problem : A Computational Study, New Jersey, Princeton University Press, 2006,

pp. 1-59.

[5] Edmund Burke, Graham Kendall, Jim Newall, Emma Hart, Peter Ross, and Sonia

Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In

Handbook of metaheuristics, pages 457–474. Springer, 2003.

[6] G. Dantzig and J. Ramser, “The Truck Dispatching Problem,” Management Science, Vol. 6,

No. 1, 1959, pp. 80-91.

[7] Braekers, Kris, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. "The vehicle routing

problem: State of the art classification and review." Computers & Industrial Engineering 99

(2016): 300-313.

[8] Zhang, Junping, et al. "Data-driven intelligent transportation systems: A survey." IEEE

Transactions on Intelligent Transportation Systems 12.4 (2011): 1624-1639.

[9] Laporte, Gilbert. "A concise guide to the traveling salesman problem." Journal of the

Operational Research Society 61.1 (2010): 35-40.

[10] Lust, Thibaut, and Jacques Teghem. "The multiobjective traveling salesman problem: a

survey and a new approach." Advances in Multi-Objective Nature Inspired Computing.

Springer, Berlin, Heidelberg, 2010. 119-141.

[11] Doerner, Karl F., and Verena Schmid. "Survey: matheuristics for rich vehicle routing

problems." International Workshop on Hybrid Metaheuristics. Springer, Berlin, Heidelberg,

2010.

[12] Lin, Canhong, et al. "Survey of green vehicle routing problem: past and future trends."

Expert Systems with Applications 41.4 (2014): 1118-1138.

[13] Zhao, Na, Jiabin Yuan, and Han Xu. "Survey on intelligent transportation system." Computer

science 41.11 (2014): 7-11.

33

BAB VII LAMPIRAN

34

LAMPIRAN 1 Tabel Daftar Luaran

Program : Penelitian Unggulan ITS

Nama Ketua Tim : Ahmad Muklason, S.Kom., M.Sc., Ph.D

Judul : Pengembangan Model Traveling Salesman Problem &

Vehicle Routing Problem dan Algoritma Generik Berbasis

Hyper-heuristics Untuk Menyelesaikan Permasalahan

Optimasi Operasi dan Penjadwalan Public Transport di Kota

Surabaya dalam Kerangka Kerja Intelligent Transport

Systems

1.Artikel Jurnal

No Judul Artikel Nama Jurnal Status Kemajuan*)

1 Solving Travelling Salesman

Challenge 2.0 Problem

with Artificial Bee Colony

Algorithm

Expert System With Its

Application

Persiapan

*) Status kemajuan: Persiapan, submitted, under review, accepted, published

2. Artikel Konferensi

No Judul Artikel Nama Konferensi (Nama

Penyelenggara, Tempat,

Tanggal)

Status Kemajuan*)

1 Self Adaptive Learning – Great

Deluge Based Hyper-heuristics

for Solving Cross Optimization

Problem Domains

IEEE: The 17th

International

Conference on

Electrical

Engineering/Electronics,

Computer,

Telecommunications

and Information

Technology (ECTI-CON

2020) 24-27 June 2020

Virtual Conference

Hosted by College of

Computing, Prince of

Songkla University,

Thailand

Published

2 Route Optimization of Airplane

Travel Plans Using

the Tabu-Simulated Annealing

Algorithm to Solve

the Traveling Salesman

Challenge 2.0

IEEE 2020

International

Conference on

Computer Engineering,

Network and Intelligent

Multimedia (CENIM),

17-18 November, 2020

Presented

35

*) Status kemajuan: Persiapan, submitted, under review, accepted, presented

3. Paten

No Judul Usulan Paten Status Kemajuan

*) Status kemajuan: Persiapan, submitted, under review

4. Buku

No Judul Buku (Rencana) Penerbit Status Kemajuan*)

*) Status kemajuan: Persiapan, under review, published

5. Hasil Lain

No Nama Output Detail Output Status Kemajuan*)

*) Status kemajuan: cantumkan status kemajuan sesuai kondisi saat ini

4. Disertasi/Tesis/Tugas Akhir/PKM yang dihasilkan

No Nama Mahasiswa NRP Judul Status*)

1 SHOF RIJAL AHLAN

ROBBANI

05211850012002

Hyper-heuristic

for Solving

New variant

TSP Problem

In Progress

2 LANANG ALUN

NUGRAHA

05211850012003 Hyper-heuristic

for Solving

New variant

VRP Problem

In Progress

*) Status kemajuan: cantumkan lulus dan tahun kelulusan atau in progress

“Self Adaptive Learning - Great Deluge Based Hyper-heuristics for Solving Cross Opti- mizationProblem Domains”

Ahmad Muklason

XXX-X-XXXX-XXXX-X/XX/$XX.00 ©20XX IEEE

Self Adaptive Learning – Great Deluge Based Hyper-heuristics for Solving Cross Optimization

Problem Domains

Widya Saputra Information Systems Department

Institut Teknologi Sepuluh Nopember Surabaya, Indonesia

[email protected]

Ahmad Muklason Information Systems Department


[email protected]

Baiq Z.H. Rozaliya Information Systems Department


[email protected]

Abstract—In the literature, almost all optimization problems in NP-hard class are solved by meta-heuristics approach. However, this approach has the drawback of requiring tuning parameters for each different problem domain and different instances of the same problem. This approach is considered less effective in resolving these problems. Therefore, a new approach is needed, namely the hyper-heuristics approach that is able to solve cross-domain problems. Hyper-heuristic is one of the approximate search methods which is able to provide solutions to NP-hard problems in polynomial time, as well as giving fairly good and acceptable results. This method has two properties of search space, namely the selection of LLH and the acceptance of solutions (move acceptance). This approach works in barrier domains rather than directly working in problem domains. With these properties, hyper-heuristic is able to solve problems in different domains. In addition, hyper-heuristics has a learning mechanism through feedback from previously generated solutions. This final project tries to apply a hyper-heuristic algorithm in six combinatorial optimization problem domains, namely SAT, Bin Packing, Flow Shop, Personnel Scheduling, TSP, and VRP. The method that will be used in this final project is Self Adaptive - Great Deluge (SAD-GED). The Self Adaptive mechanism is used to make LLH selection to be used, while the Great Deluge is used in determining the acceptance of solutions (move acceptance) in a hyper-heuristic framework. The application of the SAD-GED algorithm is expected to be able to provide better results than the existing algorithm used previously, namely Simple Random - Simulated Annealing.

Keyword—Meta-heuristic, Hyper-heuristic, Self-adaptive

Learning, Great Deluge, Cross Domain Optimization

I. INTRODUCTION

Optimization is a method of finding feasible and optimal solutions from a collection of solutions that have been identified [1]. Optimization plays a role in minimizing or maximizing the value of the objective function in each problem. There are various optimization problems such as sat, flow shop, timetabling, vehicle routing problem, bin packing, and traveling salesman problem where trying to find the shortest distance, from one location to another [2]. These problems can be included in the NP-hard class where optimal solutions are difficult to obtain because of the complexity of the problem.

In solving increasingly complex problems, we need algorithms that are able to provide solutions with relatively fast time. Approximate algorithms such as heuristics, meta-heuristics, and hyper-heuristics are choices in solving these problems. The approximate algorithm provides a solution that does not guarantee the most optimal, but is quite good and relatively fast (polynomial).

Meta-heuristic is one method that is able to select and modify heuristics to produce new solutions or change current solutions into other solutions [3]. For many combinatorial problems, this method becomes very powerful and provides a flexible method. However, this method has drawback, unable to adapt well to the changes in the structure of problems or even instance of problems that are different from the same structure.

Unlike Hyper-heuristics, this method is a high-level methodology which combine multiple low-level heuristics (LLH) and problem instances effectively so it provides solutions in cross-domain problems. In other words, this method can determine which low level heuristic will be used and determine whether to accept the solution produced by LLH (move acceptance) or not. This method works in a heuristic workspace so there is no need to know a specific understanding of the problem to be solved. So that, hyper-heuristic is more general in solving hard combinatorial optimization problems because it does not depend on the problem parameters [4]. This study tries to apply the Hyper-heuristic Self Adaptive Learning Great Deluge (SADGED) method in solving cross domain optimization problems. The problem to be solved refers to the HyFlex framework where there are six problem domains, satisfiability (SAT), one dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman problem (TSP), and vehicle routing problem (VRP). Later, the results obtained from the method will be compared with the Simple Random Simulated Annealing (SRSA) algorithm which acts as a comparison method so that it can measure the performance of the algorithm that has been applied

II. LITERATURE STUDY

A. Combinatorial Optimization

The problem of combinatorial optimization is a problem that exists in the fields of machinery, planning, and industry that can be modeled in the form of minimizing or maximizing costs on limited discrete variables. [5]. In the optimization problem, there is a value of the objective function which will be maximized and minimized according to the objectives to be achieved based on the existing constraints.

B. Meta-heuristic

Meta-heuristics are the main strategies that guide and modify other heuristics to produce solutions outside of optimal local search. This method describes the entire search process, such as which heuristics will be used, even the criteria for accepting solutions. For many combinatorial problems, this method becomes very powerful and provides a flexible method. Meta-heuristics are mostly inspired by natural processes or science, such as the Simulated Annealing method, Taboo Search, Genetic Algorithm, and so on [3].

Meta-heuristics will succeed in optimizing the problem if it can strike a balance between exploration (diversification) and exploitation (intensification) so that it depends on parameter values [6]. Exploitation is needed to identify parts of the search for solutions with good quality results. The classification of solutions resulting from this process can be either single or plural solutions. This approach relies on parameter values so that it is less able to adapt to changes in problem structures or even different problem instances with the same structure.

C. Hyper-heuristic

Hyper-heuristic includes a collection of approaches which aim to automate, which usually combines with machine learning techniques, the process involves selecting and combining simple heuristics or creating new heuristics from existing heuristic components in order to solve optimization problems [6]. Hyper-heuristic is a methodology that can provide a solution that is not too optimal, but a fairly good and acceptable solution. the main purpose of hyper-heuristics is to create a general design method, which can provide a feasible solution based on the use of LLH.

Hyper-heuristic is a learning algorithm if it uses feedback from the solution search process. Based on the feedback dimension, there are 3 divisions of learning types. Online learning, learning is done when the algorithm is solving problems. Offline learning, which is collecting knowledge in the form of rules and programs, from a collection of training instances that are expected to generalize to resolve events that are not visible [7]. As for No-learning, Hyperheurisik does not do learning. Hyper-heuristic has a general structure consisting of high-level and low-level parts. low level heuristic is a heuristic that will be chosen which is a representation of the problem, evaluation function and initial solution related to the problem so that each problem has a different LLH collection [1]. As for the high level,

it has LLH selection mechanism (to determine new solutions) and move acceptance (determine whether to accept the solution or not).

III. METHOD

A. Problem Identification

This study aims to apply a hyper-heuristic method that is able to provide optimal results (fitness) for each problem domain contained in the HyFlex framework. Each problem contained in HyFlex has different problem characteristics so that the LLH

Fig. 1. The Design of Algorithm Flowchart for Self Adaptive Learning Great Deluge

contained in each problem is also different. Hyper-heuristics must be able to recognize every LLH and use LLH for every problem. Applying the right high level heuristic method is expected to be able to choose LLH appropriately and provide a good solution in each problem domain. this hyper-heuristic

development focuses on selection of pertubative LLH based on single point search (one solution result) [8].

B. Literature Study

At this stage a literature study is carried out related to the material that will be used as a research reference. Literature studies include concepts that will be applied in research.

C. Desain The Algorithm

At this stage the hyper-heuristic is developed as a high-level heuristic strategy that is in accordance with the problem that has been defined. At this stage the method will be described in the selection of LLH and the mechanism for accepting solutions.

In this study, the high level strategy applied to hyper-heuristics is a combination of self adaptive learning and great deluge (SADGED). The self adaptive learning method is used as LLH selection in solving problems, while the great deluge is used as a mechanism of move acceptance in obtaining new solutions resulting from the implementation of LLH in each problem domain. This mechanism will accept a better solution or below the parameter B value limit in the great deluge method at each predetermined iteration. SADGED algorithm design can be seen in Figure 1.

In this study, the LLH series (low level heuristic) used is LLH which is available in the HyFlex framework. low level heuristic is a collection of heuristics on HyFlex which is used to generate solutions so that the objective function of the solution can be known in solving problems. In HyFlex, LLH used are grouped into four types, namely mutation, ruin-recreate, local search, and crossover [9].

Fig. 2. The calculation of minimum and median value that is better than SRSA based on the trial results of the percentage of desired value based on the initial solution

The self adaptive learning method plays a role in determining the amount of LLH that will be used by the method to find the value of objective functions, this study uses the number of LLH limits as provided in the HyFlex framework. The value of the desired value variable is set to 10 percent of the initial solution value. The initial level parameter value or the solution acceptance factor is set the same as the initial solution value, while the value of the decay rate or temperature reducing factor is set based on the reduction in the initial value of the solution with the desired value, then divided by the number of iterations

[10]. Self adaptive learning plays a role in selecting LLH which produces the best value. When all the selected LLHs have been used, the algorithm will fill in the LLH that will be used with a composition of 75% of LLH that produces values that can be accepted by the move acceptance method, while the remaining 25% of LLH is in the problem domain [11].

D. Implementation

This stage is the implementation phase of the algorithm design in the hyper-heuristic Flexible (HyFlex) framework. Implementation is the stage of development of algorithm design into the program language. This stage starts from the preparation of tools to the implementation of the program.

The implementation is done on a 3.2 Ghz core i5 processor and 4096 MB of memory. The algorithm design will be implemented in the HyFlex framework using the NetBeans IDE 8.2 application. implementation is done by calling the method contained in the chesc.jar library.

E. Trial

Algorithm testing tries to find the optimal solution for the six problem domains in the HyFlex framework. A trial was conducted to find out how the performance of the algorithm that had been built on six problem domains, namely satisfaction, one-dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman problem, and vehicle routing problem.

Fig. 3. The scenario of testing methods that will be used in the HyFlex framework.

Based on the results of testing the desired value parameters in the self-adaptive learning great deluge method, the most optimal value obtained is 10 percent of the value of the initial solution. The trial is conducted by comparing the median and minimum values of the results of the execution. From Figure 2, the desired value of 10 percent provides a fairly stable number of solutions compared to other trial values. The value obtained is a percentage of the initial solution value. Meanwhile, the use of LLH length in the SADGED method is adjusted to the number of LLH contained in each problem domain.

In Figure 3 the method trial scenario, the algorithm is run by entering some required input data. Furthermore, the framework will search for solutions based on predefined input data. After the final criteria for running the algorithm are completed, the framework will return the value of the best solution resulting from the search process Simple Random Simulated Annealing Algorithm and Great Deluge Self Adaptive Learning are applied in six problem domains contained in the HyFlex framework. In each problem domain, there are five instances that have been determined in the trial process so that the total instances used are 30 instances. Each instance is tested 31 times with a time of 60000 milliseconds. From the data the results of the execution are calculated the best value (minimum), first quartile, median, third quartile, maximum value, and average that will be used as a comparison value for each method

IV. RESULTS AND DISCUSSION

The trials were conducted 31 times on six problem domains with 5 instances of each problem. In conducting trials, performance measurements are carried out by comparing the SADGED method with SRSA. Performance testing is done by doing three comparisons. First, comparing the distribution of data from the results of the method execution on some statistical data, namely the minimum value (fitness), the first quartile, median, third quartile, and the maximum value of the value of the objective function. This test uses the calculation of values and points and visualization of boxplot diagrams from the statistical data obtained. Second, comparing the median values obtained to measure the concentration of values in the data. Third, make a comparison of the minimum values obtained from the method execution results.

A. Comparison of Data Distribution

Comparison of data distribution is done by calculating based on statistical values such as minimum value, first quartile, median, third quartile, and maximum value and visualization of values against the boxplot diagram. The objective function value data from the comparison of two methods that give smaller values will get one point. The maximum point in one problem domain is 25 while the overall point of the problem domain is 150. Methods that get a greater value are said to be superior to other methods. The results of calculations and boxplot diagrams of the two methods can be seen as follows: • In the SAT problem domain, SADGED has better

performance compared to SRSA. The SADGED method excels at the five instances tested and gets 25 points.

• In the bin packing problem domain, the SADGED algorithm lost 17 points from the SRSA algorithm with the acquisition of 21 values for SRSA and 4 for SADGED. The SADGED algorithm is only able to outperform one instance and lose to the other four instances.

• In the flowshop problem domain, SADGED is only able to excel at two instances namely instance 1 and instance 8, while losing to the remaining three instances. The defeat of the SADGED algorithm is not significant where

it gets 12 points, while SRSA gets 13 points. The difference between the two methods is only 1 point and won by SRSA.

• In the personnel scheduling problem domain, SADGED excels in three instances, namely instance 5, instance 10, and instance 11, while losing to the other two. The SADGED algorithm is 5 points ahead of SRSA with 16 points.

• In the tsp problem domain, SADGED excels in all five instances by getting a value of 21, which is 19 points ahead of SRSA who gets a value of 4.

• In the vrp problem domain, SAGDED excels in the five instances tested and scores 25 points.

Based on the calculation of points that have been done, the SADGED method excels in four problem domains and gets 56 points compared to SRSA. The SADGED method gets 103 points from all 30 instances tested compared to SRSA which only gets 47 points.

Fig. 4. The comparison of median score graph of great deluge self adaptive learning method with simple random simulated annealing.

B. Comparison of Median Values

Comparison of the median value is done to measure the centralization of the results of the method execution. This second measurement uses the FIFA ball method by looking at the value of the median in each instance. the algorithm that is considered to be won will be given a value of three, then for a balanced algorithm will get a value of one and the losing algorithm will get an empty value. The method is considered to win if the total value of the changes obtained is positive and is considered losing if it is negative.

Based on the test results in Figure 4, SADGED won in four problem domains, namely sat, personnel scheduling, tsp, and vrp. However, this method loses to two other problem domains, namely Bin Packing and Flowshop. This indicates that the SADGED algorithm is not able to provide better results in the two problem domains when compared to the SRSA algorithm, which suffered quite a lot of losses. Performance testing graph can be seen below.

Fig. 5. The Rank of Hyper-heuristic methods used is based on the Formula One system.

Figure 5 shows the testing using the Formula One system for both methods, the first rank obtained by the SADGED method with a score of 50 points from the total score that can be obtained by 60 points. The SADGED method gets a percentage point of 83% with an average of points gained in each instance of 1.6 points. Furthermore, the second rank obtained by the SRSA method with the acquisition of a score of 40 points from a total score of 60 points. This method gets a percentage point of 67% with an average point on each instance of 1.3 points.

C. Comparison of Minimum Values

The comparison of minimum values is performed on 30 instances of data with 31 executions. Comparisons at this stage use the FIFA ball system. This system provides a rating of three points for the method that is considered to win, a value of one in the draw method, as well as an empty value on the losing method or produce a worse value than the other methods. a method that gives a better percentage change value will get points of 3 in each problem domain. The purpose of this comparison is to test the performance of the strategies implemented in solving domain traffic optimization problems.

Based on the graph in Figure 6, the minimum SADGED score overall wins in four problem domains, namely SAT, Personnel Scheduling, TSP, and VRP. However, in the problem domain the Bin Packing and Flowshop SADGED method is unable to compete with SRSA. In the domain of the flowshop problem, the SADGED defeat is not too significant, the percentage of changes obtained is 0.71%. The most significant defeat was found in the Bin Packing problem domain where only one instance could win to reach the minimum value with a percentage change of 78.69%.

Although in this work, the hyper-heuristics was tested over 6 problem domains only, but hyper-heuristics also works for other problems. For example, similar works using hyper-heuristics by the can be found in [12], [13], and [14] in which the hyper-heuristics was used for solving examination timetabling problem. On the other hand, in [15] the hyper-heuristics was used to solve orienteering problem.

CONCLUSIONS

Based on the results of trials and analysis of the results that have been carried out, the following conclusions can be drawn:

• The combination of Great Deluge's Self Adaptive Learning is able to give better results compared to the Simple Random Simulated Annealing algorithm. SADGED is able to provide better results in four problem domains, namely SAT, Bin Packing, TSP, and VRP based on the results of trials conducted on the HyFlex framework.

• The SADGED method used is not good enough in finding optimal solutions to the Bin Packing problem. SADGED is only able to provide optimal solutions to one of the five instances tested in the problem domain. This method gets a significant reduction in percentage change of 78% when seen from the minimum value and 92% in the median value.

• Although there was a decrease in the flowshop problem domain, the decrease that occurred was not very significant. SADGED is able to provide an optimal solution for two instances in the problem domain being tested. When viewed from the minimum side of the decline obtained by 0.71%, while providing an optimal solution for three instances when viewed from the median value with a percentage change of 0.02%.

• Based on the test results using the Formula One system, the SADGED method has a better performance compared to the SRSA algorithm. This can be seen from the percentage of performance score obtained by 83% with 50 points from a total of 60 points tested in 30 instances in six different problem domains. The SADGED method is 16% superior to the SRSA method as a comparison algorithm that gets a percentage point of 67%.

In subsequent studies, experiments can be conducted in determining the parameters of the number of LLH limits used in finding optimal objective function values in the Self Adaptive Learning method. With the determination of the right amount, it is expected to be able to provide better results in finding optimal solutions, especially for the Bin Packing and Flowshop problem domains.

Fig. 6. The comparison graph of the minimum score of the great deluge self-adaptive learning method with simple random simulated annealing

REFERENCES

[1] S. S. Choong, L. P. Wong, and C. P. Lim, “Automatic design of

hyper-heuristic based on reinforcement learning,” Inf. Sci. (Ny)., vol. 436–437, pp. 89–107, 2018.

[2] C. Rego, D. Gamboa, F. Glover, and C. Osterman, “Traveling salesman problem heuristics: Leading methods, implementations and latest advances,” Eur. J. Oper. Res., vol. 211, no. 3, pp. 427–441, 2011.

[3] E. K. Burke and G. Kendall, Search Methodologies, 2nd ed. . [4] J. D. Walker, “Design of Vehicle Routing Problem Domains for a

Hyper-Heuristic Framework,” 2015. [5] P. Franq, “Optimization Problem,” Paul Otlet Institute, 2012.

[Online]. Available: http://www.otlet-institute.org/wikics/Optimization_Problems.html. [Accessed: 21-Feb-2019].

[6] I. Boussaïd, J. Lepagnot, and P. Siarry, “A survey on optimization metaheuristics,” Inf. Sci. (Ny)., vol. 237, pp. 82–117, 2013.

[7] E. K. Burke et al., “A Classification of Hyper-heuristic Approaches,” 2009.

[8] E. K. Burke et al., “Hyper-heuristics: A survey of the state of the art,” J. Oper. Res. Soc., vol. 64, no. 12, pp. 1695–1724, 2013.

[9] E. Burke, T. Curtois, M. Hyde, G. Ochoa, and J. A. Vazquez-Rodriguez, “HyFlex: A Benchmark Framework for Cross-domain Heuristic Search,” no. January, 2011.

[10] R. A.-M. Nabeel, “Hybrid genetic algorithms with great deluge for course timetabling,” IJCSNS Int. J. Comput. Sci. Netw. Secur., vol. 10, no. 4, pp. 283–288, 2010.

[11] Q. Pan, M. F. Tasgetiren, P. N. Suganthan, and T. J. Chua, “A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem,” Inf. Sci. (Ny)., vol. 181, no. 12, pp. 2455–2468, 2011.

[12] Muklason, A., Bwananesia, P.C., YT, S.H., Angresti, N.D. and Supoyo, V.A., 2018, October. Automated Examination Timetabling Optimization Using Greedy-Late Acceptance-Hyperheuristic Algorithm. In 2018 International Conference on Electrical Engineering and Computer Science (ICECOS), pp. 201-206.

[13] Kusumawardani, D., Muklason, A., & Supoyo, V. A. (2019, July). Examination Timetabling Automation and Optimization using Greedy-Simulated Annealing Hyper-heuristics Algorithm. In 2019 12th International Conference on Information & Communication Technology and System (ICTS) pp 1-6

[14] Muklason, A., Syahrani, G.B. and Marom, A., 2019. Great Deluge Based Hyper-heuristics for Solving Real-world University Examination Timetabling Problem: New Data set and Approach. Procedia Computer Science, 161, pp.647-655.

[15] Yoga, I. Wayan AK, Arif Djunaidy, Wiwik Anggraeni, Ahmad Muklason, Faizal Mahananto, Edwin Riksakomara, Nisa D. Angresti, Hidayatul YT Sasmi, and Vicha Azthanty Supoyo. "Advanced Traveler Information Systems: Itinerary Optimisation Using Orienteering Problem Model and Genetic Algorithm." In 2018 International Conference on Information Technology Systems and Innovation (ICITSI), pp. 454-459.

Ahmad Mukhlason, S.Kom, M.Sc, Ph.D

PRESENTER

Route Optimization of Airplane Travel Plans Using the Tabu-Simulated Annealing Algorithm to Solve

the Traveling Salesman Challenge 2.0 Edwin Dwi Ahmad

Department of Information Systems Institut Teknologi Sepuluh Nopember

Surabaya, Indonesia [email protected]

Ahmad Muklason Department of Information Systems

Institut Teknologi Sepuluh Nopember Surabaya, Indoensia

[email protected]

Ika Nurkasanah Department of Information Systems


[email protected]

Abstract— Traveling Salesman Problem (TSP) has been

emerged as NP-hard problem in which there is no exact algorithm that can solve it in polynomial time. There has been an increasing interest in implementing TSP to find the shortest travel route where the trip starts from a city and must end in the same city as the departure city in a condition that every city has to be visited exactly once. Another important feature of TSP is to find travel routes with the lowest possible cost. This paper investigates a new variant of TSP to solve airplane travel plans problem in the Travelling Salesman Challenge (TSC) 2.0. A hybrid Tabu Search and Simulated Annealing was used to solve the problem. The results show that the proposed algorithm can solve the problem and outperforms great deluge algorithm, i.e. 48.54% vs 41.33% measured by the improvement from the initial solution.

Keywords—Travel Salesman Problem, Tabu Search and Simulated Annealing, Travelling Salesman Challenge 2.0

I. INTRODUCTION (HEADING 1)

Traveling Salesman Problem (TSP) is a problem faced by a salesman where the salesman must visit all cities. The salesman must start his journey from a city and must return to his departure city [1]. The expected result on the TSP is to find the shortest route that can be taken to visit each city that has been provided, with the condition that all cities must be visited once in each trip [2]. Besides being used to find the shortest travel route, TSP is also used to find travel routes with the least total cost [3].

TSP represents a classic problem in combinatorial optimization and is classified as NP-hard problem, which means a problem is difficult to solve in a polynomial time. The computational complexity in TSP will increase along with the increasing number of cities [2]. There have been some recent studies that solve the TSP problem using heuristic algorithms, such as simulated annealing, ant colony optimization and tabu search [4].

In 2018, there was a competition, Travelling Salesman Challenge (TSC) 2.0, raising the use of TSP in addressing airplane travel plan problem. The expected outcome of TSC 2.0 is an itinerary route using the lowest possible cost. The route chosen must pass through all the available areas where each area consists of at least one city. However, if there is one area that has several cities then only one city may be visited. The selection of cities in each area in the planning of this travel route is free as long as conditions for visiting the entire area have been met.

Recent developments in the field of TSP have led to a renewed interest in using various kinds of approaches, such

as Hybrid Simulated Annealing and Tabu Search algorithms. Previous researches show that the combination of those algorithms can obtain optimal results, as well as overcome the weaknesses of each algorithm. Therefore, Tabu-Annealing Simulated is chosen in this study to increase population diversity in Gene-Expression and to improve global search. The result expected from this study is the algorithms used successfully outperform other heuristic algorithms in terms of finding the best solution for airplane itinerary route problem.

II. LITERATURE REVIEW

A. Travelling Salesman Problem

Traveling Salesman Problem (TSP) is one of the classic problems in combinatorial optimization that aims to find the shortest route in visiting all the cities on the tourist map [2]. The selected route starts from a city and must end in the same city as the departure city, and each city should only be visited once. Besides aiming to find the shortest route, the search for a trip route with a minimum total cost must also be considered in the TSP to save the travel budget.

The mathematical modelling of TSP are expressed in the following equation: 1 0 min∑ ∑ , 0 ≤ ≤ 1 , = 0, … , ∑ = 1, = 0, … , ∑ = 1, = 0, … , ∈ = 0, … , − + ≤ − 11 ≤ ≠ ≤

Equation (1) shows the decision variable in binary number where 1 represents travelling route from city i to city j, while 0 indicates the reversed route (from city j to city i). Equation (2) expresses the objective of TSP to minimize the cost with the shortest distance throughout airplane travel routes. The condition in which all cities must be visited no more than 0 is illustrated in equation (3), (4), and (5), while equation (6) and (7) describe the constraint that all cities are connected to a route chosen by the salesman by adding a dummy variable to check that there are no sub routes.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

B. Travelling Salesman Challenge 2.0

Traveling Salesman Challenge (TSC) 2.0 is a competition organized by online travel company, Kiwi. The purpose of this competition is to solve problems in planning the route of travel by airplane. The trip must be done by visiting a city in the given areas where an area can consists of more than or equal to one city.

TSC 2.0 provides the following hard constraints that should be met during the formulation of the solution: 1) the journey must start from the pre-determined city, 2) each area must be visited exactly once, 3) there are one or more cities in the areas, while each salesman area must visit exactly one city, 4) every day salesmen must move from one area to another, 5) salesmen may only visit one area every day, 6) the salesman's journey to the next area must continue from the city in the area visited the day before, 7) the trip must end in the same area as the first departure area.

The dataset used in this study are taken from TSC 2.0 in which some attributes are already provided, such as number of areas, the first city point to start the trip, the list of airports, as well as the flight schedule and prices for each flight. Table I below illustrates the breakdown of TSC 2.0 dataset.

TABLE I. TSC 2.0 DATASET

Dataset Number of Areas

Number of Cities

Data Type

Dataset 1 10 10 Artificial










Dataset 11 150 200 Real




C. Hyper-Heuristic

Hyper-heuristic is a heuristic search method used to automate processes, usually using machine learning. Hyper-heuristic can also be interpreted as a collection of approaches used to combine several heuristic methods to solve several computational problems that have a high degree of difficulties [9]. The Hyper-heuristic was developed to increase the scope of problem solving to become more general and simpler.

Hyper-heuristic is different from metaheuristic where metaheuristic is mostly implemented in the search space for problem solutions. Meanwhile, hyper-heuristic is

implemented beyond search space in the form of solution space. Hyper-heuristic has no guarantee of success in finding the optimal solution. However, the tuning parameters in such method are done automatically, so it no longer requires manual tuning parameters [10].

D. Tabu-Search Algorithm

Tabu Search is one of the metaheuristic algorithms that applies local search methods to do mathematical optimization [11]. The basic principle of the Tabu Search algorithm is to prevent a solution that does not improve by utilizing memory space, which is a taboo list. Tabu Search will save the solutions that have been found and the solutions will as much as possible avoid the process of searching back to the candidate from the previous solution. The concept used in the tabu list is to use FIFO (first in first out) rules, which means that the earliest taboo solution will be replaced by a new solution [12]. Therefore, Tabu Search Algorithm can avoid the local optima solution.

E. Simulated Annealing Algorithm

Simulated Annealing is a metaheuristic algorithm that adopts the concept of steel expansion in physical theory [13]. In the simulated annealing algorithm, if the new solution is no more optimal than the initial solution, then the new solution will pass the control function [14]. The control function is expressed by the Boltzmann equation: =

where P is probability, e is exponential number, c is the difference in the evaluation of the objective function between the solution and the candidate solution, and t is the temperature parameter.

III. IMPLEMENTATION

A. Initial Route Formation

Initial solution is formed by taking the city as the initial route randomly according to the available flight schedules. In order to avoid routes that have no flight schedules in the next day, a graph is made which consists of cities and flight schedules. The initial route must meet all applicable constraints, and once it is formed then an optimization will be performed using the tabu-simulated annealing algorithm.

B. Implementation of Tabulated Simulated Annealing Algorithm

Tabu-simulated annealing algorithm is performed to get the optimum solution. After getting the initial solution, a low level heuristic is applied by conducting 2-city-swap, 3-city-swap, and 4-city swap, and 1-city-swap. A temporary solution then generated by choosing the low level heuristic result randomly.

The temporary solution obtained will go through the tabu-simulated annealing process. If the temporary solution is better than the initial solution, then the temporary solution is accepted as a new solution. However, if the temporary solution is worse than the initial solution, the Boltzmann equation will be accomplished. Temporary

solution is accepted as a new solution if the value of the Boltzmann equation is greater than the random value.

The tabu list will be administered if the temporary solution is worse than the initial solution by entering the low level heuristic result. However, it will be checked beforehand whether there are still slots in the tabu list. If the tabu list slot is full, its contents will be removed first. Low level heuristics that have entered into the tabu list will not be used again in the next process until it is out of the list.

A temporary solution can be accepted as a new solution if its cost is lower than the initial solution’s or provided the random value is greater than the value of the Boltzman equation, as well as the low level heuristic used is not included in the taboo list.

The pseudocode of tabu-simulated annealing is illustrated as follow:

Fig. 1. Pseudocode of Artifical Bee Colony Algorithm

C. Parameters Experiment

There are several parameters tested in the tabu-simulated annealing algorithm as stated in the Table II below.

TABLE II. ALGORITHM PARAMETERS

Parameters Description

LLH Number of low level heuristic used

T0 Initial temperature of simulated annealing algorithm

T1 Final temperature of simulated annealing algorithm

cr Cooling Rate

TL Length of list of tabu search algorithm solutions

IV. RESULTS & DISCUSSIONS

A. Optimization Result

The research is carried out through several scenarios to get the optimum solution. Table III shows a list of the scenarios where each of them is run 11 times for one dataset. Meanwhile, the dataset chosen in the experiment are the 1st , 6th, 11th, and 12th since those can represent the characteristics of the entire dataset.

TABLE III. ALGORTHM PARAMETERS EXPERIMENTS

Scenario T0 T1 cr TL

1 100 0.1 0.95 2

2 10000 0.1 0.9025 2

3 100000000 0.1 0.81450625 2

4 1000000000 0.1 0.9995 2

5 1000000000 0.1 0.9995 3

6 1000000000 0.1 0.999995 3

7 1000000000 0.1 0.9999995 3

8 1500000000 0.1 0.999995 3

9 1500000000 0.001 0.99999995 3

10 1500000000 0.001 0.999995 2

11 1000000000 0.1 0.9999995 2

12 1000000000 0.001 0.9999995 3

The experimental results of 1st to 12th scenarios are compared to find out the combination of parameters that produces the optimum value. On the other side, in order to obtain the right scenario, a weight is given for each dataset, then it is added up based on each scenario, so it can lead to the most optimal scenario.

The 1st and 6th dataset are given a weight of 1 while 11th st and 12th datasets are given a weight of 1.5. The output of each scenario represents airplane travelling cost and Fig. 2

below depicts the results of cost comparison among all scenarios i.e during scenario selection.

Fig. 2. The comparison of each scenario

According to the graph above, the most optimum result or the cheapest travelling cost is triggered by 6th scenario, accounting for 428,0989. Therefore, the senario is used to find out optimum solution for the entire dataset.

B. Comparison between Optimal and Initial Solution

In this section, optimization result in the previous section above is compared to the initial solution for examining the tabu-simulated annealing algorithm performance in providing a more optimum solution (as shown in Table IV). The parameters used in this section are obtained from the scenario experiment where initial temperature equals to 1,000,000,000, cooling rate is 0.9999995, the final temperature is 0.1, while the taboo list length made up 3 and 4 low-level heuristics.

TABLE IV. THE RESULT OF INITIAL AND FINAL SOLUTION

Dataset Initial Final Percentage

1 15,444 1,710 88.9%

2 1,498 1,498 0.0%

3 18,283 10,255 43.9%

4 57,140 20,317 64.4%

5 5,152 1,304 74.7%

6 12,968 4,239 67.3%

7 91,014 37,873 58.4%

8 17,528 10,414 40.6%

9 299,022 167,997 43.8%

10 376,472 135,590 64.0%

11 102,443 70,881 30.8%

12 145,963 94,873 35.0%

13 188,607 170,909 9.4%

14 229,867 207,373 9.8%

Mean 48.5%

It can be seen from Table IV that tabu-simulated annealing algorithm is able to optimize solution at the average of 48.5%, having 1st dataset as the largest percentage of optimization, whilst 2nd dataset is excluded it results no change.

C. Comparison with Other Algorithm

In order to ensure that tabu-simulated annealing algorithm provide best solution, it must be compared with other algorithm. During the research, great deluxe is used by running the algorithm 11 times with 46,051,691 iterations. The summary of comparison can be found in Table V and Fig.3.

Dataset

Tabu-Simulated Annealing Great Deluge

Best Average Best Average

1 1,396 1,710 1,431 3,727

2 1,498 1,498 1,498 1,498

3 9,751 10,255 10,118 11,121

4 19,299 20,317 19,683 22,124

5 1,128 1,304 1,525 1,873

6 3,759 4,239 5,354 5,956

7 35,565 37,873 38,588 39,793

8 7,718 10,414 9,198 11,399

9 144,419 167,997 167,291 183,655

10 122,088 135,590 158,551 172,350

11 66,939 91,008 73,181 81,354

12 91,008 94,873 103,641 109,146

13 164,764 170,909 170,116 178,626

14 204,185 207,373 211,069 221,194

Fig. 3. The comparison of optimal solution using T-SA and GD

0

50000

100000

150000

200000

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Trav

ellin

g Co

st

T-SA GD

Based on the table and figure above, it can be confirmed that tabu-simulated annealing (T-SA) performs better than great deluge (GD) since T-SA allows lower travelling costs.

V. CONCLUSION

This paper set out to investigate how TSP solve airplane travel plan problems in the Travelling Salesman Challenge (TSC) 2. The obvious findings to emerge from this research are as follow:

1. By comparing initial solution and the final solution that has been done, it is known that the taboo-simulated annealing algorithm can improve the initial solution more optimally by an average of 48.54% considering 1st and 2nd dataset

2. In small and medium datasets, the performance of tabu-simulated annealing algorithm in producing optimal solutions is better than large sized datasets.

3. In the dataset included in the artificial data group i.e. 1st to 10th data, the performance of the taboo-simulated annealing algorithm is more optimal when compared to the real data group. The initial solution in the artificial dataset can be optimized with a percentage of 40.59% - 88.92%. Meanwhile, in the real dataset, the percentage generated is smaller (in the range of 9.38% - 35%).

4. In term of finding the optimal solution for the entire dataset, tabu-simulated annealing algorithm provides a better average than great deluge algorithm.

5. Changes in parameters made in this study can affect algorithm performance. However, the greater the value of the parameters used does not guarantee a more optimal solution.

VI. FURTHER RESEARCH

Further studies regarding the efficiency of TSP to solve similar problem as in this paper would be worthwhile if more dataset and more complex scenarios perform, so the result can be more accurate. Another improvement area is to fully accomplish all parameter combinations that perhaps can help to find the most influential parameters in producing an optimal solution. Furthermore, low level heuristics used in this study are limited to moves and swaps, so adding other ones will produce a more optimum solution.

REFERENCES

[1] A. A. Ismail and S. Herdjunanto, “Penerapan Algoritma Ant System dalam Menemukan Jalur Optimal pada Traveling Salesman Problem ( TSP ) dengan Kekangan Kondisi Jalan,” vol. 1, no. 3, pp. 1–6, 2012.

[2] Y. Wang, “The Hybrid Genetic Algorithm with two Local Optimization Strategies for Traveling Salesman Problem,” Comput. Ind. Eng., 2014.

[3] Kara, I. and Derya, T., “Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows”. Procedia Economics and Finance, vol. 26, no. 15, pp.1026-1034, 2015.

[4] A. Zhou, L. Zhu, B. Hu, S. Deng, Y. Song, and H. Qiu, “Traveling-Salesman-Problem Algorithm Based on Simulated Annealing and Gene-Expression Programming.”

[5] Y. Lin, Z. Bian, and X. Liu, Developing a Dynamic Neighborhood Structure for an Adaptive Hybrid Simulated Annealing – Tabu Search Algorithm to Solve the Symmetrical Traveling Salesman Problem. Elsevier B.V., 2016.

[6] X. Geng, Z. Chen, W. Yang, D. Shi, and K. Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” Appl. Soft Comput. J., vol. 11, no. 4, pp. 3680–3689, 2011.

[7] S. Suwannarongsri and D. Puangdownreong, “Adaptive Tabu Search for Traveling Salesman Problems,” Int. J. Math. Comput. Simul., vol. 6, no. 2, pp. 274–281, 2012.

[8] G.B. Dantzig, D.R. Fulkerson, and S. M. Johnson, “Solution of a large-scale traveling salesman problem,” Oper. Res., vol. 2, p. 393, 1954.

[9] E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, and E. Ozcan, “A Classification of Hyper-heuristic Approaches A Classification of Hyper-heuristic Approaches,” no. August 2016, 2010.

[10] E. K. Burke et al, “Hyper-heuristics: A survey of the state of the art,” J. Oper. Res. Soc., vol. 64, no. 12, pp. 1695–1724, 2013.

[11] S. E. E. Profile, “A hybrid simulated annealing-tabu search algorithm for the part selection and machine loading problems in flexible manufacturing systems,” no. March 2012, 2014.

[12] F. S. Hillier, Handbook of Metaheuristics, 2nd ed. Springer, 2010.

[13] R. W.Eglese, “Simulated annealing A tool for operational research.” European Journal of Operational Research 46, North-Holland, pp. 271–281, 1990.

[14] L. Ingber, “Simulated Annealing : Practice versus Theory,” vol. 18, no. 11, pp. 29–57, 1993.

IAES International Journal of Artificial Intelligence (IJ-AI)

Vol. 8, No. 1, March 2019, pp. xx~xx

ISSN: 2252-8938, DOI: 10.11591/ijai.v8.i1.ppxx-xx 31

Journal homepage: http://iaescore.com/online/index.php/IJAI

Solving Travelling Salesman Challenge 2.0 Problem

with Artificial Bee Colony Algorithm

I Gusti Agung Premananda1, Ahmad Muklason2, Aurelius Ian3 , Nuri Wahyuningsih, Retno Aulia

Vinarti, Raras Tyasnurita 1,2,3Department of Information Systems, Institut Teknologi Sepuluh Nopember, Indonesia

Article Info ABSTRACT

Article history:

Received Feb 12, 2020

Revised, 2020

Accepted, 2020

Traveling Salesman Problem (TSP) is a very popular problem in

combinatorics optimization. The TSP problem consists of finding the shortest

route from several cities where the distance between cities is known while

the salesman must visit each city exactly once and must return to his

hometown. This problem belongs to the non-polynomial hard (NP-hard)

problem and can be solved using heuristic method. One of the issues

included in the TSP is the search for the cheapest flight routes to several

cities in the Traveling Salesman Challenge 2.0 (TSC 2.0) competition in

2018. This final project aims to resolve TSC 2.0 problems using the artificial

bee colony (ABC) algorithm. ABC algorithm is an algorithm that is inspired

by the way the bee colony find and determine the best food sources. This

algorithm has been widely implemented for NP-hard problems. The results of

this study indicate that the ABC algorithm can solve TSC 2.0 problems with

a fairly good performance by generating savings on travel costs by an

average of 56.1% from the initial solution.

Keywords:

Flight route

Travelling salesman problem

Artificial bee colony

Copyright © 2019 Institute of Advanced Engineering and Science.

All rights reserved.

Corresponding Author:

Ahmad Muklason,

Department of Information Systems,

Institut Teknologi Sepuluh Nopember,

Jalan Raya ITS, Kampus ITS Sukolilo, Surabaya 60111.

Email: [email protected]

1. INTRODUCTION

Travelling salesman problem (TSP) is one of the most popular problems in the world of

combinatoric optimization [1]. In the TSP problem the number of cities and the distance between them is

known. A salesman will start from one of the cities and depart to visit all the cities exactly once and return to

his hometown. The aim of this problem is how to find the right city order to cover the minimum possible

distance. [2] Generally there are two ways to solve the CSR problem, namely the exact method and the

heuristic method. The exact method searches all possible solutions and the best solution will be chosen.

However, the exact method is only possible for TSP with a small number of cities. For problems with a large

number of cities, heuristic methods such as Genetic Algorithm (GA), Particle Swarm Optimization (PSO),

Artificial Bee Colony (ABC), and others can be used. [3].

ABC is an algorithm developed by Dervis Karaboga inspired by the way of bees finding the best

food sources around their hives. ABC algorithm has been claimed to have better performance compared to

several other algorithms such as GA, PSO and Particle Swarm Inspired Evolutionary Algorithm (PS-EA)

(Dervis Karaboga, 2007). This algorithm has also been widely used to solve optimization problems such as

Knapsack Problems, Job Shop Scheduling Problems, Vehicle Routing Problems, Traveling Salesman

Problems etc. [4]. Based on the strengths of the ABC algorithm mentioned earlier, this research will use the

ABC algorithm to solve the TSP problem in hopes of producing an optimal solution. This research will use a

dataset from the Traveling Salesman Challenge 2.0 (TSC 2.0) competition. The TSC 2.0 dataset consists of

ISSN: 2252-8938

IJ-AI Vol. 8, No. 1, March 2019: xx – xx

32

14 datasets in which each dataset has a different number of cities and characteristics. So by using TSC 2.0

dataset, it is expected that the ABC algorithm test can run better.

1.1 Theoritical Basis

This section explains theories that support the thesis.

A. Travelling Salesman Problem

TSP can be written in mathematics equation from the equation 1 to 7.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Equation 1 is the decision variable of the TSP Problem where if Xij is worth 1 then there is a trip

from city i towards city j. Equation 2 is an objective function of TSP i.e. find the cheapest route by

multiplying Cij which is the cost from city i to j with Xij which is a decision variable. Equation 3 up to 7 are

the restrictions used in finding a solution according to the objective function. Limitation 3 until 5 serves to

ensure that travelling from city i to city j is only allowed for a maximum of 1 time and vice versa. Limitation

6 and 7 used to ensure that there are no subroutes [1].

B. Travelling Salesman Challenge 2.0 Dataset

The TSC 2.0 dataset is a dataset given by Kiwi travel company in the TSC 2.0 race. The dataset is

divided into three types. Those three types are small dataset (dataset 1-3), medium (dataset 4-6) and large

(dataset 7-14). On each dataset contains different numbers of areas and cities. From the 14 datasets, there are

several datasets that are taken from real world data while some are artificial data. More can be seen in Table

1. In each dataset there will be a city of departure, a list of areas and cities within these areas and available

flight schedules along with the cost of the trip.

Table 1 Specified TSC 2.0 Dataset

Dataset Total

Area

Total

City

Data

Type








Dataset 8

Dataset 9

Dataset 10

Dataset 11

Dataset 12

Dataset 13

Dataset 14

200

250

300

150

200

250

300

300

250

300

200

250

275

300

Artificial

Artificial

Artificial Real

Real

Real

Real

IJ-AI ISSN: 2252-8938

Title of manuscript is short and clear, implies research results (First Author)

33

In the TSC 2.0 dataset there are limits (hard constraints) in finding the best solution. These limits

consist of:

1. City of departure has been determined at the beginning.

2. Each area must be visited exactly once.

3. The trip to the next area must be a continuity from the city you visited the previous day.

4. Transfer between areas must be done exactly once every day.

5. The trip must end in the same area as the departure city area.

C. Artificial Bee Colony

ABC algorithm consists of three parts, namely employed bee, onlooker bee and scout bee.

Employed bees are bees that will directly investigate food sources. Onlooker bees are bees who will observe

and decide which is the good solution. While scout bee is a bee that searches randomly for food sources [5].

The ABC algorithm begins with the initiation, which is the stage where scout bee randomly finding

food source. After that scout bee will provide the food source information to the employed bee, that then will

go to the food source. Employed bees will look whether there are better food sources around food sources

that are informed by the scout bee. If there is one, an employed bee will remember the better food source and

forget the old one [6].

Bee onlookers will then get information of the food sources found by the employed bee and will

choose some of the best food sources that will be re-searched for whether there are better food sources

around. If the bees cannot find a better food source after a few trials, scout bee will randomly search for other

food sources and return to employed bee and onlooker bee stages. This stage will continue until the food

source is found as desired [6].

How the onlooker bee selecting food sources using probability as in equation 8.

(8)

Probability is calculated by dividing the value of food source to i with the overall value of the food

source [7]. ABC algorithm combines local search and global search methods. Local searches are performed

by employed bee and onlooker bee while a global search is performed by bee scout and bee onlooker. The

purpose of this combination is to get a balance between the exploration and exploitation process. [8]

2. RESEARCH METHOD

A. Initial Solution

The initial solution is an established solution that will be used as an initial tour in optimizing.

Making the initial solution starts with making a graph inside array form consisting of cities as nodes and

schedules flight as edge. The purpose of making graph is to minimize the possibility of non-route that has a

connection to the next city. After that it will randomly select the cities in the graph to fill in the tour sequence

from the initial solution.

Figure 1. Graph Illustration in Array

B. Artificial Bee Colony Algorithm Implementation

The implementation of the Artificial Bee Colony algorithm begins by making initial solutions of a

number of food sources is desirable. After that, the value will be calculated from initial solution that has been

produced.

The next step is the employed bee stage which is changing the initial solution by doing a low level

heuristic (LLH) swap, through exchanging several cities randomly and calculate the value of the solution that

has been exchanged. If a better solution is found, then the solution will be save and replace the previous

solution.

The next step is to calculate the probability of each solution. After obtaining the probability value, it

will enter the next stage which is the onlooker bee stage, where at this stage it will choose several solutions

ISSN: 2252-8938


34

Figure 2. Pseudocode Algorithm Artificial Bee Colony

based on value the probability. Furthermore, the stages will be carried out the same as employed bee stage

which is swapping several cities, comparing results and saving the best results.

The last step is on scout bee. Employed bee will turn into scout bee if the value of the solution never

changes as many as the pre-determined limit. City on the solution will be swapped without regard of getting

better or not. Meanwhile, if the solution before entering the scout bee stages is the best solution during the

search on food source to i, then that solution will be saved.

1: procedure Artificial Bee Colony

2: NP initial bee colony

3: Limit initial limit

4: FoodSource initial solution

5: While ~Stop Condition () Do

6: Employed Bee phase

7: For each employed bee

8: Swap City in FoodSouce

9: Calculate value fit

10: Apply greedy selection mechanism

11: End

12: Calculate the probability value pi for the solution

13: Onlooker Bee phase

14: Chooses a food source depending on pi


16: Apply greedy selection mechanism

17: End

18: Scout Bee Phase

19: If there is an employed bee becomes scout Then


21: End

C. Parameter Experiment and LLH

In the ABC algorithm there are several parameters that are tested. The list of parameters tested in

this study is explained in table 2. In addition to the parameters, trials will also be conducted on several types

of LLH.

Table 2. Algorithm Parameter List Parameter Description

NP The total of the bee colony that consist of

employed bee and scout bee.

Limit The solution limitation does not increase.

MaxCycle The number of iterations.

IJ-AI ISSN: 2252-8938


35

3. RESULTS AND DISCUSSION

3.1. Optimation Result

In order to produce an optimal solution, this study conducted a trial in the search for parameter

values and LLH types that are able to produce an optimal solution. The test is carried out by trying several

parameter values in datasets 6,11 and 14. This dataset was chosen because this dataset represents the

characteristics of other datasets. Trials are conducted 11 times in each dataset and parameter values with the

best average values will be selected to be used in producing the final solution.

The first experiment is to test the limit parameters with values 2500, 5000 and 7500. This

experiment produces the most optimal limit parameter values is 2500. The results of the trial can be seen in

table 4.

Table 3. Parameter Limit Test Result Limit Dataset 6 Dataset 11 Dataset 14

2500 3668,1 61681,8 151380

5000 3723,9 62113,8 150909

7500 3777.1 62491,1 152161

Subsequent experiments were carried out on NP parameters by trying out values 4.8 and 12. This

experiment resulted in the value of parameter 8 being the optimal value. But the difference is only around 1-

2% and is not proportional to the increase in running time which is almost 2 times. So the NP parameter

value to be used is 4. The trial results can be seen in table 5.

Table 4. NP Parameter Test Result NP Dataset 6 Dataset 11 Dataset 14

4 3668,1 61681,8 151380

8 3723,9 62113,8 150909

12 3777.1 62491,1 152161

Subsequent experiments were carried out on the number of iterations to be performed. The

experiments were conducted with an iteration value of 100,000,000, 250,000,000 and 500,000,000. The

results of this experiment prove the 500,000,000 iteration value is the value that can produce the most

optimal solution. The results of the trial can be seen in table 6.

Table 5. Number of Iteration Test Result Num. of Iteration Dataset 6 Dataset 11 Dataset 14

100.000.000 3856,1 63267,5 160492

250.000.000 3764,4 62908,9 154094

500.000.000 3668,1 61681,8 151380

The last experiment was conducted for the selection of LLH which can produce the most optimal

solution. LLH that will be tested are 2-city swap, 3-city swap, 4-city swap and a combination of 3-city swap

and 4-city swap. The result is a combination of 3-city swap and 4-city swap can produce the most optimal

solution.

Table 6. LLH Test Result LLH Dataset 6 Dataset 11 Dataset 14

2 City Swap 3668,1 61681,8 151380

3 City Swap 3429,8 61242,6 148982

4 City Swap

3 & 4 City Swap

3351,5

3420

61196,5

60453,7

148956,7

148304,6

After finding parameter values that can produce optimal results, the ABC algorithm is applied to 14

datasets.

Based on comparison with the initial solution, the ABC algorithm can optimize travel costs by an

average of 56.1% less than the results of the initial solution. ABC algorithm only produces the same solution

in dataset 2 because the results of the initial solution are already the most optimal.

ISSN: 2252-8938


36

In the artificial dataset, ABC algorithm is able to produce excellent results by producing better

solutions above 50%. There are three datasets that are able to produce better solutions above 80%. But in

datasets based on real data, the increase in solutions is only around 20 to 40%. More can be seen in Figure 3.

3.2. Other Algorithm Comparison

Furthermore, the ABC algorithm will be compared with GA algorithm, Nearest Neighbor (NN) and

Simulated annealing (SA). These three algorithms have also been searched for parameter values that can

produce optimal solution results with a running time approaching the ABC algorithm's running time.

In the comparison of the ABC algorithm and the NN algorithm, the ABC algorithm successfully

excels in 13 datasets and produces the same results in dataset 2. The NN algorithm can only produce 6 viable

solutions. More can be seen in Figures 4 and 5.

Figure 3. Initial Solution and Last Solution Comparison.

Figure 4. ABC Algorithm and NN Comparison

Figure 5. ABC Algorithm and NN Comparison

IJ-AI ISSN: 2252-8938


37

From the results above it can be concluded that the ABC algorithm has a much better performance

than the NN algorithm.

The next comparison is with GA. In this comparison the ABC algorithm is superior to 13 datasets

and produces the same results in dataset2. In datasets 4,9,10,13 and 14, the difference in solutions is quite

large, where the ABC algorithm is able to produce a much better solution than the GA algorithm. More can

be seen in Figures 6 and 7.

Based on the above comparison, it can be concluded that the ABC algorithm produces much better

results than the GA algorithm.

The last comparison is with the SA algorithm. In dataset 1-8 there is no significant difference

between the two algorithms. If you look at it from the average, the SA algorithm is thinner in 5 datasets,

namely dataset 4,5,6,7 and 8. The ABC algorithm is thinner in dataset 3 and in dataset 1 and 2 both

algorithms produce the same results.

The difference starts to be seen from dataset 9-14. The SA algorithm is much superior in the 5

datasets with a difference of 7 to 23%. More can be seen in Figures 8 and 9.

Figure 6. ABC Algorithm and GA Comparison



ISSN: 2252-8938


38

In terms of the distribution of the value of the solution, the ABC algorithm is superior to the SA

alogirthm. The biggest difference can be seen in datasets 10 and 13 which can be seen in the box plot in

figure 10.

Although the ABC algorithm is far better in the distribution of the results of the solution, the ABC

algorithm still can not outperform the performance of the SA algorithm. ABC algorithm is only able to

compete in dataset 1-9 and starts to lag behind in larger datasets (dataset 11-14).

For comparative data, the best results and the averages of the three algorithms can be seen in Table

9.

Table 7. Comparison of ABC Algorithm Optimization Results with other Algorithms Dataset ABC GA NN SS

Best Average Best Average Best Average Best Average

Dataset 1 1396 1396 1407 1986,4 5267 5267 1396 1396

Dataset 2 1498 1498 1498 1498 1498 1498 1498 1498

Dataset 3 8530 9032,2 8666 10874,4 17710 17710 8296 9028,3

Dataset 4 16447 17313,5 29851 34243 59187 59187 17143 17991,6

Dataset 5 833 911,2 2789 3366,5 2440 2440 725 902,2

Dataset 6 3223 3420 3984 4332,4 - - 2408 2754,7

Dataset 7 32854 33238,1 36834 38000,9 - - 30898 31234,4

Dataset 8 6226 7518,1 7767 8674,2 - - 4055 4394,3

Dataset 9 82096 83534,2 119647 126242 378471 378471 76800 77604,4

Dataset 10 57977 62852,8 103577 120034,4 - - 49486 54686,3

Dataset 11 58642 61681,8 63979 67614,4 - - 47599 49410,6

Dataset 12 82071 85024,8 93914 97529,4 - - 63004 66039,9

Dataset 13 138227 142147 164443 170819,8 - - 121007 128090,4

Dataset 14 144815 148304,6 204967 209126,3 - - 141817 145287,7


Figure 10. Dataset 10 and 13 Box Plot

IJ-AI ISSN: 2252-8938


39

4. CONCLUSION

From the final research that has been done, the following conclusions can be drawn,

1. Artificial Bee Colony Algorithm is able to solve the Traveling Salesman problem especially in the

Traveling Salesman Challenge 2.0 case study.

2. The ABC algorithm produces a fairly good performance by producing a solution that is 55% better

than the initial solution and superior to the genetic algorithm and nearest neighbor.

3. The ABC algorithm is not the best algorithm in solving TSP problems, especially in the case study

of TSC 2.0 proven by the results of Simulated annealing algorithm which performs better.

As a development for further research, suggestions that the writer can give include,

1. This research only conducted 3 experiments on each parameter. In future research, it can use more

variations in parameters in order to produce more optimal solutions.

2. This study only uses the artificial bee colony algorithm. In future research, further development of

the artificial bee colony algorithm or other better algorithms can be used to produce a better solution

ACKNOWLEDGEMENTS

The author would like to thank the author's parents, supervisors, lecturers of the Information

Systems Department who have guided, supported, and prayed for the writer in doing this final project. And

thank you to all the friends and writers, and all parties involved in this final project.

REFERENCES

[1] M. Cárdenas-Montes, “Creating hard-to-solve instances of travelling salesman problem,” Applied Soft

Computing, vol. 71, pp. 268-276, 2018.

[2] I. U.Hacizade, “GA Based Traveling Salesman Problem Solution and its Application to Transport

Routes Optimization,” vol. 51, no. 30, pp. 620-625, 2018. [3] M. K. M. Indadul Khan, “A swap

sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem,” Swarm and

Evolutionary Computation, vol. 44, pp. 428-438, 2019.

[4] L.-P. W. ,. C. P. L. Shin Siang Choong, “An artificial bee colony algorithm with a Modified Choice

Function for the traveling salesman problem,” Swarm and Evolutionary Computation, vol. 44, pp. 622-

635, 2019.

[5] H. Jiang, “Artificial Bee Colony algorithm for Traveling Salesman Problem,” pp. 468-471, 2015.

[6] B. B. Dervis Karaboga, “A powerful and efficient algorithm for numerical function optimization:

artificial bee colony (ABC) algorithm,” vol. 39, pp. 460-471, 2007.

[7] M. A. a. S. Abdullah, “Artificial bee colony search algorithm for examination timetabling problems,”

vol. 6, pp. 4264-4272, 2011.

[8] M. A. a. S. Abdullah, “Artificial bee colony search algorithm for examination timetabling problems,”

International Journal of the Physical Sciences, vol. 6, pp. 4264-4272, 2011.

ISSN: 2252-8938


40

BIOGRAPHIES OF AUTHORS

First author’s

Photo (3x4cm)

I Gusti Agung Premananda

Second author’s

photo(3x4cm)

Ahmad Muklason

Aurelius Ian

laporan akhir penelitian unggulan its dana its 2020 · 2020. 11. 30. · i laporan akhir penelitian...

Documents