Masalah Rute Kendaraan Listrik Multi-Depot dengan Time Windows Menggunakan Two-Stage Hybrid Ant Colony Algorithm

Abstract

Vehicle routing problem adalah masalah pencarian rute bagi kendaraan yang harus berangkat dari depot, mengunjungi setiap pelanggan tepat satu kali, lalu kembali lagi ke depot. Masalah ini telah berkembang menjadi berbagai jenis varian, salah satunya adalah multi-depot electric vehicle routing problem with time windows (MDEVRPTW). MDEVRPTW adalah masalah vehicle routing problem yang menggunakan kendaraan listrik, berangkat dan kembali ke beberapa pilihan depot, dan harus memenuhi time windows pelanggan. MDEVRPTW sudah diselesaikan dengan metode eksak dalam bentuk mixed integer linear programming (MILP) pada penelitian sebelumnya. Waktu komputasi untuk metode eksak ini mencapai 19 jam untuk kasus 10 pelanggan, 1 depot, dan 1 stasiun pengisian daya. Waktu komputasi ini dinilai tidak efektif untuk operasional perusahaan, karena sebuah perusahaan bisa saja memiliki puluhan atau bahkan ratusan pelanggan. Oleh karena itu, diperlukan metode pendekatan yang disebut sebagai metode metaheuristik untuk mendekati solusi dari metode eksak. Metode metaheuristik yang diajukan dalam penelitian ini adalah two stage hybrid ant colony algorithm (TSHACA). Tujuan dari penelitian ini adalah melihat seberapa baik solusi yang diberikan metode TSHACA dibandingkan metode eksak dan menerapkan TSHACA pada kasus yang lebih besar, yaitu 25, 50, dan 100 pelanggan. Untuk kasus besar, data yang digunakan berasal dari data solomon bertipe c101 dan r205. Parameter model dan data 10 pelanggan diambil dari penelitian sebelumnya. Kapasitas baterai kendaraan pada penelitian ini adalah 75 kWh, sedangkan kapasitas muatan kendaraan adalah 125 kg untuk kasus 10, 25, dan 50 pelanggan, lalu 200 kg untuk kasus 100 pelanggan. Metode TSHACA terdiri dari dua tahapan, yaitu klasterisasi dan penentuan rute. Pada proses klasterisasi, setiap klaster yang terbentuk harus memiliki total permintaan pelanggan yang tidak lebih dari kapasitas kendaraan. Penelitian ini menggunakan dua jenis k-means untuk melakukan klasterisasi, yaitu k-means yang dimodelkan menjadi MILP dan improved k-means. k-means MILP hanya diterapkan pada kasus 10 dan 25 pelanggan, sedangkan improved k-means diterapkan pada kasus 50 dan 100 pelanggan. Jumlah klaster dipilih berdasarkan nilai silhouette index tertinggi. Jumlah klaster minimumnya adalah total permintaan dibagi dengan kapasitas muatan kendaraan, lalu jumlah klaster maksimumnya adalah jumlah kendaraan yang tersedia. Penentuan rute pada TSHACA menggunakan algoritma ant colony yang dimodifikasi. Pada saat pemilihan pelanggan pertama, harus dipastikan bahwa time windows pelanggan tersebut bisa dikunjungi. Jika pelanggan tersebut belum bisa dikunjungi, maka akan dilakukan pemilihan acak lagi sampai mendapatkan pelanggan yang bisa dikunjungi. Kemudian, algoritma pemilihan pelanggan selanjutnya memadukan metode deterministik dan probabilistik dalam memilih pelanggan selanjutnya yang akan dikunjungi semut. Selain itu, nilai visibilitas juga ditentukan dengan memprioritaskan time windows pelanggan-pelanggan yang sudah memenuhi. Pada tahap ini, akan dilakukan pemeriksaan time windows lagi. Selanjutnya, algoritma pembaruan feromon juga dimodifikasi agar bisa mengeksplor solusi lebih baik. Pada kasus 10 pelanggan, klaster dengan nilai silhouette index tertinggi adalah 3 klaster. Total biaya untuk 3 klaster ini adalah Rp 989.021,91 dengan waktu komputasi 0,9 detik untuk klasterisasi dan 0,0181 detik untuk peruteannya. Metode eksak untuk parameter yang sama memberikan total biaya sebesar Rp 959.055,70 dengan waktu komputasi 2.200 detik. Biaya yang dihasilkan metode eksak hanya lebih murah 3,12% dibandingkan metode TSHACA, tetapi perbedaan waktu komputasinya sangat jauh. Oleh karena itu, metode TSHACA merupakan metode yang baik untuk mendekati solusi eksak. Untuk implementasi pada kasus yang besar, akan diperiksa apakah nilai silhouette index berpengaruh pada total biaya. Pada kasus 25 pelanggan, total biaya paling kecil diberikan oleh 5 klaster yang memiliki nilai silhouette index tertinggi, yaitu 0,525. Pada kasus 50 pelanggan, total biaya paling kecil juga diberikan oleh klaster dengan nilai silhouette index tertinggi, yaitu 11 klaster. Begitupun untuk 100 pelanggan, klaster dengan nilai silhouette index tertinggi memberikan total biaya terkecil, yaitu 10 klaster. Kemudian, peneliti coba untuk tidak memasukkan biaya tetap kendaraan ke total biaya, karena semakin banyak klaster yang terbentuk, biaya tetapnya juga semakin tinggi. Setelah dikurangi biaya tetap, kasus 25 pelanggan dan 50 pelanggan memberikan hasil yang sama, yaitu total biaya terkecil tetap dihasilkan oleh 5 klaster dan 11 klaster. Kasus 100 pelanggan menunjukkan hasil yang beda. Jumlah klaster yang memberikan total biaya terkecil adalah klaster maksimumnya, yaitu 25 klaster dengan nilai silhouette index yang tidak terlalu besar dan tidak terlalu kecil. Waktu komputasi untuk proses klasterisasi kasus 25 pelanggan adalah 28 detik, lalu untuk peruteannya adalah 32 detik. Untuk kasus 50 pelanggan, waktu komputasi klasterisasinya adalah 0,02 detik dan peruteannya adalah 152 detik. Untuk kasus 100 pelanggan, waktu komputasi klasterisasinya adalah 0,03 detik dan peruteannya adalah sekitar 600 detik. Karena waktu komputasi metode ini tidak lama, maka metode ini bisa menjadi metode pendekatan yang baik untuk menggantikan metode eksak yang membutuhkan memori besar dan waktu komputasi lama. Kesimpulan dari penelitian ini adalah TSHACA membutuhkan waktu komputasi yang jauh lebih sedikit dari metode eksak dengan pendekatan solusi yang baik. Metode ini adalah metode metaheuristik yang baik yang tidak memerlukan memori yang besar, sehingga praktis untuk digunakan. Jika biaya tetap kendaraan diperhitungkan, maka cukup memilih jumlah klaster dengan nilai silhouette index tertinggi untuk mendapatkan biaya terkecil.

Kata kunci: depot, kendaraan listrik, k-means, TSHACA, soft time windows