How to become an author
Search
Write a publication
Pull to refresh

Affordable as a Bus, Comfortable as a Taxi: A Promising Type of Public Transport for Large and Medium-Sized Cities.Part2

Level of difficultyMedium
Reading time56 min
Views1.2K
Algorithms*The future is hereMathematics*TransportUrbanism
Opinion
Translation
Original author: Sergey Kovalenko

(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 )

Experiments on the Torus


This is the second part of a study dedicated to exploring new public transportation movement schemes. In the first part, we examined the simplest non-stop scheme and a single-transfer scheme based on it, which can be implemented in a grid city on a plane. In this part, our city model will be a grid city on a «flat» torus. Unlike a rectangle, a torus has no edge, and the positions of all points on it are absolutely equivalent. Due to the absence of an edge and (transitive) symmetry, calculations for a toroidal city are simpler, and numerical results are nearly identical to those for a rectangular city on a plane. These two conditions make a toroidal grid city an ideal testing ground for new passenger transportation movement schemes. In this article, we will explore two such schemes on the torus, and in the next one, we will return to the plane and adapt the results obtained here for use under the realistic conditions of a rectangular city.

The content of this study is not standalone and presupposes familiarity with the first part of the article. To understand Chapter 2, you will need a level of mathematics that corresponds roughly to the first two years of university; for everything else, high school level should suffice. It can be helpful to have a pencil and a piece of paper at hand while reading. If your browser displays formulas incorrectly, try refreshing the page a few times.

1. Euclidean Torus


1.1 Rectangle with Mirror Teleportation


Let's take a rectangular sheet of paper $\Pi$ and place it in front of us so that we can refer to its top, bottom, right, and left edges. Then, imagine that little drawn figures can move across the surface of $\Pi$. For these figures, we will establish the following teleportation rules:

1) every time a figure crosses the top boundary of the sheet at some point $A$, it is immediately teleported to the mirror-symmetric point $A'$ on the bottom boundary of the sheet, and vice versa;

2) every time a figure crosses the right boundary of the sheet at some point $B$, it is immediately teleported to the mirror-symmetric point $B'$ on the left boundary of the sheet, and vice versa;


(figure 1)

What will happen if a figure tries to exit the boundary of the sheet through its corner, for example, through the top left? In this case, we will assume that the figure is crossing two sides of the sheet at once: the top and the left, hence both rules 1) and 2) apply. It's easy to check that no matter the order of applying these rules, the result will be the same: the figure from the top left corner will be transferred to the bottom right corner.

1.2 Geometric Interpretation.


The teleportation between the opposite edges of the rectangle $\Pi$ can be visually implemented. To do this, first align the bottom edge of the sheet $\Pi$ with the top and glue them together, resulting in a hollow cylinder. Next, this cylinder needs to be significantly flattened, bent into a bagel shape, and its ends glued together. If everything is done correctly, the result will be a torus $T$. The line where the top edge of the sheet was glued with the bottom will be one of the parallels on this torus, and the line where the right edge was glued with the left — one of its meridians. The movement of any figure on the original sheet of paper $\Pi$ can now be viewed as its movement on the torus $T$ glued from this sheet, and vice versa. With this mapping, the teleportation of a figure between two opposite sides of $\Pi$ occurs exactly when its movement on the torus $T$ crosses the line where these sides were glued. Due to this duality, we will say that the rectangular sheet with mirror teleportation $\Pi$ is a representation of the torus $T$. Moreover, since every small patch cut from the surface $T$ can be laid out on a plane, we will call the torus itself $T$ flat.


(figure 2)

We have already talked about the meridians and parallels of the torus, let's give at least a semi-formal definition to these concepts. Let $\Pi$ be a rectangle with mirror teleportation, $T$ — the torus glued from it. We will call any segment $I$ on $\Pi$, the ends of which lie on the sides of $\Pi$, a through segment. Among all through segments, only strictly vertical and strictly horizontal ones have ends connected by the teleportation rule. Such segments will turn into circles when gluing the sheet into a torus. We will call horizontal through segments on $\Pi$ and the resulting circles on $T$ the parallels of the torus, and the vertical through segments on $\Pi$ and the circles formed by them on $T$ — its meridians.

1.3 Main Maps.


Let's glue a flat torus $T$ from a rectangular sheet $\Pi$ and apply some drawing on its surface. If we then carefully cut the adhesive seams, we get the original sheet of paper, which now carries a «cut» drawing from the torus. In this sense, the original sheet of paper $\Pi$ can be considered as a map of the surface of the torus $T$, similar to those used by humanity to depict, for example, the surface of the Earth. The torus can be cut not only along its adhesive seams. As a result of various cuts, different surfaces and a different number of whole components can be obtained.

Exercise. Try to cut the torus in such a way that you get a doubly twisted paper ring. Try to find such a cut that gives two paper rings, connected in a two-link chain (a fragment of a Christmas garland). A paper ring that is twisted only once is a Möbius strip. Think about whether a Möbius strip can be cut out of a torus.

In cases where a single flat sheet is obtained as a result of cutting a torus, we will call this sheet its map. Of course, not all maps of the torus will have a rectangular shape. Maps that are obtained by cutting the torus along some of its meridian and some of its parallel (i.e., parallel to the adhesive seams), we will call main. It should be obvious that every main map is rectangular.

Let $M$ be one of the main maps of the torus $T$. Each point $P$ on the map $M$ represents a single point $p$ on the torus $T$. For internal points on the map $M$, this correspondence is one-to-one. At the same time, if point $P$ lies on any of the sides of $M$, then $P$ itself and the point $P’$ symmetrically opposite to it on the opposite side of $M$ (we will call such pairs of points conjugate) represent the same point $p$ on $T$. In particular, all four corner points of the map $M$ are different representations of the point of intersection of that parallel and that meridian of the torus $T$, along which the map $M$ was obtained.

From the very definition of the main maps, it follows that each meridian and parallel on them will look like a through-segment with conjugate ends. We will assume that all main maps are oriented in space in such a way that the parallels on them are horizontal, meridians — vertical, and the directions up-down, right-left on all of them coincide.

It is easy to check that for any point $O$ on the torus, there is exactly one main map in which $O$ is strictly in the center. We will denote this map as $M_O$ and talk about it as the main map, centered at the point $O$.

1.4 Transformations of one main map of a torus into another


The fact that all main maps are the result of cutting a torus along its parallels and meridians gives us a key to understanding how to obtain one main map from another. Imagine that we have two main maps $M'$ and $M''$ of the torus $T$. Suppose the first is obtained by cutting the torus $T$ along its parallel $p'$ and meridian $m'$, and the second — by cutting along the parallel $p''$ and meridian $m''$. On the map $M''$, the image of the parallel $p''$ will be the set of all points of the lower and upper edge of $M''$, the image of the meridian $m''$ — the set of all points of its left and right edge. As for the map $M'$, in the general case, the parallel $p''$ and the meridian $m''$ will be depicted on it as «ordinary» horizontal and vertical through segments.

(Figure 3)

To turn the map $M'$ into the map $M''$ it is enough to perform the following actions:

1) Cut $M'$ along the parallel $p''$, swap the lower and upper segments, and then glue them together. The resulting sheet will also be a main map, let's denote it as $M*$. The lower and upper boundary of $M*$ will serve as the parallel $p''$, as in the map $M''$, and the meridian $m''$, as in the map $M'$, will be its internal through segment. It remains to
2) Cut $M*$ along the meridian $m''$, swap the right and left segments, after which glue them back together. The result of these actions will exactly be the map $M''$.

1.5 Curves on the torus


Let's discuss how the main maps depict curves (continuous lines) on the surface of the torus.
Let $M$ be the main map of the flat torus $T$, and $\gamma^M$ be an arbitrary curve on $M$. If we glue the opposite edges of $M$, we will turn it back into $T$, while the curve $\gamma^M$ will become a curve on the torus. Thus, each curve on the main map $M$ can be thought of as a curve on the surface of the torus $T$. In the opposite direction, the latter statement is not true, as not every curve on the surface of $T$ will become a curve on $M$ after transforming it into the main map $M$.

Suppose $M$ is to be obtained by cutting $T$ along its parallel $p$ and meridian $m$. Consider an arbitrary curve $\gamma^T$ on the surface of the torus $T$. The points of intersection of $\gamma^T$ with the lines of future cuts $p$ and $m$ divide it into a sequence of segments ${\gamma}_1, … {\gamma}_N$. Each of these segments will become an independent curve on $M$ after cutting $T$, and their sequence will have the property that the starting point of each next curve will be conjugate to the end point of the previous one. This time, the opposite statement is also true: any sequence ${\gamma^M}_1, … {\gamma^M}_N$ of curves on $M$, in which the starting point of each next curve is conjugate to the end point of the previous one, will turn into some single curve $\gamma^T$ on the surface of $T$ after gluing the map $M$ into the torus $T$. In this sense, we will say that the sequence of curves ${\gamma}_1, … {\gamma}_N$ defines a curve $\gamma^T$ on $T$.


(Figure 4)

For an arbitrary curve $\gamma$ on the surface of a flat torus of an arbitrary meridian $m$ and parallel $p$, we can construct the projection of the set of points $\gamma$ onto $p$ along $m$, denote it as $\gamma^p$ and the projection of $\gamma$ onto m along $p$, which we will denote as $\gamma^m$. The sets $\gamma^p$ and $\gamma^m$ will either be segments on $p$ and $m$, or completely coincide with $p$ or $m$. We will call the length of $\gamma^p$ the width or horizontal span of the curve $\gamma$, and the length of $\gamma^m$ — its height or its vertical span. From the properties of parallels, it follows that the definition of horizontal and vertical span does not depend on the choice of a specific $p$ and $m$.

When projecting passenger transport schemes, we will always strive to ensure that each trip on this transport takes as little time as possible. This goal cannot be achieved if one does not make sure that the routes of travel on such transport are in some sense the shortest curves between the points of their beginning and end, or curves close to the shortest ones. Let's try to understand what the shortest curves of the flat torus look like, in particular, how they are depicted on its main maps.

1.6 Shortest paths on the torus.


In the survey of shortest routes, we will be interested in two cases: the shortest routes among all the curves on the torus and the shortest routes among so-called «stepped» curves. We will call such polygons «stepped», where each segment is either a horizontal or vertical segment (a piece of parallel or meridian of the torus).

