Perbandingan Algoritma Welch Powell dan Algoritma Greedy dengan Pewarnaan Simpul pada Persimpangan Empat

Fadhillah, Rosadha (2024) Perbandingan Algoritma Welch Powell dan Algoritma Greedy dengan Pewarnaan Simpul pada Persimpangan Empat. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6002221005_Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (2MB) | Request a copy

Abstract

Peningkatan mobilitas masyarakat yang terjadi mengakibatkan peningkatan penggunaan kendaraan sebagai sarana transportasi. Peningkatan ini akan menyebabkan kemacetan apabila jumlah kendaraan yang ada tidak seimbang dengan lebar jalan pada persimpangan. Untuk mengatasi hal ini dapat dilakukan dengan optimalisasi pada pengaturan lalu lintas yaitu dengan memodelkan persimpangan jalan dalam bentuk graf. Selanjutnya di lakukan pewarnaan dengan menggunakan dua algoritma yaitu Welch Powell dan Greedy yang akan di implementasikan pada persimpangan empat di Jl. Kertajaya-Jl. Manyar Kertoarjo. Hasil yang diperoleh kedua algoritma adalah bilangan kromatik sebanyak χ(G) = 4. Selanjutnya pada siklus waktu optimal dengan metode webster pada pagi, siang dan sore diperoleh 170 detik, 192 detik dan 185 detik. Perbandingan dari segi kompleksitas waktu, dalam kasus terburuk algoritma Greedy O(n^2 logn) lebih efisien dibandingkan dengan algoritma Welch Powell O(n^2). Pada hasil implementasi simulasi MATLAB R2024a diperoleh bahwa dari segi waktu eksekusi program algoritma Greedy lebih cepat dibandingan dengan algoritma Welch Powell. Hasil ini berlaku pada pada periode waktu senin pagi, siang dan sore. Dari hasil penelitian diperoleh bahwa algoritma greedy lebih efisien daripada algoritma Welch Powell.
========================================================================================================================The increase in community mobility that occurs results in an increase in the use of vehicles as a means of transportation. This increase will cause congestion if the number of vehicles is not balanced with the width of the road at the intersection. To overcome this problem, optimization of traffic management can be done by modeling the road intersection in the form of a graph. Furthermore, coloring is done using two algorithms, namely Welch Powell and Greedy, which will be implemented at four intersections on Jl. Kertajaya-Jl. Manyar Kertoarjo. The result obtained by both algorithms is a chromatic number of χ(G) = 4. Furthermore, the optimal cycle time with the Webster method in the morning, afternoon and evening is 170 seconds, 192 seconds and 185 seconds. Comparison in terms of time complexity, in the worst case the Greedy O(n^2 log⁡n) algorithm is more efficient than the Welch Powell O(n^2) algorithm. In the MATLAB R2024a simulation implementation results obtained that in terms of program execution time Greedy algorithm is faster than the Welch Powell algorithm. This result applies to the time period Monday morning, afternoon and evening. This research obtained that the greedy algorithm is more efficient than the Welch Powell algorithm.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Traffic Control, Vertex Coloring, Welch Powell Algorithm, Greedy Algorithm, Pengaturan lalu lintas, Pewarnaan Simpul, Algoritma Welch Powell, Algoritma Greedy.
Subjects:	Q Science Q Science > QA Mathematics Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Mathematics, Computation, and Data Science > Mathematics > 44101-(S2) Master Thesis
Depositing User:	Rosadha Fadhillah
Date Deposited:	07 Aug 2024 01:05
Last Modified:	25 Sep 2024 03:39
URI:	http://repository.its.ac.id/id/eprint/113633

Actions (login required)

View Item