(Jean-Claude Mézières)

Translation provided by ChatGPT, link to the original article in Russian

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )
Link to «Summary» (ру / eng )

1. About this series of articles

1.1 Central result

If I haven't made a critical mistake, I have discovered an astonishing passenger transportation scheme with unique characteristics. Imagine this scenario: you are in a big city and need to get from point A to point B. All you need to do is walk to the nearest intersection and indicate the destination on your smartphone or a special terminal installed there. In a few minutes, a small but spacious bus will arrive for you. The bus is designed for easy entry without bending, and you can bring a stroller, bicycle, or even a cello inside. It provides comfortable seating where you can stretch your legs. This bus will take you to the nearest intersection to point B, and you will reach your destination without any transfers. The entire journey, including waiting at the stop, will take only 25-50% more time than if you were traveling by private car. Based on my estimation, in modern metropolises, this type of transportation will be widely adopted, and the cost of a trip on such buses will be similar to the fare of a regular city bus.

Surprisingly, the reasoning behind these findings is based on relatively simple mathematics, and perhaps even a talented high school student, under fortunate circumstances, could have guessed them on their own. The practical significance of the topic and the modest level of mathematical requirements prompted me to make an effort to write the article in such a way that the reader could follow the path of discoveries, learn some research techniques, and gain a successful example to explain to their children the purpose of mathematics and how it can be applied in everyday life.

1.2 Initial Problem

The story of how I embarked on this research and discovered its most valuable result is quite amusing. Allow me to briefly tell you about it. This article is not my first work in the field of urban transportation issues; I have already published two or three articles (№1, №2), depending on how you count them. Sometimes, students and various entrepreneurs reach out to me regarding their topics. About six months ago, I received a call from a very ambitious young man. He asked if I could help him come up with a way to make it easier and more convenient for ordinary (and not so ordinary) people to commute to and from work. His initial idea was to transport workers using something like a school bus and create a new, more convenient form of public transportation based on that concept. As you can imagine, the idea was quite grandiose and enticing. However, at that time, I was working on my book and wanted to avoid getting too involved in another task. Nevertheless, I couldn't completely refuse, so I offered to help this young man formalize his problem and find those who would be capable of solving it. However, as is often the case with entrepreneurs (and I don't blame them at all—I've been there myself), the author of this wonderful idea disappeared from our communication. Yes… perhaps the author vanished, but at that point, his idea had already captured my thoughts, and I set aside all other matters to study it.

Quite quickly, I found a decent solution — shared taxis with one transfer, which is the subject of one of the chapters of this work. At that time, I was almost certain that there was no better solution to the problem and tried to prove it rigorously. However, I couldn't seem to come up with a proof. In the end, I had to question the hypothesis of «impossibility» and attempted to construct a hypothetical «counterexample» for it. To my surprise, such a counterexample actually emerged.

In this series, I plan to publish 3 articles: the current one — «Preliminary Analysis,» the next one — «Experiments on the Torus,» and the final one — «Practically Significant Solutions.» Their content is more of a journal documenting the steps of its directed search rather than describing a specific result. By choosing this narrative approach, I wanted each subsequent step to be almost evident to the reader, while the final result wouldn't seem astonishing.

Reading the article will take some time. If the formulas are not displayed correctly, try reloading the page several times.

2. City Model and Model of Intraurban Daily Migration

2.1 Idealization as a Research Method

In this article, we will focus only on the problems of various types of public transport that arise due to physical or mathematical constraints and therefore cannot be eliminated in principle. Problems that can be overcome due to engineering errors, imperfections in public infrastructure, lack of knowledge, or oversight will be left to specialists in other fields. The best way to see which problems are insurmountable for a particular scheme of passenger transportation is to observe its operation in the conditions of an ideal imaginary city. If a certain type of public transport exhibits drawbacks in idealized conditions, it is evident that they will persist in real-world conditions.

2.2 Ideal Grid City

Let's suppose you are tasked with designing a new city with a convenient transportation system. You wouldn't go wrong if you choose a grid layout for it, commonly known as the Manhattan grid. In an ideal Manhattan grid layout, the streets form a regular orthogonal network, dividing the city into uniformly shaped and sized blocks. In one of my previous works, I demonstrated that in cities with a Manhattan grid layout, all street traffic can be coordinated into green waves (link). When a city operates under this regime, any driver who maintains the recommended speed and moves only forward can reach the end of a street, stopping at traffic lights at most once. In another one of my works, you will find arguments that among all encountered layouts, the grid layout contributes the least to traffic congestion. These observations should explain to the reader why I consider grid cities as the idealized model in this context.



Our main model will be a rectangular grid city with square half-kilometer blocks and two-way traffic. The choice of half-kilometer block length is not arbitrary — smaller lengths make it difficult to organize green waves, while larger lengths result in excessively long distances that need to be covered on foot. An alternative model is a grid city with alternating one-way traffic and square blocks measuring 250 meters. This model will mainly be used in exercises. In terms of optimality, both models are essentially equivalent to each other. In the final chapters, the size and aspect ratio of the blocks are insignificant, as long as the blocks are not excessively large.

