A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Originally proposed in [21], an event-activity network is a directed graph $G=(V,A)$ whose vertices are called events and whose arcs are called activities.

We are particularly concerned with timetabling in public transport. Each line or trip of a public transport network admits an alternating sequence of departure and arrival events, connected by an alternating sequence of driving and dwelling activities. Relations between different trips can be described by further activities, such as transfer activities that model passenger transfers, or headway activities that ensure a certain time distance between two events. An example network is depicted in Figure 1. The goal of timetabling is then to assign times to the events such that the resulting activity duration between adjacent events is within pre-specified bounds.

A passenger journey in a public transportation network has a natural interpretation as a path in a classical event-activity network. However, when a timetable and hence activity lengths (called tensions) have been determined, it is not reasonable to solve a shortest path problem on $G$ as is: Passengers are typically not required to start and end their journey at specific departure or arrival events. Instead, they might choose any line serving a close-by stop within walking distance of their point of origin. Analogously, it makes little sense to select a specific arrival event of a specific line at a specific stop as the endpoint of a journey.

We therefore extend the event-activity network by source cells and target cells that model the origins and destinations of passengers, respectively. Source cells have no incoming edges and can be connected to several departure events by means of access activities. In the same vein, target cells have no outgoing edges, but can be reached from several arrival events by other access activities. Those access activities allow, e.g., to model walking times to different stop locations.

The same construction appears in, for example, [20, 10, 18, 12]. To illustrate, the event-activity network of Figure 1 is extended in Figure 2.

We can now interpret passenger routes as special paths in an extended event-activity network $G$, which connect source cells in $V_{\text{source}}$ to target cells in $V_{\text{target}}$ such that they begin and end with a respective access activity and their remaining activities come from $A_{\text{drive}}\stackrel{.}{\cup }{A}_{\text{dwell}}\stackrel{.}{\cup }{A}_{\text{transfer}}$. Moreover, if we are given an appropriate time duration for each activity, we can ask for a shortest passenger route from a source cell $s$ to a target cell $t$, and answer with a shortest $s$-$t$-path in $G$. How to find these times is the subject of the subsequent subsection.

The TimPass problem is an extension of the Periodic Event Scheduling Problem (PESP) for periodic timetabling to extended event-activity networks incorporating passenger routing.

The periodic timetable $\pi$ gives the departure and arrival times, which repeat with a period time of $T$. The periodic tension $x$ captures the length of each activity $a=(i,j)\in A\setminus A_{\text{access}}$ and is determined up to an integer multiple of $T$ by the event potentials ${\pi }_i$ and ${\pi }_j$ such that $\mathrm{\ell }\le x\le u$ holds. Since the duration of access activities models walking times, we consider their tensions fixed to their lower bounds. To route the passengers, we assume that for each OD pair $(s,t)\in V_{\text{source}}\times V_{\text{target}}$, all $d_{st}$ passengers travel along the same shortest path. This path is determined based on the travel times derived from the periodic tension $x$ and the lower bounds of the access activities. Additionally, each transfer activity incurs a penalty, with its actual duration increased by a supplement of $\rho$.

It is straightforward to state a mixed-integer programming formulation for TimPass:

Here, we write $𝒟≔\{(s,t)\in V_{\text{source}}\times V_{\text{target}}\mid d_{st}>0\}$ for the set of OD pairs with positive demand. The constraints (3)–(6) define PESP, while (8)–(9) describe the selection of exactly one $s$-$t$-path per OD pair $(s,t)\in 𝒟$ from the set of all such paths $P_{st}$. The number of passengers $w_a$ on each activity $a\in A$ is then simply the sum over all passengers whose selected $s$-$t$-path contains $a$, as dictated by constraint (7). The objective (2) is to minimize the total (perceived, if $\rho >0$) travel time of all passengers.

In a geometric language, we can make the following observations in Figure 4:

1. 1.

   The space of feasible periodic tensions is a disjoint union of line segments in the square.

2. 2.

   The hyperplane $x_1+x_2=15$ subdivides the square into two polytopes, where each polytope corresponds to the region where one of the two paths is a shortest path.

3. 3.

   A line segment of feasible tensions is never part of the interior of more than one shortest path region.

Revisiting the three geometric observations from Example 6, we note for Example 7:

1. 1.

   The space of feasible tension is the full square.

2. 2.

   The three paths give rise to a polyhedral subdivision of the square, each maximal region corresponding to the unique shortest $s$-$t$-path with respect to the periodic tensions of that region.

3. 3.

   The shortest path subdivision is also a proper subdivision of the square of periodic tensions.

Our interpretations look different at first glance. We offer a unifying perspective in the next subsection.

We will now generalize the geometric observations made in the previous examples. Let $I=(G,T,\rho ,\mathrm{\ell },u,D)$ be a TimPass instance.

