[Перевод] Affordable as a Bus, Comfortable as a Taxi: A Promising Type of Public Transport for Large and Medium-Sized Cities.Part1

bgdxdkwvaek7yq-7a4femo75zc8.jpeg
(Jean-Claude Mézières)

Translation provided by ChatGPT, link to the original article

Link to Part 2: «Experiments on a Torus»
Link to Part 3: «Practically Significant Solutions»
Link to «Summary»

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.

image

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.

image


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.

image


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 $3-5$ seconds. Let’s take an estimate of $4$. Suppose that on each stop, an average of $2$ people get on or off the bus. In that case, the boarding-alighting process will require approximately $16$ seconds of stoppage on average, and the average speed will not exceed $500/(46 + 16) \approx 8$ 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 $A$ and $B$, along its route.

image


Figure 4

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

$T_{tr} = |AB|/v$ — This component represents the time it would take to travel the distance between $A$ and $B$ at the maximum allowed speed $v$.

$T_a =$ «number of stops between $A$ and $B$»$ \times$ «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 $17$ seconds.

$T_w =$ «number of passengers boarding or alighting between $A$ and $B$»$ \times$ «penalty per passenger boarding/alighting».

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

$\bar {v_{AB}} = |AB|/(T_{tr} + T_a + T_w) \ \ \ \ \ (1) $

If we want $\bar {v_{AB}}$ to be as high as possible, we need to minimize the values of the components $T_{tr}$, $T_a$, and $T_w$.

We have no control over the component $T_{tr}$, as it depends on the distance $AB$ and the maximum allowed speed $v$.

The second component $T_a$ is obtained by multiplying the penalty for acceleration/deceleration by the number of stops the bus makes between points $A$ and $B$. 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 $A$ and $B$ by spacing them out more.

The third term, $T_w$, 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 $A-B$. The average number of people who board or exit the buses on route $M$ per unit of time at stops between $A$ and $B$ is almost independent of the distance between these stops. Indeed, if there is no alternative transportation, then everyone who needs to travel from $A$ to $B$ by route $M$ will eventually get on their bus, whether there are $10$ stops or $30$ stops. The same applies to those who intend to travel from $A$ to $B$ using this route.

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

And so, if we want to increase the average speed of buses on route $M$, 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.

image


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 $k$-th intersection along their path (see Figure 6).

image


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 $k$-th intersection along their path (see Figure 6).

image


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 $A$ to a sufficiently distant point $B$.

If both points are located on the same street and do not occupy any particular position, a relatively fast way to travel from $A$ to $B$ would be as follows:
First, you need to walk from point $A$ to the nearest intersection $P_1$ and catch a local bus there that goes towards the nearest stop $P_2$ where transit buses stop. Upon reaching $P_2$, get off the bus and transfer to a transit bus that is heading towards point $B$. On this second bus, ride until you reach $P_3$, which is the closest stop to point $B$ among the rest. In general, $P_3$ is not the closest intersection to $B$, so you will need to catch another local bus towards point $B$ and get off at the intersection closest to it, $P_4$. 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?

image


Figure 7

In the general case, when points $A$ and $B$ do not lie on the same street and do not have any specific positioning, the journey from $A$ to $B$ 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.

