ISSN : e-proceeding of Engineering : Vol.4, No.2 Agustus 2017 Page 2892

ISSN : 2355-9365

e-Proceeding of Engineering : Vol.4, No.2 Agustus 2017 | Page 2892

PENENTUAN RUTE ARMADA MENGGUNAKAN ALOGARITMA TABU SEARCH PADA HOMOGENUS FLEET VEHICLE ROUTING PROBLEM WITH TIME WINDOWS DI PT. XYZ WILAYAH BANDUNG UNTUK MEMINIMASI TOTAL WAKTU TEMPUH DETERMINATION OF FLEET ROUTE USING TABU SEARCH ALGORITHM ON HOMOGENEOUS FLEET VEHICLE ROUTING PROBLEM WITH TIME WINDOWS IN XYZ COMPANY BANDUNG AREA TO MINIMIZE TOTAL TRAVEL TIME R. Fauzi Novianda1, Sri Martini2, Rio Aurachman3 1,2,3

Prodi S1 Teknik Industri, Fakultas Teknik, Universitas Telkom [email protected], [email protected], 3 [email protected]

1

Abstrak PT. XYZ merupakan distributor dari suatu perusahaan besar yang bergerak di sub sektor industri makanan dan minuman. Berdasarkan data PT. XYZ selama bulan Juli-Desember 2016, terjadi permasalahan dimana tidak semua demand dapat terpenuhi tepat pada waktunya. Target pemnuhan dari pihak perushaan sebesar 7%, tetapi hanya pada bulan Juli saja yang melebihi target. Permasalahan ini disebabkan oleh beberapa penyebab dimana yang paling berpengaruh merupakan keterlambatan armada tiba pada customer. Penyebab ini terjadi karena waktu tempuh yang lama karena penentuan rute yang tidak tepat. Permasalahan ini merupakan permasalahan umum yang sering terjadi pada bidang transportasi dimana armada yang digunakan lebih dari 1, maka permasalahan ini perlu diselesaikan dengan pendekatan Vechicle Routing Problem (VRP). Karakteristik VRP pada peneilitian ini adalah time windows. Untuk penyelesaian yang digunakan dengan pendekatan metaheuristik yaitu Alogaritma Tabu Search. Penulis menggunakan Alogaritma Nearest Neighbour sebagai pembangkit solusi awal yang selanjutnya digunakan pada Alogaritma Tabu Search. Pendekatan VRP dengan pendekatan Alogaritma Tabu Search dapat mengurangi total waktu tempuh sebesar 12.3% dari kondisi awal serta seluruh demand terpenuhi tanpa mengalami keterlambatan. Kata kunci : Transportasi, Distribution Center, VRP, Time Windows, Alogaritma Nearest Neighbour, Alogaritma Tabu Search Abstract PT. XYZ is a distributor of a corporation that engaged in the food and beverage industry sub sector. Based on data of PT. XYZ during July-December 2016, there is a problem where not all demand can be fulfilled in time. The target is 7%, but only in July exceeds the target. This problem is caused by several causes where the most influential is the delay of the fleet arrives at the customer. This cause occurs due to long travel time due to inaccurate route determination. This problem is a common problem that often occurs in the field of transportation where the fleet is used more than 1, then this problem needs to be solved by approach Vechicle Routing Problem (VRP). Characteristics of VRP in this research is time windows. For the solution used with metaheuristic approach that is Alogaritma Tabu Search. This study uses Nearest Neighbors Alogaritma as the initial solution generator which is then used on Tabu Search Alogaritma. VRP approach with Tabu Search Algorithm approach can reduce total travel time by 12.3% from initial condition and all demand can be fulfilled without experiencing delay. Keywords: Transportation, Distribution Center, VRP, Time Windows, Nearest Neighbour Alogarithm, Tabu Search Alogarithm

ISSN : 2355-9365


