perencanaan rute pengiriman menggunakan metode parallel

PERENCANAAN RUTE PENGIRIMAN MENGGUNAKAN METODE PARALLELINSERTION DAN EXHAUSTIVE SEARCH PADA PT. STARMASS LOGISTICS

Irvan Maulana, Rifa ArifatiFakultas Teknik UPN “Veteran” Jakarta Program Studi Teknik Industri

E-mail: [email protected]

Abstract

PT. Starmass Logistics is a company engaged in freight forwarding/ packages and documents.The company provides both domestic and international services. In the places of delivery todestination, PT. Starmass Logistics use based solely on the preferences and experience of courieronly. Within delivery order record dated September 9, 2013, the company delivers 13.71 m3 and1713.47 kg goods to 36 locations. With that large number of customers, companies need to optimizedelivery route in order to save the transportation costs. Classical heuristics is an approach that iseasy to use to find the Basic Feasible Solution to this Capacitated Vehicle Routing Problem. Withsaving and parallel insertion we got 453.8 km mileage routes. By doing Tour Improvement withExhaustive Search, we can minimize mileage up to 360 km..

Keywords : Capacitated Vehicle Routing Problem, Saving, Parallel Insertion, Exhaustive Search

PENDAHULUANPerencanaan logistik dikatakan baik apabila

barang atau jasa sampai pada tempat yang tepat,di waktu yang tepat dan dalam kondisi yangdiinginkan pelanggan. Transportasi merupakankomponen yang vital dalam manajemen logistiksuatu perusahaan. Salah satu faktor yangmenentukan dalam manajemen logistik adalahpenentuan jalur distribusi yang akan berpengaruhterhadap biaya transportasi. Pada umumnya biayatransportasi menyerap persentase biaya logistikyang lebih besar daripada aktivitas logistik lainnya.Ballou (2000), dalam Toth dan Vigo (2002),menyatakan bahwa sistem transportasi merupakansalah satu sistem yang banyak menyerap biaya(sekitar setengah sampai dua per tiga dari totalbiaya logistik). Permasalahan di bidang transportasilebih dikenal dengan istilah Vehicle RoutingProblem (VRP), berkaitan dengan penentuan rute-rute kendaraan yang perlu ditempuh oleh suatukendaraan.

Oleh karena itu, untuk mengurangi biayatransportasi, diperlukan sistem transportasi yangefisien. Dengan menurunnya biaya transportasi,perusahaan dapat lebih mudah bersaing denganpara kompetitor dalam hal harga. Permasalahanyang bertujuan untuk membuat dan menentukansuatu rute yang optimal, untuk suatu kelompokkendaraan, agar dapat melayani sejumlah konsumen

disebut sebagai Vehicle Routing Problem (VRP).Vehicle Routing Problem adalah sebuah cakupanmasalah yang di dalamnya ada sebuah problemdimana ada sejumlah rute untuk sejumlah kendaraanyang berada pada satu atau lebih depot yang harusditentukan jumlahnya agar tersebar secara geografissupaya bisa melayani konsumen-konsumen yangtersebar.

Di dalam penyelesaian VRP suatuperusahaan, metode-metode heuristics telah banyakdikembangkan, diantaranya adalah metodeheuristics klasik (classical heuristics). Metodeheuristics klasik banyak menjadi acuan bagiperkembangan metode heuristics lain. Metode inimampu menghasilkan solusi yang cukup baikdengan waktu komputasi (waktu perhitungan) yangsingkat. Banyak dari metode heuristics klasik yangdapat dengan mudah diadaptasikan dengankeberagaman kendala yang muncul dalam kondisireal. Untuk itu, penggunaan metode ini masih seringdan banyak digunakan. Penyelesaian permasalahankendaraan dilakukan dalam dua tahap, yaitu: tourconstruction dan tour imporvement.

Tour construction merupakan tahappenentuan metode untuk membuat solusi (ruteperjalanan) awal. Metode heuristics klasik yangdigunakan pada tahapan ini adalah Clarke andWright Savings Algorithm (metode savings).Algoritma metode ini sederhana (mudah

UPN "VETERAN" JAKARTAUPN "VETERAN" JAKARTA

diimplementasikan) serta relevan dalam menjawabpersoalan VRP karena menghasilkan solusi yangcukup baik dan masih banyak juga pihak yangmenggunakan serta mengembangkannya secaraberkelanjutan agar melalui metode ini dihasilkansolusi yang semakin baik.

Tour improvement merupakan tahapan untukmemperbaiki solusi awal, Metode improvementyang digunakan yaitu Exhaustive Search. ExhaustiveSearch adalah teknik pencarian solusi secara bruteforce pada masalah yang melibatkan pencarianelemen dengan sifat khusus, biasanya di antaraobjek-objek kombinatorik seperti permutasi,kombinasi, atau himpunan bagian dari sebuahhimpunan. Algoritma exhaustive search memeriksasecara sistematis setiap kemungkinan solusi satuper satu dalam pencarian solusinya. Meskipunalgoritma exhaustive secara teoritis menghasilkansolusi, namun waktu atau sumberdaya yangdibutuhkan dalam pencarian solusinya sangat besar.Di dalam beberapa literatur strategi algoritmik,contoh masalah yang sering diasosiasikan denganexhaustive search atau brute force adalah masalah(TSP) Travelling Salesperson Problem (Munir,2004). Pada tahap ini, urutan perjalanan (dalamsatu rute) yang telah dihasilkan dari solusi awalakan mengalami perpindahan. Perpindahan yangdilakukan bertujuan untuk mencari solusi yanglebih baik dari solusi awal.

