Arsip Bulanan: Oktober 2022

Cara Mengatasi Masalah Perutean Kendaraan

Ditulis pada oleh
Balas

Apa Masalah Perutean Kendaraan Anda? Memahami Tugas Pengoptimalan Rute
Optimalisasi rute adalah proses penentuan rute yang paling hemat biaya. Anda mungkin berpikir bahwa itu berarti menemukan jalur terpendek antara dua titik, tetapi jarang sesederhana itu: Anda harus memperhitungkan semua faktor yang relevan yang terlibat seperti jumlah dan lokasi semua pemberhentian di rute, kesenjangan waktu kedatangan/keberangkatan, pemuatan efektif, dll. Optimalisasi rute adalah solusi untuk apa yang disebut masalah perutean kendaraan (VRP).

Vehicle Routing Problem atau VRP adalah tantangan dalam merancang rute optimal dari depot ke satu set tujuan masing-masing dengan kendala khusus bisnis, seperti keterbatasan kendaraan, kontrol biaya, jendela waktu, keterbatasan sumber daya mengenai proses pemuatan di depot, dll .

VRP klasik pertama dikenal sebagai travelling salesman problem (TSP), yang bermula pada awal 1800-an dan menyebar luas pada hari-hari ketika salesman door-to-door menjajakan penyedot debu dan ensiklopedia. Seiring waktu, VRP dikategorikan ke dalam tugas-tugas yang jauh lebih canggih yang melibatkan sejumlah besar data.

Mari kita lihat lebih dekat VRP dan perangkat lunak paling umum yang dapat Anda terapkan untuk mengungkapnya.

Penafian: VRP dunia nyata terdiri dari ratusan atau ribuan node. Waktu yang dibutuhkan untuk menyelesaikannya semakin meningkat relatif terhadap ukuran masalah. Untuk masalah yang cukup besar, dibutuhkan waktu bertahun-tahun untuk menemukan solusi optimal. Frane Saric, CTO di OptimoRoute, menegaskan hal itu: “Metode eksak seperti integer linear programming (ILP) jarang digunakan dalam praktik karena sangat lambat dan hanya dapat menyelesaikan masalah yang sangat kecil dengan beberapa perintah”. Oleh karena itu, solusi perutean sering mengandalkan heuristik untuk dapat dengan cepat mengembalikan solusi yang cukup baik tetapi belum tentu solusi yang optimal.

Masalah Rute Kendaraan Berkapasitas (CVRP)
Karena setiap kendaraan memiliki kapasitas muatan maksimum, Anda harus selalu mempertimbangkan berat dan volume barang yang diangkut. Tantangannya adalah menghemat biaya dengan mengangkut lebih banyak barang dalam satu perjalanan tanpa melebihi kapasitas kendaraan. Mungkin ada komplikasi tambahan seperti:

beberapa depot subset terbatas kendaraan yang memiliki permintaan fasilitas tertentu (misalnya kompartemen freezer) dimensi kargo yang berbeda untuk dikirim / diambil
kapasitas yang berbeda dari setiap kendaraan kendaraan multi-kompartemen Skenario kehidupan nyata: Tesco Company, pengecer bahan makanan dan barang umum global, menggunakan kendaraan over-the-road untuk distribusi barang. Barang diangkut dengan palet. Satu kendaraan dapat menampung palet dalam jumlah terbatas, sementara setiap unit usaha (BU) menuntut jumlah palet yang berbeda. Misalnya, department store besar membutuhkan palet beberapa kali lebih banyak daripada yang dapat ditampung oleh kendaraan.

Pendekatan solusi: Tetapkan rute terpendek untuk kendaraan sehingga jumlah total unit kendaraan memenuhi batasan kapasitasnya.

Masalah Perutean Kendaraan dengan Time Windows (VRPTW)
Seringkali pelanggan hanya tersedia selama periode waktu tertentu. Hal ini membatasi waktu pengiriman/penjemputan, karena sekarang kendaraan harus menjangkau pelanggan dalam jangka waktu yang diprioritaskan. Ketika jendela waktu terbuka, kendaraan harus melayani pelanggan. Mungkin tiba lebih awal, tetapi, tidak berarti, di luar jendela waktu yang ditentukan. Tertinggal dari jadwal dapat secara signifikan menurunkan tingkat kepuasan pelanggan yang menyebabkan hilangnya keuntungan dalam jangka panjang. Ini menentukan kebutuhan untuk menjadwalkan perjalanan, tetapi melakukannya dengan cara yang paling hemat biaya. Itulah yang dimaksud dengan VRPTW. Jendela waktu dapat berupa:

beberapa jendela waktu: satu set jendela waktu yang tidak tumpang tindih dengan panjang yang berbeda
jendela waktu terputus: tiba di antara dua jendela waktu, kendaraan harus menunggu sampai jendela waktu berikutnya terbuka
jendela waktu lunak: melayani di luar jendela waktu diperbolehkan, tetapi memerlukan hukuman
jendela waktu sulit: tidak ada pelanggaran waktu yang diizinkan. Jika kendaraan datang terlalu dini, ia harus menunggu sampai jendela waktu terbuka; dan tidak diperbolehkan datang terlambat.