Another simplification I will soon employ is folding the flat rectangular city into a torus. The thing is, a rectangle has edges, which makes the positions of points on it non-equivalent: some points are closer to the center, while others are closer to the periphery. This non-uniformity introduces qualifications into the reasoning and makes the calculations unnecessarily technically complex. A torus, on the other hand, has no edges, and all its points are in completely equal conditions. Just like on a sphere, by using a suitable «rotation,» any point on the torus can be mapped (translated) to any other point. Public transportation in a toroidal grid city encounters the same problems as public transportation in a regular «flat» city, except for the special behavior at the edges. What's more important, these problems have similar solutions in both cases. For readers unfamiliar with the concept of a (flat) torus, I have included two introductory chapters in the article.

2.3 Migration Model. City with Random Access

A detailed analysis of urban passenger transportation is hardly possible without knowing how, where, and how often the residents of the city make their trips. In this article, we will adhere to the following simplest assumptions:
1) Within the same time frame, approximately the same number of people in any given block have the desire to travel to another point in the city.
2) For a randomly selected trip, regardless of its starting point, any other point in the city is equally likely to be the destination (the probability of a point being the end of the trip is uniformly distributed throughout the city).

We will refer to this migration model as the «city with random access.»

Undoubtedly, our migration model is purely academic, and the results obtained based on it are estimations. In a real city, human migration may be subject to entirely different laws. Therefore, the implementation of any of the described transportation schemes should be preceded by careful field measurements, and the scheme itself should be appropriately adapted to the results of these measurements.

3. Inherent Limitations of Some Traditional Forms of Public Transportation

Before attempting to create new forms of public transportation, let's try to understand the advantages and disadvantages of existing ones.

3.1 Basic City Bus

By a basic bus, we mean not only regular city buses but also other forms of transportation such as trolleybuses or trams. These are the most conservative types of mass transportation, and their operation follows the same principle: a certain number of vehicles with sufficiently spacious interiors move along predetermined routes, picking up or dropping off passengers at each stop.

Let's consider a city with rectangular blocks of half a kilometer and two-way traffic. The obvious way to create a network of routes for a basic bus in such a city is to assign a separate route for each street, so that buses travel in both directions from one end to the other at intervals of a few minutes. As for the stops, it is most reasonable to locate them at intersections: one for each of the four directions. This arrangement of stops facilitates quick transfers from one direction to another. The described transportation network, in the narrow sense, is what we will refer to as a basic bus system.


Figure 2

The basic bus as a mode of transportation has several pleasant characteristics:

1) Simple route planning logic.
2) It is possible to reach any other stop from any given stop with just one transfer.
3) If you are already on a street, the stop in any direction is located no farther than half the length of a block.
4) Observations in small-sized cities with low population density show that the average number of passengers on basic buses is sufficient to make the trip relatively inexpensive.

However, despite these advantages, the basic bus has one significant drawback: it is, in theory, very slow and seemingly impossible to improve. The following reasoning explains why.

Let's assume that the maximum allowed speed in the city is 60 kilometers per hour (or 17 meters per second, or 1 kilometer per minute). When departing from the previous stop, the bus cannot instantly reach its maximum speed, and similarly, it cannot instantly come to a stop before the next stop. In both cases, it will take some time for the bus to accelerate or decelerate. Thus, the bus's journey between adjacent stops can be divided into three segments: the acceleration segment, the deceleration segment, and the middle segment, which the bus travels at a constant maximum allowed speed.

According to Google, a comfortable acceleration for passengers is when the bus increases or decreases its speed by 0.7 to 1 meter per second in one second. For calculations, let's assume that the bus's acceleration on the acceleration and deceleration segments is constant and equal to 1 meter per second per second. With these parameters, the bus will require 17 seconds to reach its full speed and another 17 seconds to come to a complete stop. The constant acceleration during acceleration and deceleration means that the speed-time graphs during these periods will be inclined straight lines. By calculating the area under these graphs, we find that the acceleration segment and deceleration segment have a length of 144.5 meters, occurring at the 289-meter mark. We assumed that the distance between adjacent stops is equal to the length of a block, which is 500 meters. Therefore, the middle segment, where the bus travels at its maximum speed, has a length of 211 meters and will be covered in approximately 12 seconds. As a result, the entire half-kilometer journey from stop to stop will be completed by the bus in the best case scenario in 17 + 17 + 12 = 46 seconds. Even if the simple bus does not have any delays at the stops themselves, its average speed would not exceed 500/46 ≈ 11 meters per second.


Figure 3

Now let's estimate the average speed of a bus taking into account the duration of its stops. Various sources state that the average time for boarding or alighting a passenger is within the range of $$ seconds. Let's take an estimate of $$. Suppose that on each stop, an average of $$ people get on or off the bus. In that case, the boarding-alighting process will require approximately $$ seconds of stoppage on average, and the average speed will not exceed $$ m/s. Therefore, being inside a regular bus, you will be moving through the city at an average speed more than two times slower compared to a private car or personal taxi.

Exercise: If you have read the article about green waves, show that the operation of buses can be integrated into the green wave schedule, allowing them to pass through all intersections without any waiting. However, this is only possible if the average speed of the buses is evenly divisible by the speed of propagation of the green waves.

3.2 Bus Network Including Local and Transit Routes

Can city buses be made faster? To answer this question, let's break down the travel time of a bus between two sufficiently distant points, denoted as $$ and $$, along its route.

Figure 4

As seen in the above Figure 4, this travel time can be represented as the sum of three components:

$$ — This component represents the time it would take to travel the distance between $$ and $$ at the maximum allowed speed $$.

$$ «number of stops between $$ and $$»$$ «time for a single acceleration/deceleration». Each bus stop requires the bus to first decelerate and then accelerate again. In total, they result in an approximate loss of $$ seconds.

$$ «number of passengers boarding or alighting between $$ and $$»$$ «penalty per passenger boarding/alighting».

In these notations, the average speed of the bus on the segment $$-$$ is given by the expression:

$$

If we want $$ to be as high as possible, we need to minimize the values of the components $$, $$, and $$.

We have no control over the component $$, as it depends on the distance $$ and the maximum allowed speed $$.

The second component $$ is obtained by multiplying the penalty for acceleration/deceleration by the number of stops the bus makes between points $$ and $$. Since the maximum allowed acceleration is a given value, we cannot change the penalty for acceleration/deceleration. However, we can reduce the number of stops between points $$ and $$ by spacing them out more.

The third term, $$, is obtained by multiplying the passenger boarding/alighting time, which is a constant value, by the total number of people who boarded or exited the bus on the segment $$. The average number of people who board or exit the buses on route $$ per unit of time at stops between $$ and $$ is almost independent of the distance between these stops. Indeed, if there is no alternative transportation, then everyone who needs to travel from $$ to $$ by route $$ will eventually get on their bus, whether there are $$ stops or $$ stops. The same applies to those who intend to travel from $$ to $$ using this route.

Let's assume that on the segment $$ of route $$, an average of $$ people leave per minute, while $$ people arrive per minute. If the interval between the movements of buses on route $$ is $$ minutes, then on the segment $$, in each interval, an average of $$ passengers will board and alight (prove it!). By reducing the interval $$, we can also reduce the time that the bus has to spend on passenger boarding/alighting between points $$ and $$.

And so, if we want to increase the average speed of buses on route $$, we need to minimize the interval between them and maximize the distance between stops. However, there are logical limitations here. Reducing the time interval between buses by a certain factor also reduces the average number of passengers on board, thereby increasing the cost per trip for each individual passenger. On the other hand, increasing the distance between neighboring stops by a certain factor also increases the average walking distance that passengers have to cover to board the bus they need or to reach their final destination from where they will alight the bus. The average walking distance in a single journey is approximately equal to the distance between stops, so making it excessively large is not advisable.


Figure 5

The problem of increasing fares with decreasing bus intervals seems to be unsolvable, but there is a rather obvious and simple solution for the problem of sparsely spaced stops. The solution is to have two duplicate bus routes on each street: one with closely spaced stops, resulting in a «slower» route, and another with stops located at greater distances from each other, making it potentially «faster.» We will refer to the slow routes and the buses operating on them as local, and the fast ones as transit. Naturally, it is necessary to ensure that the stops for local buses are placed at every intersection along their route, while the transit buses only stop at every $$-th intersection along their path (see Figure 6).

Figure 6

The problem of increasing fares with decreasing bus intervals seems to be unsolvable, but there is a rather obvious and simple solution for the problem of sparsely spaced stops. The solution is to have two duplicate bus routes on each street: one with closely spaced stops, resulting in a «slower» route, and another with stops located at greater distances from each other, making it potentially «faster.» We will refer to the slow routes and the buses operating on them as local, and the fast ones as transit. Naturally, it is necessary to ensure that the stops for local buses are placed at every intersection along their route, while the transit buses only stop at every $$-th intersection along their path (see Figure 6).

Figure 6

Let's consider the scenario where the city has both local and transit bus routes, as shown in the above diagram. Now let's think about the actions a traveler should take to reach a destination point $$ to a sufficiently distant point $$.

If both points are located on the same street and do not occupy any particular position, a relatively fast way to travel from $$ to $$ would be as follows:
First, you need to walk from point $$ to the nearest intersection $$ and catch a local bus there that goes towards the nearest stop $$ where transit buses stop. Upon reaching $$, get off the bus and transfer to a transit bus that is heading towards point $$. On this second bus, ride until you reach $$, which is the closest stop to point $$ among the rest. In general, $$ is not the closest intersection to $$, so you will need to catch another local bus towards point $$ and get off at the intersection closest to it, $$. The remaining distance should be covered on foot.

This travel algorithm can be summarized as «L -> T -> L,» where «L» represents the local bus and «T» represents the transit bus.

Exercise: Is the algorithm described above the fastest in terms of average travel time between random points A and B? If not, how should it be modified to become the fastest? What information about the traveler and buses does your solution use?

Figure 7

In the general case, when points $$ and $$ do not lie on the same street and do not have any specific positioning, the journey from $$ to $$ can be performed according to the following sequence: «l->t->l->l->t->l» (Figure 7). As you can see, the travel scenario is not the simplest and involves a total of 5 transfers. However, with a little bit of thought and by arranging the stops of transit buses slightly differently (as shown in the figure below), the maximum number of transfers required for the passenger can be reduced to 4.

Figure 8

Any bus route network constructed according to the pattern shown in Figure 8 will be referred to as a "local-transit bus network."

Exercise: Find all possible travel scenarios on a local-transit bus network between points of general (non-specific) positioning. Try to describe and classify all special cases, such as travel along a single street or from a point near a transit bus stop.

Let's make a rough estimate of what value $$ should be in order for the average speed of transit buses to approach the standard $$ kilometers per hour ($$ km/minute).