PT. STARMASS LOGISTICS merupakanperusahaan yang bergerak di bidang jasa pengirimanbarang/ paket dan dokumen. Perusahaan inimenyediakan layanan baik untuk domestik maupuninternasional. Dalam pengiriman ke tempat–tempattujuan, PT. Starmass Logistics menggunakan ruteyang hanya didasarkan pada preferensi danpengalaman kurir saja. Perusahaan belummempunyai prosedur penentuan rute yang optimal.Dengan banyaknya jumlah customer, perusahaanmembutuhkan rute pengiriman yang optimal agardapat menghemat biaya transportasi. Oleh karenaitu, diperlukan suatu program ataupun metodekhusus yang dapat memberikan solusi untukmenentukan rute optimal dalam setiap melakukanpengiriman.

Sampai saat ini, PT. Starmass Logistics masihmelakukan upaya adaptasi dan peningkatan sistem-sistem yang ada, salah satunya adalah sistemtransportasi atau Transportation ManagementSystem (TMS). Berdasarkan kondisi tersebut dandengan melihat pentingnya peranan transportasiuntuk menunjang aliran bisnis, maka fokus pada

penelitian kali ini adalah pada TMS PT. StarmassLogistics, yaitu pada permasalahan rute kendaraan(VRP) PT. Starmass Logistics.

Berdasarkan penjelasan tersebut maka padapenelitian kali tiap metode dalam tour constructionakan dipadukan dengan tiap metode dalam tourimprovement. Kemudian hasil yang diperoleh darikombinasi metode-metode tersebut akandibandingkan untuk akhirnya diketahui metodeterbaik bagi permasalahan jalur/ rute kendaraanpada PT. STARMASS LOGISTICS, yaitu metodeyang menghasilkan rute-rute dengan jarak tempuhterpendek.

TINJAUAN PUSTAKAVehicle Routing Problem

VRP atau Vehicle Routing Problemmerupakan suatu permasalahan yang berfokus padapendistribusian barang dari depot (gudang)perusahaan kepada pelanggannya. Pengirimanbarang tersebut menyangkut pelayanan yangdiberikan perusahaan dalam kurun waktu yangtelah ditentukan kepada sejumlah pelanggan denganmenggunakan kendaraan tertentu dimana lokasidepot dapat berada pada satu atau lebih lokasi.Kendaraan dikemudikan oleh pengemudi melewatijalan yang memungkinkan untuk dilewati. Solusidari VRP berupa rute-rute yang dapat ditempuhkendaraan untuk mengantarkan seluruh permintaanpelanggan dimana setiap rute ditempuh oleh satukendaraan yang berawal dan berakhir di depot.

Karakteristik VRPMenurut (Toth dan Vigo, 2002) ada beberapa

karakteristik dalam VRP yang perlu diperhatikan.Yang pertama adalah komponen-komponen yangberkaitan dalamVRP, yaitu:1. Pelanggan

- Lokasi pelanggan- Permintaan pelanggan- Rentang waktu dimana pelanggan boleh

dilayani (time windows)- Waktu yang dibutuhkan untuk bongkar-muatbarang- Perkiraan jenis kendaraan yang digunakan

untuk melayani pelanggan (mempertimbang-kan kondisi jalan yang ditempuh dan karakteristik permintaan yang dibawa)

2. Depot- Lokasi depot- Jam operasional depot- Kendaraan yang ada di depot


3. Kendaraan- Jumlah dan kapasitas angkut tiap kendaraan- Kendaraan berawal dan berakhir di depot- Setiap rute hanya dilayani oleh satu

kendaraan- Total permintaan pelanggan yang dibawa

suatu kendaraan di rute tertentu (tidak bolehmelebihi kapasitas angkut kendaraan tersebut)

- Biaya-biaya yang terkait dengan kendaraan(misalkan: biaya persatuan jarak atau per satuan waktu tempuh)

4. PengemudiPengemudi yang dipekerjakan harus memenuhikeseluruhan syarat yang dimiliki perusahaan,seperti jam kerja harian, jam istirahat selamamelakukan pelayanan kepada pelanggan, lamamaksimum mengemudi, overtime, dan lain-lain.

5. Rute Kendaraan (jalan yang ditempuh)Rute yang ditempuh perlu diperhatikan

kondisi aslinya, apakah memungkinkan untukdilewati atau tidak. Selain itu, perlu jugamemperhatikan kondisi barang yang dibawaapakah memungkinkan untuk melewati rutetersebut. Hal ini bertujuan untuk mencegahwaktu perjalanan yang lama dan juga kerusakanyang mungkin timbul akibat kondisi jalan yangditempuh.

