ABSTRAKSI: Pada kehidupan sehari-hari pengiriman barang membutuhkan jalur yang optimal agar barang-barang tersebut bisa sampai ditempat tujuan sesuai dengan permintaan kota tujuan tersebut. Kasus pengiriman barang ini merupakan contoh dari penerapan Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) pada kehidupan nyata. CVRPTW sendiri adalah sebuah permasalahan pencarian rute untuk sejumlah kendaraan dari satu depot menuju node-node yang tersedia dengan tujuan mengantarkan barang dari depot menuju node tujuan, dengan batasan time windows pada setiap node dan kapasitas kendaraan.
Dalam tugas akhir ini, diimplementasikan metode Improved Ant Colony Syetem (IACS) dan metode Simulated Annealing (SA) untuk menyelesaikan permasalahan CVRPTW dalam kasus pengiriman barang PT .POS Indonesia. Ant Colony System digunakan karena metode ini mampu melakukan multiple search pada beberapa area tertentu secara bersamaan dalam sebuah ruang pencarian, dan metode ini banyak digunakan dalam permasalahan pencarian rute. Sedangkan simulated annealing (SA), merupakan local search yang dapat menghindari solusi dari local optima. Penggabungan kedua metode ini diharapkan dapat menghasilkan solusi yang mendekati optimal dilihat dari jarak tempuh.
Pengujian yang dilakukan adalah mencari parameter-parameter terbaik untuk mendapatkan solusi yang mendekati optimal. Parameter α, β, dan q0 berpengaruh besar pada metode IACS-SA ini. Untuk mengetahui performansi metode IACS-SA ini, pada akhir pengujian akan dibandingkan dengan 2 metode lainnya yaitu metode AG-DE dan metode HS.Kata Kunci : Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), Improved Ant Colony System (IACS), Simulated Annealing (SA), pencarian rute.ABSTRACT: Delivering some goods in daily life needs some optimal routes in order to get those commodity delivered to some destination in accordance with the demands of those destination places. This case is one example of applied Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) in real life. CVRPTW itself is a route searching problem for a number of vehicles from one depot to another available nodes in purpose to deliver some goods from depot to destination nodes with time costraints for each node and vehicles’ capacity.
In this final project, Improved Ant Colony System (IACS) and Simulated Annealing (SA) methods are proposed to solve CVRPTW in PT. POS Indonesia goods’ delivering case. Ant Colony System is used because this method is able to do multiple search in certain area simultaneously in one searching space and commonly used in route searching case. Meanwhile Simulated Annealing (SA) is a local search which can avoid the solution from local optima. The combination of these two methods yields nearly optimum solution which can be seen from total distance.
Testing is done in order to find best parameters. α, β, and q0 Parameters significantly involve in IACS-SA method. To know IACS-SA method’s performance, IACS-SA is compared to two other methods like DE & AG and HS method in the end of testing.Keyword: Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), Improved Ant Colony System (IACS), Simulated Annealing (SA), route searching.