On the stretch between adjacent transit bus stops, the bus undergoes one acceleration and one deceleration. As calculated earlier, the total time lost during these stretches is approximately $$ seconds. Let's assume that the transit bus picks up and drops off $$ passengers at each stop, resulting in a dwell time of $$ seconds. If the bus stops are located at every k-th intersection, and the block length is half a kilometer, then $$. From everything said, it follows that the formula for the average bus speed can be written as:

$$

The average speed of the transit bus will be close to its maximum only if:

$$

Therefore, we can use the approximation:

$$

and rewrite $$ as:

$$.

The last formula shows that there is no point in trying to make the passenger boarding/alighting time $$ much smaller than the acceleration/deceleration penalty $$ — it will not significantly increase the average bus speed. For simplicity, let's assume that the interval between transit buses is chosen in such a way that $$ seconds. This value of $$ corresponds to approximately $$ passengers boarding and alighting at each stop. Substituting $$ sec, $$ sec into $$, we obtain the inequality for $$:

$$ or

$$.

If, for example, we want transit buses to travel at an average speed of at least $$ km/h ($$ of $$), then $$ must be at least $$, which means there should be approximately $$ kilometers between neighboring stops of the transit bus. This estimation allows us to determine the minimum size of a city where transit buses with transit routes make sense: something around $$ transit segments or $$ kilometers in length. A city of such size, with a standard density of $$ inhabitants per square kilometer, would have a population of approximately $$ people.

According to my rough estimates, in cities larger than $$ km (with a population of over $$ million people), a significant portion of typical travel routes would be covered by transit buses, and the average speed of such trips could realistically approach $$ ($$ m/s or $$ km/h). It seems like the perfect transportation for megacities, but having 4 transfers is not exactly how I would dream of starting my day!

Exercise: Consider the possibility of using underground metro systems instead of transit buses for the same purpose. What advantages and disadvantages are associated with the solutions you have discovered? Try to make numerical evaluations.

3.3 Personal Taxis

Fast, often very convenient, but also very expensive. Takes up a lot of space on the road and emits a significant amount of exhaust gases per passenger-kilometer.

4. Taxis for Shared Trips between City Districts

4.1 Shared Trip Concept

Personal taxis are perhaps the fastest mode of urban transportation, but undoubtedly the most expensive. In many cases, there is only one passenger being transported in a whole car with a hired driver. Hence, the idea of making taxi trips cheaper becomes evident: it is enough to come up with a method that allows a taxi to carry multiple passengers at once. If such a method is found and implemented, the cost of each kilometer traveled by a taxi can be divided among all the passengers who were in the vehicle at that time. The more passengers on average in the vehicle, the cheaper the trip should be for each of them.

However, the concept of shared trips faces an obvious obstacle: if a shared taxi picks up every person who signals it on the road, there may be passengers in the vehicle who are not heading in the same direction. To transport such passengers to their respective destinations, the taxi would have to travel from one end of the city to the other, wasting its working time and the time of its clients.

Figure 9

One obvious way to address the issue of mismatched fellow travelers is to always try to fill the taxi with passengers whose pickup and drop-off points are close to each other. Below, one of the shared taxi schemes that implements this idea is discussed in detail.

4.2 Operational Guidelines

Let's consider a grid-based city of size $$. We divide it into a grid of equally sized square cells $$. The idea behind this cell division is to allow only those individuals from the same cell who are heading towards the same destination to become fellow travelers. For simplicity, we can assume that a separate small fleet of vehicles is responsible for transporting passengers between each specific pair of cells, and passenger boarding and alighting only occur at intersections.

When dealing with personal taxis or private transportation, each trip from one intersection to another can be made along the shortest zigzag route at an average speed close to the maximum allowed in the city. However, enabling a shared taxi to transport multiple passengers simultaneously generally requires lengthening and complicating the route within the starting and ending squares. Of course, there are situations where a shared trip is nearly as fast as a personal taxi ride. For example, if the pickup points for a group of fellow travelers are all located along one street, and the drop-off points are also along another street (possibly a different one), the shared trip route can be planned so that each passenger is delivered to their destination via the shortest route for themselves.

However, the situation just described is more of an exception than the rule. In general, the pickup and drop-off locations of passengers traveling together will be randomly scattered within the starting and ending squares. To gather them first and then disperse them, the taxi vehicle will have to follow a winding route, reduce speed at turns, and cover extra miles. Due to all these factors, the journey in a shared taxi will obviously take, on average, longer than the same trip in a personal taxi. Figure 10 illustrates a fairly typical situation where even two passengers cannot be jointly transported without increasing the travel distance, at least for one of them. Let's try to estimate how much slower, on average, the inter-cell shared taxi is compared to a personal or private car.


Figure 10

Lemma on routes of intercellular taxi:
Let's assume that there are n travelers who need to be picked up at the «start» square $$ and dropped off at their respective destinations in the «finish» square $$, with the taxi already located at $$. For any route $$ that solves the problem of shared transportation for the travelers, there exists a route $$ such that:

1) Route $$ also solves the transportation problem for these travelers.
2) Route $$ has the same boarding and alighting order for the travelers as $$, but is one of the shortest routes with this order.
3) When using route $$ by the taxi, the trip length for each passenger is the same or shorter compared to using route $$.
4) The entire route $$ can be divided into three continuous segments: initial, middle, and final. The initial segment lies entirely within $$, the final segment lies entirely within $$, and the middle segment represents the shortest step-like curve between the end of the initial segment and the start of the final segment.
5) If squares $$ and $$ are not horizontally or vertically aligned, route $$ can be selected in such a way that its middle segment represents a shortest $$-shaped curve drawn between the nearest (corner) intersections of squares $$ and $$.


Figure 11

Proof.
The idea of proving 1)-4) is to replace each segment $$ between two taxi stops (boarding or alighting points) with a $$-shaped shortest path. Now, let's consider 5). By sequentially rotating the map by $$ degrees, we can ensure that square $$ is strictly above and to the right of $$. Let $\$inline\$\backslash beta^\$inline\$$ be the route constructed from $$ using the $$-shaped shortest paths as described earlier. One of the links in route $\$inline\$\backslash beta^\$inline\$$ is a $$-shaped shortest path $\$inline\$\backslash gamma^\$inline\$$ between the last passenger pickup point $$ in square $$ and the first passenger drop-off point $$ in square $$. We replace segment $\$inline\$\backslash gamma^\$inline\$$ in $\$inline\$\backslash beta^\$inline\$$ with a broken line $$ drawn according to the following rule: first, along the $$-shaped shortest path (possibly degenerate into a line segment or even a point) from $$ to the top-rightmost intersection in $$, then along the $$-shaped shortest path (possibly degenerate) to the bottom-leftmost intersection in $$, and finally, from there, along the $$-shaped shortest path (possibly degenerate) to point $$. It is easy to see that $$ is also a shortest path between $$ and $$, and the resulting route $$ after replacing $\$inline\$\backslash gamma^\$inline\$$ with $$ satisfies each of the conditions 1)-5).

4.3 Traversal Algorithm

Let $$ and $$ be two arbitrary cells selected from different rows and columns of the grid $$. By sequentially rotating the map by $$ degrees, we can ensure that cell $$ is strictly above and to the right of $$. Let the top-rightmost intersection in $$ be denoted as $$, and the bottom-leftmost intersection in $$ be denoted as $$. The lemma about routes allows us to assume that all taxi vehicles traveling between $$ and $$, upon leaving $$, pass through intersection $$, and upon arriving at $$, pass through intersection $$.

Now, let's imagine that at the specified point $$ in cell $$, an empty taxi appears, which must make a trip between $$ and $$, and then arrive at the specified point $$ in cell $$. The future passengers of this taxi, let's say there are n of them, are randomly scattered across all intersections within $$. What traversal algorithm should the taxi follow to pick them all up? Similarly, what algorithm should it follow to drop off all these passengers at their destinations after reaching cell $$? Clearly, both of these algorithms should minimize the taxi's route within the cells $$ and $$. I haven't been able to find the optimal traversal algorithm (perhaps you can come up with a solution), but constructing an acceptable solution is not that difficult.

To simplify calculations and reasoning, let's assume that the length $$ of the cells $$ into which the city is divided is much larger than the size of the blocks. If this assumption holds, then multiple horizontal and vertical streets will pass through each cell $$, and the distance between adjacent streets compared to the size of the cell will be small. This allows us to approximately consider that both horizontal and vertical roads pass through each point of the cell $$, and each of these points can serve as a pickup or drop-off location for taxi passengers. Another consequence of this simplification is that intersection $$ will be located in the top-right corner of $$, and intersection $$ will be in the bottom-left corner of $$.

Let's start with an estimation of the asymptotics. Suppose the number of passengers $n$ is a perfect square. We arrange these individuals in the positions of nodes of a regular square grid with a cell size of $$. The «snake» shown in the figure traverses all the grid points and ends up in the upper-right corner at point $$, with a length of $$. It is not difficult to realize that this snake represents one of the shortest routes for visiting the positions of our imaginary travelers. Indeed, no matter what route the taxi vehicle chooses, the minimum distance it will have to travel between the pickup point of each previous and each subsequent passenger is $$, and there will be a total of $$ such «transfers». Hence, the total traversal length will be at least $$.

Now let's construct a solution for the general case where the initial positions of the $$ travelers are randomly scattered within $$. To achieve this, we divide the cell $$ into $$ identical strips. The essence of the traversal algorithm is to go around all these strips in a snake-like manner, starting from the leftmost one, and only pick up passengers within the current strip. We establish the rule that while inside a strip, the vehicle should strictly move along its central line until the next traveler it needs to pick up is precisely to its right or left. Each time this happens, the taxi driver should make a sidetrack to pick up the passenger and return to the central line of the current strip using the same path. If the taxi follows this procedure, the length of the part of its route that travels along the central lines of the strips will be approximately $$. Each deviation maneuver to pick up a passenger will, on average, add $$ units of additional distance, which sums up to an extension of the route by approximately $$. Therefore, the average length of traversing the starting cell will be approximately $$.


Figure 13

Let's consider that the cell $$ is divided into the same vertical strips as the cell $$. It should be obvious that when the intercell taxi reaches $$, it will be able to deliver its passengers to their desired destinations, following the exact same algorithm as during their pickup. After this vehicle drops off all its passengers and reaches the point $$ at the end of the last strip, it can be assigned to a return trip from $$ to $$.

4.4 Average Length of the Shortest Staircase Path between Two Random Points in a Rectangle