1. Pendahuluan Transportasi merupakan serangkaian kegiatan memindahkan atau mengangkut barang dari produsen sampai kepada konsumen dengan menggunakan salah satu atau lebih moda transportasi, yang dapat meliputi moda transportasi barat, laut/sungai, maupun udara [2]. Dalam pelaksasnaannya, transportasi dilaksanakan pada suatu rute yang bisa disebut suatu jaringan rute. Dalam pengiriman sendiri, transportasi biasanya diperhitungkan dengan banyaknya jumlah armada yang dibutuhkan dalam melakukan suatu pengiriman. Pemilihan rute yang tepat serta penentuan jumlah armada jika dilaksanakan sesuai kebutuhan dan target, maka dapat dilaksanakan dengan baik dimana pengiriman bisa dilaksanakan dengan cepat dan tepat. PT. XYZ merupakan distributor dari suatu perusahaan besar yang bergerak di sub sektor industri makanan dan minuman. PT. XYZ memiliki Distribution Center (DC) yang berada di wilayah Jawa Barat, yaitu Bandung tepatnya di Kompleks Industri Sukamulya, Gedebage, Bandung. Dalam melakukan operasional pengiriman barang, PT. XYZ memiliki 6 unit armada Truk Colt Diesel Engkle (CDE). Penentuan rute pengiriman yang dilakukan oleh PT. XYZ adalah dengan membagi rute pengiriman menjadi tiga rute yaitu rute atas (Bandung bagian Utara), rute tengah (Bandung bagian Tengah) serta rute bawah (Bandung bagian Selatan). Mekanisme pengiriman barang pada PT. XYZ yaitu: Daftar customer yang akan dikirim

Bagi customer sesuai lokasi

Delivery Order (DO) dicetak

Armada Mengirim Sesuai DO

Setelah semua customer terkirim armada kembali

Gambar 1 Mekanisme Pengiriman PT. XYZ Sedangkan untuk cakupan area distribusi PT. XYZ adalah sekitar wilayah Bandung (Kota Bandung, Kota Cimahi, Kab. Bandung, Kab. Bandung Barat) dengan jenis tujuan custmer yang beragam dimulai dari pasar swalayan, pasar tradisional, hotel, hingga rumah makan. Berikut merupakan area cakupan distribusi PT. XYZ:

Gambar 2 Area Cakupan Distribusi PT. XYZ Dengan banyaknya customer yang dimiliki PT. XYZ, banyak kendala yang sering muncul. Salah satu kendala yang sering muncul adalah tidak terpenuhinya demand pelanggan tepat pada waktunya. Kondisi ini terjadi saat barang yang diantar tidak diterima oleh customer yang bisa disebabkan beberapa faktor yang mempengaruhinya seperti waktu kedatangan terlambat, ataupun barang yang dikirim tidak sesuai permintaan. Berikut merupakan laporan pengiriman PT. XYZ selama 6 bulan:

ISSN : 2355-9365


Laporan Pengiriman PT. XYZ 1600 1400 1200 1000 800 600 400 200 0

Juli

Agustus

September

Oktober

November

Desember

Demand

963

1285

1227

1231

1298

1377

Terpenuhi

924

1140

1087

1085

1163

1235

Gambar 3 Laporan Pengiriman PT. XYZ Berdasarkan Gambar 3 dapat dilihat bahwa tidak semua demand dapat terpenuhi tepat pada waktunya selama 6 bulan terakhir. PT. XYZ sendiri memiliki target pemenuhan demand sebesar 7% dari total demand. Namun sesuai data yang telah saya sebutkan diatas hanya Bulan Juli saja yang memenuhi target perusahaan. Sedangkan untuk bulan-bulan lainnya target tidak terpenuhi. Dengan kondisi seperti ini butuh penyelesaian masalah agar pemenuhan demand melebihi target yang ditentukan perusahaan. Setelah melakukan pengamatan lebih lanjut, permasalahan ini dipengaruhi oleh beberapa faktor seperti pada gambar berikut:

Penyebab Demand Tidak Terpenuhi 1%

Keterlambatan Tiba Pada Pelanggan Keterlambatan Pergi

19% 11% 3%

Barang Terkirim Defect 66%

Dokumen Tidak Sesuai Kecelakan