The shortest route from point $A$ to point $B$ in the class of all curves on the plane, or within a rectangle is, as is known, (directed) segment $AB$ (recall why). To formulate which routes on the plane are the shortest in the class of stepped curves, let's note that each stepped route defines a certain direction on each of its straight segments. It is not difficult to check that on a plane or inside a rectangle, the stepped route $\gamma$ is the shortest if and only if all its horizontal segments, as well as all its vertical segments, are directed in one direction (see paragraph 4.4 part 1). For example, if point $B$ is above and to the right of point $A$, then the shortest stepped routes from $A$ to $B$ will be exactly those where each horizontal segment «looks» to the right and vertical ones — upwards (all steps «lead» to the right up).

If the plane is equipped with Cartesian coordinates with a horizontal axis $Ox$ and a vertical axis $Oy$, then the above-written criterion of shortestness can be reformulated in another interesting way. We will call an arbitrary route $\gamma$ monotonic if the movement of a point along $\gamma$ is accompanied by a (non-strictly) monotonic change in its coordinates $x$ and $y$. Try to convince yourself that on a coordinate plane, the stepped route $\gamma$ will be the shortest if and only if it is monotonic. The length of any monotonic stepped curve with ends $A$ and $B$ equals the sum of the lengths of the vertical and horizontal components (projections) of the vector $\vec {AB}$.

image

(Figure 5)

On the flat torus $T$, things are a bit more complicated with the shortest paths. For instance, if you take a rectangular sheet $\Pi$ with mirror teleportation between the edges as a representation of the torus, you can indicate such pairs of points $A$ and $B$ on it that the path from $A$ to $B$ consisting of two or even three segments and teleportations between their ends will be shorter than the segment $AB^{\Pi}$.


(Figure 6)

Fortunately, by using a special choice of the main map, the issue of constructing the shortest paths on the torus can be greatly simplified. It turns out that if $M_A$ is the main map of the torus $T$, centered at its point $A$, then for any point $B$, the shortest route that connects $A$ and $B$ on $M_A$ will also be the shortest route that connects $A$ and $B$ on $T$. Conversely, every shortest route between $A$ and $B$ on $T$ will be depicted on the map $M_A$ as its shortest between $A$ and $B$. This is equally true for routes shortest in the class of all curves, and for routes shortest in the class of stepped curves. In particular, the shortest line on the torus between $A$ and $B$ will be depicted on the map $M_A$ in the form of a segment $AB^{M_A}$, or rather, in the form of a segment connecting point $A$ with one of those points $B^{M_A}$ that represent $B$ on the map $M_A$. The shortest stepped curve on the torus with ends $A$ and $B$ will be depicted on $M_A$ as one of the monotonic stepped curves between $A$ and (one of the images of) $B$. The reasoning behind these assertions is as follows:

The shortest path on the torus from point $A$ to point $B$ on the map $M_A$ appears either as a regular curve $\gamma$, or as a curve with teleportations $\gamma_1 *... * \gamma_k$. The fact that the second case is essentially impossible (only if all $\gamma_i$ except for $\gamma_1$ consist of a single point) is easily proven by induction on $k$.

If $k = 1$, then there is nothing to prove.
At $k = 2$ on the map $M_A$ we have two curves: $\gamma_1$ and $\gamma_2$, glued together with a single teleportation. Using your knowledge of school geometry, show that, both in the class of all curves and in the class of stepped curves, replacing $\gamma_1$ and $\gamma_2$ with a single shortest curve for $M_A$ from $A$ to $B$, certainly won't make the path between points $A$ and $B$ longer.
image

(Figure 7)

Let $k = N > 2$ and $\gamma_1 *... * \gamma_N$ is the representation by the map $M_A$ of the shortest path from $A$ to $B$. We denote the end of the segment $\gamma_1$ as $O_1$, the beginning of $\gamma_2$ as $O_2$, and the end of $\gamma_2$ as $O_3$. Since any segment of the shortest path is obviously the shortest path itself, a splice of segments $\gamma_1$ and $\gamma_2$ will be a two-segment shortest between point $A$ and point $O_3$. But if so, then we can use the statement proven for $k=2$ and replace the path $\gamma_1 * \gamma_2$ with a single-segment path $\gamma_2'$ of the same or shorter length. By doing this, we get the path $\gamma_2’ *... * \gamma_N$, which connects $A$ and $B$, consists only of $(N-1)$ segments and is no longer than the path $\gamma_1 *... * \gamma_N$, i.e., it is the shortest.

1.7 Small Rectangles


Let $A$ and $B$ be two arbitrary points on the surface of the torus, which do not lie on the same meridian or parallel, $m_A$ and $p_A$ are the only meridian and parallel passing through the point $A$, $m_B$ and $p_B$ are the only meridian and parallel passing through the point $B$. Together, the curves $m_A$, $p_A$, $m_B$ and $p_B$ divide the surface of the torus into 4 (connected) areas, each of which, with an appropriate choice of the main map, will be depicted on it as a rectangle.


(Figure 8)

In general, only one of these four rectangles will have each of the horizontal sides less than half a parallel, and the length of each vertical side will be less than half a meridian. This (generally) single rectangle we will call a small rectangle, stretched over the points $A$ and $B$, and denote as $\Pi (AB)$.

The utility of the concept of a small rectangle lies in the following. No matter what point $B$ is on the surface of the torus, the rectangle $\Pi (AB)$ will be depicted as a single figure on the map $M_A$. Consider the case when there is only one small rectangle stretched over $A$ and $B$. It is evident that any shortest curve between $A$ and $B$ within $\Pi (AB)$, whether in the class of stepwise curves or all curves, is also the shortest in the same class on the map $M_A$ and vice versa. Since the set of shortest curves between $A$ and $B$ on the torus coincides with the set of shortest curves built between these points on the map $M_A$, all these curves are the shortest within $\Pi (AB)$. Thus, small rectangles allow us to reason about the shortest paths on the torus without referring to its maps.

2*. Unmatched Taxi with Geodesic Route


2.1 The Basic Dilemma of Mass Transport with a Variable Route


A trip in a personal vehicle can always be accomplished along the shortest route (among the possible ones). If we want to create mass transport that could compete in speed with a personal car, we should strive for the route of each of its passengers not to be too much longer than the shortest. At the same time, it is intuitively clear that massiveness, i.e., the average number of passengers in the cabin, and how close the routes of these passengers are to the shortest, are opposing qualities (look at how $n_{pass}$ depends on $\lambda$ in the schemes discussed in part 1). The aim of this chapter is, albeit indirectly and very roughly, to estimate to what extent these two opposing qualities can be combined. In fact, in this chapter, we will try to answer the following two questions:

1) How should the shared taxi, the pick-up points of its future passengers, and the drop-off points of those passengers who have already boarded it be arranged relative to each other so that it could transport each of its clients along his shortest route?

2) Suppose there is only one car operating in the city and the requirement remains that each passenger's trip should follow his shortest route. How large can we make the average number of passengers transported by this car at the same time if we choose the right route for it?

2.2 Relative Position of Passenger Boarding and Drop-off Points in a Geodesic Taxi.


Let $X(t)$ be the point in the grid city where the shared taxi is located at time $t$, $Q_1, …, Q_n$ are the drop-off points of its current passengers, numbered in order of increasing the length of the shortest path to them from point $X(t)$. At any time, we will consider the positions of points $X(t)$, $Q_1 …, Q_n$ relative to the main map $M_{X(t)}$ (following the car with a movie camera so that the car remains in the center of its field of view at all times). For convenience, we will even assume that as if the map $M_{X(t)}$ is always the same for us, and the image on it gradually changes over time (what was said could be given a precise mathematical meaning, but I consider it superfluous to do so here).

Consider some moment $t$ when the car has not yet reached $Q_1$. In general, points $Q_n$ and $X(t)$ do not lie on the same meridian or parallel, so by rotating the map $M_{X(t)}$ by $90$ degrees, we can always ensure that $Q_n$ is strictly above and strictly to the right of $X(t)$. Let $\gamma$ be the stepwise route by which our car should get from point $X(t)$ to point $Q_n$. By condition, $\gamma$ must be one of the shortest stepwise curves between $X(t)$ and $Q_n$, from which it follows that:

1) the curve $ \gamma$ is monotone in the rectangle $M_{X(t)}$, the path along it on each linear section is directed either to the right or upwards (paragraph 4.4 part 1);

2) since the path of the car from $X(t)$ to all other drop-off points $Q_2, …, Q_{n-1}$ is also the shortest by condition, then all these points belong to $\gamma$ (can you explain why?).

To describe which routes between $X(t)$ and $Q_n$ are permissible for the geodesic taxi and which additional passengers it can pick up along the way, consider small rectangles $\Pi_1 = \Pi (Q_1,Q_2), …, Pi_{n-1} = \Pi (Q_{n-1},Q_n)$, as well as a small rectangle $\Pi_0 = \Pi (X(t),Q_1)$ and $\Pi_n = \Pi (Q_n, C^{u,r}(t))$, where $C^{u,r}(t)$ is the point in the upper right corner of the map $M_{X(t)}$ at time $t$. We will call all these rectangles travel rectangles.

(Fig 9)

From 1), 2), and the results of paragraph 1.7 we can assert the following:
a) any permissible route of a geodesic taxi between $X(t)$ and $Q_n$ lies entirely inside the rectangles $\Pi_0, \Pi_1, …, \Pi_{n-1}$ and within each of these rectangles it is the shortest stepwise curve between its lower left and upper right corner;
b) conversely, let $\gamma_0$ be a monotonous stepwise route from $X(t)$ to $Q_1$ within $\Pi_0$, $\gamma_1$ be a monotonous stepwise route from $Q_1$ to $Q_2$ within $\Pi_1, …, \gamma_{n – 1}$ be a monotonous stepwise route from $Q_{n-1}$ to $Q_n$ within $\Pi_{n -1}$, then their «glueing» $\gamma = \gamma_0 * \gamma_1 * … * \gamma_{n – 1}$ is a permissible route for the geodesic taxi from point $X(t)$ to $Q_n$;
c) until the taxi reaches $Q_1$, it can only pick up travelers whose boarding points are in $\Pi_0$. A traveler who is at point $X(t)$ at time $t$ can be delivered by this car to his destination point $Q_{new}$ if and only if point $Q_{new}$ is within one of the travel rectangles $\Pi_0, \Pi_1, …, \Pi_{n-1}, \Pi_n$ when considering them as they are at this moment $t$.

