Vehicular Traffic Reduction Using The Max Flow Min Cut Theorem

Vehicular traffic reduction using the Max Flow Min Cut theorem

Introduction

The congestion of vehicular flow is one of the biggest transportation problems in the urban area that occurs when the volume exceeds the capacity of road facilities. This is due to the freedom to have their own vehicles, poor land mobilization, and urban growth without measure. Therefore, we believe it is necessary to analyze this problem so that we can end or at least minimize the impact that this entails on the streets (Perez, Bautista, Salazar, & Macias, 2014).

With the help of our knowledge in computer science, flow analysis algorithms and some theorems, we plan to try to solve a problem that occurs in numerous amounts throughout the Honduran territory, which is the congestion of the land vehicular flow. To do this we decided to use the Max-Flow Min-Cut theorem (minimum-corte-chubujo) to try to solve through load flow analysis. With this theorem we can analyze from a scientific point of view the problem with the high congestion in the urban and roads of the country.

Research questions

• How is the problem of vehicular congestion in other countries solved?
• Will there be any algorithm that can be applied to generate a solution for this type of problem?
• How effective would be to use an algorithm for problems of this type?
• Will there be any real case where an algorithm has solved the problem of vehicular congestion?

Objectives

General objective

Propose a solution to solve the problem of the vehicular flow of San Pedro Sula, Cortés, Honduras using strategies similar to those found in success cases that use flow control algorithms as part of the solution,

Specific objectives

Identify the bottlenecks of vehicular flow in the city of San Pedro Sula, Cortés, Honduras using the Max-Flow Min-Cut theorem.

Investigate cases where some flow control algorithm was used to solve the problem of vehicular flow in a region.

Propose a solution based on what was investigated to solve the problem of the vehicular flow of San Pedro Sula, Cortés, Honduras.

Theoretical framework

In search of offering a better understanding of the topics to be addressed, a brief theoretical framework on key research issues is presented below.

Definition of a graph

In graph theory and computer science in general a graph is defined as an order of order (V, E) where:

•  V represents a set of vertices or nodes.
•  E represents a set of edges that connect the vertices.

Not directed graph

An unclear graph is a graph g = (v, e) where:

•  V is not empty.
•  E is an unin -ordered set of edges.

That is, the edge a = (v, w) is equal to the edge b = (w, v).

Directed graph

On the contrary, a directed graph g = (v, e) is a graph where:

• V is a non -empty set and,
• E is a set of ordered pairs or edges.

Therefore, edge a = (v, w) differs from edge b = (w, v).

Adjacencia

It is said that two vertices are adjacent if they are united by an edge. Two edges are adjacent if they have a vertex or node in common.

Vehicular traffic

Vehicle traffic (called vehicular traffic or traffic) is a phenomenon caused by car flow in a road, street or highway. Thomas & Bull (2001) claim that:

The fundamental cause of congestion is friction between vehicles in transit flow. Up to a certain level of traffic, vehicles can circulate at a relatively free speed, determined by speed limits, the frequency of intersections, etc. (p. 8)

Vehicle congestion represents a daily problem for almost any society today. As Perez, Bautista, Salazar, & Macías (2014) mention: “Traffic currentand of any kind."

Vehicle traffic can be categorized into two: recurring and non -recurring. Non -recurrent traffic is one that is caused by any number of unexpected events that can cause a delay in vehicular flow. The recurring traffic on the other hand, refers to the congestion created by time deadlines, called peak hours, where the flow of vehicles is constantly high and consistently. Non -recurrent traffic is difficult to handle, from the point of view of vehicular flow optimization, since its unpredictable nature prevents a specific solution.

Causes of vehicular traffic

Like any phenomenon, vehicular traffic does not happen naturally, it is the product of different conditions that contribute to its creation. Among the most important we can mention:

• The roads of the region are frequently poorly designed and poorly preserved;If the roads that exist and the prompt to exist lack a good infrastructure and adequate maintenance, they are not able to offer their maximum road offer to the drivers (Thomas & Bull, 2001)
• Inadequate behavior of certain motorists: users who affect inappropriate behaviors when they are in front of the steering)
• Poor information about traffic conditions: if an updated and correct real -time report on the vehicular situation in the busiest streets can not be obtained, there is a greater incidence of increasing traffic in roads already congested.

Additionally we can also mention factors that can influence the creation and prolonged maintenance of vehicular congestion as:

•  The choice of a user by a safer and comfortable personal means of personal transport, call it a vehicle, contribute much more to congestion, increasing the number of vehicles and space per road passenger, what options such as buses and taxis (Thomas & Bull, 2001).
•  Especially in urban areas, the creation of road infrastructure to meet the road demand of peak times (time terms where traffic tends to rise frequently) has a very high cost (Thomas & Bull, 2001).

Situation in San Pedro Sula

The phenomenon affects thousands of cities around the world. However, for the purposes of this investigation we will focus on the situation of the city of San Pedro Sula, Cortés located at the Northeast Honduras.

The causes of vehicular congestion in San Pedro Sula

Many times, the bottling of the city occurs by accidents. These accidents tend to occur in areas widely used by sampedran conductors, which causes extremely long cars that delay the movement of citizens. According to the Traffic Police spokesman, José Rodríguez Montoy).

Most accidents occur between 2:00 pm and 6:00 pm, hours that tend to have a lot of movement, so they are commonly known as peak hours. Of the three main boulevards in our city, the East Boulevard (exit to the Lima) is where more accidents with material and human damages are recorded. Public transport is involved in 45% of traffic accidents, while 55% is caused by private conductors (the five main causes of road accidents in Honduras, 2016).

The traffic of our city is also caused by constructions. The disorganization as appropriate work schedules for these constructions and repairs cause that essential roads of the city to be blocked, or severely damaged, forcing several drivers to seek alternatives or advance slowly, in itself delaying the flow of cars (theFive main causes of road accidents in Honduras, 2016).

The number of vehicles that are in the city exceed the limits of streets, these being usually narrow, and unable to house several car rows to allow flow. This lack of space causes drivers to resort to recklessness, such as exceeding highly risky areas, or alternating through areas that do not have a road (eg. sidewalks).

The weather also poses a great delay to traffic, since when there are heavy rains, several streets of the city are flooded, and drivers tend to maintain low speeds to try to evade accidents. Other reasons are also the saturation of sellers in the streets, the slowness of traffic lights, and the slow and inefficiency of the police to make legal lifting of bodies in case of crimes (the five main causes of road accidents in Honduras, 2016).

Relevant statistics

There are 289,362 vehicle units registered in San Pedro Sula, of which 216,511 are cars and 72,851 are motorcycles (half a million vehicles force new roads in San Pedro Sula, 2018). In addition, there are around 289,000 unregistered units, which implies that in the city there are more than 578000 units circulating.

The peak hours, hours of elevated congestion, from San Pedro Sula are: the period from 6:00 am to 9:00 am and the period from 2:00 pm to 7:00 pm

The most affected areas are the boulevards, being the Boulevards of the East and the North the ones that receive the most. Traffic accidents are the second most frequent death cause in the country (know the eleven most critical traffic in San Pedro Sula, 2016).

Max Flow Min Cut Theorem

In computer science and optimization theory, the minimum maximum flow theorem establishes that in a flow network, the maximum amount of flow that passes from the source to the sink is equal to the total weight of the edges in theMinimum cut, that is, the smallest total weight of the edges that, if eliminated, would disconnect the source of the sink (Wayne, 2004).

The theorem relates two quantities: the maximum flow through a network and the minimum weight of a network cutting.

It is based on two algorithms: maximum flow and minimum cutting.

Minimum cutting problem

This problem needs a directed graph, edges with capacities, source s node and node sump t node.

The minimum cut problem focuses on finding the best set of edges to eliminate to disconnect the origin node of a sink node.

A cut is defined as a partition of nodes (s, t) such that it belongs to s and t a t. The capacity of (s, t) is defined as the sum of the weights of the edges that leave S (Wayne, 2004).

Therefore, to find the best set of edges to eliminate, we must find a minimum capacity S-T cut.

Maximum flow problem

The maximum flow problem aims to assign flow to the edges so that the incoming and outgoing flow of each intermediate node as well as maximizing the flow of an origin node s to a node Sumidero T node (Wayne, 2004).

Like the minimum cutting problem, this problem needs a directed graph, edges with capacities, source s node and node sump t node.

Flow F is a weight assignment to the edges such that:

• Capacity: and
• The flow is conserved, that is, except in node s or in node t.

Therefore, what is sought is to find a flow that maximizes the net flow towards the sink.

Therefore, using both algorithms in sets, as proposed by Ford-Fulkerson (1956): "In any network, the maximum flow value is equal to the minimum cut capacity".

This theorem has different applications. Below is a solution using this theorem and the Ford-Fulkerson algorithm for the problem of vehicular congestion.

Applicability