Gambar 4 Penyebab Keterlambatan Sesuai dengan Gambar I.4 Keterlambatan tiba pada pelanggan merupakan penyebab yang paling berpengaruh terhadap demand yang tidak terpenuhi sebesar 66% atau sebanyak 493 kali kejadian. Penyebab ini terjadi karena lamanya waktu tempuh aramada, sehingga armada datang berada diluar time windows yang disediakan customer. Lamanya waktu tempuh dipengaruhi oleh penentuan rute yang tidak tepat sehingga jalur yang dipilih lebih jauh. Berdasarkan latar belakang tersebut, permasalahan yang terjadi pada PT.XYZ adalah permasalahan transportasi yang umunya dapat diselesaikan dengan pendekatan Vehicle Routing Problem (VRP) sesuai dengan karakteristik utamanya yaitu terdapat lebih dari 1 kendaraan dalam pengiriman. Untuk jenis VRP yang digunakan adalah VRP with time windows sesuai dengan karakteristik customer yang memiliki time windows atau waktu buka tutup pelayanan. Maka penentuan rute menggunakan pendekatan Vehicle Routing Problem (VRP) dengan karakteristik yang telah disebutkan sebelumnya dibutuhkan agar waktu tempuh armada bisa di minimasi dan keterlambatan bisa terpenuhi.. 2. Dasar Teori dan Metodologi 2.1 VRP (Vehicle Routing Problem) Vehicle routing problem berperan dalam merancang rute yang optimal yang digunakan oleh sejumlah kendaraan yang ditempatkan pada depot untuk melayani sejumlah pelanggan dengan permintaan yang diketahui [3]. Vehicle Routing Problem (VRP) diperkenalkan pertama kali oleh Dantziq dan Ramser pada tahun 1959 dan semenjak itu telah dipelajari secara luas. Oleh Fisher, VRP didefinisikan sebagai sebuah pencarian atas cara penggunaan yang efisien dari sejumlah kendaraan yang harus melakukan perjalanan untuk mengunjungi sejumlah tempat untuk mengantar dan/atau menjemput orang/barang [3].

ISSN : 2355-9365


Varian-varian VRP banyak bermunculan setelah dikembangkan dari permasalahan dasar yang telah didefinisikan oleh Toth dan Vigo (2002). Varian-varian tersebut bermunculan untuk menyesuaikan ruang lingkup masalah yang berkembang, dimana model yang telah ada perlu variabel baru atau pembatas baru jika dilakukan pengembangan varian VRP. Terdapat beberapa varian VRP yang telah dikembangkan [3]: 1. VRP with Time Window Pelayanan harus diatur sedemikian hingga barang/produk sampai kepada pelanggan tepat pada rentang waktu (time windows) yang sudah ditetapkan pada masing-masing pelanggan. Depot juga memiliki time window yang disebut dengan horison perencanaan. Jika depot atau pelanggan memiliki time windows lebih dari satu, maka disebut dengan multiple time windows. 2. VRP with Split delivery Permasalahan VRP dimana pengiriman barang/produk ke suatu pelanggan dapat dilakukan oleh dua atau lebih kendaraan. Pada VRP standar satu pelanggan hanya dikunjungi oleh satu kendaraan. 3. VRP Pick Up and Delivery Permasalahan VRP dimana kendaraan dapat melakukan tugas pengantaran (delivery) dan mengangkut (pick-up) sekaligus dalam satu kali proses pengiriman. Jenis VRP ini disebut juga VRP with linehauls atau backhauls. 4. VRP with Multiple Depot Permasalahan VRP dimana terdapat lebih dari satu depot sehingga suatu kendaraan yang berangkat dari depot tertentu dan dapat berakhir di depot yang lain. Barang / produk yang dikirimkan ke customer bisa berasal dari depot manapun selama sesuai dengan permintaan customer. 5. VRP with Multiple Product and Compartments Permasalahan VRP dimana barang/produk yang dikirimkan ke customer terdiri dari beberapa macam barang/produk. Pada umumnya jenis VRP ini melibatkan kendaraan dengan multi compartments. 6. VRP with Multiple Trip Permasalahan VRP dimana kendaraan dapat menempuh beberapa rute dengan kembali ke depot terlebih dahulu. 7. VRP with Heterogeneus Fleet of Vehicles Permasalahan VRP dimana perusahaan memiliki beberapa macam kendaraan dengan kapasitas yang berbeda-beda. 2.2 Alogaritma Penentuan Rute Dalam melakukan pemilihan rute terdapat 3 jenis metode yaitu eksak, heuristik, serta metaheuristik. Berikut merupakan penjelasan ketiga alogaritma tersebut [4]. 1. Alogaritma Eksak / Analitik Metode eksak merupakan algoritma yang dapat menghasilkan solusi secara langsung, dengan mencoba semua permutasi serta melihat yang termurah. Pendekatan yang dilakukan terletak pada faktor polinom dari O (n!), faktorial dari beberapa kota, sehingga solusi menjadi tidak praktis dan hanya dapat untuk 20 kota. Alogartima yang termasuk dalam metode eksak adalah alogaritma branch and bound, dan alogaritma cutting plane. 2. Alogaritma Heuristik Metode heuristik merupakan metode modern dalam menemukan solusi untuk masalah yang sangat besar (jutaan kota) dalam waktu wajar dengan probabilitas tinggi hanya 2-3% dari solusi optimal. Beberapa algoritma yang tergolong dalam metode heuristik yaitu algoritma nearest neighbor, nearest insertion, dan masih banyak lagi 3. Alogaritma Metaheuristik Metode metaheuristik jauh lebih efektif dibandingkan dengan metode heuristik. Waktu proses yang dibutuhkan memang lebih lama dan tidak diketahui secara pasti. Namun metaheuristik lebih mampu untuk menampung atau melibatkan lebih banyak parameter dalam pengolahannya. Perbandingan Algoritma Heuristik dan Eksak 2.3 Tabu Serach Tabu search pertama kali diperkenalkan oleh Glover pada tahun 1898. Tabu search merupakan kata serapan dari kata “Taboo” yang memiliki arti terlarang atau keramat dan berasal dari bahasa Tongan, yaitu

