Ilustrasi AIP (Artikel Ilmiah Populer) (Foto: UNAIR NEWS)

Menemukan Rute Terbaik untuk Armada Kendaraan: Strategi Dua Fase untuk Masalah Pengiriman dengan Batas Waktu Kerja

Dari Paket Kurir hingga Truk Logistik

Setiap hari, ribuan kurir, truk distribusi, dan armada layanan di seluruh dunia harus memutuskan hal yang tampak sederhana: kendaraan mana yang melayani pelanggan mana, dan dalam urutan seperti apa? Di balik keputusan itu ada persoalan matematika yang sangat rumit, yang dikenal sebagai Vehicle Routing Problem (VRP), atau masalah perutean kendaraan.

Bayangkan sebuah perusahaan distribusi dengan satu gudang pusat, sepuluh kendaraan, dan seratus pelanggan yang tersebar di berbagai penjuru kota. Setiap pelanggan harus dikunjungi tepat satu kali, dan setiap kendaraan harus berangkat dari gudang lalu kembali ke sana. Tujuannya adalah meminimalkan total biaya, yang biasanya diukur dari jarak tempuh atau waktu perjalanan. Semakin kecil biayanya, semakin hemat bahan bakar, semakin cepat barang tiba, dan semakin rendah emisi yang dihasilkan.

Mengapa Persoalan Ini Begitu Sulit?

VRP termasuk dalam kelompok masalah yang disebut NP-hard. Artinya, ketika jumlah pelanggan bertambah, jumlah kemungkinan rute meledak dengan sangat cepat. Untuk hanya 20 pelanggan, jumlah susunan kunjungan yang mungkin sudah mencapai angka yang tidak bisa diperiksa satu per satu, bahkan oleh komputer tercepat sekalipun. Karena itu, para peneliti biasanya menempuh dua jalur:

  1. Metode heuristik, yaitu cara cerdas yang cepat menghasilkan solusi yang “cukup baik”, tetapi tidak ada jaminan bahwa solusi itu yang terbaik.
  2. Metode eksak, yaitu cara yang menjamin solusi terbaik secara matematis, tetapi sering memakan waktu dan memori komputer sangat besar.

Penelitian yang dibahas dalam artikel ini berusaha menjembatani keduanya.

Mengenal Branch-and-Bound

Salah satu metode eksak yang paling dikenal adalah branch-and-bound (B&B), yang dapat diterjemahkan secara bebas sebagai “bercabang dan membatasi”. Cara kerjanya mirip seseorang yang menjelajahi labirin dengan strategi cerdas.

  • Bercabang (branch): persoalan besar dipecah menjadi beberapa persoalan yang lebih kecil, seperti pohon yang bercabang di setiap persimpangan.
  • Membatasi (bound): untuk setiap cabang, dihitung perkiraan biaya terbaik yang mungkin dicapai. Jika perkiraan itu sudah lebih buruk daripada solusi yang pernah ditemukan, cabang tersebut langsung dipangkas dan tidak perlu dijelajahi lagi.

Dengan pemangkasan ini, B&B menghindari pemeriksaan jutaan kemungkinan yang jelas-jelas tidak menjanjikan. Meski demikian, ketika ditambah dengan berbagai aturan operasional di dunia nyata, pohon pencarian tetap bisa membesar dan membuat komputasi menjadi sangat berat.

Tantangan Tambahan: Batas Durasi Maksimum

Dalam praktiknya, kendaraan dan pengemudi tidak bisa bekerja tanpa batas. Ada aturan jam kerja, ketahanan baterai kendaraan listrik, atau janji pengiriman yang harus selesai dalam kurun waktu tertentu. Inilah yang disebut batasan durasi maksimum: setiap kendaraan hanya boleh menempuh rute dengan total waktu tidak melebihi batas yang ditetapkan.

Tambahan aturan ini membuat masalah semakin sulit, karena rute yang hemat jarak belum tentu memenuhi batas waktu. Memasukkan kedua tuntutan sekaligus ke dalam satu proses pencarian membuat metode B&B tradisional menjadi lambat dan boros sumber daya.

Gagasan Utama: Pisahkan Dua Urusan