To answer what the average value of n is, we need to know the characteristic size of the travel rectangles. The area, length, and height of the travel rectangle are random variables, and the distribution law of each changes as the taxi approaches this rectangle. Let's see how this happens.

2.3 Movement along the route.


Consider two consecutive moments when the car drops off its clients. Let the last time the car dropped off its client was at time $t_0$ and at point $X(t_0) = Q_0$, and the next one it should drop off at time $t_1$ and at point $X(t_1) = Q_1$. In order to maintain balance, on the way from $Q_0$ to $Q_1$ the car must pick up on average one passenger, i.e., on average within the rectangle $\Pi(Q_0,Q_1)$ it will find one suitable traveler for itself, denote his boarding place as $P_{new}$, and the drop-off place as $Q_{new}$.

Compared to the disposition of travel rectangles on the map $M_{X(t)}$ at the moment $t=t_0$, at the moment $t=t_1$, i.e., when the car reaches $Q_1$, it will change. Firstly, the travel rectangle $\Pi_0$ will cease to be travel. Then, if we forget for a moment about the appearance of the new drop-off point $Q_{new}$, we can say that all the rectangles $\Pi_1, …, \Pi_{n-1}$ will shift towards the center of the map by the vector $\vec(Q_1,Q_0)$, and the rectangle $\Pi_n$ will not only shift by $\vec(Q_1,Q_0)$, but will also grow new territory from the top and to the right. Finally, adding the point $Q_{new}$, unless it remained inside $\Pi_0$, will turn one of the travel rectangles $\Pi_1, …, \Pi_{n-1}, \Pi_n$ into two new travel rectangles and two more which we are not interested in.

(Fig 10)

Simply put, during the movement of our car, the chain of travel rectangles moves towards the center of $M_{X(t)}$, the one on the top right grows, the one at the very center drops out, plus with some probability each element of the chain, with loss of area, divides in two.

Before we assess the size of the travel rectangles, let's consider a very similar simpler problem.

2.4 Auxiliary problem.


Imagine a conveyor belt operating outdoors, and snowflakes are falling onto it from above. Let's assume the upper part of the conveyor belt has a length of $L$ and moves from right to left at a speed of $v$. Assume that the snow falls absolutely randomly with equal intensity in time and space and this intensity is such that while the conveyor makes a half turn, on average n snowflakes manage to fall on it. It is necessary to find how the average distance between neighboring snowflakes on the belt depends on how far these snowflakes are from the left edge of the conveyor.

(Fig 11)

Here we need to clarify what we actually mean by the term «average distance». We will assume that $n$ is large. In our minds, we will divide the conveyor belt into segments of length $\Delta l$, and we will choose $\Delta l$ to be much less than $L$ on the one hand, and on the other hand, the number $n \cdot \Delta l/L$ should be much greater than one. Let $AB$ be one of such segments and at the considered moment in time its left edge is at a distance of $x \sim L$ from the left edge of the conveyor. If $(L - x)$ is of the same order as $L$, then at this moment there are about $\Delta (L-x)/l \gg 1 $ snowflakes on $AB$. Let's stop time and randomly select a point $S$ from segment $AB$ with a uniform distribution. Let $Y^L$ be the position of the nearest snowflake to $S$ on the left, and $Y^R$ be the position of the nearest snowflake to $S$ on the right. Actually, by the average distance between snowflakes in that area of the belt, which is at a distance $x$ from the left edge of the conveyor, we will mean the expected value of the length of the segment $Y^LY^R$. Let's consider two ways to calculate what it equals to: one — simple and accurate, and the other — a bit more complicated and approximate, but allowing itself to be generalized to the problem with travel rectangles.

Simple Solution.
Let's set up an imaginary plane $\pi$ across the conveyor at a distance x from its left edge. The average number of snowflakes that the conveyor belt carries across $\pi$ per unit of time equals the average number of snowflakes that manage to fall on the conveyor to the right of $\pi$ per unit of time. The average number of the latter is $n(L – x)/L \cdot v/L = nv(L – x)/L^2$. Moreover, the randomness and independence of snowflakes falling on the belt lead to their positions on the belt being random and independent of each other. In particular, if you see a snowflake that just lay on the conveyor crossing $\pi$, or on the contrary, for a long time $\Delta T$ no snowflake crossed $\pi$, these observations alone do not give you any information about how soon the next snowflake will cross $\pi$. Such observations also do not provide information about how much time has passed since the snowflake last crossed $\pi$. The homogeneity in time and the independence of snowflake crossing events through the plane $\pi$ suggest that we have a Poisson process in front of us. The average waiting time for this process $\bar {T}$ is equal to $[nv(L – x)/L^2]^{-1}$

Let $t_A$ and $t_B$ be the moments in time when the points we marked on the belt, $A$ and $B$, will cross $\pi$ once again. Let $t$ be a randomly chosen moment from the time interval $t_At_B$, $P(t)$ is a point on the belt, which at the time $t$ is at the cut $\pi$. Since the process of snowflakes passing through the cut $\pi$ is Poissonian, the nearest moment of a snowflake passing through $\pi$ after $t$ and the last one before $t$ are both on average away from $t$ by $\bar {T} = [nv(L – x)/L^2]^{-1}$. Thus, the average distance between the nearest snowflakes to the right and left of $P$ is $\bar {s} = 2v \bar {T} = 2 (n(L – x)/L^2)^{-1}$. This number is the solution to our problem, because randomly choosing from the interval $AB$ the point $P$ with uniform probability is the same as randomly choosing from the time interval $t_At_B$ the moment $t_P$, at which the point $P$ will pass through $\pi$.

Almost legal solution that can be generalized.
Let's choose $\Delta l$ equal to $L/\sqrt {n}$. As before, let $AB$ be one of the conveyor belt segments of length $\Delta l$. Let's consider a sequence of time moments ${t_k}$, when the left edge of the segment $AB$ was at a distance of $k\Delta l$ from the right edge of the conveyor, and track how the average distance $\bar {s}(k)$ between snowflakes on $AB$ at the moment $t_k$ changes with $k$.

By condition, while the belt moves a distance of $L$, $n$ snowflakes manage to fall on the conveyor. Between $t_k$ and $t_{k+1}$ time, the belt will shift by $L/\sqrt {n}$, therefore only $\sqrt {n}$ snowflakes will fall on the conveyor on average during this period. Since $AB$ makes up only $1/\sqrt {n}$ part of the conveyor length, of these $\sqrt {n}$ snowflakes on average only one will fall on it. Its place of fall will be between some two snowflakes, which were already present on $AB$ at the moment $t_k$. Since the fall location of this new snowflake is randomly chosen with uniformly distributed probability along $AB$, the average distance between its right and left neighbors will be $\bar {s}(k)$.

Let $I_k$ be the interval between the right and left neighbor of the new snowflake. As we have just established, the mathematical expectation of the length of $I_k$ is equal to $\bar {s}(k)$. The new snowflake divides $I_k$ into two segments, $I_k^L$ — the left one and $I_k^R$ – the right one. If at time $t_{k+1}$ a random point $P$ is chosen from $АB$, then with a probability of $|I_k|/|AB|$ it will fall into $I_k$, and with a probability of $ (1 - |I_k|/|AB|)$ it will end up outside $I_k$.

In cases when $P$ falls inside $I_k$ the average distance $s(I_k)$ between the nearest to $P$ snowflakes on the right and left will be given by the expression

$s(I_k) = |I_k^R| \cdot |I_k^R|/|I_k| + |I_k^L| \cdot |I_k^L|/|I_k| = (|I_k^R|^2 + |I_k^R|^2)/|I_k|\ \ \ \ \ (1) $

The average (according to the position of the new snowflake inside $I_k$) value $|I_k^R|^2 = |I_k^R|^2 = 1/3 |I_k|^2$, therefore the average value of $s(I_k)$ is $2/3 |I_k|$.

What will be the average distance $s(AB ∖ I_k)$ between the closest snowflakes to the right and left of $P$ when $P$ does not fall into $I$? Here we will make a very slippery assumption. We will assume that $\bar {s}(AB ∖ I_k)$ differs from $\bar {s}(k)$ by an amount significantly less than $\bar {s}^2(k)/|AB|$. Then:

$\bar {s}(k + 1) = (1 - \bar {|I_k|}/|AB|) \bar {s}(AB ∖ I_k) + 2/3\ \bar {|I_k|^2}/|AB| \approx \bar {s}(k) - \bar {s}^2(k) /|AB| + 2/3\ \bar {|I_k|^2}/|AB|\ \ \ \ \ (2)$

Again, we make a not quite legal assumption that $\bar {|I_k|^2} \approx (\bar {|I_k|})^2 = \bar {s}^2(k)$ (we equate the square of the average with the average of the squares), then expression $(2)$ can be rewritten as:

$\bar {s}(k + 1) - \bar {s}(k) \approx - 1/3\ \bar {s}^2(k)/|AB| \ \ \ \ \ (3) $

or so

$\bar {s}(k + 1) - \bar {s}(k) \approx (- 1/3\ \bar {s}^2(k)/|AB|)\cdot [(k + 1) - k] \ \ \ \ \ (4) $

We replace the above difference equation with a differential one:

$d \bar {s} \approx - (1/3 \bar {s}^2(k)/|AB|) dk \ \ \ \ \ (5) $

or the same

$\frac {d \bar {s}} {\bar {s}^2} \approx - 1/3\ \frac {dk} {|AB|} \ \ \ \ \ (6)$

from which

$\frac {1} {\bar {s}} \approx 1/3\ \frac {k + Const}{|AB|} \ \ \ \ \ (7)$

or with $Const = 0$ (the most plausible value for Const at $k=1$)

$\bar {s} \approx \frac {3|AB|}{k} \ \ \ \ \ (8) $

If we take the exact expression for $\bar {s}$ that we found earlier:

$\bar {s} = 2 \frac {L^2}{n(L – x)} \ \ \ \ \ (9)$

and substitute into it $(L – x) = kL/\sqrt {n}$, then we get

$\bar {s} = 2v \bar {T} = 2 \frac {L}{k \sqrt {n}} = \frac {2|AB|}{k} \ \ \ \ \ (10) $

As you can see, our nearly legal estimate accurately reflected the law of dependence and only made a mistake in the coefficient by a factor of one and a half. We will use the same technique to estimate the area of ​​path rectangles.

2.5 Estimation of the characteristic size of path rectangles


For the sake of simplicity, let's assume that the parallels and meridians of the torus, on which our imaginary city is located, have the same length $L$. In this assumption, the taxi's «attached» map $M_{X(t)}$ takes the form of a square with side $L$. Since the up-down and right-left directions in such a city are equivalent, it is natural to expect that the chain of path rectangles will stretch along the diagonal of $M_{X(t)}$.

(Figure 12 — the red squares are path containers)

Let $O$ be the current location of our car, $F$ be the point where the top right corner of the map $M_{X(t)}$ is currently located, and $m$ be the average number of passengers who will exit (enter) the taxi during the time it will take to get from $O$ to $F$. Let's cover the segment $OF$ with a chain of $\sqrt {m}$ identical squares with a side $1/2 L/\sqrt {m}$, which we will call path containers. Given that the path squares are stretched along the segment $OF$, we can expect, especially with large values of $m$, that most of them will be located inside the path containers we have constructed. We will number the containers with the index $k = 1, …, \sqrt {m}$ starting from the top right and try to estimate how they change with the number $k$:
a) the average area $s(k)$ of the path rectangle inside the container with number $k$;
b) the total area $S(k)$ of all path rectangles inside the container with number $k$.

Of course, we need to make a clarification regarding the concept of the «average area of a path rectangle» in the $k$-th container. As in the conveyor task, by average we will understand the expected area of a path rectangle, which will be hit by a point randomly thrown, if the probability is uniformly distributed over the area of all path rectangles lying inside the container numbered $k$.

Let's denote the top right corner of the container closest to the center as $O’$. When the taxi moves from $O$ to $O’$ (more precisely, to the point closest to $O’$), the path container numbered $k$ will move to the place of the path container numbered $k-1$. We'll use this observation for our calculations (akin to the movement of a conveyor belt).

On the way from $O$ to $O’$, about $\sqrt {m}$ passengers will manage to exit the taxi, which means that about the same number, i.e., $\sqrt {m}$ new passengers will enter it. If we take the figure $\Phi$, consisting of the union of all path rectangles, then per unit of its area, there will be:

$a \approx \frac {\sqrt {m}}{S(1) + … + S(\sqrt {m})} \ \ \ \ \ (11) $

drop-off points for new passengers. In the container numbered $k$, about $aS(k)$ such points will fall. Falling into a certain path rectangle, the new drop-off point will break it into two smaller ones with a total area, which on average is twice smaller than the area of the original one (Figure 10).

From this, the total area of the path rectangles inside the k-th container will become equal to $S(k+1)$, i.e.,

$S(k+1) \approx S(k) - aS(k) \cdot 1/2\ s(k) \ \ \ \ \ (12) $

At the same time, the total area of those of its path rectangles into which new drop-off points did not fall will be approximately

$S(k) - aS(k) \cdot s(k) \ \ \ \ \ (13) $

Now, regarding the «average» area of those two new rectangles into which the old path rectangle breaks down when a drop-off point of another taxi passenger falls into it. According to my very rough calculations, it is approximately $4/9$ of the area of the old one (try to find the exact value). Of course, here the average means the outcome of throwing a random point into two new rectangles. If so, then for reasons similar to those we used in the conveyor task:

$s(k+1) \approx \frac {S(k) - aS(k)s(k)}{S(k) - 1/2\ aS(k)s(k)} \cdot s(k) + \frac {1/2\ aS(k)s(k)}{S(k) - 1/2\ aS(k)s(k)} \cdot 4/9 s(k) \ \ \ \ \ (14) $

from which

$s(k + 1) \approx (1 – 1/2\ as(k))s(k) + 4/9\ \cdot 1/2\ as(k)^2 = s(k) - 5/18\ as(k)^2\ \ \ \ \ (15) $

or

$s(k + 1) - s(k) \approx - 5/18\ as(k)^2 [(k+1) - k] \ \ \ \ \ (16) $

We replace the difference equation with a differential one:

$\frac {ds}{s^2} \approx - 5/18\ a\ dk \ \ \ \ \ (17) $

from which

$s(k) \approx 18/5\ \frac {1}{a(k + c_1)} \ \ \ \ \ (18) $

for reasons of similarity, $c_1 = 0$, and finally

$s(k) \approx 18/5\ \frac {1}{ak} \ \ \ \ \ (19) $

Substituting the found expression for $s(k)$ into $(12)$, we get:

$S(k+1) \approx S(k) - 9/5\ S(k)/k \ \ \ \ \ (20) $

or

$S(k+1) - S(k) \approx - 9/5\ S(k)/k \cdot [(k+1) - k] \ \ \ \ \ (21) $

Again, we replace the difference equation with a differential one

$\frac {dS}{S} \approx - 9/5\ \frac {dk}{k} \ \ \ \ \ (22) $

from which

$ln\ S(k) \approx c_2 - 9/5 ln\ k \ \ \ \ \ (23) $

or

$S(k) \approx \frac {c_2}{k^{9/5}} \ \ \ \ \ (24) $

All that remains is to estimate the constant $c_2$. Let's resort to the following considerations:

If at the moment when the car was in point $O$, the first container contained $N$ drop-off points of its customers, then there were $\approx N$ path rectangles in it and it is plausible to assume that the characteristic size of the sides of these rectangles was $X$ times smaller than the size of the side of the container. It turns out that we just need to estimate $X$.

Let's go even further into the past. Before becoming the extreme right upper path container, container number 1 kind of surfaced from the edge of the map $M_{X(t)}$. While the area of the city inside container number 1 «was beyond the edge of the map», new passenger drop-off points could not fall into it. It seems plausible that at that stage the chance for new drop-off points to hit a unit of area of a path rectangle inside container number 1, was on average half as much as the chance to hit a unit of area of a path rectangle in containers of higher numbers. The segment of time when container 1 emerged from the edge of the map is adjacent to the segment of time when it moved to the position of container 2. Let's assume that during these two periods of time the distribution of the area of path rectangles inside 1 did not change much. If such an assumption is justified, then for an estimate of $X$ you can take half of the number of new drop-off points that fell into the first container during the period while it was moving from its place to the place of container number 2. Let's find out what it equals to.

The area of the path rectangles inside container number 1, according to $(24)$, equals $c_2$. The area of the path rectangles inside all containers, again according to $(24)$, is given by the expression

$\Sigma S = c_2 (\frac {1}{1^{9/5}} + \frac {1}{2^{9/5}} + … + \frac {1}{{\sqrt {m}}^{9/5}}) \approx c_2 \int_{1/2}^{\sqrt {m} + 1/2} \frac {dt}{t^{9/5}} \approx 5/4\ c_2 \cdot (1/2)^{- 4/5} \approx 2.17\ c_2\ \ \ \ \ (25) $

From this it follows that out of approximately $\sqrt {m}$ new drop-off points, which are added to the taxi's route during the time it crosses the $(\sqrt {m})$ — th container, approximately $(1 / 2.17) \sqrt {m} \approx 0.46 \sqrt {m}$ will fall into container number 1. Therefore,

$ X \approx 0.23\ \sqrt {m} \ \ \ \ \ (26) $

and

$ c_2 \approx (\frac {L}{2\sqrt {m}})^2 \cdot \frac {1}{0.23\ \sqrt {m}} \approx 1.1\ \frac {L^2}{m\sqrt {m}} \ \ \ \ \ (27) $

2.6 Average number of passengers in the cabin


First, we show that for large values of $m$, the value of $n_{pass}$, i.e., the average number of passengers simultaneously transported by the taxi, is approximately equal to $m$.

Indeed, if $m$ is large, then from $(24)$ it follows that almost the entire area of the path rectangles falls on the containers in the upper right corner, so almost all of our taxi's passengers travel a distance approximately equal to half the diagonal of the map $M_{X(t)}$. According to the conditions, moving the diagonal distance, the taxi picks up on average $m$ passengers. It remains to refer to the children's problem: if a bus picks up $N$ passengers for every mile, and each of the passengers travels on it just about one mile, then the average number of passengers in the bus is approximately $N$ (find the simplest way to solve it). It remains to express $m$.

In order for the taxi to pick up $sqrt {m}$ new passengers when shifting by one container, the balance equation must hold:

$\Delta T \sigma \cdot 1.1\ \frac {L^2}{m\sqrt {m}} \cdot \frac {1}{m^{9/10}} \cdot 1.1\ \frac {L^2}{m\sqrt {m}} \cdot \frac {1}{L^2} \approx \sqrt {m} \ \ \ \ \ (28) $

The value of $\Delta T$ in this equation should be understood as the maximum time a traveler is willing to lose waiting for our taxi. Let's assume that if his wait is longer, he prefers another mode of transport. We will set the maximum value for $\Delta T$ from the principle we already used in the first part of the article. Basically, we require that the difference in travel time on our taxi and in a personal car on average does not exceed the average duration of a trip around the city in a personal car, multiplied by a small number $\lambda$.

The average length of travel in a toroidal city with uniform access (for the migration model, see paragraph 2.3 part 1) is $L/2$, accordingly the average duration of a trip in a personal car is $L/2v$. Further, with a maximum waiting time of $\Delta T$, the average time will be $\approx \Delta T/2$, from where:

$\Delta T/2 = 1/2\ \lambda L/v \ \ \ \ \ (29) $

or

$\Delta T= \lambda L/v. \ \ \ \ \ (30) $

Substituting the expression for $\Delta T$ into $(28)$, we get

$1.2\ \lambda \sigma L^3/v \approx m^{3.9} \ \ \ \ \ (31) $

or finally:

$m \approx (1.2\ \lambda \sigma L^3/v)^{0.26} \ \ \ \ \ (32) $

Below are the values of $m$ for a number of model cities with $\lambda =1/2$