ISSN : 2355-9365


salah satu bahasa yang ada di Polynesia. Berdasarkan kamus Websitester, Tabu adalah sebuah larangan yang dipaksakan oleh kebudayaan sosial sebagai tindakan pencegahan atau sesuati yang dilarang karena berbahaya. Bahaya yang mungkin terjadi pada Tabu search adalah penjadwalan yang tidak layak, dan terjebak tanpa ada jalan keluar [1]. Konsep dasar dari Tabu search adalah alogaritma yang memastikan bahwa setiap tahunnya menghasilkan fungsi tujuan yang paling optimum tanpa terjebak kedalam solusi awal yang ditebukan sealma iterasi berlangsung. Salah satu tujuan utama dari penggunaan tabu search adalah untuk mencegah terjadinya pengulangan solusi dan ditemukannya solusi yang sama dalam suatu iterasi yang akan diulang pada iterai selanjutnya [1].. 3. Pembahasan 3.1 Influenced Diagram Penelitian ini bertujuan meminimasi waktu tempuh sehingga keterlambatan bisa terselesaikan. Dalam menyusun waktu tempuh terdapat 2 komponen utama yaitu kecepatan rata-rata serta jarak tempuh armada. Berikut merupakan influence diagram: Rute Distribusi

Volume Produk Time Windows Lokasi Customer

Jumlah Armada Digunakan

Jenis Armada

Jarak Antar Pelanggan Jarak Tempuh

Demand Pelanggan

Kapasitas Angkut Jarak DC ke Pelanggan

Kecepatan Rata-rata Armada

Waktu Tempuh

Gambar 5 Influence Diagram Berdasarkan Gambar 5, dapat dilihat keterkaitan antar komponen. Rute distribusi merupakan input terkontrol yang akan mempengaruhi kecepatan rata-rata yang dibutuhkan serta lokasi customer yang dituju. Kecepatan rata-rata armada selain dipengaruhi rute distribusi, dipengaruhi juga jumlah aramada yang digunakan. Lokasi Customer, dipengaruhi oleh time windows pada customer serta jenis armada yang digunakan. Lokasi Customer akan berpengaruh kepada Jarak Tempuh. Komponen Kecepatan Rata-Rata serta komponen Jarak Tempuh akan berpengaruh pada output penelitian ini yaitu Waktu Tempuh Armada 3.2 Model Matematis Permasalahan yang terdapat pada kondisi existing selanjutnya dirumuskan kedalam model matematis dengan fungsi tujuan minimasi waktu tempuh. Adapun model matematisnya adalah sebagai berikut: Indeks: i = indeks notasi, i = 1, 2, 3, 4, ................ M adalah customer / distribution centre yang memulai kegiatan distribusi. j = indeks notasi, j = 1, 2, 3, 4, ................ M+1 adalah customer / distribution centre yang memulai kegiatan distribusi. k = indeks notasi, k = 1,2,3,4, .......... K adalah jenis kendaraan yang digunakan. Parameter: x𝑖𝑗 = Jarak dari titik i ke j 𝑓𝑘 = Biaya tetap setiap jenis kendaraan 𝑐𝑖𝑗𝑘 = Biaya jalan dari customer i ke j Sik = Waktu pelayanan di titik i menggunakan kendaraan k tijk = Waktu tempuh kendaraan dari titik i ke j menggunaan kendaraan k oti = Batas awal time window di titik i cti = Batas akhir time window di titik i

