PENERAPAN METODE HEURISTIK DALAM SUPPLY CHAIN NETWORK UNTUK MENENTUKAN JALUR DISTRIBUSI TERPENDEK
FAJAR ADIYATNO
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2010
ABSTRAK FAJAR ADIYATNO. Penerapan Metode Heuristik Dalam Supply Chain Network Untuk Menentukan Jalur Distribusi Terpendek. Dibimbing oleh AMRIL AMAN dan TONI BAKHTIAR. Supply chain management adalah sebuah proses pembuatan dan penyampaian barang kepada konsumen. Salah satu faktor utama dari supply chain management adalah supply chain networks. Supply chain networks terdiri atas dua bagian utama yaitu lokasi produksi dan proses distribusi. Keduanya berkaitan dengan penentuan jalur distribusi atau rute optimum dari produsen ke konsumen yang berkaitan dengan waktu, jarak tempuh, dan kapasitas kendaraan. Masalah penentuan rute optimum ini disebut dengan Vehicle Routing Problem with Time Windows (VRPTW). Penelitian dilakukan di bagian supply chain CV KATRACO, sebuah perusahaan swasta yang bergerak dalam pendistribusian bahan bakar minyak ke SPBU dan beberapa perusahaan di wilayah Jawa Tengah dan sekitarnya. Penelitian ini bertujuan merancang supply chain network untuk kasus VRPTW untuk meminimumkan total jarak tempuh kendaraan. Metode yang digunakan adalah metode heuristic yaitu sweep heuristic, saving heuristic, dan nearest depot heuristic sebagai route constructing methods. Metode 2-opt, metode relocate, dan metode exchange digunakan sebagai route improvement methods untuk menentukan rute yang lebih optimum bagi kendaraan. Selanjutnya, masalah VRPTW diselesaikan dengan menggunakan program ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4, yang dijalankan dalam Microsoft Visual C++ versi 6.0.
ABSTRACT FAJAR ADIYATNO. Implementation of Heuristic Methods in Supply Chain Network To Determine the Distribution of the Shortest Path. Supervised by AMRIL AMAN and TONI BAKHTIAR. Supply chain management is a process of manufacture and delivery of goods to consumers. One of the main factors of supply chain management is supply chain networks. Supply chain networks consist of two main parts, i.e. , the location of production and the distribution process. Both are related to the determination of optimum distribution channels or routes from producers to consumers which are related to time, distance, and vehicle capacity. This problem is called with the Vehicle Routing Problem with Time Windows (VRPTW). This research work was conducted in the supply chain division of KATRACO CV, a private company that engaged in the distribution of fuel oil to gas stations and several companies in Central Java and surrounding areas. This research aims to design a supply chain network for VRPTW case to minimize the total distance. In this work we used a heuristic method , i.e. , sweep heuristic, saving heuristic, and the nearest depot heuristic as constructing route. We also used 2opt, relocate, and exchange methods as route improvement methods to determine a better routes. Furthermore, VRPTW problem is solved using ILOG Dispatcher program version 2.1 and ILOG Solver version 4.4, which is run in Microsoft Visual C + + version 6.0.
PENERAPAN METODE HEURISTIK DALAM SUPPLY CHAIN NETWORK UNTUK MENENTUKAN JALUR DISTRIBUSI TERPENDEK
FAJAR ADIYATNO
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2010
Judul Skripsi Nama NIM
: Penerapan Metode Heuristik Dalam Supply Chain Network Untuk Menentukan Jalur Distribusi Terpendek : Fajar Adiyatno : G54061594
Menyetujui Pembimbing I,
Pembimbing II,
Dr. Ir. Amril Aman, M.Sc. NIP. 19570330 198103 1 001
Dr. Toni Bakhtiar, M.Sc. NIP. 19720627 199702 1 002
Mengetahui: Ketua Departemen,
Dr. Berlian Setiawaty, MS. NIP: 19650505 198903 2 004
Tanggal Lulus:
1
KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT atas berkat, rahmat dan kasih sayang-Nya sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga banyak sekali orang yang membantu dan berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1.
Sang pencipta, Tuhan semesta alam Allah SWT, atas maha karya-Nya yaitu bumi yang sempurna ini; 2. keluarga tercinta: bapak dan ibu, ibu sebagai pemberi motivasi dan bapak sebagai sumber inspirasi, untuk Itang, Opi, Amel yang selalu memberikan semangat dan doa. 3. Dr. Ir. Amril Aman, M.Sc. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, semangat dan doa; 4. Dr. Toni Bakhtiar, M.Sc. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya; 5. Drs. Siswandi, M.Si. selaku dosen penguji yang telah memberikan ilmu, saran dan doanya; 6. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan; 7. staf Departemen Matematika: Bapak Yono, Bapak Hery, Bapak Deni, Ibu Ade, Bapak Epul, Bapak Bono dan Ibu Susi atas semangat dan doanya; 8. sahabat yang selalu memberi semangat: Nia, Apri, vera, Sofyan, Tami, Arum, Wira Fardan, Dandi, Slamet, dan Margi; 9. kawan yang selalu memberi inspirasi: Faisal, Dhia, Feni, Vivi; 10. keluarga besar H Khamsiah dan H Maliha yang selalu memberi motivasi dan doa; 11. semua teman Matematika 42 yang selalu menjadi contoh yang baik; 12. semua teman Matematika 43 yang selalu menjadi bagian dari keluarga; 13. semua teman Matematika 44 yang selalu mendukung agar terus berkembang; 14. perkumpulan perpustakaan: Ricken, Agnes, Ryu, Peny, Iput; 15. teman satu pembimbing: Mira, Fardan, Razono, Nurisma, Imam, Lili; 16. teman seperjuangan perwira 40: Ucok, Erwin, Satrio, Bayu, Ilman, Dandi, Anif, Hendra, Zul, Leo, Hesti, Sari; 17. teman seperjuangan 43 Banjarnegara: Galih, Heru, Jona, Ita, Vita, Bani, Arin, Revi, Okta, eny, Lia, Leli, Ayu, Anggi; 18. Gumatika dan Ikamahamas yang telah mengasah pribadi ini menjadi pribadi yang tangguh; 19. Guardian angel for being my special one; 20. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya bidang matematika dan menjadi inspirasi bagi penelitian selanjutnya.
Bogor, Desember 2010
Fajar Adiyatno
DAFTAR ISI Halaman DAFTAR GAMBAR ........................................................................................................... viii DAFTAR TABEL ............................................................................................................... viii DAFTAR LAMPIRAN ........................................................................................................ I
ix
PENDAHULUAN 1.1 Latar Belakang ...................................................................................................... 1.2 Tujuan Penelitian ................................................................................................... 1.3 Manfaat .................................................................................................................
1 1 1
LANDASAN TEORI 2.1 Supply Chain Management .................................................................................... 2.2 Supply Chain Network ............................................................................................ 2.3 Distribusi ............................................................................................................... 2.4 Graf ....................................................................................................................... 2.5 Traveling Salesman Problem ................................................................................. 2.5.1 Traveling Salesman Problem with Time Windows............................................ 2.5.2 m-TSP .......................................................................................................... 2.6 Vehicle Routing Problem ....................................................................................... 2.7 Vehicle Routing Problem with Time Windows .......................................................... 2.8 Metode Heuristic ................................................................................................... 2.8.1 Saving Heuristic ........................................................................................... 2.8.2 Sweep Heuristic ............................................................................................ 2.8.3 Nearestdepot Heuristic ................................................................................. 2.8.4 Metode 2-opt ................................................................................................ 2.8.5 Metode Relocate ........................................................................................... 2.8.6 Metode Exchange ..........................................................................................
1 2 2 2 2 3 3 3 4 5 5 7 8 9 9 10
III DISTRIBUSI BAHAN BAKAR MINYAK DI CV KATRACO 3.1 Ruang Lingkup ..................................................................................................... 3.2 Pengolahan Data .................................................................................................. 3.3 Perumusan Masalah ............................................................................................. 3.4 Formulasi Masalah .............................................................................................. 3.5 Hasil dan Pembahasan .........................................................................................
12 12 13 13 14
IV SIMPULAN ................................................................................................................ Simpulan ...................................................................................................................
20 20
DAFTAR PUSTAKA ..................................................................................................
20
LAMPIRAN ...............................................................................................................
21
II
vii
1
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11
Halaman Peta Jalan Raya di Jawa Tengah ............................................................................. 2 Rute dalam Traveling salesman Problem (TSP) ...................................................... 3 Ilustrasi Saving Heuristic ........................................................................................ 7 Ilustrasi Sweep Heuristic ........................................................................................ 8 Ilustrasi Nearestdepot Heuristic ................................................................................ 8 Diagram alir Metode 2-opt ....................................................................................... 9 Ilustrasi Metode 2-opt ............................................................................................... 9 Diagram alir Metode Relocate ................................................................................ 10 Ilustrasi Metode Relocate ....................................................................................... 10 Diagram alir Metode Exchange ............................................................................... 11 Ilustrasi Metode Relocate ....................................................................................... 12
DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Halaman Permintaan tiap TPS ............................................................................................... 5 Jarak antar-TPS ....................................................................................................... 6 Nilai savings .......................................................................................................... 6 Ranking nilai savings ............................................................................................... 7 Data permintaan dan waktu bongkar-muat tiap konsumen ....................................... 13 Hasil simulasi tahap route constructing................................................................... 15 Hasil simulasi tahap route improvement.................................................................. 16 Hasil simulasi menggunakan metode savings heuristic kendaraan pertama ............. 16 Hasil simulasi menggunakan metode savings heuristic kendaraan kedua ................ 17 Hasil simulasi menggunakan metode savings heuristic kendaraan ketiga ................. 17 Hasil simulasi menggunakan metode sweep heuristic kendaraan pertama ............... 17 Hasil simulasi menggunakan metode sweep heuristic kendaraan kedua .................. 18 Hasil simulasi menggunakan metode sweep heuristic kendaraan ketiga .................. 18 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan pertama ..... 18 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kedua ......... 19 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan ketiga ......... 19 Hasil rute saat ini kendaraan pertama ...................................................................... 19 Hasil rute saat ini kendaraan kedua ......................................................................... 19 Hasil rute saat ini kendaraan ketiga ......................................................................... 20
viii
1
DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Halaman Hasil simulasi menggunakan metode savings heuristic pada kendaraan pertama sampai kesembilan .............................................................................................................. 21 Hasil simulasi menggunakan metode sweep heuristic pada kendaraan pertama sampai kesepuluh ............................................................................................................... 23 Hasil simulasi menggunakan metode nearestdepot heuristic pada kendaraan pertama sampai kesepuluh .................................................................................................... 25 Hasil rute saat ini pada kendaraan pertama sampai keduabelas ................................. 27 Matrik jarak saaat ini (km) ....................................................................................... 30 M-File Mathlab ........................................................................................................ 31 Input program (notepad) .......................................................................................... 33 Output program savings heuristic ............................................................................ 34 Output program sweep heuristic ................................................................................ 36 Output program nearestdepot heuristic ..................................................................... 38 Skrip program savings heuristic ................................................................................. 40 Skrip program sweep heuristic ................................................................................. 43 Skrip program nearestdepot heuristic ...................................................................... 46 Peta jalur distribusi (CV KATRACO) ...................................................................... 49
ix
2
RIWAYAT HIDUP Penulis dilahirkan di Banjarnegara pada tanggal 23 Juni 1988 sebagai anak pertama dari empat bersaudara, anak dari pasangan Imam Sayoga dan Mafrukha. Pada tahun 2000 penulis lulus dari SD Muhammadiyah I Banjarnegara kemudian tahun 2003 lulus dari SLTPN I Bawang. Tahun 2006 penulis lulus dari MAN 2 Banjarnegara dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB). Pada tahun 2007, penulis memilih jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis juga aktif dalam mengajar Matematika bimbingan belajar privat maupun kelompok mahasiswa dan siswa SMA. Penulis aktif dalam organisasi kemahasiswaan di kampus, seperti ketua organisasi mahasiswa daerah Banyumas yang dikenal IKAMAHAMAS (Ikatan Keluarga Mahasiswa Banyumas) tahun 2007/2008, organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai anggota Departemen BIKERS tahun 2008/2010. Penulis juga pernah menjadi pembicara dalam acara Masa Pengenalan Departemen Matematika 2010 serta finalis PIMNAS XXIII 2010 sebagai Penyaji Nasional Program Kreatifitas Mahasiswa di Denpasar Bali yang diadakan oleh DIKTI. Selain itu, penulis juga terlibat dalam beberapa kegiatan, antara lain koordinator HUMAS Try-Out SNMPTN 2007, koordinator HUMAS Masa Pengenalan Departemen Matematika 2008, logistik dan transportasi Matematika Ria dalam acara Pesta Sains se-Indonesia 2008, konsumsi Matematika Ria dalam acara Pesta Sains se-Indonesia 2009.
1
I PENDAHULUAN Pada bagian awal bab ini, akan dijelaskan latar belakang dan tujuan penelitian yang dilakukan. Sementara itu pada bagian akhir bab ini akan disajikan manfaat dari penelitian ini bagi perusahaan. 1.1 Latar belakang Bahan bakar merupakan suatu komponen penting dalam proses produksi, terutama dalam hal pendistribusian barang. Harga bahan bakar yang tidak stabil mendorong perusahaan harus bisa membuat semua lini proses produksi berjalan secara efektif dan efisien. Perusahan harus mengintegrasikan semua arus informasi barang dan jasa, mulai dari pemasok atau agen hingga ke konsumen. Proses integrasi ini disebut dengan supply chain management. Supply chain management adalah sebuah proses di mana produk diciptakan dan disampaikan kepada konsumen. Salah satu faktor utama yang merupakan bagian dari supply chain management adalah supply chain networks. Supply chain networks terdiri dari dua bagian utama yaitu lokasi produksi dan proses distribusi. Penentuan lokasi produksi dan proses distribusi merupakan faktor yang sangat penting. Penentuannya akan berhubungan dengan proses pemasaran dan pelayanan terhadap permintaan konsumen. Lokasi produksi yang tepat akan dapat meningkatkan kinerja perusahaan, sedangkan proses distribusi berkaitan dengan pengiriman barang dan jasa dari produsen ke konsumen dengan tepat sasaran dan waktu yang cepat. Proses distribusi harus memperhatikan penentuan jalur distribusi yang tepat.
Penentuan jalur distribusi berkaitan dengan jarak tempuh, waktu tempuh dan kendaraan yang dipakai. Masalah yang berkaitan dengan penentuan jalur distribusi dalam hal ini adalah penentuan rute yang optimum untuk kendaraan dari satu produsen untuk melayani banyak konsumen yang berkaitan dengan waktu dan jarak tempuh, masalah ini disebut dengan Vehicle Routing Problem with Time Windows (VRPTW). 1.2 Tujuan Peneltian Tujuan dari penelitian ini adalah merancang supply chain network untuk kasus VRPTW pada CV KATRACO yang bergerak pada pengiriman bahan bakar minyak. Metode yang digunakan adalah metode heuristic seperti sweep heuristic, saving heuristic, nearest depot heuristic untuk menentukan rute yang optimum bagi kendaraan. Pemilihan metode yang tepat juga dapat bertujuan untuk meminimumkan biaya distribusi yang berdampak pada proses produksi dan kepuasan konsumen. 1.3 Manfaat Manfaat yang dapat diperoleh dari penelitian ini adalah perancangan supply chain network yang dapat memberikan: 1. gambaran pemilihan rute optimum bagi kendaraan untuk mencapai lokasi tujuan dengan cepat dan tepat, 2. memaksimalkan barang bawaan, 3. meminimumkan jumlah kendaraan yang dipakai sehingga dapat memberi keuntungan yang lebih bagi perusahaan.
II LANDASAN TEORI Dalam bab ini, akan dijelaskan beberapa metode yang digunakan dalam penelitian. Pertama-tama akan dijelaskan pengertian supply chain management, supply chain network, distribusi, graf, Traveling Salesman Problem (TSP) yang merupakan dasar dari Vehicle Routing Problem (VRP). Pada bagian terakhir akan diperlihatkan penggunaan metode heuristic untuk mencari solusi dari kasus VRPTW yang dihadapi.
-
2.1 Supply Chain Management Supply chain management adalah sebuah proses yang meliputi:
-
-
-
kegiatan menentukan lokasi produksi dengan tepat kegiatan merancang produk baru (product development) kegiatan mendapatkan bahan baku (procurement) kegiatan merencanakan produksi dan persediaan kegiatan melakukan produksi kegiatan inventori (penyimpanan) barangbarang hasil produksi kegiatan melakukan pengiriman barangbarang hasil produksi (distribution) planning and control. (Ayers 2001)
2
2.2 Supply Chain Network Supply chain network merupakan sebuah pilihan proses management yang melakukan fungsi dalam upaya mendapatkan bahan baku, transportasi bahan baku sampai pada tempat produksi dan distribusi hasil produksi kepada konsumen. (Ganeshan & Harrison 1995) Proses supply chain network akan menentukan kinerja suatu perusahaan dalam upaya meningkatkan keuntungan dan melayani kepuasan konsumen. 2.3 Distribusi Distribusi ialah proses pengiriman barang dan jasa sampai ke konsumen pada waktu yang cepat dan tempat yang tepat. Proses distribusi dipengaruhi oleh keputusan transportasi yang digunakan. Untuk menciptakan proses distribusi yang efektif dan efisien maka perusahaan harus merancang jalur distribusi yang tepat. Jalur distribusi yang tepat dicapai dengan memilih rute yang paling optimum antara lokasi asal dan lokasi tujuan. (Hugos 2003)
Pemilihan jalur distribusi yang tepat dapat meningkatkan kepuasan konsumen karena produk yang mereka inginkan bisa mereka terima tepat waktu, sedangkan bagi perusahaan tujuannya adalah mengefisienkan biaya dan meningkatkan kinerja sumber daya manusianya. 2.4 Graf Suatu graf G adalah pasangan terurut (V,E) dengan V himpunan takkosong dan berhingga dan E himpunan pasangan takterurut yang menghubungkan elemenelemen V. Graf G dinotasikan dengan G=(V,E). Elemen V disebut verteks (node, simpul) sedangkan elemen E disebut sisi (edge). (Foulds 1992) Dalam masalah transportasi, himpunan simpul pada graf G dinotasikan V(G) yang merupakan representasi dari kota tujuan, sedangkan himpunan sisi pada graf G dinotasikan E(G) merupakan representasi dari jalur penghubung antarkota tujuan. Gambar 1 merupakan ilustrasi sebuah graf yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah. Rembang
Brebes
Tegal
Pemalang
Demak
Kendal
Kudus
Semarang
Pekalongan Slawi
Blora Temanggung Wonosobo
Purwokerto
Purwodadi
Salatiga
Purbalingga Sragen Banjarnegara
Kroya Cilacap
Boyolali
Solo Sukoharjo
Kebumen
Magelang Klaten Purworejo Wonogiri
Gambar 1 Peta jalan raya di Jawa Tengah. 2.5 Traveling Salesman Problem Traveling salesman problem adalah suatu permasalahan di mana seorang salesman akan mengunjungi seluruh kota yang ada dan diharuskan kembali ke kota awal pada akhir perjalanannya. Tujuannya adalah menentukan rute perjalanan yang melalui seluruh kota dan meminimumkan jarak tempuh. Permasalahan semacam ini merupakan suatu contoh dari permasalahan Traveling Salesman Problem (TSP).
Definisi variabel keputusan, fungsi objektif dan fungsi kendala dalam TSP adalah sebagai berikut: Variabel keputusan 1, jika kota ke β π dikunjungi setelah kota ke β π π₯π,π = 0,
jika selainnya.
3
Fungsi objektif: π
π
min π β
ππ,π π₯π,π
(1)
π =1 π=1
Fungsi kendala: π
π₯π,π = 1 ; βπ = 1,2, β¦ π
(2)
π₯π,π = 1 ; βπ = 1,2, β¦ π
(3)
π =1 π
π=1
π₯π,π β€ πΏ β 1 ; βπΏ β (1,2, β¦ π)
(4)
π βπΏ πβπΏ
π₯π,π = 0,1 ; βπ,π = 1,2, β¦ π.
(5)
Fungsi objektif pada persamaan (1) adalah meminimumkan jarak yang ditempuh dan mengunjungi setiap kota yang ada, dengan ππ,π adalah jarak dari kota i ke kota j dan π₯π,π benilai 1 jika rute dari kota ke-i menuju kota ke-j digunakan, benilai 0 jika selainnya. Kendala (2) dan (3) memastikan bahwa rute tiap kota ke-i menuju ke-j dikunjungi tepat satu kali, sedangkan kendala (4) memastikan tidak terdapat subtour atau penumpukan kendaraan yang melayani rute dari kota ke-i menuju kota ke-j yang hanya dilayani oleh satu kendaraan. L adalah banyaknya subtour dari setiap rute dari kota-kota 1,2,...,m. Pada kendala (5) diperlihatkan bahwa π₯π,π merupakan varibel biner untuk setiap i dan j yang ada. (Hoffman & Padberg 1991) Gambar 2 merupakan ilustrasi dari TSP di mana terdapat depot yang merupakan titik awal bagi salesman untuk mendistribusikan barang kepada konsumen melalui rute yang ada.
Gambar 2 Contoh rute dalam traveling salesman problem (TSP). Dalam perkembangannya TSP memiliki beberapa variasi, yaitu: Traveling Salesman Problem with Time Windows (TSPTW) yang merupakan TSP dengan tambahan waktu pelayanan di setiap kota dan m-Traveling Salesman Problem (m-TSP) yang menggunakan sejumlah salesman untuk mengunjungi seluruh kota.
2.5.1 Traveling Salesman Problem with Time Windows Traveling salesman problem with time windows merupakan pengembangan dari TSP. Pada TSPTW rute yang ditempuh memiliki tambahan kendala waktu pelayanan (time windows) untuk setiap konsumen. Time windows pada setiap konsumen dapat berbeda satu sama lain, tetapi memiliki karekteristik yang sama yakni berupa selang waktu. Time windows ππ , ππ menunjukkan selang waktu pelayanan pada konsumen i, dengan ππ sebagai batas awal dan ππ sebagai batas akhir. Formulasi untuk TSPTW tidak berbeda dengan formulasi TSP di atas, dengan tambahan beberapa kendala. Misal ππ adalah waktu pelayanan pada kota ke-i, maka untuk setiap i haruslah berlaku: ππ β€ ππ β€ ππ ; βπ = 1,2, β¦ π (6) ππ + π‘π,π β€ ππ ; βπ,π = 1,2, β¦ π (7) βπβ π Pada (6), waktu pelayanan ππ berada di antara batas awal ππ dan batas akhir ππ dari time windows. Kendaraan harus melayani konsumen tidak kurang dari waktu ππ dan tidak lebih dari waktu ππ , sedangkan pada persamaan berikutnya (7), dipastikan waktu pelayanan di kota j (ππ ) adalah lebih besar sama dengan waktu tempuh antara kota i dan kota j (π‘π,π ) ditambahkan dengan waktu pelayanan di kota i (ππ ). (Sutapa et al 2003) 2.5.2 m-TSP Salah satu variasi dari TSP adalah m-TSP, di mana terdapat m-salesman mengunjungi seluruh kota tetapi setiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalannya juga harus kembali ke depot tersebut. Tujuannya adalah meminimumkan total jarak dari setiap rute. Masalah m-TSP dikenal juga sebagai vehicle routing problem (VRP), di mana sebuah kota direpresentasikan sebagai sebuah konsumen dan tiap kendaraan memiliki kapasitas tertentu. Total jumlah permintaan dalam suatu rute tidak boleh melebihi kapasitas dari kendaraan yang beroperasi. (Larsen 1999) 2.6 Vehicle Routing Problem Vehicle Routing Problem (VRP) merupakan masalah yang berkaitan dengan pencarian rute optimal untuk kendaraan dari satu depot dan melayani sejumlah konsumen. Ketentuan VRP meliputi setiap rute berawal
4
dan berakhir di depot, setiap konsumen dikunjungi tepat satu kali oleh tepat satu kendaraan, jumlah permintaan tiap rute tidak melebihi kapasitas kendaraan dan meminimumkan biaya perjalanan. (Cordeau et al 2002) VRP adalah masalah optimisasi kombinatorial yang kompleks, karena merupakan gabungan dari masalah kapasitas (packing problem) dan masalah pencarian rute optimal kendaraan dari suatu depot dan melayani sejumlah konsumen (traveling salesman problem). Dalam prakteknya VRP banyak digunakan pada masalah distribusi logistik. Karakteristik dari formulasi VRP adalah satu depot (dilambangkan dengan O) yang memiliki sebanyak k kendaraan untuk melakukan pengiriman, di mana kapasitas setiap kendaraan sebesar πΆπ . Kendaraan tersebut mengirimkan permintaan sebesar ππ kepada konsumen ke-i, dengan i=1,2,3,β¦,n. Jarak yang ditempuh setiap kendaraan adalah jarak yang paling minimum dengan ππ,π adalah jarak yang ditempuh dari konsumen i ke konsumen j, di mana i= 1,2,β¦,n dan j=1,2,β¦,m. Jarak antara konsumen bersifat simetris atau dapat ditulis sebagai ππ,π = ππ ,π , sedangkan jarak antara tempat yang sama bernilai nol atau ππ,π = 0. Solusi yang dihasilkan merupakan anggota dari {π
1 , β¦ π
π } di mana π
1 dan π
π merupakan representasi dari rute ke-1 sampai rute ke-k yang mengirimkan n permintaan melalui k rute yang tersedia dan permintaan yang dikirim tidak melebihi kapasitas kendaraan yang tersedia untuk setiap rute. (Machado et al 2002) Definisi variabel keputusan, konstanta, fungsi objektif dan fungsi kendala dalam VRP adalah sebagai berikut: Variabel keputusan 1, jika π dikunjungi setelah π π oleh kendaraan π π₯π,π = 0, jika selainnya. Konstanta ππ = permintaan konsumen ke β π πΆπ = kapasitas maksimum kendaraan π ππ,π = jarak yang ditempuh dari konsumen i ke konsumen j, di mana i= 1,2,β¦,n dan j=1,2,β¦,m. Fungsi objektif π
π
π, π ππ,π π₯π,π
min π β π =1 π=1 π =1
(1)
Fungsi kendala ο· konsumen π
πβ² π π₯π,π = 1 ; βπ = 2,3, β¦ π
(2)
π = 1 ; βπ = 2,3, β¦ π. π₯π,π
(3)
π=1 π=1 π πβ²
π =1 π=1
ο· depot π
π π₯1,π = 1 ; βπ = 1,2, β¦ π β²
(4)
π π₯π,1 = 1 ; βπ = 1,2, β¦ π β² .
(5)
π =2 π
π=2
ο· kekontinuan rute π
π
π π₯π,π’ π=2
π₯π’π ,π
= π=2 β²
βπ’ = 1,2, β¦ π βπ = 1,2, β¦ π β² ο· kapasitas π
π
π β€ πΆπ ; βπ = 1,2, β¦ π β² ππ π₯π,π
(7)
π=1 π =1 π = π₯π,π
(8) 0,1 ; βπ,π = 1,2, β¦ π β² βπ = 1,2, β¦ π . Fungsi objektif dari VRP (1) adalah meminimumkan total jarak tempuh kendaraan, di mana ππ,π adalah jarak dari konsumen i π menuju konsumen j. Variabel keputusan π₯π,π bernilai 1 jika rute dari konsumen i menuju konsumen j dilayani oleh kendaraan k dan bernilai nol jika selainnya. Pada kendala (2) dan (3) dipastikan tepat satu kendaraan yang datang dan pergi dari konsumen i, sedangkan kendala (4) dan (5) memastikan bahwa tepat satu kendaraan yang pergi dan tiba di depot untuk satu rute. Kendala (6) memastikan kekontinuan rute dari setiap kendaraan yang beroperasi. Kendaraan yang telah selesai melayani konsumen ke-i diharuskan segera pergi untuk melayani konsumen berikutnya. Kendala (7) memastikan agar total permintaan (ππ ) pada satu rute tidak melebihi kapasitas kendaraan (πΆπ ) yang beroperasi pada rute tersebut. (Kritikos & Ioannou 2004) 2.7 Vehicle Routing Problem with Time Windows VRP dengan tambahan kendala waktu pelayanan disebut sebagai Vehicle Routing Problem with Time Windows (VRPTW). Kendala waktu adalah selang waktu tertentu di mana setiap kendaraan dapat memberikan
5
pelayanan pada konsumen, biasanya selang waktu tersebut berbeda pada setiap konsumen. (Hideki et al 2006) Seperti halnya VRP, fungsi objektif bagi VRPTW adalah meminimumkan total jarak tempuh kendaraan. Kendala yang digunakan pun sama seperti formulasi VRP (2)-(8), tetapi perlu ditambahkan beberapa kendala yang berhubungan dengan time windows. Kendala tersebut, antara lain: Konstanta π‘π = waktu kedatangan pada tempat i π‘π = waktu kedatangan pada tempat j ππ = waktu servis di konsumen i π π‘π β₯ π‘π + ππ + π‘π,π β π 1 β π₯π,π (9) βπ,π = 2,3, β¦ , π βπ = 1, β¦ , πβ² ππ β€ π‘π β€ ππ ; π = 1,2, β¦ π (10) π‘π β₯ 0 ; π = 1, β¦ , π. (11) Kendala (9) memastikan waktu kedatangan kendaraan di konsumen j (π‘π ) selalu lebih besar dari kedatangan kendaraan di konsumen i (π‘π ), di mana π merupakan waktu service di konsumen i dan π‘π,π adalah waktu tempuh dari konsumen i menuju konsumen j. Sedangkan M (disebut big-m) merupakan bilangan yang π )besar relatif besar, sehingga jika π(1 β π₯π,π maka rute dari i ke j tidak akan ditempuh dan sebaliknya. Kendala berikutnya (10) memastikan kedatangan kendaraan di konsumen i berada di antara selang waktu yang telah ditentukan, dengan batas awal ππ dan batas akhir ππ , sedangkan kendala terakhir (11) memastikan agar waktu kedatangan kendaraan ke setiap konsumen selalu positif. (Larsen 1999) 2.8 Metode Heuristik Penggunaan metode branch and bound untuk mencari solusi VRP yang memiliki banyak kota (lebih dari 50 kota) memerlukan waktu komputasi yang lama. Alasan tersebut menjadi sebab dikembangkannya metode heuristic. Metode heuristic dapat memberikan solusi lebih cepat daripada metode branch and bound, tetapi tidak ada jaminan solusi yang dihasilkan optimal. Solusi dari metode heuristic didapat selain dengan cara trial and error juga dengan pendekatan secara intuitif. (Winston 2004) Untuk memecahkan masalah VRP dengan metode heuristic diperlukan dua tahap yaitu
route constructing sebagai tahap pertama dan route improvement pada tahap kedua. Pada penelitian ini metode sweep heuristic, saving heuristic, nearest depot heuristic akan digunakan untuk mencari solusi pada tahap pertama. Selanjutnya metode 2-opt, metode relocate dan metode exchange digunakan untuk memperbaiki solusi yang telah ada. 2.8.1 Saving Heuristic Metode savings heuristic membangun rute terpendek berdasarkan nilai saving yang diurutkan dari yang terbesar kemudian diakumulasikan berdasarkan permintaan tiap vertek tanpa melebihi kapasitas kendaraan, dinotasikan savings s(i,j). Algoritmanya sebagai berikut: 1. hitung nilai savings dari kota i ke kota j dengan cara menambahkan jarak dari depot ke kota i dan jarak dari depot ke kota j dikurangi jarak dari kota i ke kota j untuk setiap verteks. π π, π = π π, π + π π, π β π(π, π), 2. buat ranking dari perhitungan savings dan buat daftar dari hasil savings yang terbesar hingga terkecil, 3. akumulasikan tiap nilai savings dari yang paling besar hingga yang paling kecil berdasarkan permintaan tiap verteks, 4. apabila telah mencapai batas maksimum kapasitas kendaraan, maka beralih ke nilai savings terbesar kedua untuk memulai rute baru dengan kendaraan yang berbeda seterusnya hingga permintaan tiap konsumen terpenuhi. (ILOG 2002) Ilustrasi dari metode savings diberikan dalam Contoh 1.
heuristic
Contoh 1 Sebuah kota kecil mempunyai dua truk pemungut sampah dengan kapasitas 23 ton. Truk tersebut harus mengangkut sampah di 9 titik tempat pembuangan sampah (TPS). Berikut data yang disajikan pada Tabel 1 yang merupakan permintaan tiap TPS, dan Tabel 2 merupakan jarak antar-TPS. Tabel 1 Permintaan tiap TPS adalah TPS 1 2 3 4 5 6 7 8 9 Permintaan 4 6 5 4 7 3 5 4 4 (Ton)
6
TPS
0
1
0 1 2 3 4 5
0
25 0
Tabel 2 jarak antar-TPS 2 3 4 5 6 7 43 29 0
57 34 52 0
43 43 72 45 0
61 68 96 71 27 0
6 7 8 9 Berikut adalah proses perhitungan nilai savings: 1. bila kita akan menghitung s(0,1), dilihat pada Tabel 2 jarak dari depot ke node 0 adalah 0, kemudian jarak dari depot ke node 1 adalah 25, dan jarak dari depot ke node 1 adalah 25, maka: s(0,1) = d(0,0) + d(0,1) β d(0,1) = 0 + 25 β 25 = 0, 2. sama seperti perhitungan pada s(0,1), bila kita menghitung s(1,2) maka langkah pertama yang harus kita lakukan adalah
TPS
0
1
2
0 1 2 3 4 5
0
0 0
0 39 0
6 7 8 9
9
29 49 72 71 36 40
41 66 81 95 65 66
48 72 89 99 65 62
71 91 114 108 65 46
0
31 0
31 11 0
43 46 36 0
mencari data jarak dari depot ke node 1, jarak dari depot ke node 2, dan jarak dari node 1 ke node 2, sehingga: s(1,2) = d(0,1) + d(0,2) β d(1,2) = 25 + 43 β 29 = 39. Lakukan perhitungan savings terhadap semua kombinasi setiap node sehingga diperoleh nilai savings yang disajikan pada Tabel 3 dan urutkan nilai savings dari yang paling besar hingga yang paling kecil yang disajikan pada Tabel 4.
Tabel 3 Nilai savings 3 4 5 6 7 0 48 48 0
8
0 25 14 55 0
0 18 8 47 77 0
8
9
0 5 0 15 36 50
0 0 3 3 19 36
0 1 2 6 26 47
0 5 23 20 49 86
0
39 0
46 78
57 66
0
83 0
7
Urutkan berdasarkan nilai savings tertinggi Tabel 4 Ranking nilai savings No Koordinat Nilai savings 1 5,9 86 2 8,9 83 3 7,8 78 4 4,5 77 5 7,9 66 6 6,9 57 7 3,4 55 8 5,6 50 9
4,9
49
10 11 12 13 14 15 16
2,3 1,3 5,8 3,5 6,8 6,7 1,2
48 48 47 47 46 39 39
17 18
4,6 5,7
36 36
19 20 21 22
3,6 1,4 2,9 3,9
36 26 25 23
23 24 25 26
4,7 1,5 3,6 2,4
20 19 18 15
27
2,5
14
28 29 30 31 32 33
3,8 1,6 1,9 2,7 1,7 2,8
8 6 5 5 3 2
34 35 36
1,8 1,7 2,6
1 0 0
Langkah penentuan rute: 1. savings terbesar menjadi awal rute, yaitu dari 0 menuju 5 kemudian 9 dan kembali ke 0 (0,5,9,0), dengan kapasitas di node 5 adalah 7 dan kapasitas node 9 adalah 4, sehingga kapasitas angkut pada rute ini
2.
3.
4.
5.
6.
adalah 7+4=11. Mengingat kapasitas per sekali angkut adalah 23 maka rute selanjutnya dapat dibuat berdasarkan daftar ranking savings, rute yang dapat digabungkan selanjutnya adalah (0,5,9,8,0) dengan kapasitas angkut adalah 15, rute ketiga yang dapat dibuat untuk satu kali perjalanan yaitu (0,5,9,8,7,0) dengan kapasitas 20 unit. Kapasitas per sekali angkut adalah 23 unit, berarti tersisa 3 unit yang dapat diangkut, daftar savings ke-4 dicoba untuk penentuan rute, bila dibuat rute (0,5,9,8,7,4,0) akan diperoleh kapasitas 24. Kapasitas sekali angkut yang diperbolehkan adalah 23, maka rute ini tidak dapat digunakan sehingga untuk savings (4,5) menjadi awal rute kedua yang terbesar, kemudian dibuat rute dari data savings ke-5 sehingga diperoleh rute (0,5,9,8,7,6,0) dengan kapasitas adalah 23 unit. Rute ini memungkinkan karena kapasitas angkut per sekali distribusi sebanyak 23 unit, penentuan rute selanjutnya sama halnya dengan tahap awal dan dimulai dari daftar savings terbesar kedua, dari perhitungan diperoleh rute pertama yaitu (0,5,9,8,7,6.0) dengan kapasitas adalah 23. Kemudian rute kedua (0,1,2,3,4,0) dengan kapasitas 19. Dua rute ini memiliki jarak total adalah 420 km, tetapi kedua rute ini belum merupakan rute yang optimum sehingga perlu melakukan perbaikan pada tahap improvement.
Gambar 3 merupakan ilustrasi dari Contoh 1 di mana rute pertama diawali dari depot kemudian menuju ke konsumen 5,9,8,7,6 dan kembali ke depot. Rute kedua diawali dari depot ke konsumen 1,2,3,4 dan kembali ke depot.
Gambar 3 Contoh savings heuristic 2.8.2 Sweep Heuristic Metode sweep heuristic membangun rute dengan cara menelusuri sekitar depot. Jika kapasitas kendaraan atau time windows telah dicapai maka kendaraan tersebut harus kembali ke depot. Untuk kendaraan yang lain berlaku sama seperti kendaraan pertama,
8
sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritmanya sebagai berikut: 1. sejumlah kendaran yang tersedia, 2. kendaraan memulai sebuah rute dari depot 3. temukan konsumen yang terdekat dari titik awal atau depot bagi kendaraan. Kemudian temukan konsumen yang terdekat dari titik sebelumnya. Jika tidak dimungkinkan untuk melakukan kunjungan tanpa melanggar kendala kapasitas kendaraan yang ada akhiri rute kendaraan, pilih kendaraan lain dan lakukan lagi langkah 2, 4. kendaraan yang akan dialokasikan untuk mengunjungi konsumen harus memenuhi semua kendala, 5. jika semua kendaraan telah digunakan dan telah mengunjungi semua konsumen maka selesai. (ILOG 2002) Ilustrasi dari metode sweep heuristic diberikan dalam Contoh 2. Contoh 2 Dalam Contoh 2 dibahas penentuan rute pengambilan sampah seperti pada Contoh 1 dengan menggunakan metode sweep heuristic. Rute pertama diawali dari depot kemudian menuju ke konsumen 1. Pemilihan konsumen 1 sebagai awal dari rute karena memiliki jarak yang paling dekat dengan depot yaitu 25 km. Selanjutnya, dilanjutkan ke konsumen 2 karena memiliki jarak yang paling dekat dengan konsumen 1 yaitu 29 km dan seterusnya sampai ke konsumen 3,4 dan kembali ke depot. Rute kedua diawali dari depot ke konsumen 6,8,7,9,5 dan kembali ke depot. Dua rute inilah yang menjadi solusi dengan jarak total adalah 423 km. Gambar 4 merupakan ilustrasi dari Contoh 2.
berikutnya juga diawali dengan lokasi yang paling dekat dengan depot. Perjalanan berhenti ketika kapasitas kendaraan atau time windows terpenuhi untuk semua kendaraan. Jika kapasitas kendaraan atau time windows telah dicapai maka kendaraan tersebut harus kembali ke depot. Jalankan kendaraan berikutnya dengan aturan yang sama seperti kendaraan pertama, sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritmanya sebagai berikut: 1. sejumlah kendaraan yang tersedia, 2. mulai sebuah rute dari depot bagi kendaraan, 3. temukan konsumen yang terdekat dari titik awal atau depot bagi kendaraan. Jika tidak dimungkinkan untuk melakukan kunjungan tanpa melanggar kendala kapasitas kendaraan yang ada akhiri rute kendaraan, pilih kendaraan lain dan lakukan lagi langkah 2, 4. jika semua konsumen telah dikunjungi maka selesai. (ILOG 2002) Ilustrasi dari metode nearest depot heuristic diberikan dalam Contoh 3. Contoh 3 Dalam Contoh 3 dibahas penentuan rute pengambilan sampah seperti pada Contoh 1 dengan menggunakan metode nearest depot heuristic. Rute pertama diawali dari depot kemudian menuju ke konsumen 1. Pemilihan konsumen 1 sebagai awal rute karena memiliki jarak yang paling dekat dengan depot yaitu 25 km. Selanjutnya, dilanjutkan ke konsumen 6 karena memiliki jarak terpendek kedua dengan depot yaitu 29 km dan seterusnya sampai ke konsumen 7,2,4 dan kembali ke depot. Rute kedua diawali dari depot ke konsumen 8,3,5,9 dan kembali ke depot. Dua rute inilah yang menjadi solusi dengan jarak total adalah 636 km. Gambar 5 merupakan ilustrasi dari Contoh 3.
Gambar 4 Contoh sweep heuristic 2.8.3 Nearest Depot Heuristic Metode nearest depot heuristic dimulai dengan menentukan banyaknya kendaraan di depot. Membangun rute dengan menelusuri tempat yang paling dekat dengan depot atau stasiun pertama, kemudian untuk rute
Gambar 5 Contoh nearest depot heuristic
9
2.8.4 Metode 2-Opt Pada dasarnya metode 2-opt ialah memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan konsumen yang berbeda. Sebagai catatan, metode 2-opt hanya dapat dilakukan jika rute baru yang dihasilkan lebih baik daripada rute awal. Algoritmanya, sebagai berikut: 1. satu rute untuk satu kendaraan, 2. hapus 2 jalur yang menghubungkan 4 konsumen, selanjutnya hubungkan kembali keempat konsumen dengan pasangan yang berbeda, 3. jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (2), 4. selesai. (ILOG 2002) Secara umum mekanisme kerja metode 2-opt adalah seperti terlihat pada Gambar 6. Input rute dan jarak awal
Hapus 2 jalur yang menghubungkan 4 konsumen berbeda
Hubungkan kembali ke pasangan konsumen berbeda
Ilustrasi dari metode 2-opt diberikan dalam Contoh 4. Contoh 4 Dalam Contoh 4 dibahas penentuan rute pengambilan sampah seperti pada Contoh 1 hanya pada konsumen 1,2,3 dengan menggunakan metode 2-opt. Langkah penentuan rute: 1. rute pada tahap awal route constructing merupakan awal dari tahap route improvement yaitu 0 2,1,3,0 dengan jarak tempuh 163 km, 2. hapus 2 jalur yang menghubungkan 4 konsumen yaitu konsumen 0 dan 2 serta konsumen 1 dan 3, 3. hubungkan konsumen 0 dan 1 serta konsumen 3 dan 2, maka diperoleh rute 0,1,2,3,0 dengan jarak tempuh sebesar 163 km, 4. rute ini memiliki jarak tempuh yang sama dari rute awal sehingga rute 0,1,2,3,0 akan mengalami perbaikan dengan menghapus jalur yang menghubungkan konsumen 1 dan 2 serta konsumen serta 0 dan 3, 5. selanjutnya hubungkan konsumen 1 dan 3 serta konsumen 2 dan 0, maka diperoleh rute 0,1,3,2,0 dengan jarak tempuh sebesar 154 km, 6. rute ini memiliki jarak tenpuh yang lebih baik dari rute pertama sehingga rute 0,1,3,2,0 dipilih sebagai rute terakhir yang mendekati optimum. Gambar 7 merupakan ilustrasi dari Contoh 4.
Tidak
Apakah jarak < rute awal Gambar 7 Contoh metode 2-Opt Ya
Improved route Gambar 6 Diagram alir metode 2-opt
2.8.5 Metode Relocate Pada metode relocate, sebuah tempat dalam satu rute dapat dipindahkan urutan kunjungannya. Dengan syarat biaya rute berkurang dan tidak melanggar kendala yang ada maka hal tersebut dapat dilakukan.
10
Metode relocate ini dapat memindahkan sebuah kunjungan pada rute yang sama ke posisi yang berbeda. Algoritmanya, sebagai berikut: 1. satu rute untuk satu kendaraan, 2. hapus 2 jalur yang menghubungkan 3 konsumen, selanjutnya hubungkan kembali keempat konsumen dengan pasangan yang berbeda, 3. jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (2), 4. selesai. (ILOG 2002) Secara umum mekanisme kerja metode relocate adalah seperti terlihat pada Gambar 6. Input rute dan jarak awal
Hapus 2 jalur yang menghubungkan 3 konsumen berbeda
Hubungkan kembali ke pasangan konsumen berbeda
Ilustrasi dari metode relocate diberikan dalam Contoh 5 Contoh 5 Dalam Contoh 5 dibahas penentuan rute pengambilan sampah seperti pada Contoh 1 hanya pada konsumen 1,2,3,4 dengan menggunakan metode relocate. Langkah penentuan rute: 1. rute pada tahap awal route constructing merupakan awal dari tahap route improvement yaitu 0,3,4,2,1,0 dengan jarak tempuh 226 km, 2. hapus jalur yang menghubungkan antara konsumen 0 dan 3 serta konsumen 3 dan 4, 3. hubungkan konsumen 0 dan 4 serta konsumen 4 dan 2, maka diperoleh rute 0,4,2,3,1,0 dengan jarak tempuh 228 km, 4. rute ini memiliki jarak tempuh yang lebih jelek dari rute awal sehingga rute 0,4,2,3,1,0 akan mengalami perbaikan dengan menghapus jalur yang menghubungkan konsumen 0 dan 4 serta konsumen serta 4 dan 2, 5. maka diperoleh rute 0,2,3,4,1,0 dengan jarak tempuh sebesar 190 km. Rute ini memiliki jarak tempuh yang lebih baik dari rute awal sehingga rute 0,4,2,3,1,0 dipilih sebagai rute terakhir yang mendekati optimum. Gambar 9 merupakan ilustrasi dari Contoh 5
Tidak
Apakah jarak < rute awal
Ya Gambar 9 Contoh metode relocate Improved route Gambar 8 Diagram alir metode relocate
2.8.6 Metode Exchange Pada metode exchange, dua tempat dapat saling dipertukarkan urutan kunjungannya. Metode ini dapat diterapkan baik pada satu rute maupun dua rute kendaraan. Selama perubahan yang terjadi tidak melanggar kendala yang ada dan dapat mengurangi biaya
11
yang dikeluarkan. Pada satu rute kendaraan, dua kunjungan yang berbeda dapat dipertukarkan urutannya. Algoritmanya, sebagai berikut: 1. satu rute untuk satu kendaraan, 2. hapus 4 jalur yang menghubungkan 6 konsumen, selanjutnya hubungkan kembali keempat konsumen dengan pasangan yang berbeda, 3. jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (2), 4. selesai. (ILOG 2002) Secara umum mekanisme kerja metode exchange adalah seperti terlihat pada Gambar 10. Input rute dan jarak awal
Hapus 4 jalur yang menghubungkan 6 konsumen berbeda
Hubungkan kembali ke pasangan konsumen berbeda
Tidak
Apakah jarak < rute awal
Ya
Improved route Gambar 10 Diagram alir metode exchange
Ilustrasi dari metode exchange diberikan dalam Contoh 6 Contoh 6 Dalam Contoh 6 dibahas penentuan rute pengambilan sampah seperti pada Contoh 1 hanya pada konsumen 1,2,3,4,5 dengan menggunakan metode exchange. Rute diawali dari depot 0 ke konsumen 4,2,3,1,5 dan kembali ke depot 0. memiliki jarak tempuh yang belum optimum yaitu 339 km maka rute perlu dilakukan perbaikan dengan metode exchange. Rute setelah mengalami perbaikan berubah menjadi depot 0 ke konsumen 1,2,3,4,5 dan berakhir di depot 0 dengan jarak tempuh 239 km. Langkah penentuan rute: 1. rute pada tahap awal route constructing merupakan awal dari tahap route improvement (metode exchange) yaitu dari 0 menuju 4,2,3,1 kemudian 5 dan kembali lagi ke 0 dengan jarak tempuh 339 km, 2. dari rute awal dapat dilakukan perbaikan dengan cara menghapus 4 jalur yang menghubungkan 6 konsumen berbeda, 3. pada rute awal yaitu 0,4,2,3,1,5,0 akan mengalami perbaikan dengan menghapus 2 jalur pertama yang menghubungkan antara konsumen 0 dan 4 serta konsumen 4 dan 2 selanjutnya hubungkan kembali pada pasangan konsumen yang berbeda. Penghapusan jalur kedua dilakukan pada jalur yang menghubungkan konsumen 3 dan 1 serta 1 dan 5 selanjutnya hubungkan kembali pada pasangan konsumen yang berbeda, 4. hubungkan konsumen 0 dan 1, 1 dan 2, 3 dan 4 serta konsumen 4 dan 5, 5. maka diperoleh rute 0,1,2,3,4,5,0 dengan jarak tempuh sebesar 239 km. Rute ini memiliki jarak tempuh yang lebih baik dari rute awal sehingga rute 0,4,2,3,1,5,0 dipilih sebagai rute terakhir yang mendekati optimum. Gambar 11 merupakan ilustrasi dari Contoh 6
12
Gambar 8 Contoh metode exchange
III DISTRIBUSI BAHAN BAKAR MINYAK DI CV KATRACO Bab ini diawali dengan penjelasan tentang ruang lingkup penelitian, pengolahan data, rumusan masalah yang terjadi di perusahaan tempat penelitian ini berlangsung dan formulasi secara matematis. Hasil dan pembahasan dari penelitian yang dilakukan terdapat pada bagian akhir bab ini. 3.1 Ruang Lingkup Penelitian dilakukan di CV KATRACO pada bagian supply chain. CV KATRACO merupakan perusahaan swasta yang berlokasi di Banjarnegara dan bergerak dalam pendistribusian bahan bakar minyak ke SPBU dan beberapa perusahaan di wilayah Jawa Tengah dan sekitarnya. Data yang digunakan meliputi rute pengiriman bahan bakar minyak di wilayah Jawa Tengah dan sekitarnya yang dilakukan oleh CV KATRACO untuk masalah VRPTW. Menggunakan metode heuristic untuk menentukan rute yang optimum bagi kendaraan. Dalam penelitian ini, pembahasan juga akan dibatasi pada proses distribusi untuk saluran SPBU di daerah Jawa Tengah dan sekitarnya. Saluran SPBU dipilih karena jumlahnya yang terbesar dibandingkan dengan saluran lain yang ada. 3.2 Pengolahan Data Kombinasi antara data sekunder dan data primer digunakan untuk mendukung kesempurnaan dari penelitian ini. Pengumpulan data dilakukan melalui wawancara dengan pihak yang terkait untuk memahami tentang proses distribusi pada perusahaan tersebut. Setelah mendapatkan .
informasi yang dibutuhkan, penelitian dilanjutkan dengan memformulasikan masalah distribusi yang ada sebagai sebuah formulasi VRPTW. Selanjutnya, digunakan program ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4, yang dijalankan dalam Microsoft Visual C++ versi 6.0, sebagai alat untuk mencari solusi dari formulasi VRPTW yang dihadapi. Data yang diperoleh dari kegiatan tersebut, antara lain: letak konsumen, permintaan konsumen waktu bongkar-muat di tempat konsumen, jumlah kendaraan, kapasitas kendaraan, jarak antarkonsumen dengan depot dan dengan konsumen lain. Sedangkan diasumsikan kecepatan kendaraan konstan, waktu buka - tutup gudang konsumen seragam yakni pada pukul 10.00 sampai dengan pukul 20.00, dimana pukul 10.00 dimisalkan sebagai 0 dan pukul 20.00 sebagai 600 dan kendaraan mampu memuat hingga 24.000 kiloliter. Langkah pertama adalah menentukan letak setiap konsumen dan mengetahui jarak dari setiap konsumen, seperti terlihat pada Lampiran 5. Langkah berikutnya, pembuatan matriks jarak yang digunakan sebagai input untuk program ILOG bersama dengan data permintaan, jumlah kendaraan, kapasitas kendaraan dan waktu bongkar-muat di setiap tempat. Penggunaan metode heuristic dengan alat bantu ILOG akan digunakan sebagai langkah terakhir. Tabel 5 merupakan data yang diperoleh dari pihak terkait yang berisi nama tempat, permintaan tiap tempat, dan waktu bongkar-muat.
13
Tabel 7 Data permintaan dan waktu bongkar-muat tiap konsumen Permintaan (kiloliter)
Waktu bongkar-muat (menit)
Katraco CV SPBU Banjarnegara SPBU Blambangan SPBU Klampok SPBU Wonosobo SPBU Kretek SPBU Banyumas 1 SPBU Banyumas 2 SPBU Banyumas 3 SPBU Temanggung 1
16000 9000 10000 5000 14000 10000 16000 8000 12000
50 20 25 20 45 25 50 40 44
10 11
SPBU Temanggung 2 SPBU Temanggung 3
10000 11000
25 38
12 13 14 15
SPBU Temanggung 4 SPBU Rawalo SPBU buntu SPBU Gombong
3000 7500 7000 10000
30 33 44 35
16 17 18 19 20
SPBU Wangon SPBU Puwokerto 1 SPBU Puwokerto 2 SPBU Puwokerto 3 SPBU Purbalingga
13000 16000 6000 7000 9000
45 60 38 40 45
No
Nama tempat
0 1 2 3 4 5 6 7 8 9
3.3 Perumusan Masalah Perusahaan melakukan pengiriman bahan bakar minyak setiap harinya. Kemudian bahan bakar minyak tersebut akan didistribusikan ke SPBU di sekitar Jawa Tengah dan sekitarnya, sebelum sampai ke tangan konsumen. Permintaan SPBU tiap harinya telah diketahui sebelumnya. Pendistribusian akan dilakukan menggunakan satu jenis kendaraan, sehingga kapasitas setiap kendaraan seragam. Selain melakukan pengiriman bahan bakar minyak, petugas juga melakukan bongkat-muat dan memindahkan bahan bakar minyak pada tempat yang telah disediakan. Biaya tetap kendaraan akan muncul bila kendaraan tersebut dipakai dalam kegiatan distribusi. Masalah yang dihadapi adalah menetapkan jalur distribusi terpendek dengan biaya minimum dengan mempertimbangkan kendala kapasitas pada kendaraan dan untuk memenuhi setiap permintaan SPBU. Asumsi yang digunakan, antara lain: semua pesanan SPBU dapat dipenuhi oleh perusahaan, kecepatan kendaraan konstan sehingga tidak ada satu hal pun yang dapat
mempercepat atau memperlambat kecepatan kendaraan. Kendaraan yang digunakan seragam, sehingga setiap kendaraan mempunyai kapasitas yang sama, jarak antarSPBU diketahui dan permintaan tiap hari SPBU diketahui. 3.4 Formulasi Masalah variabel keputusan 1, jika π dikunjungi setelah π π oleh kendaraan π π₯π,π = 0, jika selainnya 1, jika kendaraan π dioperasikan π§π = 0, jika selainnya Konstanta ππ = permintaan dari konsumen ke β π πΆπ = kapasitas k kendaraan π π‘π,π = waktu yang dibutuhkan dari konsumen i ke konsumen π dengan kendaraan π π£π = kecepatan rata β rata kendaraan π π‘π = waktu kedatangan pada tempat π ππ = waktu buka gudang pada tempat π ππ = waktu tutup gudang tempat π
14
π€π = biaya bila kendaraan π digunakan ππ,π = jarak dari konsumen π ke konsumen π Fungsi objektif 12
min π β
21
21 π π₯π,π ππ,π
π€π π§π + π =1
(1)
π=1 π =1
kendala-kendala ο· Konsumen 21
12 π π₯π,π = 1 ; βπ = 2,3, β¦ ,21
(2)
π π₯π,π = 1 ; βπ = 2,3, β¦ ,21
(3)
π=1 π=1 21 12
π=1 π=1
ο· Depot 21
π π₯1,π = 1 ; βπ = 1,2, β¦ 12
(4)
π π₯π,1 = 1 ; βπ = 1,2, β¦ 12
(5)
π =2 21
π=2
ο· Kekontinuan rute 21
21 π π₯π,π’
π₯π’π ,π
=
π=2
(6)
π=2
βπ = 1,2, β¦ 12 βπ’ = 1,2, β¦ 21 ο· Kapasitas 21
21 π ππ π₯π,π β€ πΆπ ; βπ = 1,2, β¦ ,12
π=1 π =1 π β€ π§π π₯π,π
βπ,π = 1,2, β¦ ,21 βπ = 1,2, β¦ ,12 π = ππ,π π£π π‘π,π βπ,π = 1,2, β¦ ,21 βπ = 1,2, β¦ ,12 ππ,π = ππ ,π ; βπ,π = 1,2, β¦ ,21 21
(7) (8)
(9)
(10)
21 π π₯π,π β€ πΏ β 1 ; βπΏ β 1,2, β¦ 21 (11)
π=1 π =1
ο· Time windows ππ β€ π‘π β€ ππ ; βπ = 1,2, β¦ ,21 π‘π + ππ + π‘ππ,π < π‘π ; βπ,π = 1,2, β¦ ,21 βπ = 1,2, β¦ ,12 π§π β {0,1} ; βπ = 1,2, β¦ ,12 π π₯π,π β 0,1 ; βπ = 1,2, β¦ ,12 βπ,π = 1,2, β¦ ,21
(12) (13) (14) (15)
Fungsi objektif (1) pada model di atas adalah meminimumkan banyaknya kendaraan yang berjumlah 12 dan meminimumkan jarak tempuh kendaraan untuk melayani 21 konsumen. Fungsi objektif tersebut
dihadapkan pada kendala-kendala, sebagai berikut: pada kendala (2) dan (3) dipastikan bahwa setiap konsumen yang ada akan dilayani oleh tepat satu kendaraan. Kendala (4) dan (5) akan memastikan tersedianya kendaraan untuk melayani rute yang ada dan juga untuk memastikan kendaraan pergi dan kembali dari depot. Pada kendala (6) akan dipastikan kontinuitas rute kendaraan artinya memastikan bahwa kendaraan yang masuk ke suatu kota harus meninggalkan kota tersebut, sedangkan kendala (7) menggambarkan bahwa jumlah permintaan untuk satu rute tidak melebihi kapasitas kendaraan yang beroperasi. Selanjutnya, pada kendala (8) dipastikan bahwa tidak akan nada konsumen yang dilayani oleh kendaraan yang tidak aktif. Kendala (9) memperlihatkan hubungan antara jarak, kecepatan dan waktu tempuh kendaraan, jarak dan waktu tempuh berbanding lurus. Kendala (10) menunjukkan bahwa jarak dari i ke j sama dengan jarak dari j ke i, sedangkan kendala (11) memastikan tidak ada subtour pada formulasi yang ada. L adalah subtour dari setiap rute dari kota-kota 1,2,...,21 Berikutnya, kendala (12) dan (13) berkaitan dengan waktu pelayanan. Pada kendala (12) dipastikan waktu kedatangan kendaraan di tempat konsumen berada di antara waktu buka dan tutup gudang, sedangkan pada kendala (13) memastikan kendaraan akan berada di j pada saat kendaraan berangkat dari i ditambah dengan waktu service pada i dan waktu tempuh dari i ke j. 3.5 Hasil dan Pembahasan Pada subbab ini akan diperlihatkan hasil simulasi dari masalah yang diteliti. Kemudian hasil tersebut akan dicari metode yang paling baik dan akan dibandingkan dengan keadaan yang terjadi di lapangan saat ini. Dari Tabel 6 dan 7 dapat disimpulkan bahwa masing-masing rute pada hasil simulasi tahap route constructing tiap metode memiliki jarak tempuh yang bebeda. Pada metode sweep heuristic memiliki total jarak tempuh lebih pendek pada kendaraan yang digunakan. Pada hasil simulasi total jarak yang ditempuh kesepuluh kendaran mencapai 415.8533 kilometer, sedangkan total jarak pada metode savings heuristic adalah 430.962 kilometer dengan menggunakan 9 kendaraan dan metode nearest depot heuristic adalah 451.639 kilometer dengan menggunakan 10 kendaraan. Dari perbandingan setiap metode dapat terlihat bahwa metode sweep heuristic
15
memiliki total jarak tempuh terpendek. Jika dibandingkan dengan total jarak tempuh kendaraan saat ini, yaitu 736.2997 kilometer, metode sweep heuristic memiliki total jarak tempuh lebih pendek. Pada tahap route constructing memiliki jarak tempuh yang belum optimum maka perlu mengalami perbaikan pada tahap route improvement di mana pada savings heuristic menggunakan relocate yang menghasilkan total jarak tempuh 428.7705 kilometer, pada sweep heuristic menggunakan 2-opt yang
menghasilkan total jarak tempuh 415.2911 kilometer, dan pada nearest depot heuristic menggunakan exchange yang menghasilkan total jarak tempuh 450.6885 kilometer. Total jarak tempuh memiliki pengaruh besar terhadap pengeluaran perusahaan dalam proses distribusi, semakin pendek jarak tempuh maka biaya yang dikeluarkan dalam pendistribusian barang hasil produksi akan semakin kecil dan semakin panjang jarak tempuh maka biaya yang dikeluarkan semakin besar.
Tabel 8 Hasil simulasi tahap route constructing Savings Sweep No Jarak Muatan Jarak Muatan (km) (kl) (km) (kl) 1 35.28 22000 50.86 19500
Nearest depot Jarak Muatan (km) (kl)
Saat ini Jarak Muatan (km) (kl)
2 3 4 5 6
44.74 51.71 35.69 49.28 44.26
19000 23500 17000 24000 23000
43.04 25.96 32.01 36.07 49.34
21000 21000 22000 23000 22000
86.55 61.71 46.76 43.27 33.50 29.68
7 8
60.18 51.31
24000 23000
35.30 52.28
20000 23000
25.96 29.12
21000 16000
67.90 58.47
16000 22000
9 10
58.51
24000
45.71 45.29
22000 6000
49.71 45.39
20000 9000
71.77 74.29
14000 16000
71.83 41.27 736.30
16000 13000
11 12 Total
430.96
keterangan:
415.85 No km kl
: kendaraan 1,2,β¦,dst : kilometer : kiloliter
451.64
23000 23500 21000 21000 21000 24000
60.54 38.50 63.54 55.68 75.66 56.85
11000 16000 14000 14500 15000 19000
16
Tabel 9 Hasil simulasi tahap route improvement No
Relocate (Savings) (km)
1
keterangan:
Exchange (Nearestdepot) (km)
35.2833 44.7428 51.7056 35.6864 49.2809 44.2594 60.1812 51.3094 56.3215
50.2966 43.0438 25.9599 32.0065 36.066 49.3377 35.2996 52.2787 45.7143 45.288
85.595 61.7068 46.755 43.267 33.498 29.6803 25.9599 29.1199 49.7147 45.3919
428.7705
415.2911
450.6885
2 3 4 5 6 7 8 9 10 11 12 Total
2-Opt (Sweep) (km)
No km
: kendaraan 1,2,β¦,dst : kilometer
Dari Tabel 8,9,10 merupakan hasil simulasi menggunakan metode savings heuristic kendaraan pertama, kedua dan ketiga. Setiap kendaraan membawa sejumlah bahan bakar minyak sesuai dengan permintaan dari kapasitas maksimum 24000 kiloliter yang dapat dibawa dalam satu kali pengiriman. Pada kendaraan pertama rute yang dilalui meliputi depot, konsumen ke-10, konsumen ke-9 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 35.2833 kilometer dan banyaknya produk yang dibawa sebanyak 22000 kiloliter, serta waktu tiba kendaraan pertama di konsumen 10 yaitu antara 10.18
dan 18.33 satuan waktu dan seterusnya sampai kendaraan kembali ke depot. Sedangkan kendaraan kedua rute yang dilalui meliputi depot, konsumen ke-11, konsumen ke-8 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 44.7428 kilometer dan banyaknya produk yang dibawa sebanyak 19000 kiloliter. Kendaraan ketiga rute yang dilalui meliputi depot, konsumen ke-13, konsumen ke-7 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 51.7056 kilometer dan banyaknya produk yang dibawa sebanyak 23500 kiloliter dan seterusnya sampai kendaraan ke sembilan (Lampiran 1).
Tabel 10 Hasil simulasi menggunakan metode savings heuristic kendaraan pertama Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 10 9 0
Depot SPBU Temanggung 2 SPBU Temanggung 1 Depot
0 10.18- 18.33
0 17.6358
0 10000
10.46- 19.02
21.4458
12000
11.44 β 20.00
35.2833
0
17
Tabel 11 Hasil simulasi menggunakan metode savings heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 11 8 0
Depot SPBU Temanggung 3 SPBU Banyumas 3 Depot
0 10.21 - 18.18
0 21.4521
0 11000
11.07 β 19.04
28.7454
8000
12.02 β 20.00
44.7428
0
Tabel 12 Hasil simulasi menggunakan metode savings heuristic kendaraan ketiga Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 13 7 0
Depot SPBU Rawalo SPBU Banyumas 2 Depot
0 10.25 β 18.10 11.10 β 18.55
0 25.0952 37.1456
0 7500 120.000
12.14 β 20.00
51.7056
0
Dari Tabel 11,12,13 merupakan hasil simulasi menggunakan metode sweep heuristic kendaraan pertama, kedua dan ketiga. Setiap kendaraan membawa sejumlah bahan bakar minyak sesuai dengan permintaan dari kapasitas maksimum 24000 kiloliter yang dapat dibawa dalam satu kali pengiriman. Pada kendaraan pertama rute yang dilalui meliputi depot, konsumen ke-2, konsumen ke13, konsumen ke-12 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 50.2966 kilometer dan banyaknya produk yang dibawa sebanyak 19500 kiloliter, serta waktu tiba kendaraan pertama di konsumen 2 yaitu antara 10.13 dan 18.00 satuan waktu dan
seterusnya sampai kendaraan kembali ke depot. Sedangkan kendaraan kedua rute yang dilalui meliputi depot, konsumen ke-11, konsumen ke-3 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 43.0438 kilometer dan banyaknya produk yang dibawa sebanyak 21000 kiloliter. Kendaraan ketiga rute yang dilalui meliputi depot, konsumen ke-1, konsumen ke-4 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 25.9599 kilometer dan banyaknya produk yang dibawa sebanyak 21000 kiloliter dan seterusnya sampai kendaraan ke sepuluh (Lampiran 2).
Tabel 13 Hasil simulasi menggunakan metode sweep heuristic kendaraan pertama Kode
Nama
0 2
Depot SPBU Blambangan SPBU Rawalo SPBU Temanggung 4 Depot
13 12 0
Waktu tiba
Jarak tempuh
Permintaan
( jam )
(kilometer)
(crate)
10.13 - 18.00
0 13.5687
0 9000
10.45 β 18.31 11.19 - 19.07
25.185 26.8999
7500 3000
12.13 β 20.00
50.2966
0
18
Tabel 14 Hasil simulasi menggunakan metode sweep heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 11 3 0
Depot SPBU Temanggung 3 SPBU Klampok Depot
10.21 β 18.35
0 21.4521
0 11000
11.07 β 19.21
29.5877
10000
11.46 β 20.00
43.0438
0
Tabel 15 Hasil simulasi menggunakan metode sweep heuristic kendaraan ketiga Kode Nama Waktu tiba Jarak tempuh Permintaan 0 1 4 0
Depot SPBU Banjarnegara SPBU Wonosobo Depot
(jam)
(kilometer)
(crate)
10.12 β 18.36
0 12.8137
0 120.000
11.03 β 19.27
13.3819
5000
11.36 β 20.00
25.9599
0
Dari Tabel 14,15,16 merupakan hasil simulasi menggunakan metode nearest depot heuristic kendaraan pertama, kedua, ketiga. Setiap kendaraan membawa sejumlah bahan bakar minyak sesuai dengan permintaan dari kapasitas maksimum 24000 kiloliter yang dapat dibawa dalam satu kali pengiriman. Pada kendaraan pertama rute yang dilalui meliputi depot, konsumen ke-19, konsumen ke-14, konsumen ke-18, konsumen ke-12 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 85.595 kilometer dan banyaknya produk yang dibawa sebanyak 23000 kiloliter, serta waktu tiba kendaraan pertama di konsumen 19 yaitu antara 10.24 dan 16.26 satuan waktu dan seterusnya sampai
kendaraan kembali ke depot dan berlaku untuk kendaraan kedua sampai kendaraan kesepuluh. Sedangkan kendaraan kedua rute yang dilalui meliputi depot, konsumen ke-17, konsumen ke-13 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 61.7068 kilometer dan banyaknya produk yang dibawa sebanyak 23500 kiloliter. Kendaraan ketiga rute yang dilalui meliputi depot, konsumen ke-11, konsumen ke-10 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 46.755 kilometer dan banyaknya produk yang dibawa sebanyak 21000 kiloliter dan seterusnya sampai kendaraan ke sepuluh (Lampiran 3).
Tabel 16 Hasil simulasi menggunakan metode nearest depot heuristic kendaraan pertama Kode
Nama
0 19
Depot SPBU Puwokerto 3 SPBU buntu SPBU Puwokerto 2 SPBU Temanggung 4 Depot
14 18 12 0
Waktu tiba
Jarak tempuh
Permintaan
( jam )
(kilometer)
(crate)
10.24 β 16.26
0 24.0754
0 7000
11.14 β 17.16 12.07 - 18.09
33.6003 43.5297
7000 20.000
13.04 β 19.06
62.1983
3000
13.57 - 20.00
85.595
0
19
Tabel 17 Hasil simulasi menggunakan metode nearest depot heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 17 13 0
Depot SPBU Puwokerto 1 SPBU Rawalo Depot
10.23 β 17.48
0 23.2961
0 120.000
11.37 β 19.02 12.34 - 20.00
36.6116 61.7068
7500 0
Tabel 18 Hasil simulasi menggunakan metode nearest depot heuristic kendaraan ketiga Waktu tiba Jarak tempuh Permintaan Kode Nama (jam) (kilometer) (crate) 0 11 10 0
Depot SPBU Temanggung 3 SPBU Temanggung 2 Depot
10.21 β 18.32
0 21.4521
0 11000
11.07 β 19.17
29.1192
10000
11.49 - 20.00
46.755
0
Tabel 17,18,19 merupakan hasil rute saat ini kendaraan pertama, kedua dan ketiga. Kendaraan pertama akan menempuh jarak sepanjang 60.5436 kilometer dan membawa 14000 kiloliter dari 24000 kiloliter yang diperkenankan. Kendaraan pertama melayani rute depot, konsumen ke-2, konsumen ke-4 dan kembali ke depot. Rute untuk kendaraan kedua meliputi depot, konsumen ke-1 dan kembali ke depot. Dengan membawa 16000
kiloliter dan menempuh jarak sepanjang 38.495 kilometer untuk rute tersebut. Pada rute berikutnya, kendaraan ketiga dijadwalkan akan membawa sebanyak 14000 kiloliter dan menempuh perjalanan sepanjang 63.5430 kilometer. Rute tersebut meliputi depot, konsumen ke-12, konsumen ke-11 dan kembali ke depot dan seterusnya sampai kendaraan ke dua belas ( Lampiran 4).
Tabel 19 Hasil rute saat ini kendaraan pertama Jarak tempuh Kode Nama (kilometer) 0 2 4 0
Depot SPBU Blambangan SPBU Wonosobo Depot
Depot SPBU Banjarnegara Depot
(crate)
0 42.7528
0 9000
47.6032 60.5436
5000 0
Tabel 20 Hasil rute saat ini kendaraan kedua Jarak tempuh Kode Nama (kilometer) 0 1 0
Permintaan
0 38.4957 38.4957
Permintaan (crate) 0 16000 0
20
Tabel 21 Hasil rute saat ini kendaraan ketiga Kode Nama Jarak tempuh (kilometer) 0 12 11 0
Depot SPBU Temanggung 4 SPBU Temanggung 3 Depot
Permintaan (crate)
0 23.3967 21.4521 63.5430
0 3000 11000 0
IV SIMPULAN Berdasarkan penelitian yang dilakukan dapat diambil beberapa kesimpulan, antara lain: 1. formulasi VRPTW dalam matematika dapat digunakan untuk menyelesaikan masalah penentuan rute distribusi, 2. penggunaan formulasi VRPTW dengan metode heuristik memastikan semua konsumen dilayani permintaannya dan tidak ada keterlambatan dalam pengirimannya, 3. menetapkan bahwa metode Sweep Heuristic memiliki solusi paling baik pada kasus ini dibandingkan dengan metode Savings Heuristic dan Nearest
4.
5.
depot heuristic yaitu total jarak tempuh terpendek 415.2911 kilometer dan dibutuhkan minimal sepuluh kendaraan untuk menangani 21 SPBU dengan memenuhi semua syarat yang berlaku, rute pengiriman hasil simulasi memiliki total jarak tempuh lebih pendek daripada rute yang diterapkan pada saat ini, lebih banyak konsumen yang dikunjungi dalam satu rute sehingga dapat memaksimumkan barang yang dibawa oleh kendaraan.
DAFTAR PUSTAKA Ayers B. 2001. Handbook of Supply Chain Management. USA : st.Lucie Press. Cordeau J-F, Gendreau M, Laporte G, Potvin JY, Semet F. 2002. A Guide to Vehicle Routing Heuristics. Journal of Operation Research Soceity 53: 512-522 Hoffman K & Padberg M. 2009. Traveling Salesman Problem. http://iris.gmu.edu/ ~khoffman/papers/trav_salesman.html. [8 Feb 2009]. Hugos M. 2003. Essentials of Supply Chain Management. Canada : John Wiley & Sons,Inc Kritikos MN & Ioannou G. 2004. A synthesis of assignment and heuristic solutions for vehicle routing with time windows. Journal of the Operational Research Society (2004) 55, 2β11. Larsen Jesper. 1999. Vehicle routing with time windows finding optimal solutions efficiently. DORSnyt (engl.)(1999), no. 116
Machado P, Tavares J, Pereira BF, Costa E. 2002. Vehicle Routing Problem: Doing it The Evolution Way. Raditya A. 2009. Penggunaan Metode Heuristik Dalam Vehicle Routing Problem Untuk Meminimumkan Jumlah Dan Jarak Tempuh Kendaraan (Implementasi di PT. Nippon Indosari Corpindo) [skripsi]. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Sutapa NI, Widyadana AGI, Christine. 2003. Studi tentang Traveling Salesman Problem dan Vehicle Routing Problem dengan Time windows. Jurusan Teknik Industri, Universitas Petra, Surabaya Winston WL. 2004. Operation Research Application and Algorithm. Brooks/ColeThompson Learning.
21
LAMPIRAN
Lampiran 1
22
Tabel 7 Hasil simulasi menggunakan metode Savings Heuristic kendaraan pertama Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
0
0
0
10 9 0
Konsumen 10 Konsumen 9 Depot
17.6358 - 513.352 46.4458 - 542.163 104.283 - 600
17.6358 21.4458 35.2833
10000 12000 0
Tabel 8 Hasil simulasi menggunakan metode Savings Heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 11 8 0
Depot Konsumen 11 Konsumen 8 Depot
0 21.4521 - 498.709 66.7454 - 544.003 122.743 - 600
0 21.4521 28.7454 44.7428
0 11000 8000 0
Tabel 9 Hasil simulasi menggunakan metode Savings Heuristic kendaraan ketiga Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 13 7 0
Depot Konsumen 13 Konsumen 7 Depot
0 25.0952 - 490.39 70.1456 - 535.44 134.706 - 600
0 25.0952 37.1456 51.7056
0 7500 16000 0
Tabel 10 Hasil simulasi menggunakan metode Savings Heuristic kendaraan keempat Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 14 6 0
Depot Konsumen 14 Konsumen 6 Depot
0 17.8421 - 513.156 65.3691 - 560.683 104.686 - 600
0 17.8421 21.3691 35.6864
0 7000 10000 0
Tabel 11 Hasil simulasi menggunakan metode Savings Heuristic kendaraan kelima Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
0
0
0
15 5 0
Konsumen 15 Konsumen 5 Depot
24.6383 - 495.3 70.8836 - 541.603 129.281 - 600
24.6383 35.8836 49.2809
10000 14000 0
Tabel 12 Hasil simulasi menggunakan metode Savings Heuristic kendaraan keenam
23
Kode
Nama
Waktu tiba
Jarak tempuh
Permintaan
(menit)
(kilometer)
(crate)
0
Depot
0
0
0
16 3 0
Konsumen 16 Konsumen 3 Depot
20.635 - 506.376 75.8034 - 561.544 114.259 - 600
20.635 30.8034 44.2594
13000 10000 0
Tabel 13 Hasil simulasi menggunakan metode Savings Heuristic kendaraan ketujuh Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 12 17 4
Depot Konsumen 12 Konsumen 17 Konsumen 4
23.3967 - 453.2 65.917 - 495.736 137.603 - 567.422
0 23.3967 35.917 47.6032
0 3000 16000 5000
0
Depot
170.181 - 600
60.1812
0
Tabel 14 Hasil simulasi menggunakan metode Savings Heuristic kendaraan kedelapan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 19 1 0
Depot Konsumen 19 Konsumen 1 Depot
24.0754 - 482.766 78.4957 - 537.186 141.309 - 600
0 24.0754 38.4957 51.3094
0 7000 16000 0
Tabel 15 Hasil simulasi menggunakan metode Savings Heuristic kendaraan kesembilan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 18 20 2 0
Depot Konsumen 18 Konsumen 20 Konsumen 2 Depot
Lampiran 2
22.644 - 463.32 65.6123 - 506.291 125.753 - 566.431 159.321 - 600
0 22.644 27.6123 42.7528 56.3215
0 6000 9000 9000 0
24
Tabel 16 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan pertama Kode
Nama
0
Depot
2 13 12 0
Konsumen 2 Konsumen 13 Konsumen 12 Depot
Waktu tiba
Jarak tempuh
Permintaan
(menit)
(kilometer)
(crate)
0
0
13.5687 25.185 26.8999 50.2966
9000 7500 3000 0
13.5687 - 480.272 45.185 - 511.888 79.8999 - 546.603 133.297 - 600
Tabel 17 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
11 3 0
Konsumen 11 Konsumen 3 Depot
21.4521 - 515.408 67.5877 - 561.544 106.044 - 600
0
0
21.4521 29.5877 43.0438
11000 10000 0
Tabel 18 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan ketiga Kode Nama Waktu tiba Jarak tempuh Permintaan 0 1 4 0
Depot Konsumen 1 Konsumen 4 Depot
(menit)
(kilometer)
(crate)
12.8137 - 516.854 63.3819 - 567.422 95.9599 - 600
0 12.8137 13.3819 25.9599
0 16000 5000 0
Tabel 19 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan keempat Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
5 8 0
Konsumen 5 Konsumen 8 Depot
13.3973 - 496.391 61.0091 - 544.003 117.007 - 600
0
0
13.3973 16.0091 32.0065
14000 8000 0
Tabel 20 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan kelima Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 7 14 0
Depot Konsumen 7 Konsumen 14 Depot
14.5599 - 484.494 68.2239 - 538.158 130.066 - 600
0 14.5599 18.2239 36.066
Tabel 21 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan keenam
0 16.000 7000 0
25
Kode
Nama
0 15 9 0
Depot Konsumen 15 Konsumen 9 Depot
Waktu tiba
Jarak tempuh
Permintaan
(menit)
(kilometer)
(crate)
24.6383 - 496.301 70.5002 - 542.163 128.338 - 600
0 24.6383 35.5002 49.3377
0 10000 12000 0
Tabel 22 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan ketujuh Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 10 6 0
Depot Konsumen 10 Konsumen 6 Depot
17.6358 - 532.336 45.9823 - 560.683 85.2996 - 600
0 17.6358 20.9823 35.2996
0 10000 10000 0
Tabel 23 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan kedelapan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 17 19 0
Depot Konsumen 17 Konsumen 1 Depot
23.2961 - 471.017 88.2032 - 535.925 152.279 - 600
0 23.2961 28.2032 52.2787
0 16000 7000 0
Tabel 24 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan kesembilan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 16 20 0
Depot Konsumen 16 Konsumen 20 Depot
20.635 - 484.921 68.0183 - 532.304 135.714 - 600
0 20.635 23.0183 45.7143
0 13000 9000 0
Tabel 25 Hasil simulasi menggunakan metode Sweep Heuristic kendaraan kesepuluh Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 18
Depot Konsumen 18
0
Depot
Lampiran 3
22.644 - 539.356
0 22.644
0 6000
83.288 - 600
45.288
0
26
Tabel 26 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan pertama Kode
Nama
0 19 14 18 12 0
Depot Konsumen 19 Konsumen 14 Konsumen 18 Konsumen 12 Depot
Waktu tiba
Jarak tempuh
Permintaan
(menit)
(kilometer)
(crate)
24.0754 - 386.48 73.6003 - 436.005 127.53 - 489.935 184.198 - 546.603 237.595 - 600
0 24.0754 33.6003 43.5297 62.1983 85.595
0 7000 7000 6000 3000 0
Tabel 27 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kedua Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 17 13 0
Depot Konsumen 17 Konsumen 13 Depot
23.2961 - 468.589 96.6116 - 541.905 154.707 - 600
0 23.2961 36.6116 61.7068
0 16000 7500 0
Tabel 28 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan ketiga Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 11 10 0
Depot Konsumen 11 Konsumen 10 Depot
21.4521 - 511.697 67.1192 - 557.364 109.755 - 600
0 21.4521 29.1192 46.755
0 11000 10000 0
Tabel 29 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan keempat Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 16
Depot Konsumen 16
8 0
Konsumen 8 Depot
20.635 - 492.368
0 20.635
0 13000
72.2696 - 544.003 128.267 - 600
27.2696 43.267
8000 0
Tabel 30 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kelima Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
9 2 0
Konsumen 9 Konsumen 2 Depot
13.8375 - 516.34 63.9293 - 566.431 97.498 - 600
0
0
13.8375 19.9293 33.498
12.000 9000 0
Tabel 31 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan keenam
27
Kode
Nama
0 6 5 0
Depot Konsumen 6 Konsumen 9 Depot
Waktu tiba
Jarak tempuh
Permintaan
(menit)
(kilometer)
(crate)
14.3173 - 514.637 41.283 - 541.603 99.6803 - 600
0 14.3173 16.283 29.6803
0 10000 14000 0
Tabel 32 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan ketujuh Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 1 4 0
Depot Konsumen 1 Konsumen 4 Depot
12.8137 - 516.854 63.3819 - 567.422 95.9599 - 600
0 12.8137 13.3819 25.9599
0 16000 5000 0
Tabel 33 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kedelapan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0
Depot
7 0
Konsumen 7 Depot
14.5599 - 535.44 79.1199 - 600
0
0
14.5599 29.1199
16000 0
Tabel 34 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kesembilan Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 15 3 0
Depot Konsumen 16 Konsumen 3 Depot
24.6383 - 514.924 71.2586 - 561.544 109.715 - 600
0 24.6383 36.2586 49.7147
0 10000 10000 0
Tabel 35 Hasil simulasi menggunakan metode nearestdepot heuristic kendaraan kesepuluh Waktu tiba Jarak tempuh Permintaan Kode Nama (menit) (kilometer) (crate) 0 20 0
Depot Konsumen 20 Depot
22.6959 - 532.304 90.3919 - 600
0 22.6959 45.3919
0 9000 0
28
Lampiran 4 Tabel 36 Hasil rute saat ini kendaraan pertama Jarak tempuh Kode Nama (kilometer) 0 2 4 0
Depot Konsumen 2 Konsumen 4 Depot
0 42.7528 47.6032 60.5436
Tabel 37 Hasil rute saat ini kendaraan kedua Jarak tempuh Kode Nama (kilometer) 0 1 0
Depot Konsumen 1 Depot
0 38.4957 38.4957
Tabel 38 Hasil rute saat ini kendaraan ketiga Kode Nama Jarak tempuh (kilometer) 0 12 11 0
Depot Konsumen 12 Konsumen 11 Depot
0 23.3967 21.4521 63.5430
Tabel 39 Hasil rute saat ini kendaraan keempat Jarak tempuh Kode Nama (kilometer)
Permintaan (crate) 0 9000 5000 0
Permintaan (crate) 0 16000 0
Permintaan (crate) 0 3000 11000 0
Permintaan (crate)
0 13
Depot Konsumen 13
0 25.0952
0 7500
14 0
Konsumen 14 Depot
17.8421 55.6776
7000 0
Tabel 40 Hasil rute saat ini kendaraan kelima Jarak tempuh Kode Nama (kilometer)
Permintaan (crate)
0
Depot
0
0
8 19 0
Konsumen 8 Konsumen 19 Depot
28.7454 24.0754 75.6573
8000 7000 0
29
Tabel 41 Hasil rute saat ini kendaraan keenam Jarak tempuh Kode Nama (kilometer) 0 15 20 0
Depot Konsumen 15 Konsumen 20 Depot
0 24.6383 27.6123 56.8467
Tabel 42 Hasil rute saat ini kendaraan ketujuh Jarak tempuh Kode Nama (kilometer) 0 18 10 0
Depot Konsumen 18 Konsumen 10 Depot
0 22.644 17.6358 67.90
Tabel 43 Hasil rute saat ini kendaraan kedelapan Jarak tempuh Kode Nama (kilometer)
Permintaan (crate) 0 10000 9000 0
Permintaan (crate) 0 6000 10000 0
Permintaan (crate)
0
Depot
0
0
6 9 0
Konsumen 6 Konsumen 9 Depot
21.3691 21.4458 58.4734
10000 12000 0
Tabel 44 Hasil rute saat ini kendaraan kesembilan Jarak tempuh Kode Nama (kilometer) 0 5 0
Depot Konsumen 5 Depot
0 35.8836 71.7672
Tabel 45 Hasil rute saat ini kendaraan kesepuluh Jarak tempuh Kode Nama (kilometer) 0 7 0
Depot Konsumen 7 Depot
0 37.1456 74.2912
Tabel 46 Hasil rute saat ini kendaraan kesebelas Jarak tempuh Kode Nama (kilometer) 0 17 0
Depot Konsumen 17 Depot
0 35.917 71.834
Permintaan (crate) 0 14000 0
Permintaan (crate) 0 16000 0
Permintaan (crate) 0 16000 0
30
Tabel 47 Hasil rute saat ini kendaraan keduabelas Jarak tempuh Kode Nama (kilometer) 0 16 0
Depot Konsumen 16 Depot
0 20.635 41.27
Permintaan (crate) 0 13000 0
31
Lampiran 5 Matrik jarak saat ini km
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
0
0.00
12.81
13.57
13.46
12.58
13.40
14.32
14.56
16.00
13.84
17.6
21.5
23.4
25.1
17.8
24.6
20.6
23.3
22.6
24.1
22.70
0.00
8.76
3.00
0.57
2.16
6.00
4.32
4.32
4.56
5.88
11.40
13.32
14.88
7.08
12.84
12.48
4.91
13.32
14.42
14.35
0.00
6.45
8.28
8.88
10.44
6.60
6.60
6.09
7.92
7.56
10.48
11.62
9.12
11.64
13.56
16.44
17.28
17.35
15.14
0.00
4.00
1.56
4.92
4.56
4.32
3.36
6.00
8.14
10.80
12.36
7.20
11.62
10.17
15.84
9.72
17.59
14.47
0.00
2.60
4.44
2.76
2.76
3.00
4.32
9.84
11.76
13.08
5.40
10.08
10.92
11.69
11.76
15.91
12.79
0.00
1.97
2.16
2.61
2.40
3.72
9.24
11.16
12.48
4.92
11.25
10.32
11.64
11.16
15.31
12.19
0.00
4.08
3.84
2.88
3.35
10.92
12.84
14.40
3.53
11.40
10.80
14.64
8.88
12.36
13.99
0.00
3.23
1.20
1.68
6.84
8.76
12.05
3.66
7.32
6.96
9.60
9.96
13.27
10.15
0.00
2.80
1.68
7.29
9.00
10.56
2.88
7.56
6.63
9.60
9.72
13.27
10.15
0.00
3.81
8.04
9.96
11.52
3.84
10.86
7.92
10.56
8.76
12.24
11.11
0.00
7.67
10.44
12.00
1.20
6.96
5.28
8.40
9.60
11.59
8.47
0.00
1.92
3.48
7.32
8.16
10.08
13.56
14.40
17.83
14.71
0.00
1.71
9.24
5.16
11.04
12.52
18.67
16.03
12.91
0.00
10.80
6.48
12.60
13.32
21.67
17.11
13.99
0.00
5.76
4.08
6.72
9.93
9.52
7.27
0.00
5.88
6.36
10.20
11.71
7.75
0.00
3.84
4.32
5.83
2.38
0.00
8.16
4.91
5.28
0.00
3.48
4.97
0.00
3.12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0.00
32
Lampiran 6 M-File Mathlab consumer = {'0','1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20'}; D=[0.00 17.30 12.24 16.20 13.00 14.06 18.00 13.00 16.76 12.45 19.65 22.90 23.30 25.10 18.00 25.80 19.01 22.50 25.80 23.40 22.00; 17.30 0.00 8.76 3.00 1.56 2.16 6.00 4.32 4.32 4.56 5.88 11.40 13.32 14.88 7.08 12.84 12.48 13.92 13.32 17.47 14.35; 12.24 8.76 0.00 6.45 8.28 8.88 10.44 6.60 6.60 7.56 7.92 7.56 9.48 11.04 9.12 11.64 13.56 16.44 17.28 17.35 16.39; 16.20 3.00 6.45 0.00 4.00 1.56 4.92 4.56 4.32 3.36 6.00 8.88 10.80 12.36 7.20 9.96 15.12 15.84 9.72 17.59 14.47; 13.00 1.56 8.28 4.00 0.00 2.60 4.44 2.76 2.76 3.00 4.32 9.84 11.76 13.08 5.40 10.08 10.92 12.00 11.76 15.91 12.79; 14.06 2.16 8.88 1.56 2.60 0.00 3.84 2.16 2.16 2.40 3.72 9.24 11.16 12.48 4.92 9.48 10.32 11.64 11.16 15.31 12.19; 18.00 6.00 10.44 4.92 4.44 3.84 0.00 4.08 3.84 2.88 5.52 10.92 12.84 14.40 6.72 11.40 10.80 14.64 8.88 12.36 13.99; 13.00 4.32 6.60 4.56 2.76 2.16 4.08 0.00 3.23 1.20 1.68 6.84 8.76 10.32 2.88 7.32 6.96 9.60 9.96 13.27 10.15; 16.76 4.32 6.60 4.32 2.76 2.16 3.84 3.23 0.00 2.80 1.68 7.08 9.00 10.56 2.88 7.56 6.96 9.60 9.72 13.27 10.15; 12.45 4.56 7.56 3.36 3.00 2.40 2.88 1.20 2.80 0.00 2.64 8.04 9.96 11.52 3.84 8.52 7.92 10.56 8.76 12.24 11.11; 19.65 5.88 7.92 6.00 4.32 3.72 5.52 1.68 1.68 2.64 0.00 8.52 10.44 12.00 1.20 6.96 5.28 8.40 9.60 11.59 8.47; 22.90 11.40 7.56 8.88 9.84 9.24 10.92 6.84 7.08 8.04 8.52 0.00 1.92 3.48 7.32 8.16 10.08 13.56 14.40 17.83 14.71; 23.30 13.32 9.48 10.80 11.76 11.16 12.84 8.76 9.00 9.96 10.44 1.92 0.00 1.56 9.24 5.16 11.04 12.00 20.78 16.03 12.91; 25.10 14.88 11.04 12.36 13.08 12.48 14.40 10.32 10.56 11.52 12.00 3.48 1.56 0.00 10.80 6.48 12.60 11.52 21.67 17.11 13.99; 18.00 7.08 9.12 7.20 5.40 4.92 6.72 2.88 2.88 3.84 1.20 7.32 9.24 10.80 0.00 5.76 4.08 6.72 8.40 10.39 7.27; 25.80 12.84 11.64 9.96 10.08 9.48 11.40 7.32 7.56 8.52 6.96 8.16 5.16 6.48 5.76 0.00 5.88 6.36 10.20 11.71 7.75; 19.01 12.48 13.56 15.12 10.92 10.32 10.80 6.96 6.96 7.92 5.28 10.08 11.04 12.60 4.08 5.88 0.00 3.84 4.32 5.83 6.55; 22.50 13.92 16.44 15.84 12.00 11.64 14.64 9.60 9.60 10.56 8.40 13.56 12.00 11.52 6.72 6.36 3.84 0.00 8.16 6.36 5.28; 25.80 13.32 17.28 9.72 11.76 11.16 8.88 9.96 9.72 8.76 9.60 14.40 20.78 21.67 8.40 10.20 4.32 8.16 0.00 3.48 6.60; 23.40 17.47 17.35 17.59 15.91 15.31 12.36 13.27 13.27 12.24 11.59 17.83 16.03 17.11 10.39 11.71 5.83 6.36 3.48 0.00 3.12; 22.00 14.35 16.39 14.47 12.79 12.19 13.99 10.15 10.15 11.11 8.47 14.71 12.91 13.99 7.27 7.75 6.55 5.28 6.60 3.12 0.00]; [Y,eigvals]=cmdscale(D) format short g [eigvals eigvals/max(abs(eigvals))]; Dtriu = D(find(tril(ones(21),-1)))'; maxrelerr = max(abs(Dtriu - pdist(Y(:,1:2)))) ./ max(Dtriu); plot(Y(:,1)+0.5,Y(:,2),'.'); text(Y(:,1),Y(:,2),consumer); xlabel('Miles'); ylabel('Miles');
33
34
Lampiran 7 Input program (notepad) 20 14 24000
0
600
-15.461
6.9276
1
16000
0
600
50
-4.4515
0.37156
2
9000
0
600
20
-6.5498
-3.3047
3
10000
0
600
25
-4.6879
-1.135
4
5000
0
600
20
-4.4009
0.9375
5
14000
0
600
45
-3.6123
0.67492
6
10000
0
600
25
-2.0618
1.8832
7
16000
0
600
50
-2.4724
0.34822
8
8000
0
600
40
-1.1892
-0.29974
9
12000
0
600
44
-2.7507
1.4573
10
10000
0
600
25
0.86864
0.26707
11
11000
0
600
38
0.51228
-7.3918
12
3000
0
600
30
1.3947
-9.2986
13
7500
0
600
33
2.4478
-10.652
14
7000
0
600
44
1.1879
0.51237
15
10000
0
600
35
6.5203
-4.2021
16
13000
0
600
45
4.734
2.6892
17
16000
0
600
60
7.2559
1.7651
18
6000
0
600
38
7.1306
8.467
19
7000
0
600
40
8.6103
6.4816
20
9000
0
600
45
6.9748
3.5011
35
Lampiran 8 Output program savings heuristic Number of fails : 164 Number of choice points :0 Number of variables : 651 Number of constraints : 58 Reversible stack (bytes) : 32184 Solver heap (bytes) : 179640 Solver global heap (bytes) : 322520 And stack (bytes) : 4044 Or stack (bytes) : 4044 Search Stack (bytes) : 4044 Constraint queue (bytes) : 4120 Total memory used (bytes) : 550596 Elapsed time since creation : 0 Number of nodes : 21 Number of visits : 44 Number of vehicles : 12 Number of dimensions :3 Number of refused moves : 2237 Number of accepted moves :0 Total number of moves : 2237 =============== Problem name : batch20_1.txt Cost : 90000 Number of vehicles used : 9 Solution : Unperformed visits : None Vehicle 0 : Unused Vehicle 1 : Unused Vehicle 2 : Unused Vehicle 3 : -> Depot Time[0..495.717] Weight[0..2000] Length[0..1.#INF) -> 10 Time[17.6358. .513.352] Weight[0..2000] Length[17.6358..1.#INF) -> 9 Time[46.4458..542.163] We ight[10000..12000] Length[21.4458..1.#INF) -> Depot Time[104.283..600] Weight[22 000..24000] Length[35.2833..1.#INF) Vehicle 4 : -> Depot Time[0..477.257] Weight[0..5000] Length[0..1.#INF) -> 11 Time[21.4521. .498.709] Weight[0..5000] Length[21.4521..1.#INF) -> 8 Time[66.7454..544.003] We ight[11000..16000] Length[28.7454..1.#INF) -> Depot Time[122.743..600] Weight[19 000..24000] Length[44.7428..1.#INF) Vehicle 5 : -> Depot Time[0..465.294] Weight[0..500] Length[0..1.#INF) -> 13 Time[25.0952.. 490.39] Weight[0..500] Length[25.0952..1.#INF) -> 7 Time[70.1456..535.44] Weight [7500..8000] Length[37.1456..1.#INF) -> Depot Time[134.706..600] Weight[23500..2 4000] Length[51.7056..1.#INF) Vehicle 6 : -> Depot Time[0..495.314] Weight[0..7000] Length[0..1.#INF) -> 14 Time[17.8421. .513.156] Weight[0..7000] Length[17.8421..1.#INF) -> 6 Time[65.3691..560.683] We ight[7000..14000] Length[21.3691..1.#INF) -> Depot Time[104.686..600] Weight[170 00..24000] Length[35.6864..1.#INF) Vehicle 7 : -> Depot Time[0..470.719] Weight[0] Length[0..1.#INF) -> 15 Time[24.6383..495.3 57] Weight[0] Length[24.6383..1.#INF) -> 5 Time[70.8836..541.603] Weight[10000] Length[35.8836..1.#INF) -> Depot Time[129.281..600] Weight[24000] Length[49.2809 ..1.#INF) Vehicle 8 :
36
-> Depot Time[0..485.741] Weight[0..1000] Length[0..1.#INF) -> 16 Time[20.635.. 506.376] Weight[0..1000] Length[20.635..1.#INF) -> 3 Time[75.8034..561.544] Weig ht[13000..14000] Length[30.8034..1.#INF) -> Depot Time[114.259..600] Weight[2300 0..24000] Length[44.2594..1.#INF) Vehicle 9 : -> Depot Time[0..429.819] Weight[0] Length[0..1.#INF) -> 12 Time[23.3967..453.2 15] Weight[0] Length[23.3967..1.#INF) -> 17 Time[65.917..495.736] Weight[3000] L ength[35.917..1.#INF) -> 4 Time[137.603..567.422] Weight[19000] Length[47.6032.. 1.#INF) -> Depot Time[170.181..600] Weight[24000] Length[60.1812..1.#INF) Vehicle 10 : -> Depot Time[0..458.691] Weight[0..1000] Length[0..1.#INF) -> 19 Time[24.0754. .482.766] Weight[0..1000] Length[24.0754..1.#INF) -> 1 Time[78.4957..537.186] We ight[7000..8000] Length[38.4957..1.#INF) -> Depot Time[141.309..600] Weight[2300 0..24000] Length[51.3094..1.#INF) Vehicle 11 : -> Depot Time[0..440.679] Weight[0] Length[0..1.#INF) -> 18 Time[22.644..463.32 2] Weight[0] Length[22.644..1.#INF) -> 20 Time[65.6123..506.291] Weight[6000] Le ngth[27.6123..1.#INF) -> 2 Time[125.753..566.431] Weight[15000] Length[42.7528.. 1.#INF) -> Depot Time[159.321..600] Weight[24000] Length[56.3215..1.#INF) Press any key to continue
37
Lampiran 9 Output program sweep heuristic Number of fails : 220 Number of choice points :0 Number of variables : 651 Number of constraints : 58 Reversible stack (bytes) : 32184 Solver heap (bytes) : 180924 Solver global heap (bytes) : 322520 And stack (bytes) : 4044 Or stack (bytes) : 4044 Search Stack (bytes) : 4044 Constraint queue (bytes) : 4120 Total memory used (bytes) : 551880 Elapsed time since creation : 0.015 Number of nodes : 21 Number of visits : 44 Number of vehicles : 12 Number of dimensions :3 Number of refused moves : 2234 Number of accepted moves :0 Total number of moves : 2234 =============== Problem name : batch20_1.txt Cost : 100000 Number of vehicles used : 10 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..466.703] Weight[0..4500] Length[0..1.#INF) -> 2 Time[13.5687.. 480.272] Weight[0..4500] Length[13.5687..1.#INF) -> 13 Time[45.185..511.888] Wei ght[9000..13500] Length[25.185..1.#INF) -> 12 Time[79.8999..546.603] Weight[1650 0..21000] Length[26.8999..1.#INF) -> Depot Time[133.297..600] Weight[19500..2400 0] Length[50.2966..1.#INF) Vehicle 1 : -> Depot Time[0..493.956] Weight[0..3000] Length[0..1.#INF) -> 11 Time[21.4521. .515.408] Weight[0..3000] Length[21.4521..1.#INF) -> 3 Time[67.5877..561.544] We ight[11000..14000] Length[29.5877..1.#INF) -> Depot Time[106.044..600] Weight[21 000..24000] Length[43.0438..1.#INF) Vehicle 2 : -> Depot Time[0..504.04] Weight[0..3000] Length[0..1.#INF) -> 1 Time[12.8137..5 16.854] Weight[0..3000] Length[12.8137..1.#INF) -> 4 Time[63.3819..567.422] Weig ht[16000..19000] Length[13.3819..1.#INF) -> Depot Time[95.9599..600] Weight[2100 0..24000] Length[25.9599..1.#INF) Vehicle 3 : -> Depot Time[0..482.993] Weight[0..2000] Length[0..1.#INF) -> 5 Time[13.3973.. 496.391] Weight[0..2000] Length[13.3973..1.#INF) -> 8 Time[61.0091..544.003] Wei ght[14000..16000] Length[16.0091..1.#INF) -> Depot Time[117.007..600] Weight[220 00..24000] Length[32.0065..1.#INF) Vehicle 4 : -> Depot Time[0..469.934] Weight[0..1000] Length[0..1.#INF) -> 7 Time[14.5599.. 484.494] Weight[0..1000] Length[14.5599..1.#INF) -> 14 Time[68.2239..538.158] We ight[16000..17000] Length[18.2239..1.#INF) -> Depot Time[130.066..600] Weight[23 000..24000] Length[36.066..1.#INF) Vehicle 5 : -> Depot Time[0..471.662] Weight[0..2000] Length[0..1.#INF) -> 15 Time[24.6383. .496.301] Weight[0..2000] Length[24.6383..1.#INF) -> 9 Time[70.5002..542.163] We
38
ight[10000..12000] Length[35.5002..1.#INF) -> Depot Time[128.338..600] Weight[22 000..24000] Length[49.3377..1.#INF) Vehicle 6 : -> Depot Time[0..514.7] Weight[0..4000] Length[0..1.#INF) -> 10 Time[17.6358..5 32.336] Weight[0..4000] Length[17.6358..1.#INF) -> 6 Time[45.9823..560.683] Weig ht[10000..14000] Length[20.9823..1.#INF) -> Depot Time[85.2996..600] Weight[2000 0..24000] Length[35.2996..1.#INF) Vehicle 7 : -> Depot Time[0..447.721] Weight[0..1000] Length[0..1.#INF) -> 17 Time[23.2961. .471.017] Weight[0..1000] Length[23.2961..1.#INF) -> 19 Time[88.2032..535.925] W eight[16000..17000] Length[28.2032..1.#INF) -> Depot Time[152.279..600] Weight[2 3000..24000] Length[52.2787..1.#INF) Vehicle 8 : -> Depot Time[0..464.286] Weight[0..2000] Length[0..1.#INF) -> 16 Time[20.635.. 484.921] Weight[0..2000] Length[20.635..1.#INF) -> 20 Time[68.0183..532.304] Wei ght[13000..15000] Length[23.0183..1.#INF) -> Depot Time[135.714..600] Weight[220 00..24000] Length[45.7143..1.#INF) Vehicle 9 : -> Depot Time[0..516.712] Weight[0..18000] Length[0..1.#INF) -> 18 Time[22.644. .539.356] Weight[0..18000] Length[22.644..1.#INF) -> Depot Time[83.288..600] Wei ght[6000..24000] Length[45.288..1.#INF) Vehicle 10 : Unused Vehicle 11 : Unused Press any key to continue
39
Lampiran 10 Output program nearest depot heuristic Number of fails : 220 Number of choice points :0 Number of variables : 651 Number of constraints : 58 Reversible stack (bytes) : 32184 Solver heap (bytes) : 180924 Solver global heap (bytes) : 322520 And stack (bytes) : 4044 Or stack (bytes) : 4044 Search Stack (bytes) : 4044 Constraint queue (bytes) : 4120 Total memory used (bytes) : 551880 Elapsed time since creation : 0.015 Number of nodes : 21 Number of visits : 44 Number of vehicles : 12 Number of dimensions :3 Number of refused moves : 2242 Number of accepted moves :0 Total number of moves : 2242 =============== Problem name : batch20_1.txt Cost : 100000 Number of vehicles used : 10 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..362.405] Weight[0..1000] Length[0..1.#INF) -> 19 Time[24.0754. .386.48] Weight[0..1000] Length[24.0754..1.#INF) -> 14 Time[73.6003..436.005] We ight[7000..8000] Length[33.6003..1.#INF) -> 18 Time[127.53..489.935] Weight[1400 0..15000] Length[43.5297..1.#INF) -> 12 Time[184.198..546.603] Weight[20000..210 00] Length[62.1983..1.#INF) -> Depot Time[237.595..600] Weight[23000..24000] Len gth[85.595..1.#INF) Vehicle 1 : -> Depot Time[0..445.293] Weight[0..500] Length[0..1.#INF) -> 17 Time[23.2961.. 468.589] Weight[0..500] Length[23.2961..1.#INF) -> 13 Time[96.6116..541.905] Wei ght[16000..16500] Length[36.6116..1.#INF) -> Depot Time[154.707..600] Weight[235 00..24000] Length[61.7068..1.#INF) Vehicle 2 : -> Depot Time[0..490.245] Weight[0..3000] Length[0..1.#INF) -> 11 Time[21.4521. .511.697] Weight[0..3000] Length[21.4521..1.#INF) -> 10 Time[67.1192..557.364] W eight[11000..14000] Length[29.1192..1.#INF) -> Depot Time[109.755..600] Weight[2 1000..24000] Length[46.755..1.#INF) Vehicle 3 : -> Depot Time[0..471.733] Weight[0..3000] Length[0..1.#INF) -> 16 Time[20.635.. 492.368] Weight[0..3000] Length[20.635..1.#INF) -> 8 Time[72.2696..544.003] Weig ht[13000..16000] Length[27.2696..1.#INF) -> Depot Time[128.267..600] Weight[2100 0..24000] Length[43.267..1.#INF) Vehicle 4 : -> Depot Time[0..502.502] Weight[0..3000] Length[0..1.#INF) -> 9 Time[13.8375.. 516.34] Weight[0..3000] Length[13.8375..1.#INF) -> 2 Time[63.9293..566.431] Weig ht[12000..15000] Length[19.9293..1.#INF) -> Depot Time[97.498..600] Weight[21000 ..24000] Length[33.498..1.#INF) Vehicle 5 : -> Depot Time[0..500.32] Weight[0] Length[0..1.#INF) -> 6 Time[14.3173..514.637
40
] Weight[0] Length[14.3173..1.#INF) -> 5 Time[41.283..541.603] Weight[10000] Len gth[16.283..1.#INF) -> Depot Time[99.6803..600] Weight[24000] Length[29.6803..1. #INF) Vehicle 6 : -> Depot Time[0..504.04] Weight[0..3000] Length[0..1.#INF) -> 1 Time[12.8137..5 16.854] Weight[0..3000] Length[12.8137..1.#INF) -> 4 Time[63.3819..567.422] Weig ht[16000..19000] Length[13.3819..1.#INF) -> Depot Time[95.9599..600] Weight[2100 0..24000] Length[25.9599..1.#INF) Vehicle 7 : -> Depot Time[0..520.88] Weight[0..8000] Length[0..1.#INF) -> 7 Time[14.5599..5 35.44] Weight[0..8000] Length[14.5599..1.#INF) -> Depot Time[79.1199..600] Weigh t[16000..24000] Length[29.1199..1.#INF) Vehicle 8 : -> Depot Time[0..490.285] Weight[0..4000] Length[0..1.#INF) -> 15 Time[24.6383. .514.924] Weight[0..4000] Length[24.6383..1.#INF) -> 3 Time[71.2586..561.544] We ight[10000..14000] Length[36.2586..1.#INF) -> Depot Time[109.715..600] Weight[20 000..24000] Length[49.7147..1.#INF) Vehicle 9 : -> Depot Time[0..509.608] Weight[0..15000] Length[0..1.#INF) -> 20 Time[22.6959 ..532.304] Weight[0..15000] Length[22.6959..1.#INF) -> Depot Time[90.3919..600] Weight[9000..24000] Length[45.3919..1.#INF) Vehicle 10 : Unused Vehicle 11 : Unused Press any key to continue
41
Lampiran 11 Skrip program savings heuristic #include
#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { //////////////////////////////////////////////////////// // informasi aja //////////////////////////////////////////////////////// m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl // nama permasalahan << "Cost : " << 10000*plan.getNbOfVehiclesUsed() << endl //biaya total << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl// kendaraan yang digunakan << "Solution : " << endl //gambaran solusi yang dihasilkan << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); // definisikan permasalahan yang dihadapi IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension1 weight(plan, "Weight"); // definisikan kapasitas yang dibawa kendaraan IlcDimension2 length(plan, IlcEuclidean, "Length"); ////////////////////////////////////////////////////////////////// // membaca data dari file batch20_1.dat ////////////////////////////////////////////////////////////////// ifstream infile; char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "batch20_1.txt"; infile.open(problem); if (!infile) { m.out() << "File not found or not specified: " << problem << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } IlcInt nbOfVisits, nbOfTrucks; infile >> nbOfVisits >> nbOfTrucks; IlcFloat capacity; infile >> capacity;
42
IlcFloat openTime, closeTime; infile >> openTime >> closeTime; IlcFloat depotX, depotY ; infile >> depotX >> depotY; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); // dimulai dari depot m.add(first.getCumulVar(time) >= openTime); // definisikan waktu buka IlcVisit last(depot, "Depot"); // diakhiri di depot m.add(last.getCumulVar(time) <= closeTime); // definisikan waktu tutup char name[16]; sprintf(name, "Vehicle %d\0", j); // kendaraan yang melakukan pengiriman IlcVehicle vehicle(plan, first, last, name); vehicle.setCapacity(weight, capacity); // kendala kapasitas kendaraan vehicle.setSpeed(length, 1); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier?? IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> quantity >> minTime >> maxTime >> dropTime >> x >> y; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime); //kendala waktu bongkar-muat visit.setQuantity(weight, quantity);// kendala yang dibawa kendaraan /////////////////////////////////////////////// // kendala waktu pelayanan (time window) /////////////////////////////////////////////// ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); ///////////////////////////////////////////////////////////////////////// // mencari solusi dengan menggunakan metode savings heuristic ///////////////////////////////////////////////////////////////////////// IlcGoal generateGoal = IlcSavingsGenerate(m, plan); m.add(generateGoal); if (!m.nextSolution()) { m.out() << "Not enough vehicles to generate first solution" << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } else { m.restart(); m.remove(generateGoal); ////////////////////////////////////////////////////////////////////////////////// //memperbaiki solusi yang didapat dengan twoOP,Relocate,Exchange ////////////////////////////////////////////////////////////////////////////////// plan.improve(3, IlcTwoOpt(plan), IlcRelocate(plan), IlcExchange(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE)
43
m.closeLogFile(); #endif m.end(); return 0; }
44
Lampiran 12 Skrip program sweep heuristic #include #include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { //////////////////////////////////////////////////////// // informasi aja //////////////////////////////////////////////////////// m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl // nama permasalahan << "Cost : " << 10000*plan.getNbOfVehiclesUsed() << endl //biaya total << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl// kendaraan yang digunakan << "Solution : " << endl //gambaran solusi yang dihasilkan << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); // definisikan permasalahan yang dihadapi IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension1 weight(plan, "Weight"); // definisikan kapasitas yang dibawa kendaraan IlcDimension2 length(plan, IlcEuclidean, "Length"); ////////////////////////////////////////////////////////////////// // membaca data dari file batch20_1.dat ////////////////////////////////////////////////////////////////// ifstream infile; char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "batch20_1.txt"; infile.open(problem); if (!infile) { m.out() << "File not found or not specified: " << problem << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } IlcInt nbOfVisits, nbOfTrucks; infile >> nbOfVisits >> nbOfTrucks; IlcFloat capacity; infile >> capacity;
45
IlcFloat openTime, closeTime; infile >> openTime >> closeTime; IlcFloat depotX, depotY ; infile >> depotX >> depotY; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); // dimulai dari depot m.add(first.getCumulVar(time) >= openTime); // definisikan waktu buka IlcVisit last(depot, "Depot"); // diakhiri di depot m.add(last.getCumulVar(time) <= closeTime); // definisikan waktu tutup char name[16]; sprintf(name, "Vehicle %d\0", j); // kendaraan yang melakukan pengiriman IlcVehicle vehicle(plan, first, last, name); vehicle.setCapacity(weight, capacity); // kendala kapasitas kendaraan vehicle.setSpeed(length, 1); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier?? IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> quantity >> minTime >> maxTime >> dropTime >> x >> y; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime); //kendala waktu bongkar-muat visit.setQuantity(weight, quantity);// kendala yang dibawa kendaraan /////////////////////////////////////////////// // kendala waktu pelayanan (time window) /////////////////////////////////////////////// ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); ///////////////////////////////////////////////////////////////////////// // mencari solusi dengan menggunakan metode sweep heuristic ///////////////////////////////////////////////////////////////////////// IlcGoal generateGoal = IlcSweepGenerate(m, plan); m.add(generateGoal); if (!m.nextSolution()) { m.out() << "Not enough vehicles to generate first solution" << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } else { m.restart(); m.remove(generateGoal); ////////////////////////////////////////////////////////////////////////////////// //memperbaiki solusi yang didapat dengan twoOP,Relocate,Exchange ////////////////////////////////////////////////////////////////////////////////// plan.improve(3, IlcTwoOpt(plan), IlcRelocate(plan), IlcExchange(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE)
46
m.closeLogFile(); #endif m.end(); return 0; }
47
Lampiran 13 Skrip program nearest depot heuristic #include #include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { //////////////////////////////////////////////////////// // informasi aja //////////////////////////////////////////////////////// m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl // nama permasalahan << "Cost : " << 10000*plan.getNbOfVehiclesUsed() << endl //biaya total << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl// kendaraan yang digunakan << "Solution : " << endl //gambaran solusi yang dihasilkan << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); // definisikan permasalahan yang dihadapi IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension1 weight(plan, "Weight"); // definisikan kapasitas yang dibawa kendaraan IlcDimension2 length(plan, IlcEuclidean, "Length"); ////////////////////////////////////////////////////////////////// // membaca data dari file batch20_1.dat ////////////////////////////////////////////////////////////////// ifstream infile; char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "batch20_1.txt"; infile.open(problem); if (!infile) { m.out() << "File not found or not specified: " << problem << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } IlcInt nbOfVisits, nbOfTrucks; infile >> nbOfVisits >> nbOfTrucks; IlcFloat capacity;
48
infile >> capacity; IlcFloat openTime, closeTime; infile >> openTime >> closeTime; IlcFloat depotX, depotY ; infile >> depotX >> depotY; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); // dimulai dari depot m.add(first.getCumulVar(time) >= openTime); // definisikan waktu buka IlcVisit last(depot, "Depot"); // diakhiri di depot m.add(last.getCumulVar(time) <= closeTime); // definisikan waktu tutup char name[16]; sprintf(name, "Vehicle %d\0", j); // kendaraan yang melakukan pengiriman IlcVehicle vehicle(plan, first, last, name); vehicle.setCapacity(weight, capacity); // kendala kapasitas kendaraan vehicle.setSpeed(length, 1); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier?? IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> quantity >> minTime >> maxTime >> dropTime >> x >> y; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime); //kendala waktu bongkar-muat visit.setQuantity(weight, quantity);// kendala yang dibawa kendaraan /////////////////////////////////////////////// // kendala waktu pelayanan (time window) /////////////////////////////////////////////// ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); ///////////////////////////////////////////////////////////////////////// // mencari solusi dengan menggunakan metode nearestdepot heuristic ///////////////////////////////////////////////////////////////////////// IlcGoal generateGoal = IlcNearestdepotGenerate(m, plan); m.add(generateGoal); if (!m.nextSolution()) { m.out() << "Not enough vehicles to generate first solution" << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } else { m.restart(); m.remove(generateGoal); ////////////////////////////////////////////////////////////////////////////////// //memperbaiki solusi yang didapat dengan twoOP, Relocate,Exchange ////////////////////////////////////////////////////////////////////////////////// plan.improve(3, IlcTwoOpt(plan), IlcRelocate(plan), IlcExchange(plan)); } Info(m, plan, problem);
49
#if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; }
50
Lampiran 14 Peta jalur distribusi ( CV KATRACO )
