Perpustakaan Digital ITB

Berbagai macam model permasalahan dapat diformulasikan dari bagaimana manusia mengintegrasikan transportasi dalam bisnisnya, sebagai aspek yang esensial dalam kehidupan sehari-hari. Salah satu bentuk persoalan yang lahir dari aspek ini ialah Vehicle Routing Problem disingkat VRP, yang merupakan versi lebih general dari Travelling Salesman Problem disingkat TSP. VRP mencakupi pengalokasian titik-titik pada peta kepada sejumlah kendaraan untuk menjadi tanggung jawab masing-masing kendaraan untuk mengunjunginya tanpa memperhatikan urutan. Varian VRP yang lebih relevan dengan kasus nyata ialah penambahan batasan kapasitas kendaraan (capacity), rentang waktu (time window), dan bentuk titik berpasangan sebagai pengambilan dan pengantaran (pickup and delivery). Lebih tepatnya, varian VRP yang dibahas ialah Pickup and Delivery Vehicle Routing Problem with Time Window (PDVRPTW). Sebagai persoalan optimasi yang merupakan NP-hard, VRP umum diselesaikan dengan tahapan pembangkitan solusi inisial dan kemudian dilakukan pembelajaran atau optimasi. Pada penelitian ini, dikembangkan metode heuristik untuk membangkitkan solusi inisial memanfaatkan Balanced Graph Clustering dan Dynamic Programming. Proses pembangkitan rute ini melalui fase clustering graf secara seimbang dan dilaksanakan bertahap menghasilkan struktur hirarki, untuk kemudian secara bottom-up dilakukan pre komputasi tiap rute dalam kluster, dengan memanfaatkan algoritma rekonstruksi jalur antar kluster. Batasan waktu dapat diintegrasikan dengan memanfaatkan feasibility graph, DP, dan Maximum Bipartite Matching. Solusi ini kemudian akan dieksperimenkan pertumbuhan evaluasinya ketika diaplikasikan strategi pembelajaran Hill Climbing, Simulated Annealing, dan Tabu Search. Melalui sejumlah pengujian, diperoleh balanced K-medoids sebagai teknik clustering terbaik yang dapat membangkitkan solusi 3-15% lebih buruk dari solusi paling optimal untuk TSP. Metode heuristik ini juga dapat mencapai solusi dengan jumlah kendaraan yang dibutuhkan kurang dari 130% dari jumlah kendaraan optimal untuk kasus-kasus uji PDVRPTW, yang mayoritas dicapai oleh strategi pembelajaran Tabu Search.