Hypothetical toroidal New York (London, Moscow):
effective diameter $L \approx 28$ km,
permissible speed $v = 0.8$ km/min
$\sigma \approx 33$ people/min sq km
$m (\lambda = 1/2) \approx (1.2 \cdot 1/2 \cdot 33 \cdot 28^3/0.8)^{0.26} \approx 31.1$ people.

Hypothetical toroidal Berlin:
effective diameter $L \approx 30$ km,
permissible speed $v = 0.8$ km/min
$\sigma \approx 13$ people/min sq km
$m (\lambda = 1/2) \approx (0.36 \cdot 1/2 \cdot 13 \cdot 30^3/0.8)^{0.26} \approx 25.8$ people.

Hypothetical toroidal Paris:
effective diameter $L \approx 10$ km,
permissible speed $v = 0.5$ km/min
$ \sigma \approx 70 $people/min sq km
$m (\lambda = 1/2) \approx (0.36 \cdot 1/2 \cdot 70 \cdot 10^3/0.5)^{0.26} \approx 19.1$ people.

Hypothetical toroidal Prague:
effective diameter $L \approx 23$ km,
permissible speed $v = 0.8$ km/min
$\sigma \approx 8.3$ people/min sq km
$m (\lambda = 1/2) \approx (0.36 \cdot 1/2 \cdot 8.3 \cdot 23^3/0.8)^{0.26} \approx 18.6$ people.

Hypothetical standard toroidal half-million city.
population $P = 500K$ people,
density $\rho = 5000$ people/sq km,
effective diameter $L = 10$ km,
permissible speed $v = 1$ km/min
$\sigma \approx 17$ people/min sq km
$m (\lambda = 1/2) \approx (0.36 \cdot 1/2 \cdot 17 \cdot 10^3/0.8)^{0.26} \approx 11.6$ people.

3. Shared Route-Corridor Taxi


3.1 General Concept


Although they are rough estimates, the previous paragraph shows that with fairly realistic assumptions, the average number of passengers simultaneously transported by a shared taxi could be quite large: potentially 20-30 for megacities and 5-12 for cities with a population of several hundred thousand people. However, we should remember that these estimates were built for a single vehicle operating in non-competitive conditions, not for an entire taxi service fleet. Another note is that the route of this single geodesic taxi was prone to gravitate towards a diagonal direction, so even if there were many such vehicles in the city, it would still be difficult to meet the demand for rides with elongated directions, say, along meridians or along parallels.

What if we forcefully make different shared taxis move in different directions, albeit not exactly geodetically, but not on a very winding route either? One way to do this is to assign each vehicle a fixed route corridor within which it must then operate. Let's arrange everything so that the taxis assigned to one corridor move along it in a chain with a small temporal distance from each other. We will assume that a taxi assigned to a corridor must pick up and drop off all the travelers it encounters, if their starting and ending points are within this corridor. The work of such a taxi service will resemble the work of regular city buses, with the only difference that the routes of regular buses are strictly fixed, while the choice of route for shared taxis, although limited by the boundaries of their assigned corridor, is otherwise free. To make all city trips possible with such a taxi, at least one route corridor must pass through any two points in the city.

Our task is to find «good» networks of route corridors. Instead of dealing with an infinite set of route corridors of arbitrary shape, we use a popular method in mathematics called «discretization» and move to a sufficiently rich but (almost) finite subclass. Suppose we want to build a network of route corridors in a certain cellular city $T$, and $\Delta l$ is their expected characteristic width. Using parallels and meridians, we divide our toroidal cellular city into equal squares $S_{h,w}$ $1 \leq h \leq H$, $1 \leq w \leq W$ (where $h$ is the «row» number, $w$ is the column number) of size $\Delta l$. As before, we will call the collection of these squares a cellular grid ${S_{h,w}}$, and the squares themselves $S_{h,w}$ are cells or units of this grid. In this work, the route corridors are made up exclusively of cells of the grid ${S_{h,w}}$. Let's formalize this idea a bit more precisely.


(Fig. 13)

3.2 Cellular Paths: Definitions.


Some of the squares of the grid $\{S_{h,w}\}$ are adjacent by side. If the city $T$ has the shape of a torus and $H>2$, $W>2$, then each square of the grid $\{S_{h,w}\}$ is exactly adjacent to four other cells. Using the concept of adjacency, one can construct the exact concept of a cellular path:

A cellular path on the grid ${S_{h,w}}$ is called any finite sequence of its cells $\pi = S_{h_1,w_1}, … S_{h_N,w_N}$ in which each next cell $S_{h_{n+1},w_{n+1}}$ is side-adjacent to the previous $S_{h_n,w_n}$. The number $N$ is called the (discrete) length of the path $\pi$.

Those cellular paths whose last cell is adjacent to the first, we will call cyclic. By calling the path $\pi = S_{h_1,w_1}, … S_{h_N,w_N}$ cyclic, we thereby imply that we consider the order of its elements not linear, but cyclic. From the point of view of the cyclic order, the element $\pi_1 = S_{h_1,w_1}$ «follows» the element $\pi_N = S_{h_N,w_N}$ and, accordingly, the element $\pi_N = S_{h_N,w_N}$ «stands before» the element $\pi_1 = S_{h_1,w_1}$.

Any two cyclic cellular paths, which consist of the same cells in the same cyclic sequence, even if their linear sequences are different, we will consider equivalent and identify with each other. For example, we will consider as identical the cyclic paths $\pi = S_{1,1}, S_{1,2}, S_{1,3}, S_{2,3}, S_{3,3}, S_{3,2}, S_{3,1}, S_{2,1}$ and $\xi = S_{2,3}, S_{3,3}, S_{3,2}, S_{3,1}, S_{2,1}, S_{1,1}, S_{1,2}, S_{1,3}$. If the reader is familiar with the concept of cyclic permutations, it should be obvious to them that two cyclic cellular paths are identical if and only if the linear recordings of their elements are translated into each other by a cyclic permutation.
image

(Figure 14)

Actually, the subjects of our further research will be such networks of route corridors, all corridors within which are (cyclic) cellular paths, built on the same square grid ${S_{h,w}}$. Let's give a few more useful definitions.

A segment of the cellular path $\pi = {\pi_1 = S_{h_1,w_1}, … \pi_N = S_{h_N,w_N}}$ is called any cellular path $\eta$, all elements of which are composed of $K>0$ consecutive elements of $\pi: \eta = \pi_M, \pi_{M + 1}, … \pi_{M+K-1}$.

A segment of a cyclic cellular path $\pi$ we will call any cellular path $\eta$, if it consists of the same elements as the path $\pi$, and they are arranged in it in the same order in which they follow each other in $\pi$ (For example, for the cyclic $\pi = \pi_1, \pi_2, …, \pi_N$ the path $\eta = \pi_N, \pi_1, \pi_2$ will be its segment).

Let $O_{h,w}$ be the center of the square $S_ {h,w}$, and $\pi = S_{h_1,w_1}, … S_{h_N,w_N}$ — any cellular path. Let's connect the center of each square in the sequence $\pi$ (with the shortest) segment to the center of the next square in $\pi$. The resulting sequence of segments $O_{h_1,w_1} O_{h_2,w_2}, …, S_{h_{N-1},w_{N-1}} S_{h_N,w_N}$ we will «glue» into a single stepped curve. This curve we will denote as $mid({\pi})$ and call the median line of the cellular path $\pi$. The length of the median line of the cellular path is expressed by the formula $len(mid({\pi})) = (N – 1) \times \Delta l$, where $N$ is the length of the sequence $\pi$, and $\Delta l$ is the length of the sides of the squares of the grid ${S_{h,w}}$.

image

(Figure 15)

No matter what the cellular path $\pi = S_{h_1,w_1}, … S_{h_N,w_N}$ is, in the sequences $h_n = h_1, …, h_N and w_n = w_1, … w_N$, formed by the first and second indices of its cells, each subsequent index is either equal to the previous one or is an adjacent integer (if $T$ is a torus, then the index $h=1$ is considered adjacent to the index $h=H$, and the index $w=1$ – adjacent to the index $w=W$). The latter, in particular, means that the cells of the path $\pi$ are located on the grid ${S_{h,w}}$ in some $\Delta h(\pi )$ sequentially lying rows and some $\Delta w(\pi )$ sequentially standing columns. The number $\Delta h(\pi )$ we will agree to call the height or vertical span of $\pi$, and the number $\Delta w(\pi )$ — its width or horizontal span.

3.3 Cellular Paths of Minimal Length


Let's agree to call any cellular path, which contains the minimum number of cells among other cellular paths with the same start and end as it, minimal or geodesic. If the cellular path $\eta$ is minimal and serves as a segment for the cellular path $\pi$, then in relation to \eta we will say that it is a minimal (geodesic) segment of the path $\pi$.

Exercise: Verify that every one-cell path, just like any path composed of two different cells, will always be minimal. Prove that every segment \eta of any minimal cellular path $\pi$ will be its minimal segment.

There is a fairly simple criterion for minimality, almost obvious for those who have dealt with chess. If you move a rook several times, the sequence of cells it passes through will be a cellular path. Suppose you need to move a rook from cell $X$ to cell $Y$ so that the number of intermediate cells on its path is minimal. It is easy to figure out that in the case when $X$ is located lower and to the left of $Y$, the solution to your problem will be any sequence of moves (starting at $X$ and ending at $Y$), in each of which the rook moves either up or to the right. Let's give these considerations a rigorous form and generalize them to the case of a torus.

Let $\pi$ be an arbitrary cellular path, and the square $S_{h_n,w_n}$ is not the last element of it. The next square in the sequence $\pi$, $S_{h_{n+1},w_{n +1}}$, either lies on the same horizontal with $S_{h_n,w_n}$ and adjoins it from the right or left, or these squares stand on the same vertical and $S_{h_{n+1},w_{n +1}}$ adjoins $S_{h_n,w_n}$ from above or below. We will call the cellular path $\pi$ monotonic if and only if in the sequence $\pi$ each subsequent square, when it is on the same horizontal as the previous one, always adjoins it either only from the left or always only from the right, and when it stands on the same vertical as the previous one, it always adjoins it either only from the top or always only from the bottom. The figure below shows examples of monotonic and non-monotonic paths.

