ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal Regular Issue, Vol. 10 N. 2 (2021), 157-163 eISSN: 2255-2863 DOI: https://doi.org/10.14201/ADCAIJ2021102157163

Analysis Performance of Conventional Algorithm and HMS Algorithm for Four-Way Intersection with Modified Round Robin

Wirawan Istiono^a

^a Universitas Multimedia Nusantara, Indonesia

wirawan.istiono@umn.ac.id

ABSTRACT

KEYWORDS

1. Introduction

The development of cities in the current era of globalization shows a significant increase. City governments in various countries around the world have begun to develop their cities to improve the welfare of the people who live in the city. The development of the city is marked by the construction of supporting infrastructure such as roads, hospitals, schools and so on. Several cities in Indonesia make their cities with certain characteristics such as education cities, tourist cities, Batik cities which means the city where someone can shop for batik clothes and so on to attract more people to visit their cities in the hope of moving the wheels of the people's economy. However, along with the development of the city, new problems emerge that become new jobs for the city government, one of the problem is traffic jams. Traffic congestion arises due to the increasing number of vehicles crossing the road while the road capacity is insufficient (Algorithm, Nipa, & Islam, 2015). Growth in traffic congestion on the roads of major cities in developing countries such as Indonesia often increases from year to year. Traffic congestion at a crossroads is very important because crossing performance affects the overall productivity of the entire road network. At present, in the traffic light system, there is a lot of time wasted (Tama et al., 2016; Ferdinand & Ferdinand, 2018). Every day, around 650,000 four-wheeled vehicles enter the capital city of Jakarta from buffer zones such as Bogor, Depok, Tangerang, and Bekasi (Faza & Natalia, 2018), of course, this adds to the congestion that arises from the two million cars and three million motorbikes that already exist in Jakarta (Susila, 2015). Efficient traffic light control is one solution to minimize traffic jams on the highway. Congestion monitoring can be done by using a camera as a traffic jam detector on a highway that is installed at every intersection (Jatmika & Andiko, 2014; Sinaga & Hansun, 2018). In his research, Hussian, Sharma states that the most commonly used traffic control systems in developing countries are microcontroller-based systems. This system involves setting a predetermined time interval for each intersection at each intersection (Hussian, Sharma, & Sharma, 2013). And according Mahdi and Zuhairi in they research, they mentioned that several cases of accidents on traffic control have been reported in the past because of poor traffic control controls at the crossroads. They focus that current speed is the last word. Everyone runs an unrelenting busy life and people would prefer to spend more time and utilize their energy doing their professional work rather than wasting their valuable time and energy on road trips, and the size of the vehicle that they used, wheter big or small vehicle such as small car or truck, absolutly will has a big effect on speed and also will be affected the level of congestion on the road (Al-zuhairi & Mahdi, 2013; Hartono, Saputra, & Hutasoit, n.d.).

Several type of algorithms have been used to solve these problems, such as the HMS Algorithm and the Conventional Algorithm or can be called as brute force algorithm (Anusha, Yashaswini, & Manishankar, 2016; Mohammad, 2006). And the main purpose of HMS algorithms and Convetional algorithm is to provide the system with to reducing waiting time (da Costa Vieira Rezende, Souza, Coelho, & Martins, 2018), where the system can reduce the amount of time needed by vehicles in the traffic light queue and Utilization of resources, that aims to ensure maximum use of roads and resources. But it is not yet known which algorithm has better performance than other algorithms, so the purpose of this study is to compare the performance between Conventional and HMS algorithms, so that it will be known which algorithm is best used to solve the problem by existing cases. In this study will only discusses four tracks and uses only three case examples data and two algorithms that are compared, namely conventional algorithm or brute force and HMS algorithm. Where form that data, will find the duration of the next green light and also the level of comparison of the effectiveness of the two algorithms. In the early stages of this research, a literature study was carried out, and then will be continued with the analysis and calculation phases with various data and afterwards will do comparisons of the data obtained.

2. Research Method and Discussion

The problem of optimizing delays on traffic lights can take place under a variety of conditions such as the number of lanes, lane widths, unequal traffic rules in various regions and so on. To simplify the problem, a model is chosen that can represent the other models in general and is simple. The model in question has the following constraints, such as four-lane vehicles, one lane consists of two lanes (left and right) in opposite directions, in one lane there is one streetlight, At one time there was only one lane whose street lights were green, so the other street lights would be red and the width of one lane in a certain direction is the same as the width of the vehicle passing the road, assuming the size of each vehicle in this model is the same and vehicles drive on the left side of the road. To solve this problem, the physical implementation needs to add the use of two sensors for each lane that will be used to obtain the information needed such as the density and number of vehicles entering. The above model can be described in Figure 1.

After sample road model, will do testing of cases, where each case has different conditions. The large variety of cases will help us get more varied results data. The difference in each case lies in the number of vehicles detected by the sensor. The 3 cases referred to above are shown in Table 1.

Table 1. Case One, Track with Number of Vehicles

