Modifikasi Algoritma Heuristik Vogel's Approximation Method Untuk Optimasi Initial Basic Feasible Solution Pada Transportation Problem

Putra, Farhan Dwi (2026) Modifikasi Algoritma Heuristik Vogel's Approximation Method Untuk Optimasi Initial Basic Feasible Solution Pada Transportation Problem. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211093-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (4MB) | Request a copy

Abstract

Transportation Problem (TP) merupakan permasalahan riset operasi yang bertujuan menentukan distribusi barang dari beberapa lokasi supply ke lokasi demand dengan cost transportasi minimum. Penyelesaian TP umumnya diawali dengan pembentukan Initial Basic Feasible Solution (IBFS), di mana kualitas solusi awal sangat memengaruhi hasil akhir proses penyelesaian. Penelitian ini mengusulkan modifikasi terhadap Vogel’s Approximation Method (VAM) karena metode tersebut umumnya mampu menghasilkan IBFS yang baik, namun masih memiliki kelemahan pada kondisi nilai penalty yang sama sehingga proses pemilihan alokasi barang belum sepenuhnya konsisten. Modifikasi dilakukan dengan menambahkan selection layer pada tahap pembentukan solusi awal serta mekanisme 4-cell improvement. Selection layer menggunakan urutan pemilihan berdasarkan penalty terbesar, average cost terkecil, dan prioritas baris terhadap kolom sehingga proses alokasi barang menjadi lebih terstruktur dan deterministik. Setelah IBFS terbentuk, solusi diperiksa kembali menggunakan sub-matriks berukuran 2 × 2 yang memiliki alokasi barang diagonal. Apabila ditemukan sub-matriks dengan nilai delta negatif, maka dilakukan pertukaran alokasi barang untuk menurunkan total cost transportasi. Pengujian dilakukan menggunakan 40 data uji TP yang bersifat balanced dan dibandingkan dengan metode LCM, VAM, TOCM-MT, JHM, BCE, EDM, dan SSM. Hasil pengujian menunjukkan bahwa metode yang diusulkan menghasilkan 35 solusi optimal dengan tingkat keberhasilan sebesar 87,50%, sehingga efektif digunakan sebagai alternatif constructive heuristic dalam penyelesaian TP.
======================================================================================================================================
Transportation Problem (TP) is an operations research problem that aims to determine the distribution of goods from several supply locations to demand locations with minimum transportation cost. The solution process generally begins with the construction of an Initial Basic Feasible Solution (IBFS), where the quality of the initial solution significantly affects the overall solution process. This study proposes a modification of the Vogel’s Approximation Method (VAM) because the method generally produces good IBFSs but still suffers from inconsistencies when equal penalty values occur. The proposed modification incorporates a selection layer in the initial solution construction stage and a 4-cell improvement mechanism. The selection layer applies a priority sequence based on the largest penalty, the smallest average cost, and row priority over column priority, resulting in a more structured and deterministic allocation process. After the IBFS is obtained, the solution is re-examined using 2 × 2 submatrices containing diagonal allocations. If a submatrix with a negative delta value is found, the allocation is adjusted to reduce the total transportation cost. The proposed method was evaluated using 40 balanced Transportation Problem datasets and compared with LCM, VAM, TOCM-MT, JHM, BCE, EDM, and SSM. The experimental results show that the proposed method achieved 35 optimal solutions with an accuracy rate of 87.50%, indicating that it is an effective constructive heuristic alternative for solving the Transportation Problem.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Initial Basic Feasible Solution, Transportation Problem, Vogel’s Approximation Method, Initial Basic Feasible Solution, Transportation Problem, Vogel’s Approximation Method.
Subjects:	T Technology > T Technology (General) > T57.62 Simulation T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Farhan Dwi Putra
Date Deposited:	29 Jul 2026 02:52
Last Modified:	29 Jul 2026 02:52
URI:	http://repository.its.ac.id/id/eprint/139384

Actions (login required)

View Item