image


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 $k$ should be in order for the average speed of transit buses to approach the standard $60$ kilometers per hour ($1$ 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 $T_a = 17$ seconds. Let’s assume that the transit bus picks up and drops off $x$ passengers at each stop, resulting in a dwell time of $T_w ≈ 2x \cdot 4$ seconds. If the bus stops are located at every k-th intersection, and the block length is half a kilometer, then $T_{tr} = 500k/v$. From everything said, it follows that the formula for the average bus speed can be written as:

$\bar {v} = 500 k/ (T_{tr} + T_a + T_w) = v \frac {1}{1 + (T_a + T_w)/T_{tr}} \ \ \ \ \ \ (2)$

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

$\frac {T_a + T_w}{T_{tr}} \ll 1 \ \ \ \ \ \ (3)$

Therefore, we can use the approximation:

$\frac {1}{1+\varepsilon} \approx 1 - \varepsilon \ \ \ \ \ \ (4)$

and rewrite $(2)$ as:

$\bar {v} = v (1 - (T_a + T_w)/T_{tr}) \ \ \ \ \ \ (5)$.

The last formula shows that there is no point in trying to make the passenger boarding/alighting time $T_a$ much smaller than the acceleration/deceleration penalty $T_w$ — 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 $T_w = T_a = 17$ seconds. This value of $T_w$ corresponds to approximately $2$ passengers boarding and alighting at each stop. Substituting $T_w = T_a = 17$ sec, $T_{tr} = 500k/17 \approx 30 k$ sec into $(5)$, we obtain the inequality for $k$:

$1 - \frac {17 + 17}{30k} \geq \bar {v}/v \ \ \ \ \ \ (6)$ or

$k \geq 1.13 \frac {1}{1 - \bar {v}/v} \ \ \ \ \ (7)$.

If, for example, we want transit buses to travel at an average speed of at least $45$ km/h ($3/4$ of $v$), then $k$ must be at least $5$, which means there should be approximately $2.5$ 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 $3$ transit segments or $7.5 - 10$ kilometers in length. A city of such size, with a standard density of $5000$ inhabitants per square kilometer, would have a population of approximately $300,000$ people.

According to my rough estimates, in cities larger than $20$ km (with a population of over $2$ 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 $0.6v$ ($13$ m/s or $36$ 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.

image


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 $L_H \times L_W$. We divide it into a grid of equally sized square cells ${S_{h,w}}$. 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.

image


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 $S_{h',w'}$ and dropped off at their respective destinations in the «finish» square $S_{h'',w''}$, with the taxi already located at $S_{h',w'}$. For any route $\alpha$ that solves the problem of shared transportation for the travelers, there exists a route $\beta$ such that:

1) Route $\beta$ also solves the transportation problem for these travelers.
2) Route $\beta$ has the same boarding and alighting order for the travelers as $\alpha$, but is one of the shortest routes with this order.
3) When using route $\beta$ by the taxi, the trip length for each passenger is the same or shorter compared to using route $\alpha$.
4) The entire route $\beta$ can be divided into three continuous segments: initial, middle, and final. The initial segment lies entirely within $S_{h',w'}$, the final segment lies entirely within $S_{h'',w''}$, 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 $S_{h',w'}$ and $S_{h'',w''}$ are not horizontally or vertically aligned, route $\beta$ can be selected in such a way that its middle segment represents a shortest $\Gamma$-shaped curve drawn between the nearest (corner) intersections of squares $S_{h',w'}$ and $S_{h'',w''}$.

image


Figure 11

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

4.3 Traversal Algorithm


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

Now, let’s imagine that at the specified point $S$ in cell $S_{h',w'}$, an empty taxi appears, which must make a trip between $S_{h',w'}$ and $S_{h'',w''}$, and then arrive at the specified point $F$ in cell $S_{h'',w''}$. The future passengers of this taxi, let’s say there are n of them, are randomly scattered across all intersections within $S_{h',w'}$. 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 $S_{h'',w''}$? Clearly, both of these algorithms should minimize the taxi’s route within the cells $S_{h',w'}$ and $S_{h'',w''}$. 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 $\Delta l$ of the cells $S_{h,w}$ 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 $S_{h,w}$, 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 $S_{h,w}$, 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 $A$ will be located in the top-right corner of $S_{h',w'}$, and intersection $B$ will be in the bottom-left corner of $S_{h'',w''}$.

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 $\Delta l/ (\sqrt{n} - 1)$. The «snake» shown in the figure traverses all the grid points and ends up in the upper-right corner at point $A$, with a length of $(\sqrt{n} + 1) \Delta l$. 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 $\Delta l/ (\sqrt{n} - 1)$, and there will be a total of $n - 1$ such «transfers». Hence, the total traversal length will be at least $(n - 1) \cdot \Delta l/ (\sqrt{n} - 1) = (\sqrt{n} + 1) \Delta l$.

Now let’s construct a solution for the general case where the initial positions of the $n$ travelers are randomly scattered within $S_{h',w'}$. To achieve this, we divide the cell $S_{h',w'}$ into $sqrt{n} - 1$ 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 $(\sqrt{n} + 1) \Delta l$. Each deviation maneuver to pick up a passenger will, on average, add $1/2 \Delta l/(\sqrt{n} - 1)$ units of additional distance, which sums up to an extension of the route by approximately $\sqrt{n} \Delta l/2$. Therefore, the average length of traversing the starting cell will be approximately $\approx 3/2 \sqrt{n} \Delta l$.

image


Figure 13

Let’s consider that the cell $S_{h'',w''}$ is divided into the same vertical strips as the cell $S_{h',w'}$. It should be obvious that when the intercell taxi reaches $S_{h'',w''}$, 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 $F$ at the end of the last strip, it can be assigned to a return trip from $S_{h'',w''}$ to $S_{h',w'}$.

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


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

The first question is to determine which staircase curves from $A$ to $B$ will have the shortest length. The second question is about

© Habrahabr.ru