A City Without Traffic Jams
Chapter 2.
(the link to Chapter 1)
The Art of Designing Road Networks
Transport problems of a city through the eyes of a Computer Scientist
If I were recommended an article with the title «The Art of Designing Road Networks,» I would immediately ask how many road networks were built with the participation of its author. I must admit, my professional activity was far from road construction and was recently associated with the design of microprocessors where I, among other responsibilities, was engaged in the resource consumption of data switching. At that time my table stood just opposite the panoramic window which opened up a beautiful view of the long section of the Volgograd Highway and part of the Third Transport Ring with their endless traffic jams from morning to evening, from horizon to horizon. One day, I had a sudden shock of recognition: «The complexities of the data switching process that I struggle with on a chip may be similar to the difficulties the cars face as they flow through the labyrinth of road network».
Probably, this view from the outside and the application of methods that were not traditional for the area in question gave me a chance to understand the cause of traffic jams and make recommendations on how to overcome the problem in practice.
So, what is the novelty of the approach?
Historically, the main purpose of roads is considered to be the opportunity they provide to travel long distances fast (between Rome and the provinces). Such a judgment is justified when it comes to the federal-level intercity highway network: the cities that they connect look like small rare dots on the atlas, and most of the cars traveling between these cities pass their way without turning anywhere.
However, as soon as we turn over several pages and open a detailed map of a large city, the picture changes immediately: the number of addresses where the journey can be started or ended reaches approximately ten thousand, all of them are quite densely spread and relatively small in size. At the same time, hundreds of thousands of cars can be in motion on the streets of such a city at once, moreover, the goal of each of them is not just to fill already empty roads, but to move a person or cargo from a point with a specific address X to a point with a specific address Y. All together, this means that the urban transport system must be adapted to effectively solve the problem of multiple concurrent addressing. Thus, the functions of the urban transport system become even more similar to the telephone or computer network than the intercity road network.
Considering the road network as a switching circuit for a hardware developer or engineer in the field of information transfer technologies is a completely natural way to talk about a problem, but among people involved in research on transport problems, this view is, to my knowledge, new.
The theory of signal switching is a narrow engineering science and it alone, of course, is not enough to plan a separate street, road junction or predict the behaviour of a traffic stream on a straight, isolated section of a highway. Fortunately, the issues listed above are well researched today, and the methods developed to solve them have already successfully come into practice. The theory of switching, in turn, allows the architect to mitigate the risk, in which the city comes into a state of transport collapse despite the fact that all the elements of the road network are perfectly executed. This risk exists because performing multiple concurrent addressing is a resource- and time-consuming task, the key to an effective solution of which is not in the width of the streets and the convenience of transport interchanges, but in the competent choice of which particular switching scheme the proposed road network will implement.
From this research, for example, you will find out why the «arterial» type of transport networks, which are still often used in modern cities, are «bad» and together with the growth of the population will necessarily lead to traffic jams. Another interesting result, which is in good agreement with the observations, explains why the expansion of roads alone, if before all the traffic jams occurred exclusively in the vicinity of the interchanges, is unlikely to somehow improve the situation even if the number of cars in the city remains the same.
When I wrote this article, it was crucial for me that it was understandable to the most ordinary architect, could be useful through his work. I tried to introduce the reader into switching issues in a simple language, to develop criteria for assessing how well a particular road network will cope with the task of concurrent addressing, and using model examples I showed how to use this knowledge in practice.
The article is intended for a wide circle of readers who are slightly familiar with the university-wide course in mathematics, the theory of algorithms and are ready to devote 1 to 5 days to it.
Separation and merger of car flows
It is an obvious observation for many drivers that traffic difficulties arise mainly in those parts of the road where cars for some reason are forced to change lanes. Examples include road forks, narrowings, areas adjacent to highway exits and access roads, sections of highways where some lanes are blocked by an accident or roadworks.
In this section, an attempt will be made to give a quantitative description of the processes occurring in such cases, and we will start by understanding how cars switch lanes.
Two strategies to switch to an adjacent traffic lane
The traffic along a highway has a natural unevenness: someone prefers to drive a little faster, someone a little slower, between some cars the distance decreases and becomes hardly comfortable for driving, while between the others it increases so much that it allows cars to fit in there from adjacent lanes. The appearance of such gaps in the flow of the adjacent lane directly on the side of the random driver may be frequent or not very. If, at the moment when he needs to make a manoeuver, there is no gap, the driver can resort to at least two behavioural strategies:
Strategy 1
Several suitable gaps may simply be located close to the driver’s location. If the movement is dense enough, then it«s unlikely that the driver will be able to add speed and catch the necessary gap, but by slowing down a bit the driver would let the neighbouring stream overtake the car so that to become equal with the gap that was originally behind — it would be not a big trouble. The costs of this strategy are obvious: the driver himself and the cars driving behind in his lane lose some time due to the need to reduce speed.
Strategy 2
In order to wait, you need to have patience and have the necessary amount of time for this. An alternative may be an attempt to perform the necessary manoeuver «here» and «now.» According to this idea, the driver gives a sign to the cars behind him of the lane to which he is going to move. Those, in turn, in response to his signal should slow down a bit and «let the cars moving in front of them to go forward», thereby creating the gap of the necessary size in their flow. The time costs in this case are distributed between the cars of the lane, onto which the driver eventually switches.
In real life, both strategies are involved at the same time: at first, the driver slows down, waiting for a relatively large gap in the stream of the adjacent lane, and only after that, they give a signal to the cars moving in it about their intention to make a switching manoeuver.
Undoubtedly, access roads, highway exits and narrowings are not the only reason for the switching between lanes, which is worth remembering when designing roads. The ability of cars with higher speeds to overtake unhurried traffic is necessary in order to prevent the situation on the highway when it degrades to one large queue crawling at the speed of the slowest tractor. Nevertheless, the problem of coexistence of vehicles moving on a road at different speeds has a slightly different nature and can be separated from the issues in question, since the overtaking process and respective switching between lanes are not forced for the driver. If the driver does not hasten, according to the probability theory, a convenient opportunity to perform a manoeuver will be given to the driver naturally and for this he does not need to disturb the movement of other drivers.
The cost of a single switching
The behaviour of drivers in reality can be very complicated, but it is primarily crucial for us that the result obtained within model conditions remains plausible: each forced switching between lanes imposes a time penalty on traffic participants.
Let’s now evaluate how the amount of lost time depends on the density of traffic on the road.
We will consider the movement along each lane as a separate stream. Trying to stay at a comfortable distance from cars on the same lane, drivers thereby reserve a road stretch with a certain characteristic length d in the stream. Let ρ cars fall in a stream per unit length. We agree to call the flow density small, or to say that ρ is small if the product ρ × d is much less than 1.
At the moment when the driver realises the need to move to the next row, the probability that a road stretch with the length d, which the driver was going to occupy, will be not free, at small ρ, will be approximately proportional to ρ itself. If the described event really takes place, then two cars competing for a place will experience in total, as a result of the manoeuvers, some delay in the average constant value δ.
Assuming ρ is small, we can neglect the probability that their actions at this moment will affect the movement of other cars. Thus, when ρ is small, the time loss from one switching will be α⋅ρ, where the coefficient α is an empirically measurable quantity depending on culture, weather, speed limits (and so on), but remaining approximately constant in this particular time and for this city as a whole.
Loss intensity rate on a road stretch before the exit
The cars heading for the exit, before they get to the ramp (Chart 2), have to, sometimes even several times, switch to the adjacent row on the right. Each such manoeuver disturbs the flow, and as a result, the average speed in the section before the exit is noticeably lower than in the «transit» (deprived of the exits, entrances and forks) sections of the highway.
Chart 2
To pass some part of the way at a lower speed — represents for drivers (and their passengers) an additional amount of time spent on the trip. In other words, the area of the highway adjacent to the exit is a constant generator of time losses.
Let’s suppose that the average car speed ν and the flow density ρ at the frontal boundary of this stretch are the same for all lanes.
Moreover, let’s suppose that the density ρ and the flow rate q heading for the exit (the average number of cars falling onto the ramp per unit time) are simultaneously small, and s is the number of lanes on the highway. To get to the exit, the driver will make 1 to s switching manoeuvers. If the flow density on the ramp is much lower than ρ, then only the last manoeuver will be for the driver practically «for free», while the rest will in any case cause losses of α⋅ρ. On average, you will have to perform (0 + 1 + 2 +… + s — 1) / s = (s — 1) / 2 «expensive» manoeuvers.
Given the difficulties caused by all cars heading for the exit, we can create the formula for the intensity of time losses:
Iout = q ⋅ αρ ⋅ (s − 1)/2 = (α/2ν) ⋅ q ⋅ (sρν) ⋅ (1 − 1/s)
The value p = (sρν) is nothing more than the flow rate of all the cars moving along the highway in the direction in question (the average number of cars passing by a bus stop per unit time). The last remark gives us the opportunity to rewrite the formula for I a more symmetrical form:
Iout = (α/2ν) ⋅ pq ⋅ (1 − 1/s)
Loss intensity rate at the adjoining section of the access road
The situation arising on the highway behind the section where the access road connects with it largely repeats the situation on the section before the exit, although there are some differences. Let a small flow of cars of power q through the lateral ramp pours in the main traffic of the highway (Chart 3).
рис. 3
The ramp has only a finite length, so all newly arriving cars should be switched to the right edge lane of the highway. As a result, the traffic density in the right edge lane1 is locally higher than the average on the road, that’s why some drivers in it decide to switch to a less busy adjacent lane on the left, which, in turn, leads to a local increase in density already on the second lane. This process of switching between lanes will continue until the flow density is leveled out across the entire width of the highway. Assuming the average speed ν to be the same for all n lanes, we can expect that, upon completion of the switching processes, the flow power in each of them will increase by exactly (1/s)⋅q.
To see how much such switching will cost to drivers, we at first calculate the power of all switching flows. The flow from the ramp to the first lane of the highway we already know: it is equal to q. In order to equate the increase in the first lane power to (1/s)⋅q, the flow from the first lane into the second one should be (1 − 1 /s)⋅q, from the second into the third = (1 − 2 /s)⋅q, from the k-th to the (k + 1)th = (1 − k/s)⋅q. According to the last formula, the capacity of the switching flow to the left edge lane will be (1 − (s − 1)/s)⋅q = (1/s)⋅q, as commanded by common sense.
Since we know the time penalty of a single switching and the power of all switching flows, we can now calculate the total intensity of the losses generated by them:
Iin = αρ⋅q + αρ⋅(1 − 1/s)⋅q + αρ⋅(1 − 2/s)⋅q +… + αρ⋅(1/s)⋅q =
αρq (1 + 2 +… + s)/s =
αρq (s + 1)/2 =
(α/2ν) ⋅ q ⋅ (sρν) ⋅ (1 + 1/s).
Remembering again that sρν is the power p of the flow of all cars along the highway, we obtain the cost formula in its final form:
Iin = (α/2ν) ⋅ pq ⋅ (1 + 1/s).
Loss intensity rate at the symmetrical fork
In the previous paragraphs, we found losses from the interaction of flows, one of which was necessarily large, and the other was necessarily small. In order to demonstrate an approach to solving problems when the capacities of both flows are comparable in power, let us consider another extreme: a fork in which both branch directions are equally popular for drivers (Chart 4).
Chart 4
For convenience, cars going to the right on the fork will be called «blue», and cars leaving to the left — «red». Initially, cars of both «colours» move mixed, dispersed between all 2s lanes of the highway. As they approach the fork, the red cars begin to drift slowly towards the left n lanes, and the blue ones toward the s right: there are switching flows in the two directions between adjacent lanes. Unlike the access road example, these flows are no longer «relatively small». By the way, only between the two central lanes there is a forced exchange of traffic, the intensity of which in any of the directions (from left to right, or from right to left) is equal to a quarter of the power of the entire stream moving along the highway. Fortunately, in this situation there is a good enough way to estimate the generated costs.
At first, we can note that the process of dividing cars into «red» and «blue» most likely begins long before the fork and proceeds slowly, therefore, on the one hand, it should have little effect on traffic density within a separate row, and on the other, make switching streams stretched over long distances, thereby giving the opportunity to represent each of them as a combination of a large number of streams of low power (Chart 5).
Chart 5
Since now we are talking about small flows, albeit in larger numbers, nothing prevents us from reducing the problem in question to already solved ones. We can mentally divide the highway in the center into two equal parts, and then connect them together with a larger number of single-lane jumper roads, allowing red cars to get to the left and blue cars to the right (Chart 6). Due to obvious symmetry, when calculating the generated losses, we can focus on car of any one colour, for example, blue, and in the end just double the result.
Chart 6
Let speed ν and density ρ be the same for all lanes and remain constant over the entire stretch where cars are separated by colours. In this case, the flow power of all cars moving along the highway will be:
p = 2sρv.
Let q1, q2,… qm denote the flows of blue cars moving along imaginary jumper roads to the right half of the motorway. Suppose that shortly before the separation section in each lane of the motorway, both colours are represented with equal proportions of 50%, which implies that in total
q1 + q2 +… + qm equals to sρv/2, or in other words, p/4.
Losses generated by the flow qidue to its smallness, we can calculate by the formula:
Ii = Iout + Iin = (α/2ν)⋅(p/2)⋅qi(1 − 1/s) + (α/2ν)⋅(p/2)⋅qi(1 + 1/s) = (α /2ν) pqi
Summing up the last formula over all i, we find the losses generated only by the blue cars:
Iblue = (α/2ν)⋅p⋅(q1 + q2 +… + qm) = (α/2ν) p2/4.
The total losses, as already mentioned, will be twice as high and amount to:
Idiv = (α/2ν) p2/2.
Analysis of the obtained formulae
If we divide the intensity I, that is the amount of time totally lost by the participants per second, by the lateral flow q, which by definition is equal to the number of cars connecting or leaving the highway in one second, we will get the average losses caused by one such car:
iin = Iin/q = (α/2ν) ⋅ p ⋅ (1 + 1/s)
iout = Iout/q = (α/2ν) ⋅ p ⋅ (1 − 1/s)
Perhaps the most important thing in these formulae is the direct proportionality between the power flow of cars on the highway p and the unit costs i. Everything looks as if a car seeking to join, or vice versa — to leave the main flow, thereby causing constant disturbance to every driver nearby.
The second, interesting and very unexpected observation concerns the extremely weak effect on the intensity of the generated losses in the number of lanes near the highway directly next to the junction. As you can see, looking at the formula for Iout, the exit is generally the most time-efficient for a single-lane road (s = 1, iout = 0), and the difficulties caused by the adjoining access road for a three-lane and six-lane highway differ by only
100% ⋅ [(1 + ⅓) − (1 + 1/6)] / (1 + ⅓) = 12,5%.
If we consider that every car that has ever joined the traffic on the highway will eventually have to leave it, then it seems quite legitimate to use a unified value instead of iin и iout when calculating interchange losses
iav = (iin + iin)/2 = (α/2ν) ⋅ p.
Despite the fact that the formula for iav does not explicitly depend on the number of lanes, it must be remembered that its creating (see the assumptions for Iin and Iout) bases heavily on the assumption of low density of cars on the road, so it is unlikely to give satisfactory results when applied to too narrow highway with too much traffic.
Preliminary findings
In areas near junctions, traffic hindrances inevitably occur, taking time away from drivers, reducing the average speed, the latter leads to an increase in the density of cars and, as a consequence, the possible occurrence of traffic jams. The time losses associated with the separation and merger of car flows will be called switching losses.
Losses of a similar type are present one way or another in any switching scheme: be it a telephone or computer network, a multi-core microprocessor, or a mail delivery service.
When the driver joins, or, conversely, leaves the traffic on the highway, the switching costs incurred by his actions are proportional to the power of the flow of cars observed at that time on the highway.
To reduce switching losses throughout the city, it is necessary to carefully consider the road network implemented in it at the design stage. A bit later we will analyse this task in detail, but some obvious recommendations can be listed now:
- switching losses are proportional to the flow power on the highway — it is not necessary to enlarge the roads without the need, two small highways are twice as good as one big one;
- switching losses are proportional to the power of the side flows — it is worth designing the network so that the driver has to turn as few times as possible during his journey;
- mutual disturbance caused by the drivers of the main and side flows should be less on a citywide scale if we try to prevent merger of routes that overlap only in a short section of the road.
Economic prerequisites for the existence of cities.
A city model with 'random access'2
(Note 2: the term is taken from the RAM concept and means random by probability and even by time consumption.)
Perhaps the first stage of any project to design (or re-design) the city transport system is to try to determine what kind of switching the city really needs now and how its needs will change in the future.
Such an analysis can be carried out if we first divide the city into not too large, but not too small areas, and then for each pair of such zones indicate what approximate number of trips to one side or the other is needed by their inhabitants at one or another time of the day. By placing the predictions made in a matrix, you will thereby receive a migration needs matrix of the city residents.
Exactly for this matrix, we should search a network that allows drivers and passengers to spend as little time as possible on a separate trip, requiring from the city authorities as little resources as possible for the network realisation.
When it comes to existing cities, it is important here not to make a mistake and not to replace the number of trips that people really need with the number of trips that have historically been established under the influence of some obstacles or difficulties at the time of the design work. Probably, the transport network of Berlin «before» and «after» the fall of the separation wall can serve as the most striking illustration of what has been said.
This section will mainly deal with humanitarian issues in which I am not a specialist, but I think that discussing them as an amateur is nevertheless more correct than simply avoiding the problem.
In order to better represent the migration needs of the population, it is worth starting with the fundamental question: «What are cities for and what is their useful function?»
Let’s try to answer it not as ordinary residents of cities (and villages), but from the perspective of the person responsible for the process of urbanisation in some large and developed state. From this point of view, it is no longer important what historical motives once made so many people crowded into a tiny piece of land, or the reasons why they continue to do it now, it is crucial — what economic effect is made by the cities of one size or another and by what mechanisms this effect is achieved.
In my opinion, the main reason for the existence of large cities is, on the one hand, the opportunity for technology firms to find employees of rare professions, and on the other hand, the opportunity for people who have mastered rare professions to sell their services to companies interested in them on competitive terms. In a small (non-specialised) city, the production of many goods and services is either simply impossible, or puts the technology companies and their employees in the position of mutual hostages, without giving either one or the other any alternatives.
For example, take the not-so-rare profession of a school literature teacher. According to statistics, the need for them is approximately 1 teacher per 1000 people. In a regular school, 3–4 tutors teach literature. The choice of a job for a literature teacher can be called competitive if there are at least 4–5 secondary schools in the city, which, in terms of population, corresponds to about 15 thousand people.
Apparently, people with an engineering specialisation feel comfortable on the labour market in cities with a population of at least 100 thousand. Of course, there are also such professions, the demand for which appears only in cities with more than one million people, however the existence of multi-million cities does not make any economic sense to me.
After all the above-mentioned, two hypotheses look quite reasonable (the validity of which, however, does not affect the truth of the main contents of the article):
- the average adult has a need to travel most frequently over distances that capture 4–5 of the most promising jobs for them;
- for a significant part of the population that represents the rare and most economically valuable professions, the distance of the most frequent trips may well be comparable with the radius of their city.
As an enhanced reflection of hypotheses 1 and 2, in my examples I will often use the model of the city with 'random access', assuming that the power of the flows of required travel is the same between any two quarters of it, or, in other words, in all cells of the migration needs matrix there are the same positive number. If you randomly look at the records of trips made in such a city during the day, then for the next marked trip all quarters will have the same probability of being whether the start or finish of such trip, and no relationship between the position of the 'initial' and 'final' quarters should be observed.
Road networks with the simplest topology
Let’s try to apply the ideas described in the previous paragraphs to some types of city plans taken from life.
Linear city
The first large settlements were originated predominantly along the coast, in areas of a thin strip of land between the sea and the cliffs, or along the paths of busy roads, so in the process of growth they acquired narrow elongated borders. Many of these settlements have survived to our days, retaining their elongated shape and turning into modern cities (please see the illustration below).
(an excluded area of Rio de Janeiro, the author is unknown)
Often in such a city there is only one wide road around which it is built. Suppose that each quarter (zone of territorial division) generates a stream of travels with power 1, the number of all such quarters equals to n, and the city itself follows the 'random access' migration model.
Chart 7
Let us try to find for the parameters listed above how the average travel time and the required road area change with increasing n.
So, let all the quarters have the same shape and size, and their number multiplies by λ (lambda) times. It’s obvious that
- the length of the main road increases by a factor of λ.
Due to the accepted model of 'random access', 50% of the journeys that started in the right half of the city will end in its left half (the opposite will be correct too), therefore, with an increase in the number of quarters by a factor of λ, the power of the flow passing through the middle of the city will also multiply by λ times. Similar discussions with the same inference will be true if, instead of the middle, we take any point dividing the city in a given ratio (1:3, 2:5), which implies that
- the power of the flow along the main road increases by a factor of λ;
- the number of lanes of the main road required in each section multiplies by λ times.
More or less obvious that the average length of the trip, and with it
- the net travel time spent to cover the distance increases by a factor of λ.
All that remains to calculate is the number of times the time lost due to switching costs in one trip will increase. A lateral flow with power 1 enters into and comes out of each quarter, which together generate time losses with intensity:
I = Iin + Iout = (α/2ν) p⋅2,
where p is the power of the flow on the main road. We already know that the number of quarters and the flow power on the main road increases by a factor of λ, therefore, the total time losses generated by the network multiply by λ2 раз. On the other hand, the number of trips generated by the network, between which as a result all these losses are allocated, increases by a factor of λ, that’s why
- the net travel time lost due to switching costs increases by a factor of λ.
Let’s exhibit all the results in one table:
Linear topology
The number of address points (quarters) with power 1 …n
Total road area…O (n2)
Net travel time,
spent to cover the distance…O (n)
Net travel time,
lost due to switching costs…O (n)
Number of switching nodes…O (n)
Number of switching nodes, given the power of the side flows…O (n)
Notation used 'y = O (x)' means that the parameters x and y are functionally dependent, and when x grows without limit, the ratio x/y tends to a finite, different from zero, number.
Cellular city
The second, fairly common planning method is to arrange the quarters in the form of a rectangular matrix, similar to how portioned pieces are placed in a chocolate bar.
We agree to call such cities 'cellular'.».
(Los Angeles, photo: Slava Stepanov)
Chart 8 shows a pattern of a cellular city which consists of n (taking into account the 'halves') quarters, forming together a regular square. The quarters are separated from each other by a total of √n roads, conditionally stretching from west to east, and √n roads stretching from south to north. In total, these roads form √n×√n crossings, each of which can be implemented either as a traffic light intersection or through road bridges / overpasses.
Chart 8
Regardless of whether there is one-way or two-way traffic, any journey from point A to point B in a cellular city can be realised along a route involving no more than two streets and no more than one turn at an intersection.
Assuming that, as in the previous example, each quarter generates a stream of travels with power 1, and the migration needs of the population follow the 'random access' model, we can calculate, now for a cellular city, the laws by which the average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.
If the number of quarters increases by a factor of λ, then:
- the area of the city multiplies by λ times, and its linear dimensions while maintaining the proportions — by √λ,
- the average travel distance and the net time to cover it, being proportional to the linear dimensions, multiply by √λ times,
- the number of streets and the number of quarters adjacent to one given street multiply by √λ times,
- the power of the traffic flow, being proportional to the number of quarters with which the flow is 'in contact' (an explanation of this term will be given later), multiplies by √λ times,
- the required area of all roads grows as (number of streets) × (length of one street) × (power of street flow) = √λ⋅√λ⋅√λ = λ√λ
Lateral flows are divided into those that go from or towards the quarters and those that turn from one street to another at intersections. The power of first flows, according to the conditions, always remain equal to unity. Through the second ones, almost all traffic is moving, coming or leaving the highway, if we take into account that there are much more quarters in the city than quarters on one given street. As a result, the change in the power of the second flows can be estimated by the formula (change in the power of the flow) / (increase in the number of intersections on a particular street) = √λ / √λ = 1. Equality of the last ratio to the constant suggests that these flows do not significantly change with an increase in the number of quarters, therefore, the increase in switching costs generated by the network as a whole will be: (increase in the total number of quarters + intersections) × (change in the value of the flow on a single street) = λ√λ. Since the power of the migration flow generated by all quarters increased by a factor of λ, then
- net travel time lost due to switching costs increases by a factor of √λ
Let’s exhibit all the results in one table:
Cellular topology
The number of address points (quarters) with power 1…n
Total road area…O (n√n)
Net travel time,
spent to cover the distance…O (√n)
Net travel time,
lost due to switching costs…O (√n)
Number of switching nodes…O (n)
Number of switching nodes, given the power of the side flows…O (n)
Comparing the linear and cellular networks with each other, it is difficult not to notice that the increase in the resource intensity required for construction and the time spent on one trip, with the growth of the city, is much faster for the first network than for the second one. For example, a cellular city consisting of 100 quarters requires 10 times less asphalt, and traveling through it on average requires 10 times less time compared with a linear city of the same size. Therefore, it makes sense to use road networks with linear topology only in very small towns.
If for a while we forget about the existence of switching costs, then cellular topology can be considered an ideal way to design road networks, since it gives an asymptotically optimal O-estimate for both the average trip length and the required road area. Indeed, for any more or less 'compact' location of the city (with random access), the length of the trip will grow no slower than the square root of the area of the city, which is in turn usually directly proportional to the population. As a result, we get all the same O (√n).
The fact that a typical route in a cellular city runs along a 'corner' rather than a straight line, in principle, implies the opportunity to look for the best ways to plan cities, but the savings in the amount of 20% (that«s the maximum we can win if cars learn to travel through walls) are unlikely someday will force architects to abandon the rectangular arrangement of streets and roads.
The lowest possible limit of the network building (and maintaining) costs can be obtained by remembering that each car reserves a part of the lane for its movement. As a result, the total area of roads is proportional to the product of the average travel time (average trip length) and the number of cars in the city: O (√n)×O (n) = O (n√n) (compare with the table for a cellular city).
If we talk about the amount of time that is lost in travel due to switching costs, then surprisingly its relation to the amount of time to cover the distance does not asymptotically depend on the number of quarters in either cellular or linear city (O (√n)/O (√n) = O (1), O (n)/O (n) = O (1)). In other words, the percentage of time lost in travel due to switching, in both big and small cities, will be the same. From this we can conclude that, if there were no serious problems with switching costs in a small city (we can suggest they amounted to 10–20%), then in a big city they still should not be observed, and if they were, then they would remain to exist, no matter how the city grew and enlarged.
Since we do not know which of the alternatives is true (or rather, we know that problems with traffic in big cities do exist), it is worth trying to improve the topology of a cellular city so that the switching costs in it decrease at least by a factor of some constant times.
Useful examples of unrealistic networks
Let’s test if cellular topology follows the recommendations that we have developed by analysing the switching of flows on the highway.
1) Do not enlarge roads without the need.
— Yes. Traffic is distributed over many roads (compare with a linear city).
2) Avoid designing the network where the driver has to turn a large number of times in one trip.
— Yes. Any trip will most likely be carried out along a route requiring only one turn on the streets.
3) Try to prevent merger of routes that overlap only in a short section of the road.
— Here, perhaps, there is something to work on. Despite the minimum number of turns per trip, the route as part of the main highway flow passes through a large number of switching nodes (O (n)), in each of which valuable time is wasted.
The last remark motivates to investigate the following question: «What is the minimum of the average number of switching nodes through which a journey must pass through a road network connecting n quarters?»
The task of searching for such a network makes sense, of course, only on condition that the number of flows combined or divided by any switching node is preliminarily limited from above by a certain fixed value. Otherwise, you can always present a road network with n address points and a single mega-junction.
(the author is unknown)
It is much easier to investigate the real problem if it was previously possible to reveal at least part of the patterns using some simple, even if not at all realistic, model examples. Following this logic, we will temporarily forget about the geometrical limitations of road construction and the need of travelers to cover distances, focusing all our attention on how abstract networks solve the parallel addressing problem. Regarding the switching nodes, we will assume for now that each of them either divides the flow into two parts (the division node), or combines two flows into one.
Chart 9
Address tree
Let there be one start address point, where all travels, without exception, begin, and another n finish address points at which they end with equal probability (Chart 9).
It is required to build a transport network that allows the driver to go through as few switching nodes as possible.
The obvious (for programmers) solution, which suggests itself here, is to use a balanced binary tree, at the same time we need to place a single start point at the top of the tree, and place the remaining n finish points one in each of its leaves (Chart 10). The network constructed in the described way will be called as the direct Address tree.
Chart 10
Changing the directions of all flows in the direct Address tree to the opposite, we thereby obtain the reverse Address tree, the purpose of which is to connect n start points with a single finish point.
In cases where n is a power of two, any route inside the Address tree passes exactly through log2n switching nodes, which is undoubtedly (asymptotically) less than the same indicator for a network with cellular (O (√n)), or linear (O (n)) topology.
Two simplest types of logarithmic networks
Using 'tree-like' networks as building blocks, it is not difficult to generalise the previous solution to the case when there are k start points. There are two easy ways to do this.
The first way is to use the reverse Address tree to first collect the routes of all the trips into one common stream, and then, using the direct Address tree, divide this stream into sub-flows addressing to its destination (Chart 11, top scheme).
Chart 11
If k and n are powers of two, then, in the end, any route passes exactly through the log2k + log2n узлов коммутации. witching nodes. We agree to refer to the networks designed according to the algorithm just described as (one-way) Logarithmic networks with preliminary merging.
The second way to solve the same problem can be realised by reversing in the first solution the order of the merging and division operations. Its implementation can be described as follows: for each start point we create a unique set of imaginary duplicates of all the finish points, and after that, we connect it to these duplicates (no longer imaginary) with a direct Address tree.
To complete the network design, it remains only to connect now each finish point with its k imaginary duplicates by applying the reverse Address tree (Chart 11, bottom scheme).
Whenever n and k are powers of two, the number of switching nodes along any route within the newly built network will again be equal to log2k + log2n.We agree to refer to such networks as (one-way) Logarithmic networks with preliminary division.
Conversion of one-way networks into symmetric ones
Generally we refer to any network as one-way if the address points connected by it are divided strictly into start and finish points. By default, for one-way networks, it will be assumed that it provides at least one route of possible travel from any start point to any finish point.
Besides a lifelong journey, it is difficult to find examples where some address points would serve as the start of a route only, and others would only be its end. We will bring our reasoning closer to reality if we also include networks in which any two address points are connected by routes in both directions. We agree to refer to such networks as symmetric.
In fact, there is no ideological gap between one-way and symmetric networks: each symmetric network can also be used as a one-way network, and each one-way network, initially connecting an equal number of start and finish points, can be transformed into a symmetric one (Chart 12).
Chart 12
Charts 13a and 13b show the 'symmetric' forms of the Logarithmic network with preliminary merging and the Logarithmic network with preliminary division. Their examples prove the fundamental possibility of connecting n quarters by such a type of network, within which the number of switching nodes during any trip will be proportional to the logarithm of the number of quarters in the city.
Chart 13 a
Chart 13 b
Accurate lower limit estimate
A wide variety of networks has already been accumulated so far, each of which include own function describing dependency of the average number of switching nodes along the journey on the number of address points in the city. Nevertheless, we still do not know how small this number can be in principle for a given number of quarters. The lower limit estimate can be obtained using the information approach.
Actually, let some road network connect n address points to each other, and the migration needs of the population are such that any trip, no matter where it started, has an equal chance of ending anywhere in the city.
To solve the problem in question, we will generate an auxiliary informational message, following this recipe: for a long period of time, we will collect records of all the trips that have a fixed start point, and randomly write down the addresses where these trips ended. The resulting message will be a random sequence which consists of the names of n address points of the city.
One way to transmit this message to Mars is firstly to encode all the names into binary words of the same length, thereby turning the original message into a sequence of 0s and 1s, and secondly to send the resulting sequence through a digital communication channel. Since for distinguishable coding of the set of n names binary words of log2n length are required, the length of the digital message will be:
(number of records)×log2n characters.
The most interesting thing is that according to information theory, regardless of the encoding algorithm used, it is simply impossible to transmit the same message with a smaller number of binary characters.
An alternative to directly transmitting the encoded names of the finish points can be a method in which it is indicated for each trip in what possible direction the route turned at the next fork. According to our assumptions, all the forks in the network can only have two branches, therefore, to indicate the direction in each case, exactly 1 bit is required. For anyone who has a map of the city and knows the starting point, the chain of bits will be enough to trace each route and restore the original sequence of their destinations. If the average number of forks (division nodes) visited during one trip is x, then the length of the binary message with the new encoding method will be: (number of records)×x.
As there was said earlier, the new encoding method cannot be more efficient than the direct binary address transfer method, therefore: (number of records)×x ≥ (number of records)×log2n, that’s why:
x ≥ log2n.
Although the last inequality was initially deduced for a group of trips that had a common fixed start point, it turned out to be independent of the specific choice of this point. That’s why we can extend the result to all trips in the city at once, thereby obtaining the first part of the estimate in question:
P1) Provided that each new trip has equal probability of finishing at any of the n address points of the city, the average number of division nodes per route cannot be less than log2n.
Mentally turning the clock back, we can convert each finish point of the trip into the start point, and each binary node of the division of the network — the binary node of the merging. This little trick allows us to automatically obtain from P1 the second, missing part of the estimate:
P2) Provided that each completed trip would have equal chances to start at any of the n address points of the city, the average number of merging nodes per route cannot be less than log2n.
If we recall the existence of a logarithmic network with preliminary merging and a logarithmic network with preliminary division, then we immediately get two examples of networks that are optimal in terms of the number of switching nodes, which, on average, is visited inside them during one trip. Let’s see if this quality helps reduce the intensity of the generated switching losses.
Switching costs in Logarithmic networks
If we compare the networks with preliminary merging and preliminary division, the first one looks much more attractive because of its simplicity. Unfortunately, this simplicity also has a reverse side to the coin: combining all routes into one stream contradicts i1 recommendation, thereby potentially causing large time losses. The network with preliminary division seems to meet the requirements i1 — i3, however, judging from Chart 13b, it tends to rapidly increase the number of road limbs and switching nodes used. The latter quality may make networks of this type too expensive for practical use.
We will analyse these questions in more detail. To begin with, we agree that the city follows the migration model with 'random access', and the flow generated by any of its address points has a power 1.
Losses in the networks with preliminary merging
In Chart 14 you can see a diagram of flows arising from the above-mentioned conditions within the network with preliminary merging.
Chart 14
It seemed to me convenient to depict the network itself in its one-way form, implying that each start and finish points, signed with the same numbers in the Chart, actually mean the same address point in the city.
Based on the diagram, we can calculate the switching costs intensity generated in the network. Let’s start from the left half, where through the reverse Address tree, all routes are gathered in one flow. Each switching node in this part of the network represents the place where two one-way highways merge into one (Chart 15).
Chart 15
If initially each of the roads is efficiently loaded, then after their merging, there is no need to reduce the number of lanes, as a result, there should not be any respective switching costs.
Let’s suppose that a flow with power 1 is already sufficient to effectively load the road along at least two lanes. In this case, we will come to a rather unexpected conclusion: the merging of car flows inside the Logarithmic network with preliminary merging occurs absolutely 'for free', without causing any time losses.
Calculation of the costs that arise in the right half is not much more difficult. This part of the network is a direct Address tree, each node of which is a symmetrical fork we have already studied. When the incoming flow with power p, the intensity of the losses arising at the fork is (α/2ν)⋅p2/2. The power of the flow entering the root fork is: n, therefore, the intensity of losses in the root node is: (α/2ν)⋅n2/2. In each next generation of the Address tree, the number of forks doubles, and the power of the incoming flow is halved. As a result, the formula of the losses inside the whole tree will take the form:
It_div1 = (α/2ν)⋅(½)⋅[ n2 + 2 (n/2)2 + 4 (n/4)2 +… + (n/2)⋅22 ] =
(α/2ν)⋅(n/2)2 [ 1 + ½ + ¼ +… + 2/n ] ≈ (α/2ν)⋅n2
Since the power of the flow of trips generated jointly by all address points is n, the time costs per trip are on average (α/2ν)⋅n, thereby showing a linear dependence on the size of the city.
When it comes to abstract networks, it is difficult to give any meaningful estimate of the area of the roads they use. As an alternative measure of structural complexity, the total power of all side flows can be calculated. As planned, the resulting value should reflect the resource intensity of building of all the interchanges required by the network. I can«t say that in practice this method will always have a good interpretation, but some approximate idea of the amount of work ahead will probably be obtained.
Inside the Logarithmic network with preliminary merging, lateral flows exist only in the direct Address tree, and their total power for each generation of nodes is the same: n/2. In total, there are log2n of generations of nodes in the tree, thus a new method for assessing complexity gives an estimate of complexity: O (n log2n).
Logarithmic networks with preliminary merging
The number of address points with power 1…n
Average travel time
lost due to switching costs:
asymptotics…O (n)
exact value…(α/2ν)⋅n
Number of switching nodes…O (n)
Number of switching nodes, given the power of the side flows…O (n log2n)
Losses in the networks with preliminary division
We now turn to the analysis of the Logarithmic network with preliminary division, again assuming that the network is used to connect the address points with power 1 in the city with 'random access'.
Chart 16 shows a fragment of it consisting of one address point along with the direct and reverse Address trees adjacent to this point.
Chart 16
First of all, we can estimate the intensity of the switching losses generated by the fragment.
The costs incurred during division of the flows can be found by the following equation It_div1 = (α/2ν)⋅n2, which was deduced for the direct Address tree in the previous example, 1 instead of n. Indeed, the direct Address trees in Charts 16 and 14 have the same depth and involve the flows similar in power (note: similarity means the ability to get one set of values by multiplying the values from another set by some fixed number, to illustrate, the similarity between triangles by their sides). Due to the quadratic relationship between the value of the switching costs that occur at a single fork and the power of its incoming flow, a simultaneous decrease in all flows by n times will reduce losses in the entire tree by n2 times, therefore, instead of the old (α/2ν)⋅n2, we obtain a value equal to:
It_div2 = (α/2ν).
We can now calculate the value of the costs in the left half of the fragment.
Due to the little value of the combined flows of the road inside the reverse Address tree, this time it would not be reasonable to build a road wider than two lanes. Merging under such conditions is no longer for free: in contrast to the previous example, there are narrowing areas on the highway (Chart 17), where switching costs will be necessarily occur.
рис. 17
Assuming that the driver is aware of the forthcoming narrowing in advance, we can assume that the process of switching from the dead end lane is slow, being stretched hundreds of metres along the highway. In this case, we have the right to resort to the trick that we used earlier to calculate the losses at the symmetrical fork — to divide the total migration flow q into many small parts qiand then interpret each of them as a side stream from the ramp. The losses generated by each such substream are calculated by the formula:
Ii = (α/2ν) ⋅ pqi ⋅ (1 + 1/s), however, there are two subtleties here.
The first one is that cars will not migrate further than the next row.
In fact: the flows in the two central lanes, due to obvious symmetry, should always have approximately the same density, so drivers will not have much reason to cross the middle line. From the observation made, it can be inferred that in the formula for losses caused by partial lateral flow, s is equal to 1.
As the cars leave the edge lanes, switching into two central lanes, the flow power inside the central lanes gradually increases, changing in each case from P/2 to P. Thus, the second subtlety is the significant dependence of p on the number of substream i, which makes us write:
not
Ii = (α/2ν) ⋅ pqi ⋅ (1 + 1/s),
but:
Ii = (α/2ν) p(i) ⋅ qi ⋅ (1 + 1/s).
In the case when many small parts, into which the migration flow was divided, were all of equal size, the dependence p(i) is expressed by a linear graph (Chart 18)
Chart 18
To calculate the loss intensity rate, we must either resort to integration, or (this makes it possible to make a particularly simple form of an integrable function) take as p(i) the average value on the graph equal to 3P/4. Since the total migration flow from the side of each edge lane is P/2, the intensity of losses in a separate merger node will be:
Imerge = 2 ⋅ (α/2ν) ⋅ (3P/4) ⋅ (P/2) =
= (α/2ν) 3P2/4.
To find the time losses generated inside a fragment on the reverse Address tree, we can apply the formula for Imerge to each of its nodes:
It_merge = (¾) ⋅ (α/2ν) [ 1⋅(½)2 + 2⋅(¼)2 + 4⋅(1/8)2 +… + (n/2)⋅(1/n)2 ] ≈
≈ (¾) ⋅ (α/2ν) [ ¼ + 1/8 + 1/16 +… ] =
= (3/8) ⋅ (α/2ν) [ ½ + ¼ + 1/8 +… ] =
= (3/8) ⋅ (α/2ν).
The total costs arising within the fragment due to the merger and division of flows will be:
It_merge + It_div2 = (α/2ν) [ 1 + 3/8 ] = 11/8 (α/2ν).
A logarithmic network with preliminary division contains only n such fragments, and exactly n flows with power 1 are generated by its address points, so the value we have just found is exactly equal to the switching losses per average trip.
In fact, it«s more important for us not even a specific number, which is equal to the specific switching costs, but the fact that these costs remain constant with increasing n. The latter makes the Logarithmic network with preliminary division asymptotically the most economical with respect to switching losses among all the types of networks that we studied earlier.
Unfortunately, leadership is not free. Despite the vanishingly small value of the overwhelming number of flows, each Address tree included in the network contains about 2n two-lane road limbs and approximately n full-sized switching nodes. There are 2n trees in the network, which meansO (n2) limbs and nodes, which makes it not only the most economical in terms of time efficiency, but also the most expensive network to build, among all the examples considered.
As for the sum of the lateral flows, its value, as can be easily calculated, grows with the speed O (nlog2n) and in this case does not carry much meaning.
Logarithmic networks with preliminary division
The number of address points with power 1…n
Average travel time
lost due to switching costs:
asymptotics…O (1)
exact value…11/8 (α/2ν).
Number of switching nodes…O (n2)
Number of switching nodes, given the power of the side flows…O (n log2n)
Balanced logarithmic network
Exceptionally small switching losses and at the same time considerable resource consumption of the network construction, arising from applying of a logarithmic network with preliminary division, make us want to find some way to change its design so that the resource consumption would be significantly reduced whereas the switching costs would not increase substantially.
Obviously, the main c