(fig 16)

Exercise: The numeric sequence $x_n = x_1, …, x_N$ is considered monotonic if as the number increases, the values of its elements change monotonically: they either do not decrease or do not increase. Let $T$ be a rectangle (without teleportation between edges), check that the cellular path $\pi = S_{h_1,w_1}, … S_{h_N,w_N}$ on $T$ is monotonic if and only if both numeric sequences of indices $h_n = h_1, … h_N$ and $w_n = w_1, …, w_N$ are monotonic. Try to generalize the last statement to the case when $T$ is a flat torus.

The concept of a monotonic cellular path is closely related to the concept of a monotonic step curve, which was introduced in paragraph 4.4 of Part 1 for the case of a plane and naturally extends to a flat torus (construct the generalization explicitly). It should be obvious to the reader that a path $\pi$ that includes more than one cell is monotonic if and only if its median line $mid({\pi})$ is monotonic (check!). In addition, as with curves, the monotonicity of cellular paths says something about their property to have a minimal length. The connections between these concepts are expressed in the following

Lemma about the minimum path (criteria for minimality).
Let $T$ be a rectangle or a flat torus, ${S_{h,w}}$, $1 \leq h \leq H$, $1 \leq w \leq W$ — square grid on $T$, $\pi$ — cellular path over ${S_{h,w}}$, in this case:

1) $\pi$ is minimal if and only if its median $mid({\pi})$ is the shortest in the class of step curves on $T$;
2) if $T$ is a rectangle, then the path $\pi$ will be minimal if and only if it is monotonic;
3) if $T$ is a torus, then the path $\pi$ will be minimal if and only if it possesses the following two properties:
a) $\pi$ is monotonic,
b) the median line of $\pi$ is such that its horizontal span is no more than half the length of the parallel, and vertically — no more than half the length of the meridian of the torus $T$.

Proof.
As an example, I'll prove 1), and leave 2) and 3), which follow easily from 1), to the reader.

Sufficiency of 1). The length of the median line of a cellular path is expressed through the number of squares that this path is composed of. Therefore, if the median line is the shortest (in the class of step curves), then no other cellular path with the same start and end can consist of a smaller number of squares. So, if the median line of the path is the shortest, then the path itself is necessarily minimal.

Necessity of 1). All minimal cellular paths with the same start $S_{h',w’}$ and end $S_{h’',w’’}$ consist of the same number of squares, hence their median lines have the same length. It turns out, to complete the proof of 1) it is enough to construct at least one cellular path starting in the cell $S_{h',w’}$ and ending in $S_{h’',w’’}$, where the median line would be the shortest step curve between the centers of these cells.

(fig 17)

Doing this is not difficult. According to 1.6, no matter what two points of the torus are, among the shortest step curves connecting the first with the second, there is at least one $\Gamma$-shaped one (consisting of no more than one horizontal and no more than one vertical segment). Let $\gamma$ be this $\Gamma$-shaped shortest step curve from the center of $S_{h',w’}$ to the center of $S_{h’',w’’}$. It is easy to see that the sequence of cells that the path $\gamma$ passes through is a cellular path starting in $S_{h',w’}$ and ending in $S_{h’',w’’}$. All that remains is to note that for this cellular path, the curve $\gamma$ is its median line.

Exercise: Let ${S_{h,w}}$, $1 \leq h \leq H$, $1 \leq w \leq W$ be a square grid on a torus. Show that a monotone cellular path is minimal when its range horizontally does not exceed the integer part of the number $(W+1)/2$, and its range vertically — does not exceed the integer part of the number $(H+1)/2$.

3.4 Requirements for «Good» Routing Corridor Networks


Geodesic Connectivity.
Suppose the city is already divided into squares $\{S_{i,j}\}$ and some set of cellular paths $\Omega$ claims to serve as a network of route corridors for a shared taxi. If we want this taxi to allow any city journey, then we must require that any two cells $S_{I',j’}$ and $S_{I'’,j’’}$ were connected by at least one segment of at least one cellular path from \Omega. We will call corridor networks that meet this requirement route-connected.

In fact, the requirement of simple route connectivity is still too weak and cannot guarantee the practical suitability of networks that meet it. The $"Snake"$ network, which consists of a single route corridor snaking around all the city's cells, is obviously route-connected, but it's hard to call it «good» in practical terms. A journey along the snake-like corridor from one random point to another will, on average, be much longer than if it were to follow the optimal route.


(fig 18)

The «snake» example suggests how we should modify the requirement of route connectivity to make it practically meaningful.

We will call a network of cellular routes $\Omega$ geodesically connected if, for any pair of squares $S_{I',j’}$ and $S_{I'’,j’’}$ in the grid ${S_{i,j}}$, there exists at least one route in $\Omega$ that connects these cells by one of its minimal (geodesic) segments. In other words, there should exist a cellular path $\pi$ and a segment $\eta$ of it among the elements of $\Omega$ such that the squares $S_{I',j’}$ and $S_{I'’,j’’}$ serve as the beginning and end for $\eta$, and $\eta$ itself is minimal. If a network of route corridors is geodesically connected, then from the center of each square in the grid ${S_{i,j}}$, in theory at least, a passenger can reach the center of any other by the shortest (stepped) route.

Competitive Minimalism.
Constructing any kind of geodesically connected network of route corridors is not difficult. For example, we get such a network if, for each pair of cells $(S_{I',j’}, S_{I'’,j’’})$, we add some minimal cellular path from the first cell to the second to the initially empty set of corridors. As a result, the collected set of corridors $\Omega_{full}$ will obviously be geodesically connected, but can it be considered «good» for practical implementation? To answer this question, let's estimate the average number of different route corridors in $\Omega_{full}$ whose minimal segments allow you to get from a random cell $S_{I',j’}$ to a random cell $S_{I'’,j’’}$.

For simplicity, let's assume that the city's length and width are equal. In this case, the grid ${S_{i,j}}$ has as many columns as rows, let's denote their number as $N$. Then:

1) the number of different pairs of squares in the grid will be of order $N^4$;
2) the number of different route corridors in ${\Omega}_{full}$ will also be of order $N^4$;
3) on average, each corridor in ${\Omega}{full}$ will have about $N$ cells, so each such corridor will connect about $N^2$ pairs of cells in the grid ${S{i,j}}$;
4) from 1)-3), it follows that typically a pair of cells will be connected by a number of corridors of the order of «total number of corridors» $×$ «average number of pairs of cells connected by one corridor» $/$ «total number of pairs of cells» $\sim N^2$.

It turns out that if we put into operation a shared taxi with a network of route corridors ${\Omega}_{full}$, then on average, cars from about $N^2$ different route corridors will compete for each passenger. The number $N$ is essentially how many times the city's width is larger than the width of a route corridor. Obviously, in practice, $N$ will not be less than $5-10$. Now let's recall that our estimates of the average number of passengers a taxi will transport at once with a geodesic route were calculated under the assumption that there is no competition for passengers. If we divide the optimistic $10-30$ people we got then by $5^2-10^2$, the result will no longer look so attractive and promising.

Imagine any route-corridor taxi. It is plausible to think that the price (cost) a passenger must pay for his ride, all other things being equal, will be inversely proportional to the number of his fellow passengers. The number of fellow passengers is inversely proportional to the number of cars competing for the passenger or the same — the number of route corridors competing for his journey. From the last two statements, we conclude that the average fare for a shared taxi is proportional to the average number of route corridors competing for this ride. If we want to make rides cheaper, we should use networks of route corridors in which competition between corridors is low. In other words, we can consider a network of route corridors \Omega to be «good» only when the average number of its corridors, whose minimal segments connect the squares $S_{I',j’}$ and $S_{I'’,j’’}$, is small and ideally close to one — this is the requirement of competitive minimalism.

Let's now move on to an example of a network that is both geodesically connected and sufficiently competitively minimalist.

4. Shared Taxi with Rectangular Routes


4.1 Network of Large Rectangles


Suppose we are dealing with a flat torus that is divided into squares of the grid $\{S_{h,w}\}$. It will be convenient for us to assume that the number of rows $H$ and columns $W$ is odd: $H = 2M + 1$, $W = 2N +1$ and $- M \leq h \leq M$, $- N \leq w \leq N$. Consider two arbitrary cells $S_{h’,w’}$, $S_{h’’,w’’}$. If these cells belong to different rows and columns, then from $S_{h’,w’}$ to $S_{h’,w’}$ exactly two $\Gamma$-shaped shortest cellular paths can be drawn, and otherwise — exactly one shortest «straight» path (think about whether this statement will be correct if one of the numbers $H$ or $W$ is even?). In both cases, these shortest paths can be, and not in a unique way, completed to closed rectangles. The latter means that any two cells of the grid $\{S_{h,w}\}$ can be connected to each other by a geodesic segment of some rectangular cellular path.

(Fig 19)

In order to connect all pairs of cells with geodesic segments, it is not necessary to take all rectangles on ${S_{h,w}}$. The shortest \Gamma — shaped cellular path from $S_{h’,w’}$ to $S_{h’’,w’’}$ is no more than $N+1$ cells wide and no more than $M + 1$ cell high (otherwise its median line will be too large, see paragraph 3.3), which means it can always be completed to a rectangle of size $N+1 \times M+1$ cells. Thus, for the network of route corridors to be geodesically connected, it is enough to include all rectangles of size $N+1 \times M+1$ cells.

We will call rectangular cyclic cellular paths with a width of $N+1$ cells and a height of $M+1$ cell «large rectangles» and divide them into clockwise-oriented (negatively oriented) and counterclockwise-oriented (positively oriented). It is easy to see that if cells $S_{h’,w’}$ and $S_{h’,w’}$ are in a general position relative to each other (that is, they lie in different rows and columns), then exactly one large rectangle passes through them (up to equivalence, see paragraph 3.2) oriented clockwise (negative orientation), and exactly one oriented counterclockwise (positive orientation). From this it follows that the set $Rotor^+$ of all large rectangles with positive orientation and the set $Rotor^-$ of all large rectangles with negative orientation are both geodesically connected networks of route corridors with a competition index close to 1.

(Fig 20)

Below is a detailed analysis of a taxi with the $Rotor^+$ network of route corridors. Note that along each route corridor in $Rotor^+$ a chain of cars moves only in one direction: counterclockwise.