Karakteristik berikutnya dari VRP adalahdalam hal kendala yang ada dalam VRP tersebut.Berdasarkan batasan atau kendala yang ada,VRP dalam penelitian ini adalah:CVRP (Capacitated Vehicle Routing Problem)yang merupakan model dasar dalam VRP dengankapasitas angkut kendaraan sebagai kendalayang dihadapi. Semua permintaan pelanggandiketahui di awal dan pengantaran permintaantersebut, untuk setiap pelanggan, dilakukan padasatu rute yang sama (keseluruhan permintaansuatu pelanggan diletakkan pada rute yangsama). Kendaraan yang digunakan adalah identikdan hanya terdapat satu depot sebagai lokasiawal dan akhir setiap kendaraan.

Model Dasar VRPMenurut (Toth dan Vigo, 2002) berikut inimerupakan model matematis dasar dari VRP yaitumemiliki kendala pada kapasitas angkut kendaraan.Apabila terdapat kendala lain, maka model ini bisadikembangkan sesuai kebutuhan: = Node (titik) depot dan pelanggan, N = ( 0, 1, 2,. . . . . . , n)N = 0 Node gudang


dengan waktu komputasi yang singkat. Banyakdari metode ini dapat dikembangkan lebih lanjutsesuai dengan kendala-kendala yang datang dalampraktek nyatanya. Karena itu, heuristics klasikmasih banyak digunakan sekalipun pada saat yangbersamaan telah berkembang metode-metode lain.Heuristics klasik dalam penelitian kali ini, sepertiyang dijelaskan pada bagian pendahuluan, tahapanpembuatan rute terbagi ke dalam dua tahap : TourConstruction dan Tour Improvement.

Tour ConstructionPada tahap ini, dilakukan upaya untuk

menciptakan solusi awal dari permasalahan rutekendaraan. Dalam menciptakan solusi tersebut,metode yang digunakan berasal dari golonganconstruction method adalah Clarke and WrightSavings Algorithm.

Algoritma ini tergolong dalam constructionmethod, yaitu metode yang secara berangsur-angsur(bertahap) memasukkan setiap pelanggannya kedalam suatu rute. Metode ini, sesuai namanya, dipublikasikan oleh Clarke dan Wright denganberdasarkan pada prinsip penghematan (savings).Penghematan yang dimaksud adalah penghematanyang diperoleh apabila menggabungkan dua rutemenjadi satu. Dua rute yang memiliki penghematanterbesarlah yang pertama kali mendapat kesempatanuntuk dimasukkan ke dalam rute.

Gambar 2.1 Ilustrasi Konsep Savings

(sumber: Toth dan Vigo, 2002)

Keterangan:i, j = pelanggan i, pelanggan j0 = depot

Gambar 2.1 (a) menunjukkan bahwapelanggan i dan pelanggan j dilewati (dikunjungi)oleh rute yang berbeda. Pada Gambar 2.1 (b),pelanggan i dan pelanggan j berada pada rute yangsama. Dengan mengacu pada ilustrasi tersebut,maka bisa dicari penghematan yang bisa diperolehdari (a) menuju (b). Penghematan yang dimaksudberupa penghematan biaya atau jarak (tergantungdata yang diketahui).

Keterangan:Da = biaya atau jarak total dua rute (rutepelanggan I ditambah dengan rute pelanggan j)Db = biaya atau jarak total satu rute (rutepelanggan i dan j)coi = biaya atau jarak dari depot ke pelanggan icio = biaya atau jarak dari pelanggan i ke depotcoj = biaya atau jarak dari depot ke pelanggan jCjo = biaya atau jarak dari pelanggan j ke depotcij = biaya atau jarak dari pelanggan i ke pelangganjSij = penghematan biaya atau jarak antara pelanggani dan j

Tiap dua rute dicari terlebih dahulu nilaisavings-nya lalu dibuat savings list (suatu daftaryang berisi nilai savings dari yang terbesar hinggaterkecil). Pelanggan dengan nilai savings terbesarakan diprioritaskan untuk masuk terlebih dahuluke dalam rute.

Ada dua versi dalam proses memasukkanpelanggan ke dalam rute :

Sequential versionVersi ini membentuk rute demi rute secara

bertahap. Semua nilai savings yang terdapat padasavings list akan dibaca dan pelanggan-pelangganyang terkait dengan nilai tersebut dicoba untukdimasukkan ke dalam rute. Apabila feasible (sesuaidengan kendala yang ada), maka pelanggan-pelanggan tersebut akan masuk ke dalam rute.Apabila tidak memungkinkan lagi untukmemasukkan pelanggan pada rute tersebut, makarute tersebut dianggap selesai dibangun kemudianmulai membentuk rute yang baru dengan cara yangsama (mengulang pembacaan nilai savings lalumencoba memasukkan pelanggan-pelanggan yangbelum masuk ke dalam rute). Prioritas pembentukanrute kendaraan terkonsentrasi pada pembentukansatu rute terlebih dahulu berdasarkan nilai savingsterbesar.

Parallel versionPada versi ini, rute yang terbentuk bisa lebih

