Perpustakaan Digital ITB

Tidak jarang konsep distribusi dan paralelisasi diaplikasikan dalam menyelesaikan persoalan optimasi kombinatorial. Salah satu optimasi kombinatorial NP-hard yang relevan dan terkenal adalah Vehicle Routing Problem (VRP). Pada kasus ini, batasan pengiriman, waktu pelayanan, dan kapasitas diberlakukan pada persoalan menjadi PDVRPTW. Terdapat metode heuristik yang dijadikan acuan, bertujuan menyelesaikan persoalan soft constraint PDVRPTW dengan memanfaatkan Hierarchical Graph Clustering dengan Balanced K-means dan batasan waktu dan kapasitas sebagai fungsi objektif utama, serta kemudian sejumlah strategi optimasi Local Search dengan operator insertion sebagai pembangkitan solusi tetangga. Dalam rangka mengaplikasikan prinsip distribusi dan paralelisasi, dirancang model hasil modifikasi metode acuan. Dari segi pemrosesan graf, Affinity Hierarchical Clustering dengan memanfaatkan Adaptive Massively Parallel Computation diaplikasikan dalam pemrosesan graf pada metode acuan. Selain itu, fungsi objektif baru reachability dirancang dan ditambahkan pada multi objektif yang sudah ada. Terakhir dari segi strategi optimasi, metode acuan yang telah terbukti mengalami optimasi terbaik dengan strategi Tabu Search, ternyata mengalami peningkatan lagi setelah diintegrasikan Genetic Algorithm menjadi optimasi hybrid karena potensi paralelisasi Genetic Algorithm yang besar. Pengujian model yang paralel dan terdistribusi menggunakan dataset solomon dan sejumlah adaptasi varian lain dari VRP-REP 100, 200, 400, 800 jumlah pekerjaan. Pada jumlah pekerjaan cukup besar, diperoleh hasil modifikasi metode acuan dan optimasi yang telah mengintegrasikan Genetic Algorithm memiliki galat 4-10% dari solusi terbaik, memiliki peningkatan cukup signifikan dari metode acuan yang memiliki galat berkisar pada 15%. Seiring bertambahnya unit komputasi, faktor percepatan juga mendekati jumlah unit komputasi yang digunakan, yang membuktikan modifikasi metode agar dapat paralel cukup berhasil.