4.2 Transport load and passenger flow.


To calculate the average number $n_{pass}$ of passengers that a single taxi car carries at the same time, we introduce the concept of transport load. In a city covered by a grid $\{ S_{h,w}\}$ of size $H$ rows $W$ columns, a random traveler moves on average $W/4 \approx N/2$ cells horizontally $+ H/4 \approx M/2$ cells vertically (from the center of the main map to its random point, see paragraph 4.4 of the first part). We can say that by appearing on the city map, a traveler creates a need for moving $1$ person on average $(M + N)/2$ person-cells — this is the transport load he brings. In one unit of time, ${\sigma} \Delta l^2$ travelers appear inside one cell, so each cell generates a transport load of $\approx1/2 (M + N) \times {\sigma}d^2$ per unit of time, and all cells together generate $ \approx 2MN(M + N) \times {\sigma} \Delta l^2$ person-cells.

Taxi cars transport travelers and thus satisfy (neutralize) the transport load. Let $\bar {v}$ be the average speed at which a taxi car integrally passes the cells of its route corridor, that is, $\bar {v}$ is such a value that on average per unit of time the car moves forward by $\bar {v}/\Delta l$ cells. Since any traveler's trip always goes along the minimum segment of the route corridor, from the passengers' point of view, the taxi does not pass «extra» cells. The latter means that in one unit of time one taxi car eliminates $n_{pass} \bar {v}/\Delta l$ units of the transport load generated by the city. Let $N_bus$ be the number of all cars in the taxi service. The requirement for balance between generation and elimination of transport load leads us to the equation:

$N_{bus} \times n_{pass} \bar {v}/\Delta l = 2MN(M + N) \times {\sigma}(\Delta l)^2 \ \ \ \ \ \ (1)$

To express $\bar {n_{pass}}$ from it, we need to find what $N_bus$ is. Let's first say that $\Delta T$ is such that the average distance between neighboring buses of the same route is equal to $\Delta l$, that is, there is exactly $1$ bus for each cell of the corridor. In this case, $N_bus$ is exactly equal to the number of cells in all the route corridors $Rotor^+$, let's count them.

Each large rectangle contains $M + N + M + N = 2(M + N)$ cells. Each of the $(2M + 1)(2N + 1) \approx 4MN$ grid cells ${S_{h,w}}$ serves as the bottom left corner for exactly one large rectangle. From the last two statements, it follows that all the corridors $Rotor^+$ contain (taking into account repetitions) $\approx 8MN(M + N)$ grid cells ${S_{h,w}}$. Substituting the found $N_{bus}$ into equation $(1)$, we get:

$8MN(M + N) n_{pass} \bar {v}/\Delta l = 2MN(M + N){\sigma}(\Delta l)^2\ \ \ \ \ \ (2)$

from where

$n_{pass} = 1/4\ {\sigma} (\Delta l)^3/ \bar {v}\ \ \ \ \ \ (3) $

Let's now assume that the bus interval $\Delta T$ is chosen arbitrarily. In this case, the distance between neighboring vehicles of one route will be $\Delta T \bar {v}$, and their number in the city will change by $\Delta l/ \Delta T \bar {v}$ times compared to what we had above. The more taxi cars there are, the less transportation load falls on each of them, and therefore the less the average number of passengers simultaneously transported by one car should be. Thus, for an arbitrary $\Delta T$:

$n_{pass} = 1/4\ \sigma (\Delta l)^3/ \bar {v} \times \Delta T \bar {v}/\Delta l = 1/4\ \Delta T \sigma (\Delta l)^2 \ \ \ \ \ \ (4)$

It is remarkable that $n_{pass}$ ultimately does not directly depend on the average speed $\bar {v}$.

And so, we expressed $n_{pass}$, that is, the average number of passengers who are simultaneously in the salon of one car, averaged over all taxi cars and all their working time. However, it is interesting to know not only this super-averaged value, but also how the expected number of passengers in the salon changes over time for a specific car, and how its time-averaged value differs for different cars?

The answer to the second question should be obvious: since all route corridors of the $Rotor^+$ network are equivalent (any large rectangle can be translated into any other by torus movement), then the average conditions over time of all cars circulating along these corridors will be absolutely identical. Let's now answer the question of how the expected number of passengers in a taxi cabin changes as it moves forward along its corridor.


(Fig 21)

Cars from many large rectangles compete for the transportation of passengers between squares located within one row or one column. In the same case, when squares $S_{h’,w’}$ and $S_{h’’,w’’}$ belong to different rows and different columns, you can get from one to another via a single large rectangle from $Rotor^+$. From all this, we can conclude that while a taxi is driving, say, along the left side of its assigned large rectangle $\pi$, the vast majority of passengers it picks up there are heading to the cells of the lower side of $\pi$, and most of the passengers it drops off came from the cells of the upper side of $\pi$. It is clear that similar statements will be true in cases where the taxi is on any other side of $\pi$.

Considering the remark above, we can count how many passengers, on average, a taxi picks up and drops off inside each non-corner cell of the rectangle $\pi$. For definiteness, let's consider the cell $S_{h’,w’}$ on the left side of $\pi$ again. The expected number of passengers that the car will bring to $S_{h’,w’}$ from the cells of the upper side of $\pi$ can be expressed by the formula:

$K_{out} \approx \Delta T\sigma \times$ «area of cell $S_{h’,w’}$» $\times$ «area of cells on the upper side of $\pi$»$/$ «area of the city»

In turn, the expected number of passengers who will go by this car from the cell $S_{h’,w’}$ to the cells of the lower side of $\pi$ can be approximately expressed by the formula:

$K_{in} \approx \Delta T\sigma \times$ «area of cell» $S_{h’,w’}$" $\times$ «area of cells on the lower side of» $\pi$"$/$ «area of the city»

Since $K_{out} = K_{in}$, the expected number of passengers in the cabin of this car almost does not change with the passing of cell $S_{h’,w’}$, which means that due to the randomness of the choice of $S_{h’,w’}$, it should remain almost unchanged throughout the entire route $\pi$.

4.3 Route traversal algorithm and travel time


In the chapter dedicated to intercellular taxi, we have already considered the traversal algorithm, which allows a taxi car to pick up passengers inside the route corridor assigned to it (paragraph 4.3 part 1). Let's slightly improve it.

Most cells of a large rectangle are «laid out in a straight line», while the corners make up its insignificant part. Consider the moment when the taxi car has just dropped off or picked up its next passenger and has a long straight stretch of the assigned route corridor ahead. We will not force this car to return to the middle line of its corridor, as was the case in the algorithm for intercellular taxi, but will allow it to move forward parallel to this middle line directly from the point where it is currently located.


(fig 22)

The car should move parallel to the middle line until it is directly to the right or directly to the left of the point where it should drop off or pick up its next client. When this happens, it should turn 90 degrees and drive the remaining distance to the pick-up/drop-off point in a straight line. Upon reaching it, the taxi car finds itself in conditions for which the algorithm of its actions is already defined. Let's now estimate how much our shared taxi will lose in speed to a personal car with this traversal algorithm.

For the previous traversal algorithm, in which the taxi car always returned to the middle line of the assigned corridor, each pick-up/drop-off point cost the passengers on board an average of an additional $\Delta l/2$ units of travel distance. Since the average distance between two randomly chosen points of the segment $I$ with length $\Delta l$ is $\Delta l/3$ (see paragraph 4.4 part 1), then in the new traversal algorithm, the average additional path from one stop is only $\Delta l/3$ — a small but valuable improvement. Let's now turn to the issue of travel time.

The journey length between random points in a toroidal cell city of size $L_w \times L_h$, if it is performed along the shortest route, is on average equal to $(L_w + L_h)/4$ (why?). In a personal car, such a distance can be overcome in

$\bar {t_{pers}} \approx 1/4\ (L_w + L_h)/v \ \ \ \ \ \ (5)$

units of time.

In the case when city travels are carried out in a shared taxi, the waiting time for the car and the penalty associated with the fact that the passenger's journey route is no longer the shortest (we will neglect the pick-up/drop-off time and acceleration/braking penalty for now) are added to their duration. If the interval between cars operating within one route corridor is $\Delta T$, then the waiting time for a suitable car for travel can be estimated as $\Delta T/2$. Now, let's talk about the non-ideal nature of the route.

Above, we found that each stop of a taxi car that a passenger passes in transit costs him an average of $\Delta l/3$ additional travel units or the same — $1/3\ \Delta l/v$ additional time. To understand how much these delays slow down the journey, we need to calculate the average number of taxi stops a passenger will endure during his trip. We will prove that if the expected number of passengers in the cabin $n_{pass}(t)$ remains almost constant over time, then the average number of stops endured by a passenger is about twice $n_{pass}$.

Indeed, let's imagine that every time a taxi passenger sees himself or any of his fellow travelers enter or leave the salon of this car, he makes a paper airplane and throws it out the window. If over a certain large period of time $T$, $X \ll n_{pass}$ passengers entered the car, then approximately the same number, i.e. $X$, should have left the car over this period $T$. Each time a new traveler boarded or left the car, this event was observed by approximately $n_{pass}$ passengers (since $X$ is large and therefore the law of large numbers works). It turns out that over the time period $T$, approximately $2X \times n_{pass}$ paper airplanes were launched, i.e., on average, $2n_{pass}$ airplanes per passenger.

Adding up the waiting time and the penalty for the non-ideal nature of the route, we get a formula for the average travel time of a shared taxi passenger:

$\bar {t_{cop}} \approx \bar {t_{pers}} + \Delta T/2 + 1/6\ \Delta T \sigma (\Delta l)^3/v \ \ \ \ \ \ (6)$

Exercise: try to come up with conditions under which the average number of times a passenger observes himself or other passengers getting on the bus (himself or other passengers getting off the bus) is only half the average number of passengers in this bus over time. Can these quantities be even smaller?

4.4 Optimization


Let's select such values of $\Delta T$ and $\Delta l$ that, on the one hand, the average number of passengers in the taxi becomes maximal, and on the other hand, the average duration of their journey does not exceed more than $(1 + \lambda)$ times the average duration of a journey by private car (for comparison, see paragraphs 4.6 and 5.3 of Part 1). For simplicity, let's solve the problem for a torus with parallels and meridians of equal length: $L_w = L_h = L$. Formally, we need to maximize

