This post may be of general interest to people looking at optimization as a concept; it’s something I wish I’d understood when I taught calculus for economics. The transportation context is network optimization – there is a contrast between the sort of continuous optimization of stop spacing and the discrete optimization of integrated timed transfers.

Minimum and maximum problems: short background

One of the most fundamental results students learn in first-semester calculus is that minimum and maximum points for a function occur when the derivative is zero – that is, when the graph of the function is flat. In the graph below, compare the three horizontal tangent lines in red with the two non-horizontal ones:

A nonzero derivative – that is, a tangent line slanting up or down – implies that the point is neither a local minimum nor a local maximum, because on one side of the point the value of the function is higher and on the other it is lower. Only when the derivative is zero and the tangent line is flat can we get a local extreme point.

Of course, a local extreme point does not have to be a global one. In the graph above, there are three local extreme points, two local maxima and one local minimum, but only the local maximum on the left is also a global maximum since it is higher than the local maximum on the right, and the local minimum is not a global minimum because the very left edge of the graph dips lower. In real-world optimization problems, the global optimum is one of the local ones, rather than an edge case like the global minimum of the above graph.

First-semester calculus classes love giving simplified min/max problems. This class of problems is really one of two or three serious calc 1 exercises; the other class is graphing a function, and the potential third is some integrals, at universities that teach the basics of integration in calc 1 (like Columbia and unlike UBC, which does so in calc 2). There’s a wealth of functions that are both interesting from a real-world perspective and doable by a first-semester calc student, for example maximizing the volume of some shape with prescribed surface area.

My formulas for stop spacing come from one of these functions. The overall travel time is a function of walking time, which increases as stops get farther apart, and in-vehicle time, which decreases as stops get farther apart. A certain stop spacing produces the minimum overall trip time; this is precisely the global minimum of the travel time function, which is ultimately of the form where a and b are empirical parameters depending on walking speed and other relevant variables.

Continuous optimization

The fundamental fact of continuous optimization, one I wish I’d learned in time to teach it to students, is that at the optimum the derivative is zero, and therefore making a small mistake in the value of the optimum is not a big problem.

What does “mistake” mean in this context? It does not mean literally getting the computation wrong. There is no excuse for that. Rather, it means choosing a value that’s slightly suboptimal for ancillary reasons – perhaps small discontinuities in the shape of the network, perhaps political considerations.

Paul Krugman brings this concept up in the context of wages. The theory of efficiency wages asserts that firms often pay workers above the bare minimum required to get any workers at all, in order to get higher-quality workers and incentivize them to work harder. In this theory, the wage level is set to maximize employer productivity net of wages. At the employer’s optimum the derivative of profit is by definition zero, so a small change in wages has little impact to the employer. However, to the workers, any wage increase is good, as their objective function is literally their wage rather than profits. They may engage in industrial action to raise wages, or push for favorable regulations like a high minimum wage, and these will have a limited effect on profits.

In the context of transit, this has the obvious implication to wages – it’s fine to set them somewhat above market rate since the agency will get better workers this way. But there are additional implications to other continuous variables.

With stop spacing specifically, the street network isn’t perfectly continuous. There are more important and less important streets. Getting transit stops to align with major streets is important, even if it forces the stop spacing to be somewhat different from the optimum. The same is true of ensuring that whenever two transit lines intersect, there is a transfer between them. This is the reason my bus redesign for Brooklyn together with Eric Goldwyn involved drawing the map before optimizing route spacing – the difference between 400 and 600 meters between bus stops is not that important. For the same reason, my prescription for Chicago, and generally other American cities with half-mile grids of arterial roads, is a bus stop every 400 meters, to align with the grid distance while still hewing close to the optimum, which is about 500.

When I talked about stop consolidation with a planner at New York City Transit who worked on the Staten Island express bus redesign, the planner explained the philosophy to me: “get rid of every other stop.” In the context of redesigning a single route, this is an excellent idea as well: the process of adding and removing bus stops in New York is not easy, so minimizing the net change by deleting stops at regular intervals so as to space the remaining stops close to the optimum is a good idea.

The world of public transit is full of these tradeoffs with continuous variables. It’s not just wages and interstations. Fares are another continuous variable, involving particular tensions as different political factions have different objective functions, such as revenue, social rate of return, and social rate of return for the working class alone. Frequency is a continuous variable too in isolation. Top speed for a regional train is in effect a continuous variable. All of these have different optimization processes, and in all cases, it’s fine to slightly deviate from the strict optimum to fulfill a different goal.