dari satu pada setiap kali pembacaan nilai savings.Prioritas pembentukan kendaraan sangat

i i

0

a i i

0

b


terkonsentrasi pada nilai savings terbesar. (Lysgaard,1997) menampilkan cara menghitung solusi versisequential dan parallel yang mudah dipahami.Keduanya menghasilkan solusi yang berbeda.

Tabel 2.1 Jarak dan Permintaan Pelanggan

Dari Tujuan Permintaan0 1 2 3 4 5

0 (Depot) - 28 31 20 25 34 01 - 21 29 26 20 372 - 38 20 32 353 - 30 27 304 - 25 255 - 32


Tabel 2.2 Nilai Savings Pelanggan

Saving Pelanggan42 1-538 1-236 2-434 4-533 2-527 1-427 3-519 1-315 3-413 2-3


Pada Tabel 2.1 terdapat informasi mengenaisebuah depot dan lima pelanggan dengan diketahuijumlah permintaan tiap pelanggan dan besarnyajarak antar titik. Berdasarkan rumus savings,diperoleh nilai savings dengan urutan dari yangterbesar hingga terkecil seperti yang terdapat padaTabel 2.2. Kendaraan yang tersedia diasumsikanberkapasitas 100 unit. Jika menggunakan sequentialversion, dihasilkan solusi jarak total 187.

Rute I : 0-1-5-4-0 (jarak = 98)Rute II : 0-2-3-0 (jarak = 89)

Jika menggunakan parallel version, solusi yangdihasilkan berjarak total 171:

Rute I : 0-1-5-3-0 (jarak = 95)Rute II : 0-2-4-0 (jarak = 76)

Gambar 2.2 Perbandingan Sequential dan ParallelVersion


Gambar 2.2 merupakan sebuah tabel yang diberikanToth dan Vigo yang menunjukkan bahwa

hasil perhitungan parallel version lebih baikdaripada sequential version.

Dalam pengolahan data selanjutnya, metodesavings yang akan digunakan adalah parallel versionkarena terbukti menghasilkan solusi yang lebihbaik dari sequential version.

Tour ImprovementPada tahap ini, solusi awal yang telah dibuat

pada tour construction mengalami perbaikan denganmenggunakan metode yang tergolong dalamimprovement method. Perbaikan terhadap solusitersebut dilakukan salah satunya denganmenukarkan letak node (titik) yang berada dalamsatu solusi (single route improvement). Letak atauurutan node berpindah-pindah sedemikian rupamenurut aturan tertentu. Selama perpindahan terjadi,apabila solusi yang lebih baik ditemukan, makasolusi yang terdahulu akan digantikan dengan solusiyang baru.

Exhaustive Search adalah teknik pencariansolusi secara Brute force pada masalah yangmelibatkan pencarian elemen dengan sifat khusus,biasanya di antara objek-objek kombinatorik sepertipermutasi, kombinasi, atau himpunan bagian darisebuah himpunan. Berdasarkan definisi ini, makaExhaustive Search adalah brute force juga (Munir,2004).Metode Exhaustive Search dapat dirumuskanlangkah-langkahnya sebagai berikut:1. Enumerasi (list) setiap solusi yang mungkin

dengan cara yang sistematis.2. Evaluasi setiap kemungkinan solusi satu per

satu, mungkin saja beberapa kemungkinan solusi


yang tidak layak dikeluarkan, dan simpan solusiterbaik yang ditemukan sampai sejauh ini (thebest solusi found so far).

3. Bila pencarian berakhir, umumkan solusi terbaik(the winner).

Algoritma Exhaustive Search memeriksasecara sistematis setiap kemungkinan solusi satuper satu dalam pencarian solusinya. Meskipunalgoritma Exhaustive Search secara teoritismenghasilkan solusi, namun waktu atau sumberdaya yang dibutuhkan dalam pencarian solusinyasangat besar. Di dalam beberapa literatur strategialgoritmik, contoh masalah yang seringdiasosiasikan dengan Exhaustive Search atau BruteForce adalah masalah Travelling SalespersonProblem (TSP). Untuk mengingat kembali masalahTravelling Salesperson Problem (TSP) ini, berikutdiulang kembali deskripsi masalahnya.TSP:diberikan buah kota serta diketahui jarak antarasetiap kota satu sama lain. Temukan perjalanan(tour) terpendek yang melalui setiap kota lainnyahanya sekali dan kembali lagi ke kota asalkeberangkatan. Jika setiap kota direpresentasi-kandengan simpul dan jalan yang menghubungkanantar kota sebagai sisi, maka persoalan TSP inidimodelkan dengan graf lengkap dengan n buahsimpul.

Bobot pada setiap sisi menyatakan jarak antarsetiap kota. Persoalan TSP tidak lain adalahmenemukan sirkuit Hamilton dengan bobotminimum.Algoritma Exhaustive Search untuk persoalan TSPini adalah:1. Enumerasikan (list) semua sirkuit Hamilton dari

graf lengkap dengan n buah simpul.2. Hitung (evaluasi) bobot setiap sirkuit Hamilton

