PENYELESAIAN MASALAH RUTE KENDARAAN DENGAN TIME WINDOWS MENGGUNAKAN METODE PEMBANGKITAN KOLOM

VITRIYANI TRI P, Dr. Indarsih, M.Si.

2016 | Skripsi | S1 MATEMATIKA

Pada skripsi ini akan dibahas mengenai masalah rute kendaraan dengan kendala time windows. Masalah rute kendaraan dengan time windows (VRPTW) adalah masalah pencarian path fisibel yang akan dilewati oleh setiap kendaraan dengan memperhatikan batasan waktu dan kapasitas kendaraan. Tujuan dari masalah VRPTW adalah meminimumkan jarak yang ditempuh oleh kendaraan dengan batasan waktu dari pelanggan melalui path fisibel tersebut. Masalah VRPTW akan diformulasikan sebagai masalah program bilangan bulat 0-1. Selanjutnya, masalah VRPTW akan didekomposisikan menjadi masalah utama dan submasalah. Diasumsikan untuk semua tipe kendaraan adalah homogen dan menggunakan hard time windows pada masalah VRPTW ini. Metode yang akan digunakan untuk menyelesaikan masalah VRPTW tersebut adalah metode pembangkitan kolom. Metode tersebut akan mencari solusi dari masalah utama terbatas dan menggunakan pendekatan masalah harga yaitu nilai tereduksi minimum untuk mencari path fisibel yang akan dibangkitkan. Solusi optimal diperoleh ketika tidak ada lagi path yang mungkin dipilih sebagai rute optimal untuk kendaraan.

In this paper, we will explain about the vehicle routing problem with time windows. Vehicle routing problem with time windows (VRPTW) is a problem to find feasible path that will be passed by each vehicle with take the time limits and vehicle load capacity. The purpose of the VRPTW problem is to minimize the distance traveled by the vehicle with time constraints of customers through the feasible path. VRPTW problem will be formulated as a binary integer programming problem. Furthermore, VRPTW will be decomposed into master problem and subproblem. Assumed that all types of vehicles are homogeneous and using hard time windows on this VRPTW problem. Method to be used to solve the problem VRPTW is column generation. The method will look for a solution of the restricted master problem and approach the pricing problem, that is minimum reduced cost to find feasible paths that will be raised. The optimal solution is obtained when there is no longer a path that may be selected as the optimal route for the vehicle.

Kata Kunci : VRPTW, masalah utama, submasalah, metode pembangkitan kolom, time windows, masalah rute kendaraan