Implementasi Particle Swarm Optimization (PSO) pada Vehicle Routing Problem with Time Windows (VRPTW)

ABSTRAKSI: Permasalahan distribusi dan pergudangan dalam manajemen rantai pasok menjadi permasalahan yang sangat krusial. Pendistribusian produk yang baik akan meringankan biaya produksi dan meningkatkan efisiensi. Permasalahan distribusi ini lebih dikenal dengan nama Vehicle Routing Problem (VRP). VRP merupakan permasalahan optimasi kombinatorial dengan ruang solusi yang besar dan sulit diselesaikan. Permasalahan meningkat apabila setiap node memiliki batasan waktu pelayanan yaitu time windows. Dengan adanya time windows maka permasalahan menjadi Vehicle Routing Problem with Time Windows (VRPTW). Tujuan dari tugas akhir ini adalah mengimplementasikan algoritma Particle Swarm Optimization yang cocok untuk permasalahan kombinatorial dan mampu menghasilkan solusi optimum. PSO merupakan algoritma yang terinspirasi dari sekawanan burung. Solusi awal PSO dibangkitkan secara random dan kemudian diarahkan untuk menghasilkan solusi yang optimal. Hasil penelitian memperlihatkan PSO mampu memberikan solusi yang mendekati optimal untuk VRPTW. PSO mampu menghasilkan relative percentage deviation (RPD) rata-rata kurang dari 5,3% untuk dataset 25 node. Namun semakin banyak node yang dilayani semakin menurun performansinya.Kata Kunci : manajemen rantai pasok, VRP, VRPTW, Particle Swarm OptimizationABSTRACT: Problems of distribution and warehousing in the supply chain management becomes a crucial issue. A good distribution of the products will reduce the production cost and increase the efficiency. Distribution problem is better known as the Vehicle Routing Problem (VRP). VRP is a combinatorial optimization problem with a large solution space and difficult solve. The problems increase if each node has a time limit for the service which is called time windows. By the time windows, then the problem becomes Vehicle Routing Problem with Time Windows (VRPTW). The purpose of this final task is to implement the Particle Swarm Optimization algorithm that suitable for combinatorial problem that able to produce the optimum solution. PSO is an algorithm which is inspired by birds flocking. Initial solution of PSO generated randomly and then directed to produce the optimal solution. The results showed that PSO is able to provide a near optimal solution for VRPTW. PSO is able to produce an average of relative percentage deviation (RPD) less than 5,3% for dataset 25 nodes. But system’s performance will be decreasing with an increasing nodes that are served.Keyword: supply chain management, VRP, VRPTW, Particle Swarm Optimizatio