yang ditemukan pada langkah 1 (satu).3. Pilih sirkuit Hamilton yang mempunyai bobot

terkecil.

Contoh: n = 4

Misalkan simpul a adalah kota tempat dimulainyaperjalanan (starting city).

Enumerasikan semua sirkuit Hamilton sebagaiberikut:

Tabel 2.3 Enumerasi Sirkuit Hamilton

Rute perjalanan (tour) Bobot

aÆbÆcÆdÆa 12+8+15+10 = 45

aÆbÆdÆcÆa 12+9+15+5 = 41

aÆcÆbÆdÆa 5+8+9+10 = 32

aÆcÆdÆbÆa 5+15+9+12 = 41

aÆdÆbÆcÆa 10+9+8+5 = 32

aÆdÆcÆbÆa 10+15+8+12 = 45

(sumber: Munir, 2004)

Untuk 4 kota, terdapat 6 buah kemungkinan ruteperjalanan (atau sirkuit Hamilton).Rute perjalananan terpendek adalah aÆcÆbÆdÆaatau aÆdÆbÆcÆa dengan bobot = 32. Karenaperjalanan berawal dan berakhir pada simpul yangsama, maka untuk n buah simpul semua ruteperjalanan yang mungkin dibangkitkan denganpermutasi dari n – 1 buah simpul. Permutasi darin – 1 buah simpul adalah (n – 1)!. Pada contoh diatas, untuk n = 6 akan terdapat (4 – 1)! = 3! = 6buah rute perjalanan.

Jika persoalan TSP diselesaikan denganmetode Exhaustive Search, maka kita harusmengenumerasi sebanyak (n–1)! buah sirkuitHamilton, menghitung setiap bobotnya, danmemilih sirkuit Hamilton dengan bobot terkecil.Kemudian ntuk menghitung bobot setiap sirkuitHamilton dibutuhkan waktu O(n), makakompleksitas waktu algoritma exhaustive searchuntuk persoalan TSP sebanding dengan (n–1)!dikali dengan waktu untuk menghitung bobot setiapsirkuit Hamilton. Dengan kata lain, kompleksitaswaktu algoritma exhaustive search untuk persoalanTSP adalah O (n ◊ n!).

Kita dapat menghemat jumlah komputasidengan mengamati bahwa setengah dari ruteperjalanan adalah hasil pencerminan dari setengahrute yang lain, yakni dengan mengubah arah ruteperjalanan : (1 dan 6), (2 dan 4), (3 dan 5), makadapat dihilangkan setengah dari jumlah permutasi(dari 6 menjadi 3).

Ketiga buah sirkuit Hamilton yang dihasilkanadalah seperti gambar di bawah ini:

Gambar 2.3 Sirkuit Hamilton

(sumber: Munir, 2004)


Dengan demikian, untuk graf dengan n buah simpul,kita hanya perlu mengevaluasi sirkuit Hamiltonsebanyak (n – 1)!/2. Jelaslah bahwa kebutuhanwaktu algoritma Exhaustive Search adalah dalamorde ekponensial. Algoritma ini hanya bagus untukukuran masukan (n) yang kecil sebab bebutuhanwaktunya masih realistis. Untuk ukuran masukanyang besar, algoritma Exhaustive Search menjadisangat tidak mangkus. Pada persoalan TSPmisalnya, untuk jumlah simpul n = 20 akan terdapat(19!)/2 = 6x1016sirkuit Hamilton yang harusdievaluasi satu per satu. Sayangnya, untukpersoalan Travelling Salesperson Problem (TSP)tidak ada algoritma lain yang lebih baik daripadaalgoritam exhaustive search. Algoritma yangmangkus selalu mempunyai kompleksitas waktudalam orde polynomial (Munir, 2004).Exhaustive Search sering disebut-sebut di dalambidang kriptografi, yaitu sebagai teknik yangdigunakan penyerang untuk menemukan kuncienkripsi dengan cara mencoba semua kemungkinankunci. Serangan semacam ini dikenal dengan namaExhaustive Search Attack atau Brute Force Attack.Misalnya pada algoritma kriptografi DES (DataEncryption Standard), panjang kunci enkripsiadalah 64 bit (atau setara dengan 8 karakter). Dari64 bit tersebut, hanya 56 bit yang digunakan (8 bitparitas lainnya tidak dipakai). Karena ada 56 posisipengisian bit yang masing-masing memiliki duakemungkinan nilai, 0 atau 1, maka jumlahkombinasi kunci yang harus dievaluasi oleh pihaklawan adalah sebanyak: (2)(2)(2)(2)(2)…(2)(2)(sebanyak 56 kali) = 256 = 7.205.759.403.7927.936buah.

Meskipun algoritma Exhaustive Search tidakmangkus (masih belum efisien), namun nilaiplusnya terletak pada keberhasilannya yang selalumenemukan solusi jika diberikan waktu yang cukup(Munir, 2004).

METODE PENELITIANPenelitian ini bertujuan untuk mencari metode