ISSN : 2355-9365


q = demand dari konsumen Qk = Kapasitas angkut kendaraan S = Bilangan riil yang bernilai sangat besar. a = Kedatangan kendaraan di customer pi = Keberangkatan kendaraan dari customer i. Bp = Volume produk p Hpj = Kuantitas produk p yang akan dikirim ke pelanggan Mj = Total volume yang diminta pelanggan j T = Waktu Horison Satu Hari Vk = Kecepatan Rata Rata Kendaraan Variabel Keputusan: 𝑥𝑖𝑗𝑘 = Variabel keputusan rute terpilih, 1 jika dari i ke j menggunakan kendaraan k, 0 jika lainnya 𝑦𝑘 = Variabel keputusan setiap penggunaan jenis kendaraan, 1 jika kendaraan k digunakan, 0 jika lainnya Fungsi Tujuan: 𝐾

𝑀

𝑀

𝑚𝑖𝑛 ∑ ∑ ∑ 𝑘=1 𝑗=1 𝑖=1

𝑥𝑖𝑗𝑘 𝑣𝑘

∀ 𝑖 = 1, 2, … 𝑀, ∀ 𝑗 = 1, 2, … 𝑀 + 1, ∀ 𝑘 = 1, 2 … 𝐾 Fungsi tujuan diatas menjelaskan tujuan dari penelitian ini yaitu meminimumkan waktu tempuh yang dibutuhkan pada aktivitas pengiriman barang ke lokasi konsumen sehingga tidak terjadi keterlambatan yang melewati batas time windows konsumen dimana 𝑥𝑖𝑗𝑘 merupakan rute dari i ke j dengan menggunakan kendaraan k dan 𝑣𝑘 merukan kecepatan rata-rata kendaraan k. Dengan kendala-kendala: 𝐾

𝑀

∑ ∑ 𝑥𝑖𝑗𝑘 = 1, ∀ 𝑗 = 2, 3, 4 … 𝑀 + 1 ………………….. (1) 𝑘=1 𝑖=1

Kendala (1) memastikan bahwa satu customer hanya terdapat pada satu rute yang terpilih, dinotasikan dengan i = 1, 2, 3……M. Dimana 1 merupakan depot dan Merupakan himpunan tujuan atau customer. 𝑀 𝑘 ∑ 𝑥𝑜𝑖 = 1, ∀ 𝑘 = 1, 2 … 𝐾 ……………………...… (2) 𝑖=1

Kendala (2) memastikan bahwa setiap kendaraan berangkat dari depot. Dimana 1 merupakan depot dan merupakan himpunan tujuan atau customer. 𝑀 𝑘 ∑ 𝑥𝑖ℎ 𝑖=1

𝑀 𝑘 − ∑ 𝑥ℎ𝑗 = 0, ∀ 𝑘 = 1, 2 … 𝐾, ∀ ℎ = 1, 2 … 𝑀..……… (3) 𝑗=1

Kendala (3) memastikan selesai melayani seorang customer kendaraan akan meninggalkan customer tersebut untuk customer lainnya. 𝑀

∑ 𝑥𝑗𝑘𝑀+1 = 1, ∀ 𝑘 = 1, 2 … 𝐾 ……………………….. (4) 𝑗=1

Kendala (4) memastikan bahwa setiap rute kembali ke depot. Dimana pada akhir rute depot dinotasikan sebagai M+1. 𝑀

𝑀

∑ ∑ 𝑞𝑗 𝑥𝑖𝑗𝑘 ≤ 𝑄𝑘 , ∀ 𝑘 = 1, 2, 3 … 𝐾 ………….….…… (5) 𝑖=1 𝑗=1

Kendala (5) memastikan bahwa permintaan dari customer tidak melebihi kapasitas armada angkut yang digunakan. 𝑝

∑ 𝐵𝑝 . 𝐻𝑝𝑗 = 𝑀𝑗 , ∀ 𝑗 = 1, 2, 3 … 𝑀………………...….. (6) 𝑝=1