The fractional tension polytope is the space of all vectors $x\in {ℝ}^{A\setminus A_{\text{access}}}$ that satisfy the constraints of the linear programming relaxation of (2)–(9). $X_{\text{LP}}$ is by definition a hyperrectangle, such as the squares in Example 6 and Example 7. The periodic tension space $X$ is the space of vectors $x$ that are feasible for the mixed-integer program (2)–(9), e.g., the blue line segments in Figure 4 and the full square in Figure 6.

We refer to [7] for the origin of the name polytrope, and recall a few results from [5]: Let $\mathrm{\Gamma }$ be the cycle matrix of an integral cycle basis of the induced subgraph $G[V_{\text{dep}}\cup V_{\text{arr}}]$.

1. 1.

   For $z,z^{\prime }\in {\mathbb{Z}}^A$ we have either $R(z)\cap R(z^{\prime })=\mathrm{\varnothing }$ or $R(z)=R(z^{\prime })$, the latter case occurring if and only if $\mathrm{\Gamma }z=\mathrm{\Gamma }{z}^{\prime }$.

2. 2.

   The periodic tension space is the union of all $R(z)$, taken over all $z\in {\mathbb{Z}}^A$.

3. 3.

   For each $z\in {\mathbb{Z}}^A$, solving PESP restricted to $x\in R(z)$ is a linear program dual to minimum cost network flow, and hence solvable in polynomial time.

4. 4.

   One can define a neighborhood relation such that two non-empty polytropes $R(z)$ and $R(z^{\prime })$ are neighbors if $\mathrm{\Gamma }z$ and $\mathrm{\Gamma }{z}^{\prime }$ differ by $\pm$ a column of $\mathrm{\Gamma }$.

These insights led to tropical neighborhood search, a powerful heuristic for the Periodic Event Scheduling Problem [4]. This is a local search that starts with a non-empty polytrope and scans for improving neighbors. Any polytrope has at most $2|A\setminus A_{\text{access}}|$ neighbors, and PESP can be solved on each polytrope in polynomial time.

We will generalize tropical neighborhood search to integrated tropical neighborhood search (ITNS). To this end, we need to include passenger paths into our considerations.

Speaking geometrically, finding a passenger routing for a periodic tension $x\in X$ then amounts to determining, for each $(s,t)\in 𝒟$, an $s$-$t$-path $p$ such that $x\in S_{s,t}(p)$. In Figure 4, the orange polytope is $S_{s,t}(p_b)$, defined by the inequality $x_1+x_2\le 15$, and the grey polytope is $S_{s,t}(p_r)$, defined by $x_1+x_2\ge 15$. Analogously, we see the subdivision of the square $X_{\text{LP}}$ into $S_{s,t}(p_{bb}),S_{s,t}(p_{br}),S_{s,t}(p_{rr})$ in Figure 6 according to (10).

The shortest path subdivision ${𝒮}_{s,t}$ of $X_{\text{LP}}$ naturally induces a subdivision of each polytrope $R(z)$. Looking at Figure 4, this subdivision is rather trivial, as is confirmed by the following:

In the coarse polytrope heuristic, for a given initial tension $x\in R(z)$, we determine the region $R$ in the sense of (17) such that $x\in R\cap R(z)$ and solve TimPass optimally by means of Corollary 14. To this end, we solve the linear program indicated in the proof, and its optimal objective value will give the minimum total travel time on $R\cap R(z)$.

The fine polytrope heuristic proceeds as the coarse heuristic, but then tries to improve the solution by re-routing passengers for single OD pairs in the spirit of Corollary 13.

In view of Theorem 12, Step (2) can be understood as a heuristic exploration of the neighboring regions of $R(z)\cap {\bigcap }_{(s,t)\in V_{\text{source}}\times V_{\text{target}}}{S}_{s,t}(p_{s,t})$. The algorithm may be fine-tuned by adapting the selection and sorting of the OD pairs. Note that for the linear programs in (2), only the objective function changes, so that warm-starting is possible.

We embed the two polytrope heuristics into tropical neighborhood search for periodic timetabling [4].

As computing shortest paths for all OD pairs is the major bottleneck, we do not use the fine polytrope heuristic in Step (3). Depending on the algorithm chosen in Step (2), we speak of coarse or fine ITNS. The ITNS might be refined in several ways, e.g., by different pivot or quality-first rules, see [4].