Discrete optimization

Whereas continuous optimization deals with flat tangent lines, discrete optimization may deal with delicate situations in which small changes have catastrophic consequences. These include connections between different lines, clockface scheduling, and issues of integration between different services in general.

An example that I discussed in the early days of this blog, and again in a position paper I just wrote to some New Hampshire politicians, is the Lowell Line, connecting Boston with Lowell, a distance of 41 km. The line is quite straight, and were it electrified and maintained better, trains could run at 160 km/h between stops with few slowdowns. The current stop spacing is such that the one-way trip time would be just less than half an hour. The issue is that it matters a great deal whether the trip time is 25 or 27 minutes. A 25-minute trip allows a 5-minute turnaround, so that half-hourly service requires just two trainsets. A 27-minute trip with half-hourly service requires three trainsets, each spending 27 minutes carrying passengers and 18 minutes depreciating at the terminal.

A small deterioration in trip time can literally raise costs by 50%. It gets to the point that extending the line another 50 kilometers north to Manchester, New Hampshire improves operations, because the Lowell-Manchester trip time is around 27-28 minutes, so the extension can turn a low-efficiency 27-minute trip into a high-efficiency 55-minute trip, providing half-hourly service with four trainsets.

In theory, frequency is a continuous variable. However, in the range relevant to regional rail, it is discrete, in fractions of an hour. Passengers can memorize a half-hourly schedule: “the inbound train leaves my stop at :10 and :40.” They cannot and will not memorize a schedule with 32-minute frequency, and needing to constantly consult a trip planner will degrade their travel experience significantly. Not even smartphone apps can square this circle. It’s telling that the smartphone revolution of the last decade has not been accompanied with rapid increase in ridership on transit lines without clockface schedules, such as those of the United States – if anything, ridership has grown faster in the clockface world, such as Germany and Switzerland.

Transit networks involving timed connections are another case of discrete optimization in which all parts of the network must work together, and small changes can make the network fall apart. If a train is late by a few minutes and its passengers miss their connection, the short delay turns into a long one for them. As a result, conscientious schedule planners make sure to write timetables with some contingency time to recover from delays; in Switzerland this is 7%, so in practice, out of every 15 minutes, one minute is contingency, typically spent waiting at a major station.

But this gets even more delicate, because different aspects of the transit network impact how reliable the schedule is. If it’s a bus, it matters how much traffic there is on the line. Buses in traffic not reliable enough for tight connections, so optimizing the network means giving buses dedicated lanes wherever there may be traffic congestion. Even though it’s a form of optimization, and even though there’s a measure of difficulty coming from political opposition by drivers, it is necessary to overrule the opposition, unlike in continuous cases such as wages and fares.

Infrastructure planning for rail has the same issues of discrete optimization. It is necessary to design complex junctions to minimize the ability of one late train to delay other trains. This can take the form of flying junctions or reducing interlining; in Switzerland there are also examples of pocket tracks at flat junctions where trains can wait without delaying other trains behind them. Then, the decision of how much to upgrade track speed, and even how many intermediate stations to allow on a line, has to come from the schedule, in similar vein to the Lowell Line’s borderline trip time.

Continuous and discrete optimization

Many variables relevant to transit are in theory continuous, such as trip time, frequency, stop spacing, wages, and fares. However, some of these have discontinuities in practice. Stop spacing on a real-world city street network must respect the hierarchy of more and less important destinations. Frequency and trip times are discrete variables except at the highest intensity of service, perhaps every 7.5 minutes or better; 11-minute frequency is worse to the passenger who has to memorize a difficult schedule than either 10- or 12-minute frequency.

New York supplies a great example showcasing how bad it can be to slavishly hew to some optimal interstation and not consider the street network. The Lexington Avenue Line has a stop every 9 blocks from 33rd Street to 96th, offset with just 8 blocks between 51st and 59th and 10 between 86th and 96th. In particular, on the Upper East Side it skips the 72nd and 79th Street arterials and serves the less important 68th and 77th Streets instead. As a result, east-west buses on the two arterials cross Lexington without a transfer.

Just east of Lex, there is also a great example of optimization on Second Avenue Subway. The stops on Second Avenue are at 72nd, 86th, and 96th, skipping 79th. It turns out that skipping 79th is correct – the optimum for the subway is to the meter the planned stop spacing for the line between 125th and Houston Streets, so it’s okay to have slightly non-uniform stop spacing to make sure to hit the important east-west streets.