$n_{pass} = 1/4\ \Delta T \sigma (\Delta l)^2 \ \ \ \ \ \ (7)$

subject to the «constraint»

$\Delta T/2 + 1/6\ \Delta T \sigma (\Delta l)^3/v \leq \lambda [1/4 (L + L)/v] = 1/2\ \lambda L/v \ \ \ \ \ \ (8)$

Let $p$ be an arbitrary number from the segment $[0,1], q = 1 – p$. Let's use the method from the first part and set:

$ \Delta T/2 =1/2\ p\lambda L/v \ \ \ \ \ \ (9)$

and

$1/6\ \Delta T \sigma (\Delta l)^3/v = 1/2\ q \lambda L/v \ \ \ \ \ \ (10)$

From this, we get:

$\Delta T = p\lambda L/v \ \ \ \ \ \ (11) $,

$1/3\ p\lambda L \sigma (\Delta l)^3/v = q \lambda L \ \ \ \ \ \ (12)$

$\Delta l = 3^{1/3} (q/p)^{1/3} (v/\sigma)^{1/3} \ \ \ \ \ \ (13)$

$n_{pass} = 1/4\ p\lambda \sigma L/v \cdot 3^{2/3} (q/p)^{2/3}(v/\sigma)^{2/3} = (3^{2/3}/4)\ p^{1/3}q^{2/3} \lambda L (\sigma/v)^{1/3} \ \ \ \ \ \ (14)$

The expression

$p^{1/3}q^{2/3} \ \ \ \ \ \ (15)$

under the condition

$p + q = 1 \ \ \ \ \ \ (16)$

reaches a maximum when $p = 1/3$, $q = 2/3$ (check by calculating the derivatives), therefore finally:

$\Delta T = 1/3\ \lambda L/v \ \ \ \ \ \ (17)$

$\Delta l = 1.82\ (v/\sigma)^{1/3} \ \ \ \ \ \ (18)$

$n_{pass} = 0.28\ \lambda L (\sigma/v)^{1/3} \ \ \ \ \ \ (19)$

4.5 Estimates for (almost) real cities


Let's calculate what $n_{pass}$ equals at optimal $\Delta l$ and $\Delta T$ in our already familiar typical cities when the value of $\lambda$ equals $1/2$.

Hypothetical toroidal New York (London, Moscow):
effective diameter $L \approx 28$ km,
permitted speed $v = 0.8$ km/min
$\sigma \approx 33$ people/min per sq km
$n_{pass} (\lambda = 1/2) \approx 0.28 \cdot 1/2 \cdot 28 (33/0.8)^{1/3} \approx 13.5$ people.
$\Delta l (\lambda = 1/2) \approx 1.82 (0.8/33)^{1/3} \approx 0.53$ km
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 28/0.8 \approx 5.8$ min

Hypothetical toroidal Berlin:
effective diameter $L \approx 30$ km,
permitted speed $v = 0.8$ km/min
$\sigma \approx 13$ people/min per sq km
$n_{pass} (\lambda = 1/2) \approx 0.28 \cdot 1/2 \cdot 30 (13/0.8)^{1/3} \approx 10.6$ people.
$\Delta l (\lambda = 1/2) \approx 1.82 (0.8/13)^{1/3} \approx 0.71$ km
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 30/0.8 \approx 6.1$ min

Hypothetical toroidal Paris:
effective diameter $L \approx 10$ km,
permitted speed $v = 0.5$ km/min
$\sigma \approx 70$ people/min per sq km
$n_{pass} (\lambda = 1/2) \approx 0.28 \cdot 1/2 \cdot 10 (70/0.5)^{1/3} \approx 7.3$ people.
$\Delta l (\lambda = 1/2) \approx 1.82 (0.5/70)^{1/3} \approx 0.35$ km
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 10/0.5 \approx 3.4$ min

Hypothetical toroidal Prague:
effective diameter $L \approx 23$ km,
permitted speed $v = 0.8$ km/min
$\sigma \approx 8.3$ people/min per sq km
$n_{pass} (\lambda = 1/2) \approx 0.28 \cdot 1/2 \cdot 23 (8.3/0.8)^{1/3} \approx 7$ people.
$\Delta l (\lambda = 1/2) \approx 1.82 (0.8/8.3)^{1/3} \approx 0.83$ km
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 23/0.8 \approx 4.8$ min

Hypothetical standard toroidal half-million city.
population $P = 500K$ people,
density $\rho = 5000$ people/sq km,
effective diameter $L = 10$ km,
permitted speed $v = 1$ km/min
$\sigma \approx 17$ people/min per sq km
$n_{pass} (\lambda = 1/2) \approx 0.28 \cdot 1/2 \cdot 10 (17/1)^{1/3} \approx 3.6$ people.
$\Delta l (\lambda = 1/2) \approx 1.82 (1/17)^{1/3} \approx 0.7$ km
$\Delta T (\lambda = 1/2) \approx 1/6 \cdot 10/1 \approx 1.7$ min

4.6 Criticism


Of course, humanity has not yet learned how to fold real cities into a torus.
Naturally, we've overlooked acceleration/braking time as well as boarding/alighting time, and as a result we've overestimated the number of passengers for such oversights to be justified (demonstrate that the taxi car stops approximately $ \frac {2n_{pass}}{L/2} $ times per unit length of the route corridor, calculate the average distance between its stops in each of the cities mentioned above).
Finally, we've once again exceeded the limits of our model's applicability since the grid cell sizes $ S_{h,w} $ derived from it — $ 0.53 $ km for New York, $ 0.71 $ km for Berlin, and especially $ 0.35 $ km for Paris — turned out to be definitely not «much larger than a half-kilometer block» (an implicit assumption for the routing algorithm, see paragraph 4.3 of part 1 for details). Nonetheless, this chapter still holds value because:

First, all the problems listed in this model can be rectified and we will do so in the third part of the paper.
Second, it applies the principle of decomposition: «break down the problem into its main parts and study each separately». Decomposition is a powerful research technique, popularized in ancient Greece. One of the main problems with shared taxis is the increase in the route length for its passengers — and this is the issue we've studied separately here.
Third, it's always important to compare like with like. If we look at the figures obtained under the same assumptions for intercellular taxis, we'll see that the average load of shared taxis with rectangular routes $ n_{pass} $ has almost tripled with the same value of $ \lambda $. Such an increase in efficiency should hint to the reader that we are on the right track.

5. Research tasks for independent resolution


5.1 Parting Advice


I wanted to include a description of an improved taxi scheme with one transfer in this article, but then I realized I didn't want to take away the reader's pleasure of making a discovery themselves. You will need a lot of imagination, some mental experiments, and simple calculations. Each time you find another solution, try to criticize it and think about whether it could be improved a little. Experiment, analyze, and experiment again. I will give you a few leading ideas, but otherwise, let this be entirely your own research project for a month or half a year.

5.2 Improved Scheme with One Transfer


Assume you are dealing with a cellular city on a torus. Consider such a modification of the simple bus scheme (paragraph 3.1 in part 1) that allows an individual bus not to stop at the next stop if there's nobody there and not a single passenger on that bus wants to get off there. Suppose you have a requirement that the duration of the «average» journey on such buses should not exceed the «average» journey by private car by more than $ (1+\lambda) $ times. By varying the bus headway $ \Delta T $, optimize the expected number of passengers $ n_{pass} $ in each of them. What expression did you get for $ n_{pass} $? Try to think of a trick that, all other things being equal, would allow you to increase $ n_{pass} $ almost twice as much. Estimate the minimum size of cities for which the solutions you have found are suitable.

5.3 The Best Passenger Transport Scheme on a Straight Line (for those confident in their math skills)


Suppose you have an infinite road extending in both directions and that on every kilometer of its length, on average, $\sigma$ new travelers appear every minute. These travelers choose their destinations randomly. By definition, the probability that a journey will be of length from $ l $ to $ l +\delta l $ equals $ f(l)\delta l $. For simplicity, let's assume that journeys are made from left to right. Think about how to organize passenger transportation in the «best possible way». The definition of «the best way» you can give at your discretion but in a way that it has practical value.

Acknowledgements


One would think, what's so difficult, I'll get everything done by the beginning of winter. Working on the text, unexpected discoveries, errors, and dead-end paths stretched the research over six months. A usual story, if I had known in advance — I would never have taken it :)

I could not have walked this path without my friends, for which I am very grateful.

Also, I am grateful to a small winged muse, who always answered my smile with a smile :)

Days of work almost in complete solitude merged into one, I lost count of them. Music helped me not to lose heart and reach the end. I don't have the means to adequately pay for the artists' work, so let me thank them with a little advertising.

In case you need a little inspiration and beauty:

1) London Grammar – an amazing band, their songs are the most «catchy» I've ever heard. They've rightfully received recognition and probably don't need my promotion, but still.

2) Rachel Hardy — this lady knows how to get to your heart. Warning, at first, her voice will sound in your dreams. Belongs to a new generation of artists who are betting on YouTube. In my opinion, her creativity is greatly underrated.

3) Alexian — if you are a fan of Luc Besson's movies, you've definitely heard her. Her singing style is like no other.

4) Emily Linge — a very young singer, but damn, she managed to perform Bohemian Rhapsody in a way that in some places she outdid the queen herself!

Music without words for those moments when you are writing text:

5) Kelsey Lee Cate — an optimistic pianist and composer, I love listening to her in the mornings.

6) Karolina Es — beautiful string music and bright shows for cat-music lovers)

7) Rhapsodie — her interaction with the keys is like witchcraft, gives piano lessons.

Listen to a bedtime story

8) Puffin Cafe – the golden age of world fiction and attention to talented budding authors. Pleasant voice, good taste.

That's probably it for today. Thanks to those who read to the end, or at least tried to do so. If you want to write me a letter, send it to my email [email protected]

Sergey Kovalenko
Spring 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 )
Tags:
Hubs:
Total votes 3: ↑3 and ↓0+3
Comments0
24
Karma
0
Rating
@Sergey_Kovalenko

User

Send message

Articles

Your account

Sections

Information

Services

Support
© 2006–2024, Habr