All presented algorithms in this paper are neighborhood searches that require an initial feasible timetable. We outline a heuristic to obtain those by constructing a spanning tree structure $𝒯={𝒯}_{\mathrm{\ell }}\stackrel{.}{\cup }{𝒯}_u$. First, note that it is usually assumed that $u_a={\mathrm{\ell }}_a+T-1$ holds for transfer activities $a\in A_{\text{transfer}}$. So if $A_{\text{other}}=\mathrm{\varnothing }$, adding all driving and dwelling activities to the lower bound tree ${𝒯}_{\mathrm{\ell }}$ and connecting the resulting line components by transfer activities always yields a feasible timetable. We can weigh the transfer activities by the number of passengers on them subject to a lower bound routing, i.e., with respect to shortest paths when all tensions $x_a$ are at their lower bound ${\mathrm{\ell }}_a$. If there are any other activities in $A_{\text{other}}$, then special care has to be taken to ensure feasibility:

• $\mathrm{■}$

  Turnaround activities model the required downtime between the end of a line and the beginning of its reversal direction due to constraints such as driver breaks. Thus, the driving and dwelling activities of a line, its reversal direction and turnover activities form a cycle whose tensions have to sum to zero modulo the period time $T$ due to the cycle periodicity property. We always add this cycle to the tree omitting one of its activities. Some activities may have to have their tension fixed to the upper bound to ensure feasibility.

• $\mathrm{■}$

  If a line is repeated within the global period of the instance, its events are copied appropriately often in the event-activity network and connected by synchronization activities. We construct the connected tree component of a line to always include all of its repetitions along those timing activities.

• $\mathrm{■}$

  Like transfers, headway activities connect line components but may have bounds that impact feasibility. When we add a line component to the tree under consideration of the previous two points, we collect all outgoing transfer and headway activities. We then process them in some order to either connect additional lines to the growing tree or, if both events incident to the activity are already in the tree, we store them for later. Once we have connected all lines and the tree is spanning, we check if the tension of the remaining co-tree activities is feasible. If not, we attempt pivot operations and to switch up membership in ${𝒯}_{\mathrm{\ell }}$ and ${𝒯}_u$ along the fundamental cycle until we have a feasible timetable, or we have to give up.

Whether this process succeeds in finding a feasible timetable is sensitive to the order in which we process transfer and other activities. It always succeeds on the TimPassLib instances if we process activities in $A_{\text{other}}$ in decreasing order of $u_a-{\mathrm{\ell }}_a$ and then the transfer activities weighted by the lower bound routing, or, if this fails, in increasing order of $u_a-{\mathrm{\ell }}_a$ until $u_a-{\mathrm{\ell }}_a>T/2$, then the weighted transfer activities, then the remaining other activities.

We ran C++ implementations of our proposed methods on an initial solution obtained as explained in the previous subsection on each TimPassLib instance with a time limit of an hour. For an overview on the instance sizes we refer to [17] and https://timpasslib.aalto.fi/. For ITNS, we report the best solutions in terms of total travel time found across three parameter settings concerning a quality-first rule and numbers of OD pairs considered in Step (3) of Algorithm 16. We always sort the OD pairs with respect to decreasing weighted slack along the current path $p$, i.e., $d_{st}{\sum }_{a\in p}(x_a-{\mathrm{\ell }}_a)$, so that heavy demand relations with much longer travel times than necessary come first.

All computations have been carried out on an Intel Core i7-9700K CPU with 64 GB RAM. The results are presented in Table 1 in the appendix.

For six of the instances, we provide better incumbent solutions (Hamburg, grid, long, metro, Erding20, Erding21). The Stuttgart instance is very large and causes a memory problem in the ITNS implementation. The RIMNS performs particularly strong. For ITNS, the coarse version is on level with RIMNS, better on larger instances, but worse on smaller.

The fine ITNS is never better than coarse ITNS. This is also highlighted in Table 2 in the appendix, where we collect the computation times and the total travel time improvement in relation to the initial solution. It turns out – see that last column of Table 2 – that the improvements made in (2) of Algorithm 16 are very minor, while moving to neighboring polytropes has a larger impact on the total travel time. In particular, it is not advisable to spend computation time for the fine ITNS.

Unfortunately, we could not determine better travel times for the RxLy instances within one hour, whose current incumbents are based on a heavy machinery of periodic timetable optimization [3, 17]. However, since our methods performed strongly on the instances where the time limit was not an issue, we became curious if we would be able to beat the best known incumbents if we allotted more computation time. Moreover, it is straightforward to parallelize the exploration of the neighborhood of the current solution for both MNS and TNS, and the shortest path computations for TNS, yielding massive speed-up by moving to high-throughput cluster nodes with 96 threads composed of Intel Xeon Gold 6342 CPUs with 512 GB RAM. Within a wall time limit of 24 hours, we provide better incumbent solutions for all TimPassLib instances except toy, toy2, and Stuttgart, see Table 3 in the appendix. Note that toy and toy2 have already been solved to proven optimality previously. It becomes apparent that RIMNS outperforms coarse ITNS in this setting, the latter stopping earlier with worse local optima. The 24 new incumbents have all been computed by RIMNS, while coarse ITNS improves the TimPassLib bounds only for 6 instances.