In the first case that shown in Table 1, the number of vehicles in each lane is not too large, at most only 15 vehicles (cars/motorbikes) with a difference in the number (gaps) between lanes of only 5 to 10 vehicles. In the second case, the number of vehicles in each lane has increased, and the difference in the number of vehicles per lane is quite far, which is to add 10 vehicles in the next lane. In the third case, it is similar to the first case and the second case but the number of vehicles is multiplied.

Modified Round Robin method that will be used in this research is used to analyse basic performance and simple scheduling that will be used to serve many queues. The HMS scheduling algorithm provides equal opportunity (green light time) for each queue regardless of car size and load path (Novel, 2013). The first step is to collect the number of vehicles in each row by using a sensor or camera network, which uses image processing to determine the vehicles that are passed, and then forwards the number of vehicles to the main control board, which can become an Arduino Board (Hamarashid, Saeed, & Saeed, 2017). Then the number of vehicles will be sent to the control system to calculate the amount of time provided for each lane. After that, the workings of the HMS algorithm based on the Round Robin algorithm and the equation 1 designed for it.

3. Result And Analysis

Based on formula in the equation 1, it can be describe that Yn symbol is the amount of green time allotted for a lane, and n symbol is for Lane number, F symbol for the total number of vehicles in all lanes, and L symbol for number of vehicles in lane n. After that, each path will get the duration of the green light. As a note, in this study, it is assumed that one second duration of the next green light is for one car. In settlement for cases 1, the time was initially given 120 seconds. The number of vehicles for each case and each lane can be seen in Error! Reference source not found. after that, apply the HMS formula that written at equation 1 for this problem, and then will get the result; Ya = 120 / 35 * 5 = 17 Second, Yb = 120 / 35 * 15 = 51 Second, Yc = 120 / 35 * 10 = 34 Second and Yd = 120 /35 * 5 = 17 Second. And for cases 2, apply HMS formula that written at equation 2, and will get result; Ya = 120 / 100 * 10 = 12 Second, Yb = 120 / 100 * 20 = 25 Second, Yc = 120 / 100 * 30 = 36 Second and Yd = 120 /100 * 40 = 48 Second. And for cases 3, apply again HMS formula that written at equation 1, and then will get the result; Ya = 120 / 120 * 5 = 15 Second, Yb = 120 / 120 * 15 = 60 Second, Yc = 120 / 120 * 10 = 30 Second and Yd = 120 / 120 * 5 = 15 Second. All result for all calculation for each cases can be seen in Table 2.

Table 2. Result calculation of HMS algorithm

In the first step of HMS algorithm, the HMS algorithm is need to get numbers of vehicles data in each lane or track, however in conventional algorithm, just only need to specify determine the desired waiting time or initial time. After that, the conventional algorithm will be works using the equation 2.

From the equation 2, can be describe that Yn symbol is The amount of green time allotted for a lane, and Jn for number of available lanes. If on the HMS algorithm, each path has a difference green light duration time based on following the number of vehicles. In conventional algorithms, each path has the same green duration, regardless of the number of vehicles (Ali et al., 2018). In settlement of cases 1, cases 2, cases 3 and cases 4, the time is initially given time 120 seconds, and number of lines is 4, after that apply the conventional formula equation 2, and we will got that Ya = 120 / 4 = 30 Second, Yb = 120 / 4 = 30 Second, Yc = 120 / 4 = 30 Second, Yd = 120 / 4 = 30 Second. And the result table of conventional algorithms can be seen in Table 3.

Table 3. Result calculation of Conventional algorithm

Based on the results of the application on the algorithm HMS and conventional algorithm that shown in Table2 and table3, that we can calculate efectiveness of algorithm HMS and conventional algorithm from duration of the next green light subtracted amount of vehicle, and from the result can get effectiveness algorithm for each cases. As a note, that if the amount of vehicle is greater than the duration of the next green light, the percentage of effectiveness will be calculated at 100%, because there is no time is wasted. And the result effectiveness algorithm HMS and conventional for each case can be seen in Table 4.

Table 4. Effectiveness Comparison between Conventional and HMS Algorithm with Amount of vehicle

From the result of Table , that can be stated the level of effectiveness on each route with the HMS algorithm tends to be the same, even though the number of vehicles on each route is a lot different, but on the conventional algorithm it can be seen that the algorithm ini will be more effective if the number of vehicles is not too different from the duration of the next green light provided, However in the conventional algorithm, if there are a lot different of amount vehicles on each lane, the effectiveness of this algorithm is not too good, because the amount of time is wasted on the lane with a smaller number of vehicles, and the increasing queue number of vehicles on the crowded lane, whereas on lanes with a few vehicles there is a lot of time is wasted.

4. Conclusion