terbaik untuk sistem transportasi PT. StarmassLogistics. Dimana melaluinya akan dihasilkan rutekendaraan yang memiliki jarak tempuh terpendek.Metode yang digunakan adalah metode heuristicsklasik, dimana metode ini memang digunakanuntuk membangun solusi/rute awal (TourConstruction) dari permasalahan yang ada,kemudian menggabungkannya dengan MetodeExhaustive Search untuk membuat perbaikan ruteawal (Tour Improvement).

Data berasal dari PT. Starmass Logistics yangmerupakan data permintaan/pengiriman harian,karena data tersebut cukup untuk mewakili kondisipermintaan pelanggan yang bersifat harian. Datasekunder yang didapat dari perusahaan disusunterlebih dahulu sebelum diolah pada MicrosoftOffice Excel. Pelanggan-pelanggan yang alamatnyatidak terdapat dalam data sekunder dieliminasi(tidak diikutsertakan dalam pengolahan data)kemudian lokasi pelanggan-pelanggan tersebutdiperkirakan pada peta dan dibuat matriks jaraknyadengan menggunakan Google Maps. Memasukkanmatriks jarak dari masing-masing lokasipengiriman/permintaan (demand), serta volumeuntuk mengoptimalkan kapasitas angkut kendaraanyang digunakan kedalam Microsoft Office Excel,kemudian mengolahnya berdasarkan algoritma darimasing-masing metode. Setelah didapatkan hasilmaka dilakukan perbandingan terhadap hasil darimasing-masing metode tersebut.

PEMBAHASANBerdasarkan catatan data pengiriman

(Delivery Order) pada tanggal 9 September 2013,terdapat 36 Delivery Order yang harus diantarkanoleh ke empat kendaraan perusahaan pada haritersebut. Dengan jumlah 36 lokasi lokasi yangharus dikunjungi dengan total volume permintaansebesar 13,71 m3 dan tonase seberat 1713.47 kg.Data pengiriman (Delivery Order) dapat dilihatpada tabel berikut :

Tabel 4.1. Permintaan Pelanggan

(Sumber : PT. Starmass Logistics)


Dari data tersebut, perlu diketahui terlebih dahululetak suatu titik dalam Google Maps dan jaraknyadengan titik-titik yang lain sehingga keseluruhanjarak antar titik diperoleh dan dapat disusun dalamsatu matriks yang disebut sebagai matriks jarak.Matriks jarak tersebut dapat dilihat pada tabelberikut :

Tabel 4.2. Matriks Jarak

Tabel 4.2. Matriks Jarak (Lanjutan)

Tabel 4.2. Matriks Jarak (Lanjutan)

Matriks jarak masing-masing lokasi tersebutdiketahui dengan melakukan pencarianmenggunakan Google Maps. Kemudian pada tahapselanjutnya, dilakukan upaya untuk menciptakansolusi awal dari permasalahan rute kendaraan.Dalam menciptakan solusi tersebut, metode yangdigunakan berasal dari golongan Constructionmethod adalah Clarke and Wright SavingsAlgorithm.4.1 Menghitung Nilai SavingsContoh perhitungan Nilai Savings :

Tiap dua rute dicari terlebih dahulu nilaisavings-nya lalu dibuat savings list (suatu daftaryang berisi nilai savings dari yang terbesar hinggaterkecil). Pelanggan dengan nilai savings terbesarakan diprioritaskan untuk masuk terlebih dahuluke dalam rute.


Tabel 4.3. Sampel Savings List

4.2 Pembuatan rute awal (Sequential) dan (ParallelInsertion)

Pada pembuatan Sequential, semua nilaisavings yang terdapat pada savings list akan dibacadan pelanggan-pelanggan yang terkait dengan nilaitersebut dicoba untuk dimasukkan ke dalam rute.Apabila feasible (sesuai dengan kendala yang ada),maka pelanggan-pelanggan tersebut akan masukke dalam rute. Apabila tidak memungkinkan lagiuntuk memasukkan pelanggan pada rute tersebut,maka rute tersebut dianggap selesai dibangunkemudian mulai membentuk rute yang baru dengancara yang sama (mengulang pembacaan nilaisavings lalu mencoba memasukkan pelanggan-pelanggan yang belum masuk ke dalam rute).Prioritas pembentukan rute kendaraan terkonsentrasipada pembentukan satu rute terlebih dahuluberdasarkan nilai savings terbesar.Contoh pembuatan rute Sequential pada Truk 1:Rute : 0 21 14 20 29 10 0Pembuatan rute berhenti pada node 10, karenakapasitas kendaraan sudah tidak memungkinkan

lagi untuk ditambahkan node (titik) berikutnya.Sedangkan pada Parallel Insertion, prioritaspembentukan rute kendaraan dibentuk secaraberurutan dan sangat terkonsentrasi pada nilaisavings terbesar, dan dengan jarak tempuh yangpaling terdekat dengan node (titik) sebelumnya.Contoh dari beberapa tahap pembuatan rute ParallelInsertion:Keterangan :1. T1 = Truk 1, T2 = Truk 2, T3 = Truk 3, T4 =Truk 4.2. Pada tahap ke 2 terdapat pertukaran node padaT2 (truk 2) karena dari node 22 ke 20 menghasilkansirkuit (rute) yang lebih baik dibandingkan jikadimulai dari node 20 ke 22.3. Pada tahap ke 4 juga terdapat pertukaran nodepada T4 (truk 4) karena dari node 32 ke 9menghasilkan sirkuit (rute) yang lebih baikdibandingkan jika dimulai dari node 9 ke 32