Let's consider a rectangle $$ with a horizontal side of length $$ and a vertical side of length $$. By staircase curves inside $$, we mean piecewise linear curves composed of horizontal and vertical segments. Now, let's take two arbitrary points $$ and $$ inside $$. To further explore this, we need to address two questions.

The first question is to determine which staircase curves from $$ to $$ will have the shortest length. The second question is about the average length of such curves when points $$ and $$ are chosen randomly and independently within $$, with the probability distribution describing this selection being uniformly distributed across $$.

To answer the first question, we will consider every staircase path from $$ to $$ as a chain of vectors, where the start of each subsequent vector coincides with the end of the previous one. Let $$ and $$ be the projections of points $$ and $$ onto the bottom side of $$, and let $$ and $$ be their projections onto the left side of $$. It can be observed that if $$ is an arbitrary staircase path from $$ to $$, then the projections of all its horizontal segments will sum up to the vector $$, while the projections of all its vertical segments will sum up to the vector $$.


Figure 14

In that case, and only in that case, when all the horizontal segments of $$ have the same direction, the sum of their lengths will be equal to the length of the vector $$. Similarly, when all the vertical segments of $$ have the same direction, the sum of their lengths will be equal to the length of the vector $$. Staircase paths where both the horizontal and vertical segments are oriented in the same direction are referred to as monotonic paths. Thus, a staircase path will be the shortest path if and only if it is monotonic.

Now let's address the second question. Suppose points $$ and $$ are randomly and independently chosen within the rectangle $$. We know that the length of any shortest staircase curve from $$ to $$ is equal to the sum of the projections of segment $$ onto the bottom and left sides of $$. Therefore, to calculate the average length of such curves, we only need to compute the average length of segments $$ and $$.

It can be shown, and it is nearly obvious, that the uniform distribution and independence of the selection of points $$ and $$ within $$ imply the uniform distribution and independence of the random positions of their projections onto each side of $$. Let's then calculate the average distance between two randomly chosen points $$ and $$ on a segment $$ of length $$. Since the result is clearly proportional to $$, it suffices to consider the case when $$.

Let $$ and $$ represent the distances of points $$ and $$ from the left end of segment $$. In this case, the pair $$ fully encodes the choice of $$ and $$, and the probability of having a particular pair $$ is uniformly distributed within the unit square of the Cartesian plane.


Figure 15

The distance between $$ and $$ is described by the function $$, and its graph consists of two identical pyramids with a height of $$ and a base area of $$ each. The average distance between $$ and $$ is equal to the average value of the height of the graph $$, which is the total volume of the pyramids divided by the total area of their bases. The volume of a pyramid is equal to one-third of the product of the base area and the height. Therefore, the average distance between two random points on a segment of length $$ is $$, and the average distance between two random points in a rectangle of size $$ is $$.

Exercise: Show that in a rectangle of size $$, the average length of the shortest staircase curve constructed between a randomly chosen point and the center of the rectangle is $$, and between a randomly chosen point and its corner is $$.

4.5 Average Duration of Inter-Cell Taxi Journeys

If all journeys in the city are made by private cars, the routes of most of them can be planned along the shortest staircase curve. In this case, the average trip length would be close to $$, and the duration would be $$. What will be the average length and duration of journeys if all city residents make them using inter-cell taxis?

Let's consider a traveler who needs to travel from an intersection $$ in the square $$ to an intersection $$ in the square $$. We divide their future route into three segments: the initial segment within $$, the middle segment between the closest corners of $$ and $$, and the final segment within $$. The initial and final segments are part of the zigzag path that the taxi takes around the cells $$ and $$. With randomly located intersections $$ and $$, the traveler will traverse approximately half of each zigzag on average. Therefore, the average length of the initial and final segments of their journey will be approximately $$ each. This approximation holds when the number of passengers $$ carried by the vehicle at once is sufficiently large.

To estimate the average length of the middle segment, let's assume that the size of the cells into which the city is divided is much smaller than the size of the city itself, i.e., $$. If this is the case, the cells $$ appear as points on the city scale, and the average distance between them, up to an order of magnitude of $$, is $$. Consequently, with relatively large $$ and relatively small $$, inter-cell taxi journeys in the city will be on average approximately $$ longer than private car trips.

The average time required for a journey in the city using inter-cell taxis can be found as the «average trip length divided by the average speed, plus the average waiting time for transportation.» We estimated the average trip length as $$. Let's neglect the time for acceleration, braking, boarding, alighting, and other minor delays encountered by passengers, and assume that the average speed of the taxi is close to the speed limit v in the city. Furthermore, we assume that taxis traveling between a pair of cells follow each other with a time interval of $$. If that's the case, a person who has just decided to travel from cell $$ to cell $$ will have to wait, on average, approximately $$ units of time for an available taxi. Putting it all together, the average travel time on an inter-cell taxi is approximately

$$,

which is

$$

longer than the average travel time by a private car.

4.6 Average Number of Passengers in the Cabin

How many passengers does an inter-cell taxi carry at once? Let's assume that, on average, there are $$ individuals per unit area with the intention to travel within the city. During the time interval $$, which is the time between taxis traveling between $$ and $$, the number of individuals with such an intention within cell $$ will be, on average, $$. However, not all of them will have their destination within cell $$. The probability that a randomly chosen trip ends in cell $$ is $$, which is the ratio of the area of that cell to the total area of the city. As a result, on average, each taxi traveling between $$ and $$ will have:

$$

passengers striving to travel.

The formula written above predictably shows that the larger the size of the cells we divide the city into and the larger the movement interval we set for the taxis circulating between these cells, the greater the number of passengers each of them will transport at once. However, we cannot make the cell size $$ and the movement interval $$ too large, otherwise the trip on the intercellular taxi will become excessively long. We require that the average travel time on the intercellular taxi differs from the average travel time in a private car by no more than a factor of $(1 + \lambda)$. This requirement leads us to the inequality:

$$,

from which:

$$,

or in the limit:

$$.

Substituting the expression for $$ into $$, we obtain the equation relating the parameters $$, $$, and $$:

$$

Let's find the values of $$ and $$ that maximize the quantity $$ given a specific $$. For simplicity, let's consider the case when the city has a square shape and $$.

Taking derivatives directly here would be too cumbersome, so we will use a little trick. Notice that the constraint equation consists of two terms. Let's take an arbitrary $$ and $$ ranging from zero to one, and distribute their sum between the terms of equation $$ in the ratio of $$:

$$

$$

From which we have:

$$,

$$,

$$,

$$

$$

Now we can optimize $$ with respect to $$ and $$. These parameters will be optimal when

$$

subject to the condition

$$.

From the two equations above, we immediately have:

$$,

which implies $$, $$.

Substituting the optimal values of $$ and $$ into the formulas for $$, $$, $$:

$$,

$$,

$$.

4.7 Estimation for Real Cities

Let's see how $$, $$, and $$ would look like if we take $$, $$, and $$ corresponding to real cities, and set $$ to $$. We will obtain the population size $$, population density $$, and the allowed speed $$ from encyclopedic sources. With a population of $$ and density $$, the square city will have a size $$. We will estimate $$, which represents the average number of trips starting from a unit area in one unit of time, based on the following assumptions:

Let's assume that each city resident makes an average of $$ trips per day, and the migration activity is evenly distributed over $$ morning hours and $$ evening hours. In a city of size $$, there are $$ people, and in $$ minutes they will make $$ trips. Therefore, during the periods of migration activity, an average of $$ people should start their journey per minute from a 1-square-kilometer area. Let's move on to specific examples.

For a hypothetical New York (London, Moscow):
Population $$ million people,
Density $$ people/sq km,
Effective diameter $$ km,
Allowed speed $$ km/min,
$$ people/min sq km,
$$ people,
$$ km,
$$ min

For a hypothetical Berlin:
Population $$ million people,
Density $$ people/sq km,
Effective diameter $$ km,
Allowed speed $$ km/min,
$$ people/min sq km,
$$ people,
$$ km,
$$ min

For a hypothetical Paris:
Population $$ million people,
Density $$ people/sq km,
Effective diameter $$ km,
Allowed speed $$ km/min,
$$ people/min sq km,
$$ people,
$$ km,
$$ min

For a hypothetical Prague:
Population $$ million people,
Density $$ people/sq km,
Effective diameter $$ km,
Allowed speed $$ km/min,
$$ people/min sq km,
$$ people,
$$ km,
$$ min

4.8 Critique

The estimates we obtained above show that the idea of shared trips has theoretical validity (Uber can make it happen) and should be further explored. As for the intercellular taxi scheme, while it serves as a good starting point for research, it is not well-suited for practical implementation. The main reasons for its limited applicability can be summarized as follows:
1) Only in very large cities will there be enough fellow passengers to fill a very small bus, so intercellular taxi cannot be considered as mass transport.
2) The claim that traveling by intercellular taxi in the city takes, on average, no more than $$ times longer than using a private car is only valid if the destination is chosen randomly each time. If you plan to travel between neighboring squares using intercellular taxis every day, it would be faster to walk.

In the following sections, we will develop non-stop public transport schemes that completely overcome problem 2) and, to a large extent, problem 1), but they will only be suitable for cities with a population above one million. Therefore, let us consider an interesting solution that can effectively operate in smaller cities.

5. Shared Taxi with One Transfer

5.1 Guiding Considerations

Let's consider a city with a square shape and a side length of approximately 10 km, populated with a density of around 5000 people per square kilometer. With these assumptions, the city would be home to approximately 500,000 people, so it cannot be considered small. The average travel distance within the city would be $$ km = $$ km, and the maximum distance would be $$ km.

If we set the permissible driving speed in this city to be $$ km/h ($$ km/min), the formula for the optimized number of fellow passengers in intercellular taxis would give us:

$$ passengers.

Can we somehow increase this number?

To make it easier to understand how this can be done, let's make some changes to the taxi movement regulations. Firstly, we will assume that vertical and horizontal roads pass through the center of each cell $$, and taxis only move between cells along these roads. Secondly, we will require that the taxi moves from the starting cell to the destination cell along a $$-shaped path $$, and out of the two possible paths, it chooses the one that starts with a horizontal segment.

If we observe the taxis carrying passengers from cell $$ to cells in the $$-th column, we will notice that they all share a common segment of the path: from the center of $$ to the center of $$. So why not transport the passengers traveling from $$ to the cells in the $$-th column with a common bus up to the center of $$, and then come up with something there. Let's do just that.


Figure 16