The conclusion for this research can be stated that the HMS algorithm is very suitable to be used in any condition both vehicles in large numbers or a little, whereas conventional algorithms are only suitable for use in the number of vehicles in the lane a little or the number of vehicles between lane one with another lane is the same, because conventional algorithms are very susceptible to build up of vehicles, on a lane that has many vehicles, if a lane that has fewer vehicles will be given a long green light duration. The HMS algorithm is very suitable to be used in any condition for large or little vehicles, while conventional algorithms are only suitable to use for vehicles in the one little lane or the vehicles in one lane with other lane direction in the same place of lane.

5. Future work

The future research section, this research result will be implement to create traffic simulation with graphic and controller. The simulation will be made using game development software, such as Unity3D, to see whether the theoretical results and calculations that obtained, can be used in traffic simulations, wherein if the simulation experiment goes well it will be tested in the real world.

Acknowledgements

Authors are greatful to Unversitas Multimedia Nusantaran, Tangerang, Indonesia for providing financial assistance to carried out this research work.

6. References

Algorithm, R. S., Nipa, L. N., & Islam, M. (2015). Intelligent Traffic Control System Based On Round. International Journal of Scientific and Research Publications, 5(8), 1–8.

Ali, S., Rose Alinda, A., Syed Norris, H., Marlia, P., Siti Hamisah, T., Cotet, G. B., … Othman, A. (2018). ANALYSIS OF TRAFFIC LIGHT SYSTEM USING ARTIFICIAL INTELLIGENCE. E-Proceeding of Engineering, 5(2), 975.https://doi.org/10.1051/matecconf/201712107005

Al-zuhairi, & Mahdi, A. S. (2013). Automatic Railway Gate and Crossing Control based Sensors & Microcontroller. International Journal of Computer Trends and Technology (IJCTT), 4(7), 2135–2140.

Anusha, K., Yashaswini, C., & Manishankar, S. (2016). Segmentation of retail mobile market using HMS algorithm. International Journal of Electrical and Computer Engineering, 6(4), 1818–1827. https://doi.org/10.11591/ijece.v6i4.10295

da Costa Vieira Rezende, J., Souza, M. J. F., Coelho, V. N., & Martins, A. X. (2018). HMS: A hybrid multi-start algorithm for solving binary linear programs. Electronic Notes in Discrete Mathematics, 66, 7–14. https://doi.org/10.1016/j.endm.2018.03.002

Faza, A., & Natalia, F. (2018). Modelling of Traffic Flow on West Jakarta Highways. International Journal of Engineering and Technology, 10(3), 658–666. https://doi.org/10.21817/ijet/2018/v10i3/181003002

Ferdinand, F. N., & Ferdinand, F. V. (2018). A study on network design for the shortest path in expedition company. Journal of Telecommunication, Electronic and Computer Engineering, 10(1), 1–4.

Hamarashid, H. K., Saeed, M. H. R., & Saeed, S. (2017). Designing a Smart Traffic Light Algorithm (HMS) Based on Modified Round Robin Algorithm. Kurdistan Journal of Applied Research, 2(1), 27–30. https://doi.org/10.24017/science.2017.1.8

Hartono, R., Saputra, D. W., & Hutasoit, J. T. H. P. (n.d.). Penerapan Algoritma Greedy pada Optimasi Pengaturan Lampu Lalu Lintas Sederhana. 1–5.

Hussian, R., Sharma, S., & Sharma, V. (2013). WSN Applications: Automated Intelligent Traffic Control System Using Sensors.International Journal of Soft Computing and Engineering (IJSCE), (3), 77.

Jatmika, S., & Andiko, I. (2014). Simulasi Pengaturan Lampu Lalu Lintas Berdasarkan Data Image Processing Kepadatan Kendaraan Berbasis Mikrokontroler ATMEGA16. Jurnal Ilmiah Teknologi Informasi Asia, 8(2), 81–96.

Mohammad, A. O. S. R. A. A. (2006). Occurrences Algorithm for String Searching Based on Brute-force Algorithm Ababneh Mohammad, Oqeili Saleh and Rawan A . Abdeen Department of Information Technology, Al-Balqa’ Applied University, Salt, Jordan. Journal of Computer Science 2, 2(1), 82–85.

Novel, I. P. M.-A. (2013). AWERProcedia Information Technology & Computer Science Predicting Joint Angle Of Hand Opening-Closing by Using Surface. AWERProcedia Information Technology & Computer Science, 04, 723–728.

Sinaga, D. D., & Hansun, S. (2018). Indonesian text document similarity detection system using rabin-karp and confix-stripping algorithms. International Journal of Innovative Computing, Information and Control, 14(5), 1893–1903. https://doi.org/10.24507/ijicic.14.05.1893

Susila, T. (2015). Model Pemantauan dan Pengaturan Lampu Lalu Lintas Secara Wirelles Berdasarkan Panjang Antrian Kendaraan. TESLA, 17(2).

Tama, I. P., Sari, R. A., Umar, F., Industri, J. T., Teknik, F., & Brawijaya, U. (2016). Jemis Vol . 4 No . 2 Tahun 2016 Analisa Durasi Lampu Lalu Lintas Menggunakan Metode. JEMIS, 4(2), 130–140.