Tabel 4.4. Perbandingan Sequential dan ParallelInsertion’

Tabel 4.4. Menunjukan perbandingan antaraSequential dan Parallel Insertion, dan hasilnyadapat terlihat perbandingan rute yang lebih baik.Maka dipilihlah Parallel Insertion sebagai ruteawal, selanjutnya dilakukan kembali perbaikan ruteawal (Tour Construction) dengan melakukanExhaustive Search dan Enumerasi untukmenghasilkan perbaikan rute (Tour Improvement)yang terbaik.4.3 Perbaikan rute Parallel Insertion (TourConstruction) dengan Exhaustive Search danEnumerasi (Tour Improvement)

Pada tahap ini, solusi awal yang telah dibuat


pada tour construction mengalami perbaikan denganmenggunakan metode yang tergolong dalamimprovement method. Perbaikan terhadap solusitersebut dilakukan salah satunya denganmenukarkan letak node (titik) yang berada dalamsatu solusi (single route improvement). Letak atauurutan node berpindah-pindah sedemikian rupamenurut aturan tertentu. Selama perpindahan terjadi,apabila solusi yang lebih baik ditemukan, makasolusi yang terdahulu akan digantikan dengan solusiyang baru. Pencarian rute terbaik dilakukan denganbantuan Exhaustive search pada Ms. Excel.

Tabel 4.6. Sampel dari proses Exhaustive Searchdan Enumerasi (Perbaikan rute Parallel Insertion)

Tabel 4.6. merupakan sampel dari proses ExhaustiveSearch dan Enumerasi (Tour Improvement) dalammelakukan perbaikan rute Parallel Insertion (TourConstruction)

4.4 Hasil dari proses Exhaustive Search danEnumerasi

Berikut ini adalah hasil dari perbaikan ruteParallel Insertion (Tour Construction) yang akandigantikan dengan solusi yang baru dan lebih baikdar i sebelumnya (Tour Improvement ) .

Tabel 4.7. Hasil Exhaustive Search dan Enumerasi

4.5 Perbandingan rute Parallel Insertion(Tour Improvement) dengan (TourConstruction)

Pada Tabel 4.7 terlihat perbaikan

(Improvement) dan perpindahan rute dari masing-masing kendaraan, dengan kapasitas volume yangtetap sama, hanya titik lokasinya yang berubahnamun menghasilkan jarak yang terbaik. Pada Tabel4.8 sampai dengan Tabel 4.11 berikut ini adalahhasil dan perbandingan rute sebelumnya (parallel)dengan rute yang sudah diperbaiki denganExhaustive Search dan Enumerasi.

Tabel 4.8. Perbandingan hasil dari TourConstruction dan Tour Improvement 1st Truck

Tabel 4.9. Perbandingan hasil dari TourConstruction dan Tour Improvement 2nd Truck

Tabel 4.10. Perbandingan hasil dari TourConstruction dan Tour Improvement 3rd Truck

Tabel 4.11. Perbandingan hasil dari TourConstruction dan Tour Improvement 4th Truck


ANALISA PERMASALAHANAnalisa Hasil

Jarak yang dihasilkan dari metode sequential(savings), parallel insertion, dan exhaustive searchselalu menghasilkan solusi dengan jarak tempuhterpendek.Sekalipun waktu perhitungan metodetersebut tidak selalu unggul pada kelompoknyamasing-masing, karena banyak membutuhkan sum-ber daya khususnya waktu dalam perhitungannya.

Analisa Matriks jarakSaat pembuatan matriks jarak, dipilih lintasan

yang memiliki jarak tempuh terpendek untukmenghubungkan tiap titik. Sesudah rute didapatkan,diketahui bahwa jarak solusi rute yang diolah secaramatematis dengan jarak solusi rute. Namunkemungkinan google maps masih belum cukupakurat untuk menghitung jarak antar titik. Tetapijarak yang berbeda dalam google maps adalahwajar terjadi mengingat bahwa google maps sendirimemberikan beberapa alternatif jalan untukmenghubungkan dua titik. Maka dalam pencarianjarak, rute terpendek yang diusulkan oleh googlemaps yang dipilih pada awal pembuatan matriksjarak.

Analisa Cost SavingAlgoritma savings Clark and Wright mampu

menghasilkan solusi yang baik bagi permasalahanrute kendaraan. Dengan berdasarkan pada prinsippenghematan, maka penyusunan rute kendaraanakan lebih efisien. Hal ini dikarenakan prioritaspemasukan titik tujuan untuk membentuk suaturute menjadi sangat jelas, yaitu mendahulukan titik-titik tujuan yang memberikan penghematan(savings) terbesar. Dengan prinsip ini, penyusunanrute kendaraan menjadi lebih terarah dan teratur.Pelanggan dengan nilai savings terbesar akandiprioritaskan untuk masuk terlebih dahulu kedalam rute.

