IMPROVED SIMULATED ANNEALING FOR OPTIMIZATION OF VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW)

Abstract

IMPROVED SIMULATED ANNEALING FOR OPTIMIZATION OF VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (VRPTW) Wayan Firdaus Mahmudy Department of Computer Science, University of Brawijaya (UB) Email: wayanfm@ub.ac.id Abstrak Vehicle routing proble with time windows (VRPTW) merupakan permasalahan optimasi kombinatorial yang banyak ditemui pada sistem distribusi permasalahan ini berkaitan dengan pengalokasian sejumlah kendaraan umum untuk melayani sejumlah konsumen, sejumlah konsumen mempunyai rentang waktu kesediaan yang berbeda dan harus dilayani dalam waktu tersebut. Paper ini memaparkan penggunaan metode simulated annealing yang diperkaya dengan beberapa fungsi khusus untuk menghasilkan solusi tetangga yang digunakan pada penelusuran are pencarian solusi dari VRPTW. Serangkaian percobaan menunjukkan bahwa simulated annealing yang diperkaya dengan fungsi-fungsi khusus dapat menghasilkan solusi yang baik dalam waktu rata-rata 82.29 detik. Kata kunci: Vehicle Routing Problem with Time Windows (VRPTW), Permasalahan optimasi kombinatoria, Simulated annealing, solusi tetangga. Abstract The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem that exists in various distribution systems. The problem deals with allocation of vehicles to service several customers, each customer has different available time, and the vehicles must visit the customers in their available time.This paper addresses the VRPTW by using an improved simulated annealing algorithm. Special functions to effectively exploring neighborhood solutions are developed. The functions are required to deal with the large search space of the VRPTW and enhance the power of the simulated annealing to obtain better solutions. The proposed approach is evaluated in comparison with well-known benchmark problems available in the literature. A set of computational experiments prove that the improved simulated annealing could produce promising results in the average of computational time of 82.29 seconds. Keywords: Vehicle Routing Problem with Time Windows (VRPTW), combinatorial optimization problem, simulated annealing, neighborhood solution