Kendala (6) menunjukan bahwa total volume produk yang diminta oleh suatu konsumen j merupakan penjumlahan dari hasil kali antara jumlah suatu jenis produk dikalikan dengan volume produk tersebut. 𝑎𝑖 + 𝑆𝑖 + 𝑡𝑖𝑗 − 𝑆 (1 − 𝑥𝑖𝑗𝑘 ) ≤ 𝑎𝑗 , ………………..……. (7) ∀ 𝑖 = 1, 2, … 𝑀, ∀ 𝑗 = 1, 2, … 𝑀 + 1, ∀ 𝑘 = 1, 2 … 𝐾

ISSN : 2355-9365


Kendala (7) memperlihatkan bahwa waktu kedatangan di customer-j adalah hasil dari penjumlahan jam kedatangan di customer-i dengan waktu pelayanan yang terjadi di customer-i waktu keberangkatan di customer-i ditambah dengan waktu tempuh i ke j. 𝑜𝑡𝑖 ≤ 𝑎𝑖 ≤ 𝑐𝑡𝑖 , ∀ 𝑖 = 1, 2, 3 … 𝑀 ……………………... (8) Kendala (8) menjelaskan bahwa kedatangan pada customer i harus berada di selang waktu time window, sehingga pelayanan dilakukan pada rentang waktu time window tersebut 𝑀

𝑀

∑ ∑(𝑆𝑖 + 𝑡𝑖𝑗𝑘 ) 𝑥𝑖𝑗𝑘 ≤ 𝑇, ∀ 𝑘 = 1, 2 … 𝐾.…………...…... (9) 𝑖=1 𝑗=1

Pembatas (9) memastikan bahwa semua rute perjalanan harus kurang dari waktu horizon satu hari. 𝑥𝑖𝑗𝑘 ∈ {0,1}, ∀ 𝑖, 𝑗 = 1, 2, … . , 𝑀 + 1, ∀ 𝑘 = 1, … . , 𝐾 .…………… (10) 𝑦𝑘 ∈ {0,1}, ∀ 𝑘 = 1, … . . , 𝐾 ………………….…....... (11) Pembatas (10) dan (11) menunjukkan bahwa nilai dari setiap variabel keputusan ialah 0 atau 1. Bernilai 1 apabila terdapat rute dari titik i ke j yang terpilih, dan sebaliknya apabila tidak 3.3 Kondisi Existing Setelah data yang didapat diolah, maka didapatlah urutan rute pada kondisi existing beserta biaya yang dikeluarkan pada kondisi existing. Dapat dilihat pada tabel 1 urutan rute pada kondisi existing beserta jarak tempuh yang dilalui. Tabel 1 Urutan Rute dan Jarak Existing Armada Rute Kunjungan Awal Jarak (KM) A1 D – P46 – P27 – P37 – D 36,905 A2 D – P34 – P40 – P05 – P44 – P32 – P02 – P41 – D 42,474 A3 D – P01 – P15 – P35 – P03 – P25 – P36 – P16 – P07 – P28 – D 53,998 D – P13 – P14 – P24 – P17 – P11 – P18 – P08 – P20 – P06 – P12 – A4 61,495 P26 – P04 – P10 – D A5 D – P33 – P39 – P47 – P09 – P19 – P23 – D 33,984 A6 D – P3 – P21 – P45 – P31 – P42 – P29 – P38 – P43 – P22 – D 70,487 Total Jarak 299,343 Berdasarkan Tabel 1 diatas, rute existing membutuhkan jarak tempuh sejauh 299,343 Km dengan kebutuhan armada sebanya 6 armada dengan waktu tempuh pada kondisi existing adalah 10.43 Jam. 3.4 Alogaritma Penentuan Rute Dalam penelitian ini, untuk melakukan pencarian rute dipilih alogaritma heuristic dan metaheuristik sebagai alogaritma penyelesaian masalah. Pencarian rute dilakukan kepada dua tahap dengan menemukan solusi awal terlebih dahulu, kemudian solusi awal di optimasi agar hasil pencarian rute menjadi optimal. Untuk tahap pertama, solusi awal dibentuk menggunakan algoritma heuristic nearest neighbour, hasil dari algoritma ini adalah sebuah rute usulan pertama, atau individu pertama yang masih dapat di optimalkan hasilnya. Untuk model pencarian rute awal, rute yang dicari adalah rute yang meminimasi jarak tempuh agar dapat meminimasi waktu tempuh sehinggan dapat menghindari keterlambatan pada proses distribusi, rute yang dicari memperhatikan time window dari masing-masing customer, demand customer, kapasitas dari kendaraan serta kendaraan yang digunakan. Setelah didapatkan solusi awal selanjutnya solusi diproses kembali dengan alogaritma tabu search agar dapat meminimasi waktu tempuh 3.5 Hasil Solusi Nearest Neighbour Setelah dilakukan iterasi terakhir, maka didapatkan solusi awal dengan nearest neighbour dengan rincian pada Tabel 2 dan Tabel 3 Tabel 2 Solusi Awal Nearest Neighbour Armada Rute Kunjungan D – P19 – P23 – P9 – P47 – P39 – P44 – P32 – P2 – P21 – P30 – P40 – P34 – P10 – Armada 1 P24 – P29 – P31 – P45 – P27 – P41 – D Armada 2 D – P13 – P14 – P33 – P5 – P25 – P36 – P7 – P16 – P35 – P 38 – P43 – P22 – D Armada 3 D – P4 – P12 – P26 – P20 – P6 – P18 – P8 – P11 – P17 – P46 – P1 – D Armada 4 D – P15 – P37 – D Armada 5 D – P3 – P28 – P42 – D