Artikel ini mengusulkan algoritma B&B dua fase dengan prinsip sederhana namun efektif: pisahkan urusan mencari rute murah dari urusan memenuhi batas waktu. Ibarat menyusun perjalanan wisata, Anda tidak perlu memikirkan rute tercepat dan jadwal istirahat harian secara bersamaan. Susun dulu urutan kunjungan yang efisien, baru bagi menjadi perjalanan harian yang sesuai batas waktu.

Fase Pertama: Menyusun Satu Tur Besar

Pada fase ini, sebuah metode heuristik digunakan untuk membangun satu tur yang memenuhi syarat-syarat dasar VRP klasik. Pada tahap ini, batas durasi maksimum belum dipertimbangkan. Fokusnya hanya pada urutan kunjungan yang efisien, sehingga ruang pencarian menjadi jauh lebih ringan.

Fase Kedua: Memotong Tur Menjadi Rute-Rute yang Layak

Tur besar tersebut kemudian dipecah menjadi sejumlah sub-rute, satu untuk tiap kendaraan, sehingga tidak ada yang melampaui batas durasi. Pemotongan ini dilakukan dengan pemrograman dinamis, teknik yang menyelesaikan masalah besar dengan menyimpan dan memakai ulang hasil dari masalah-masalah kecil. Alih-alih menghitung ulang hal yang sama berkali-kali, algoritma “mengingat” potongan terbaik yang pernah ditemukan dan membangun solusi akhir dari sana. Analogi sederhananya adalah memotong seutas tali panjang menjadi beberapa bagian dengan panjang maksimum tertentu, dengan memilih titik potong yang paling menguntungkan agar total biaya tetap rendah.

Bagaimana Hasilnya?

Algoritma ini diuji pada kumpulan data uji standar (benchmark) VRP yang lazim dipakai dalam penelitian, lalu dibandingkan dengan metode eksak lain dan berbagai algoritma heuristik. Hasilnya menunjukkan bahwa algoritma dua fase ini secara konsisten unggul dalam tiga hal:

  • Kualitas solusi: rute yang dihasilkan lebih murah, atau setidaknya sebaik pembanding.
  • Jumlah simpul yang dijelajahi: pohon pencarian lebih kecil, artinya lebih sedikit kemungkinan yang perlu diperiksa.
  • Waktu komputasi: solusi diperoleh lebih cepat.

Dengan kata lain, pemisahan tugas ini mampu menjaga jaminan solusi optimal khas metode eksak tanpa menanggung beban komputasi yang biasanya menyertainya.

Mengapa Ini Penting bagi Kita?

Meski terdengar sangat teknis, dampak penelitian semacam ini dekat dengan kehidupan sehari-hari:

  • Logistik dan e-commerce: rute lebih efisien berarti paket tiba lebih cepat dengan biaya operasional lebih rendah.
  • Lingkungan: jarak tempuh yang berkurang menekan konsumsi bahan bakar dan emisi karbon.
  • Kendaraan listrik: batas durasi dapat mewakili batas daya baterai, sehingga pendekatan ini relevan untuk armada listrik.
  • Layanan publik: pengangkutan sampah, layanan antar-jemput, hingga distribusi bantuan dapat dijadwalkan lebih adil dan hemat.

Bagi negara kepulauan seperti Indonesia, dengan tantangan geografis dan biaya logistik yang tinggi, perencanaan rute yang cerdas dapat memberi selisih nyata pada harga barang maupun ketepatan layanan.

Pendekatan dua fase ini mengingatkan kita bahwa persoalan yang rumit sering kali dapat diurai dengan memisahkannya menjadi bagian-bagian yang lebih sederhana. Dengan menyerahkan urusan “rute murah” kepada tahap pertama dan urusan “batas durasi” kepada tahap kedua, algoritma ini mencapai keseimbangan antara ketepatan dan kecepatan.

Tentu saja, pengujian pada data benchmark belum sepenuhnya mencerminkan kerumitan lapangan, seperti kemacetan, jendela waktu pelanggan, atau permintaan yang berubah mendadak. Namun, penelitian ini memberi fondasi yang menjanjikan bagi pengembangan sistem perutean yang lebih cerdas, hemat, dan andal.

Penulis: Asri Bekti Pratiwi

Detail tulisan ini dapat diakses pada: https://accscience.com/journal/IJOCTA/16/3/10.36922/IJOCTA025480215

Accessibility ✕
Bahasa Indonesia Bahasa Indonesia English English
Universitas Airlangga
Excellence with Morality
Scroll to Top