MODEL MATEMATIKA GENERALIZED VEHICLE ROUTING PROBLEM DAN EKSTENSINYA STUDI KASUS: PT. PAPERTECH INDONESIA UNIT II MAGELANG

KOKO HERMANTO, Dr. Salmah, M.Si

2015 | Tesis | S2 Matematika

Vehicle routing problem (VRP) merupakan salah satu masalah optimasi kombinatorial yang telah banyak dikaji karena banyak aplikasinya di bidang industri, logistik dan sebagainya. Generalisasi dari VRP disebut generalized vehicle routing problem (GVRP), dimana setiap vertek dari graph dipartisi menjadi himpunan-himpunan vertek disebut kluster, akan ditentukan rute optimal yang diberikan kepada tiap kluster yang telah ditetapkan meliputi tepat satu vertek dari setiap kluster. Selanjutnya diperkenalkan ekstensi dari GVRP yaitu cluster generalized vehicle routing problem (CGVRP) yang bertujuan untuk menenentukan rute optimal setiap vertek untuk masing-masing kluster. Hasil penelitian menunjukan bahwa metode GVRP dan CGVRP yang dimodelkan dalam bentuk program linier integer variabel biner kemudian diselesaikan dengan algoritma enumerasi implisit. Dalam masalah pedinstribusian menggunakan jaringan jalan yang sesungguhnya yaitu pada PT. Papertech Indonesia Unit II Magelang dapat diimplementasikan dengan cara membuat hubungan langsung antar kota-kota. Sistem ini menghasilkan rute terpendek, rician perjalanan, jarak antar kota dan biaya perjalanan.

The vehicle routing problem (VRP) is one of the most famous combinatorial optimization problems and it has been intensively studied due to the many practical applications in industrial fields, logistics,etc. A generalization of the VRP is called the generalized vehicle routing problem (GVRP) where each node of the graph partitioned into node sets called clusters, we want to find the optimal routes from the given depot to the number of predefined clusters covering exactly one node of each cluster. Furthermore, the extension of GVRP is introduced, i.e., cluster generalized vehicle routing problem (CGVRP) aiming to specify an optimal route for each vertex of every cluster. The result of this research indicated that the method of GVRP and CGVRP modeled in the form of binary variable integer linear programming and solved with an implicit enumeration algorithm. In rationing route problems using the real road network, i.e., the application of PT. Papertech Indonesia Unit II Magelang being able to implement in a way setting the intercity direct connection. This system produced the shortest route, the tour in detail, the distance between cities, and the cost of a travel.

Kata Kunci : VRP, GVRP, CGVRP, program linier integer variabel biner, enumerasi implisit rute terpendek ; GVRP, CGVRP, integer linear programming binary variables, the shortest path implicit enumeration.