ISSN : 2355-9365

Armada 1 2 3 4 5


Tabel 3 Total Jarak dan Waktu Tempuh Nearest Neighbour Jarak Tempuh (KM) Waktu Tempuh (Jam) 75,22 2,62 76,57 2,67 52,44 1,83 35,31 1,23 45,66 1,59

3.6 Hasil Perhitungan Alogaitma Tabu Search Setelah iterasi selesai dilakukan maka didapatlah urutan rute terbaik dengan jumlah armada yang digunakan hanya 5 dari 6 armada dengan total jarak tempuh sejauh 275.125 km dan waktu tempuh total selama 9.587 jam. Selain itu seluruh demand konsumen terantarkan dengan sesuai pada waktu tutup customer. Berikut merupakan solusi dari Alogaritma Tabu Search pada Tabel 4

Armada 2 Armada 3 Armada 4 Armada 5

Tabel 4 Solusi Rute Alogaritma Tabu Search Rute Kunjungan D – P23 – P19 – P9 – P47 – P39 – P44 – P32 – P2 – P21 – P30 – P24 – P10 – P34 – P40 – P29 – P31 – P45 – P27 – P41 – D D – P13 – P14 – P33 – P5 – P25 – P36 – P7 – P16 – P38 – P22 – P43 – P35 – D D – P4 – P12 – P26 – P20 – P6 – P8 – P18 – P11 – P17 – P46 – P1 – D D – P15 – P37 – D D – P3 – P28 – P42 – D

Armada 1 2 3 4 5

Tabel 5 Total Jarak dan Waktu Tempuh Tabu Search Jarak Tempuh (KM) Waktu Tempuh (Jam) 72,99 2,54 70,91 2,47 50,26 1,75 35,31 1,23 45,66 1,59

Armada Armada 1

4. Kesimpulan Setelah didapatkan hasil penelitian perencanaan rute pendistribusian menggunakan algoritma Tabu Search, dapat ditarik kesimpulan bahwa sesuai dengan total jarak tempuh yang turun dari kondisi existing, total waktu tempuh distribusi armada pun akan turun. Waktu tempuh pada awalnya selama 10,93 jam menjadi 9,59 jam dengan perubahan sebesar 80 menit lebih cepat atau terjadi penurunan sebesar 12,3%. Dengan waktu tempuh yang berkurang keterlambatan bisa terpenuhi, setelah dilakukan penyesuaian antara waktu tiba armada dengan time windows, tidak terjadi keterlambatan karena semua armada yang datang berada pada range time windows setiap customer. Daftar Pustaka: [1] Fred, G., 1989. Tabu Search. ORSA Journal on computing, 1(3), pp. 190-206. [2] Salim, H. A., 1993. Manajemen transportasi. Jakarta: Raja Grafindo Persada. [3] Tooth, P. & Vigo, D., 2002. The Vehicle Routing Problem. s.l.:Society for Industrial and Applied Mathematics. [4] Faisal, F. (2012). Penentuan Alokasi dan Rute Transportasi yang Optimal di PT. Sumber Alfaria Menggunakan Metode ABC dan Algoritma Tabu Search. Sarjana Bandung: Institut Teknologi Bandung.

ISSN : e-proceeding of Engineering : Vol.4, No.2 Agustus 2017 Page 2892

Recommend Documents