Moore et al. (2013) studied the maximum flow in road networks with speed -dependent capabilities to traffic in Bangkok. A traffic flow problem took the weights of the edges that represented the abilities of the road, defined as vehicles per hour, which were functions of traffic speed, defined as a kilometer per hour, and traffic density (vehicles per kilometer) (Abdullah & Hua, 2017).

To estimate the capacity of the road for a given speed, empirical data were used on safe vehicle separations for a given speed. A modified version of the Ford-Fulkerson algorithm was developed to solve maximum flow problems with speed-dependent capacities, with multiple nodes of origin and destination. It was found that the maximum safe traffic flow occurred at a speed of 30 km/h (Abdullah & Hua, 2017).

Baruah & Baruah (2013) presented the minimum cutting theorem, maximum flow applied using the set of cuts of a pounded graph. A weighted graph was a resulting graph with a real number that served as a structural model in transportation. The minimal cutting and maximum flow control strategy was to minimize the number of edges in a network and the maximum capacity of vehicles that moved through these edges. With a minimum cut in the traffic network, a minimum waiting time of traffic participants for a soft and incongruous traffic flow was allowed (Abdullah & Hua, 2017).

Dong and Zhang (2011) presented an investigation into the method of identification of bottlenecks in the traffic network according to the minimum cutting theorem, maximum flow. Allowed to identify the weak road section and provided a solution for the traffic problem. Traffic networks should be formed on the map of graph theory before the identification of the bottleneck. They applied the minimum cutting theorem, maximum flow to discover the bottleneck of the network. […] The maximum capacity of the entire network was determined. The weak parts of the road allow traffic engineers to know which parts of the road need to be expanded. In addition, they proposed a way to solve the bottleneck of traffic that was to increase road lines. The simulation software, exspect was applied to perform the simulation on the new network with which the road line was added to test the efficiency of the solution. The results showed that the identification of the bottleneck based on the minimum cutting theorem, maximum flow could thus determine the bottleneck effectively (Abdullah & Hua, 2017).

Based on what was investigated, on cases of solutions applied in places such as Kota Kinabalu, Sabah, Malaysia and the Changyi District, of the Jilin City in China, we propose that each of these applications of the Min Cut theorem, Max Flow for Solvent are reviewedThe problem of San Pedro Sula.

Conclusions

Vehicle congestion is a big problem in our region and therefore we must use all the available tools to try to solve it. A single solution will never be enough for very good result that it offers, it is recommended to combine different strategies to maximize the optimization of vehicular flow in San Pedro Sula.

Using the Max-Flow Min-Cut theorem would allow us.

We took into account several cases where it was possible to reduce vehicular congestion through the use of algorithms such as Ford-Fulkerson and Max-Flow Min-Cut theorem and analyzed the solutions that could be applied to our region.

Alternatively, as an additional measure the implementation of alternate routes, improvement of information available in real time on the state of current traffic, and apply the transit laws are possible solutions to increase flow in critical routes.

Bibliography

1. Traffic accidents have caused 1,133 deaths during 2018 in Honduras. (October 5, 2018). The Herald. Obtained from https: // www.the Herald.HN/COUNT/1222053-466/ACCIDENTS-DE-TR%C3%A1NSITO-HAN-PROVADO-133-MUERTES-DURA-2018-EN-HANDURAS
2. Bull, a. (2003). Traffic congestion, the problem and how to face it. Santiago: United Nations.
3. Know the eleven most critical traffic points in San Pedro Sula. (May 16, 2016). The press. Obtained from https: // www.Lapresea.HN/HONDURAS/960952-410/Conscan-Los-Once-Puntos-M%C3%A1S-CR%C3%Additas-Del-TR%C3%A1FICO-EN-SAN-PEDRO-SULA
4. The five main causes of road accidents in Honduras. (October 5, 2016). The press.
5. Half a million vehicles force new roads in San Pedro Sula. (April 19, 2018). The press. Obtained from https: // www.Lapresea.HN/HONDURAS/1170666-410/VE Veh%C3%ADCULOS-BLIGAN-ORIR-NUEVAS-V%C3%ADAS-SAN_PEDRO_SULA
6. Perez, f., Bautista, a., Salazar, m., & Macias, to. (2014). Vehicle traffic flow analysis through a macroscopic model. Dyna, 81, 36-40.
7. Thomas, i., & Bull, to. (2001). The congestion of urban traffic: economic and social causes and consequences. Santiago: United Nations.
8. Wayne, k. (2004). Max Flow, Min Cut. Algorithms and Data Structures. Princeton University. Obtained from http: // www.cs.Princeton.Edu/Courses/Archive/SPR04/Cos226/Lectures/Maxflow.4up.PDF