Frequency and trip times are subject to the Swiss maxim, run trains as fast as necessary, not as fast as possible. Hitting trip times equal to an integer or half-integer number of hours minus a turnaround time has great value, but small further speedups do not. Passengers still benefit from the speedup, but the other benefits of higher speed to the network, such as better connections and lower crew costs, are no longer present.

The most general rule here is really that continuous optimization tolerates small errors, whereas discrete optimization does not. Therefore, it’s useful to do both kinds of optimization in isolation, and then modify the continuous variable somewhat based on the needs of the discrete one. If you calculate and find that the optimal frequency for your bus or train is once every 16 minutes, you should round it to 15, based on the discrete optimization rule that the frequency should be a divisor of the hour to allow for clockface timetable. If you calculate and find that the optimal bus stop spacing is 45% of the distance between two successive arterial streets, you should round it to 50% so that every arterial gets a bus stop.

Getting continuous optimization right remains important. If the optimal stop spacing is 500 meters and the current one is 200 meters, the network is so far from the local maximum of passenger utility that the derivative is large and stop consolidation has strong enough positive effects to justify overruling any political opposition. However, it is subsequently fine to veer from the optimum based on discrete considerations, including political ones if removing every 1.7th bus stop is harder than removing every other stop. Close to the local maximum or minimum, small changes really are not that important.

Rail services can be lines or circles. The vast majority are lines, but circles exist, and in cities that have them they play an important niche. Owing to an overreaction, they are simultaneously overused and underused in different parts of the world. However, that some places overuse circles does not mean that circles are bad, nor does it mean that specific operational problems in certain cities are universal.

In particular, what I think of as the ideal urban rapid transit network should feature circles once the network reaches a certain scale, as in the following diagram that I use as my Patreon avatar:

Circles and circumferentials

Circles are transit lines that run in a loop without having a definitive start or end. Circumferentials are lines that go around city center, connecting different branches without passing through the most congested part of the city. In the ideal diagram above, the purple line is both a circle and a circumferential. However, lines can be one without being the other, and in fact examples of lines that are only one of the two outnumber examples of lines that are both.

For example, here is the Paris Metro:

Paris has a circle consisting of Metro Lines 2 and 6, which are operationally lines; people wishing to travel on the arcs through the meeting points at Nation and Etoile must transfer. Farther out, there is an incomplete circle consisting of Tramway Line 3, where the forced transfer between 3a and 3b is Porte de Vincennes. Even farther out there is an under-construction line not depicted on the map, Line 15 of Grand Paris Express, which has a pinch point at its southeast end rather than continuous circular service. All three systems are great example of circumferential lines with very high ridership that are not operationally circles.

Another rich source of circumferential lines that are not circles is cities near bodies of water. In those cities, a circumferential line is likely to be a semicircle rather than a circle. This is responsible for the current state of the Singapore Circle Line, although in the future it will be closed to form a full circle. The G train in New York is a single-sided circumferential line to the east of Manhattan, not linking with anything to the west of Manhattan because of the combination of wide rivers and the political boundaries between New York and New Jersey.

In the opposite direction – circles that are not circumferentials – there are circular lines that don’t neatly orbit city center. The Yamanote Line in Tokyo is one such example: its eastern end is at city center, so it combines the functions of a north-south radial line with those of a north-south circumferential line connecting secondary centers west of Central Tokyo. London’s Circle Line is no longer operationally a circle but was one for generations, and yet it was never a circumferential – it combined the central legs of two east-west radial mainlines, the Metropolitan and District lines.

We can collect this distinction into a table:

Operational concerns: the steam era

In the 19th century, it was very common to build circular lines in London. In the steam era, reversing a train’s direction was difficult, so railways preferred to build circles. This was the impetus for joining the Metropolitan and District lines to form the Circle line. Mainline regional rail services often ran in loops as well: these were as a rule never or almost never complete circles, but instead involved trains leaving one London terminus and then looping around to another terminus.

Another city with a legacy inherited from steam-era train operations is Chicago. The Loop was built to easily reverse the direction of trains heading into city center. At the outer ends they would need to reverse direction the traditional way, but there was no shortage of land for yards there, unlike in the Chicago CBD since named after the Loop.