Analisa Tour ConstructionDalam Tour Construction, ada dua versi dalamproses memasukkan pelanggan ke dalam rute. Versipertama adalah Sequential version. Versi inimembentuk rute demi rute secara bertahap. Semuanilai savings yang terdapat pada savings list akandibaca dan pelanggan-pelanggan yang terkaitdengan nilai tersebut dicoba untuk dimasukkan kedalam rute. Apabila feasible (sesuai dengan kendalayang ada), maka pelanggan-pelanggan tersebut

akan masuk ke dalam rute.Apabila tidak memungkinkan lagi untuk

memasukkan pelanggan pada rute tersebut, makarute tersebut dianggap selesai dibangun kemudianmulai membentuk rute yang baru dengan cara yangsama (mengulang pembacaan nilai savings lalumencoba memasukkan pelanggan-pelanggan yangbelum masuk ke dalam rute). Prioritas pembentukanrute kendaraan terkonsentrasi pada pembentukansatu rute terlebih dahulu berdasarkan nilai savingsterbesar. Dari proses Tour Constructionmenggunakan Sequential Version dihasilkan totaljarak tempuh sebesar 454.7 km.Versi kedua yaitu Parallel Insertion. Pada versi ini,rute baru yang terbentuk bisa lebih dari satu padasetiap kali pembacaan nilai savings. Prioritaspembentukan kendaraan sangat terkonsentrasi padanilai savings terbesar. Cara menghitung solusi versisequential dan Parallel Insertion mudah dipahami,dan keduanya menghasilkan solusi yangmenunjukan perbandingan antara Sequential danParallel Insertion, dan hasilnya dapat terlihatperbandingan rute dan kapasitas volume yang lebihbaik. Sedangkan dari proses Tour Constructionmenggunakan Parallel Insertion dihasilkan totaljarak tempuh sebesar 453.8 km.

Analisa Tour ImprovementBerdasarkan hasil yang terlihat pada Tabel

4.5, maka dipilihlah Parallel Insertion sebagai ruteawal, untuk selanjutnya akan dilakukan kembaliperbaikan rute awal (Tour Construction) denganmelakukan Exhaustive Search dan Enumerasi untukmenghasilkan rute baru atau perbaikan rute (TourImprovement) yang terbaik.

Pada tahap ini, solusi awal yang telah dibuatpada tour construction akan mengalami perbaikandengan menggunakan metode yang tergolong dalamimprovement method. Perbaikan terhadap solusitersebut dilakukan salah satunya denganmenukarkan letak node (titik) yang berada dalamsatu solusi (single route improvement). Letak atauurutan node berpindah-pindah sedemikian rupamenurut aturan tertentu. Selama perpindahan terjadi,apabila solusi yang lebih baik ditemukan, makasolusi yang terdahulu akan digantikan dengan solusiyang baru sampai ditemukan hasil yang terbaik.Dan dari proses Tour Improvement menggunakanExhaustive Search dihasilkan total jarak tempuhsebesar 360 km.


Gambar 5.1. Hasil Tour Improvement Truk 1 padaGoogle Maps




KESIMPULANDari hasil penelitian penentuan metode

heuristics klasik terbaik pada permasalahan rutekendaraan (studi kasus: PT. Starmass Logistics),

diketahui bahwa metode savings dikombinasikandengan metode perbaikan Parallel Insertion,Exhaustive Search dan Enumerasi mampumenghasilkan solusi (rute kendaraan) dalammembuat Tour Improvement dan Tour Constructiondengan jarak tempuh yang lebih baik.

Tabel 6.1. Perbandingan Hasil/Total Jarak TempuhTiap Metode.

Metode Total JarakTempuh (km)

Sequantial Version 545,7

Parallel Insertion (Tour Construction) 553,8

Exhausive Search (Tour Improvement) 360

Dengan demikian metode-metode ini mampumenghasilkan solusi yang semakin baik untukpermasalahan rute kendaraan PT. StarmassLogistics.

DAFTAR PUSTAKABallou, R. H. (2004). Business Logistics/ Supply

Chain Management. New Jersey: PrenticeHall.

Fauzy, Akhmad. (2008). “Statistik Industri”.Erlangga : Jakarta

Helsgaun, K. (2006). An Effective Implementationof K-opt Moves for the Lin Kernighan TSPHeuristic. Roskilde: Computer Science,Roskilde University. Didapat dari :http://akira.ruc.dk/~keld/research/LKH/KoptReport.pdf

Lysgaard, J. (1997). Clarke & Wright's SavingsAlgorithm. Department of ManagementScience and Logistics, The Aarhus Schoolof Business.

Munir, Rinaldi. (2004). Strategi Algoritmik danAlgoritma Exhautive Search. Bandung :Institut Teknologi Bandung (ITB)

Toth dan Vigo (2002). The Vehicle Routing Problem.Philadelphia, SIAM Monographs on DiscreteMathematics and Application.


perencanaan rute pengiriman menggunakan metode parallel

Documents