To make it easier to understand how this can be done, let's make some changes to the taxi movement regulations. Firstly, we will assume that vertical and horizontal roads pass through the center of each cell $$, and taxis only move between cells along these roads. Secondly, we will require that the taxi moves from the starting cell to the destination cell along a $$-shaped path $$, and out of the two possible paths, it chooses the one that starts with a horizontal segment.

If we observe the taxis carrying passengers from cell $$ to cells in the $$-th column, we will notice that they all share a common segment of the path: from the center of $$ to the center of $$. So why not transport the passengers traveling from $$ to the cells in the $$-th column with a common bus up to the center of $$, and then come up with something there. Let's do just that.


Figure 16

5.2 Vehicle Movement Regulations

Alright, for each cell $$ in the $$-th row, we have a separate fleet of taxis whose sole purpose is to pick up all the travelers within that cell whose destinations are in the $$-th column and transport them to the center of the cell $$. Thus, the entire flow of travelers from the $$-th row to the $$-th column is now accumulated at the center of the cell $$. The next step is evident: in each cell $$ of the $$-th column, we need to establish a separate fleet of taxis whose sole task is to pick up travelers from the center of $$ and shuttle them in a zigzag pattern within the cell $$.

If we extend the described rules to all rows and columns of the grid $$, we will obtain a shared taxi movement scheme that allows travelers to reach any intersection from any other intersection with just one intermediate transfer. However, this movement scheme is not yet fully efficient.

Indeed, within such a scheme, all the shared taxi cars are distributed into two roles: some solely collect passengers from their starting positions — let's call such cars «collecting» cars, while others only deliver them to their destinations — let's call them «delivering» cars. When a collecting car reaches the transfer point, it drops off all its passengers and returns empty to its home cell. Similarly, after a delivering car has once again transported all its passengers within its home cell, it travels to the transfer point empty, ready to pick up the next passengers there.

Can we optimize the scheme so that all cars operate at full capacity? It turns out we can. To achieve this, we establish a one-to-one correspondence between the sets of cells $$-th row and $$-th column by defining that cell $$ corresponds to cell $$. Next, we establish the rule that whenever a collecting car from cell $$ and column $$ reaches the center of cell $$, it drops off its passengers and transforms into a delivering car for the $$-th row and cell $$. In its new role, this car can immediately pick up waiting passengers there and transport them to cell $$. Similarly, we establish the rule that whenever a delivering car from the $$-th row and cell $$ drops off its last passenger, it becomes a collecting car between that cell and column $$.

Thanks to the implementation of the two new rules, the shared taxi cars will always operate at full capacity. The route of each car will follow a circular pattern: from its «home» cell $$ to the transfer stop at the center of $$, then to the second «home» cell $$, further to the transfer stop at the center of $$, and finally back to $$ (Figure 17).


Figure 17

5.3 Travel Delay and Passenger Count

The travel routes for taxis with one transfer, excluding any additional transfers, remain almost the same as those for intercellular taxis. The average delay in traversing the snake-like sections within the starting and finishing cells remains unchanged and is given by:

$$,

However, the average time spent waiting at the stop for a suitable car has doubled (one needs to wait twice), and it is now approximately:

$$.

Now let's calculate the expected number of passengers in the car. When the car serves as a delivery vehicle between cell $$ and column $$, during the traversal of $$, on average, it should pick up

$$

If we want the travel time for taxis with one transfer to be, on average, no more than $$ times longer than travel by personal car, we should write the inequality:

$$.

To optimize $$, we set

$$,

$$,

where

$$,

$$.

After the transformations, we have:

$$,

which implies:

$$

and consequently:

$$

As an approximation, $$, $$ would maximize $$, if so, then the final forms of the formulas will be:

$$,
$$,
$$.

Let's see what values $$, $$, and $$ will have for taxis with one transfer in the familiar cities with $$.

For a hypothetical New York (London, Moscow):
Effective diameter $$ km,
Permitted speed $$ km/min,
$$ people/min km^2,
$$ people,
$$ km,
$$ min.

For a hypothetical Berlin:
Effective diameter $$ km,
Permitted speed $$ km/min,
$$ people/min km^2,
$$ people,
$$ km,
$$ min.

For a hypothetical Paris:
Effective diameter $$ km,
Permitted speed $$ km/min,
$$ people/min km^2,
$$ people,
$$ km,
$$ min.

For a hypothetical Prague:
Effective diameter $$ km,
Permitted speed $$ km/min,
$$ people/min km^2,
$$ people,
$$ km,
$$ min.

For a hypothetical standard half-million city:
Population $$ people,
Density $$ people/km^2,
Effective diameter $$ km,
Permitted speed $$ km/min,
$$ people/min km^2,
$$ people,
$$ km,
$$ min.

5.5 Critique

From the above estimates, it can be seen that the average occupancy of taxis with one transfer is approximately twice as high as the average occupancy of intercellular taxis, all else being equal. But!

Like intercellular taxis, taxis with one transfer prove to be too slow for transportation if all your trips are made between closely located cells. Like intercellular taxis, the scheme of taxis with one transfer, as presented here, is not designed for practical implementation: in the following parts, we will explore more advanced implementations of this scheme.

---

Let's start the discussion! If you would like to discuss anything in detail, you can email me at magnolia@bk.ru.

Sergey Kovalenko,
April 2023.

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )
Link to «Summary» (ру / eng )