As soon as multiple-unit control was invented in the 1890s, this advantage of circles evaporated. Subsequently rapid transit lines mostly stopped running as circles unless they were circumferential. London’s Central line, originally pitched as two long east-west lines forming a circle, became a single east-west line, on which trains would reverse direction.

Operational concerns: the modern era

Today, it is routine to reverse the direction of a rapid transit train. The vast majority of rapid transit routes run as lines rather than circles.

If anything, there have been complaints that circles are harder to run service on than lines. However, I believe these concerns are all specific to London, which changed its Circle line from a continuous loop to a spiral in 2009. I have heard concerns about the operations of the Ringbahn here, but as far as I can tell the people who express them are doing so in analogy with what happened in London, and are not basing them on the situation on the ground here. Moreover, there are no plans to make the Yamanote Line run as anything other than the continuous loop it is today.

The situation in London is that the Circle line has always shared tracks with both the Metropolitan and District lines. There has always been extensive branching, in which a delay on one train propagates to the entire network formed by these two mainlines. To this day, Transport for London does not expect the lines in the subsurface network to have the same capacity as the isolated deep tube lines: with moving block signaling it expects 32 trains per hour, compared with 36 on isolated lines.

What’s more, the junctions in London are generally flat. Trains running in opposite directions can conflict at such junctions, which makes the schedules more fragile. Until 2009, London ran the Circle line trains every 7 minutes, which was bound to create conflicts with other lines.

The importance of this London-specific background is that the argument against circles is that they make schedules more fragile. If there is no point on the line where trains are regularly taken out of service, then it is hard to recover from timetable slips, and delays compound throughout the day. However, this is relevant mainly in the context of an extensively-branching system like London’s. Berlin has some of that branching as well, but much less so; one of the sources of reverse-branching on the S-Bahn is a line that should get its own cross-city route anyway, and another is a Cold War relic swerving around West Berlin (S8/85).

The benefits of complete circles

The complete circle of the Yamanote Line or the Ringbahn can be compared with incomplete circles, such as the Oedo Line or the various circumferentials in Paris. From passengers’ perspective, it’s better to have a complete circle, because then they can undertake more trips.

Circumferential lines broadly have two purposes:

1. They offer service on strong corridors that are orthogonal to the direction of city center, such as the various boulevards hosting the M2/6 ring as well as the Boulevards des Maréchaux hosting T3.
2. They offer connections between two radial lines that may not connect in city center, or may connect so far from the route of the circumferential that transferring via the circumferential is faster.

Both purposes are enhanced when the route is continuous. In the case of Paris, a north-south trip east of Nation is difficult to undertake, as it requires a transfer at Porte de Vincennes. Passengers connecting from just south, on M8 or even on M7, may not save as much time traveling to lines just north, such as M9 or M3, and might end up transferring at the more central stations of Republique or Opera, adding to congestion there.

In contrast, in Berlin the continuous nature of the Ring makes trips across the main transfer points more feasible. Just today I traveled from my new apartment to a gaming event on the Ringbahn across Ostkreuz. At Ostkreuz the trains dwelled longer than the usual, perhaps 2 minutes rather than the usual 30 seconds, which I imagine is a way to keep the schedule. That delay was, all things considered, minor. Had I had to transfer to a new train, I would have almost certainly taken a different combination of trains altogether; the extra waiting time adds up.

Why are circles so uncommon?

The operational concerns of London aside, it’s still uncommon to see complete circles on rapid transit networks. They are the ideal for cities that grow beyond the scale of three or four radial trunks, but there are only a handful of examples. Why is that?

The answer is always some sort of special local concern. If city center is offset to one side of the built-up area, such as in a coastal city, then circumferential lines will be semicircles and not full circles. If there is some dominant transfer point that requires a pinch, then cities prefer to build a pinch into the system, as is the case for Porte de Vincennes on T3 or for some of the lines cobbled together to form the London Overground.

This is similar to the question of missed connections. Public transportation networks must work hard to ensure that whenever two lines meet, they will have a transfer. Nonetheless, missed connections exist in virtually all large rapid transit networks. Some of those are a matter of pure incompetence, but in many, rail networks that developed over generations may end up having one subway line that happens to intersect another far from any station on the older line, and there is little that can be done.

Likewise, it is useful to ensure that circumferential lines be complete circles whenever the city is symmetric enough to warrant circles. Paris, like other big cities with strong transit networks, is good but not perfect, and it is important to call it on the mistakes it makes, in this case building M15 to have a jughandle rather than running as a complete circle.