The Line-Based Dial-a-Ride Problem with Transfers

The dial-a-ride problem and variants thereof have been studied extensively in the literature, see the surveys by [9] (up until 2007) and [16] (until 2018) for an overview, as well as the typography provided by [21]. Solution methods for the static setting include exact, MILP-based methods such as branch-and-cut [7, 27, 28] or branch-cut-and-price [15], as well as (meta-)heuristic-based methods, including tabu search [8], simulated annealing [5, 25], and adaptive large neighborhood search [22, 23, 24, 29], to give an overview. Further works study dynamic variants of the DARP, see, e.g., [1, 2, 6, 12, 17].

Recently, a number of DARP variants that allow transfers, named DARPT, have been proposed, see, e.g., [10, 14, 20, 25, 30], whose solution approaches all use (meta-)heuristics. Solely [14], who consider a single transfer station, additionally evaluate a branch-and-cut approach for instances with up to 10 requests.

The line-based dial-a-ride problem (on a single line) was first introduced by [26], wherein different MILP formulations were proposed and compared. Lauerbach et al. [18] study the complexity of the liDARP (and the related MinTurn problem).

In this paper, we develop an event-based approach for the liDARPT, which first constructs an event-based graph encoding structural instance information, and then finds feasible circulations on this graph using a MILP. Such an approach was proposed first for the DARP in [12, 13]. In an event-based graph, nodes represent so-called events, consisting of a boarding or alighting action and information on which passengers are already on board of the vehicle, and arcs represent feasible transitions between the events. In [13], it was already observed that the number of events is exponential in the vehicle capacity for DARP event-based graphs. Event-based MILPs introduce a binary variable for each arc in the event-based graph. To obtain a tractable event-based MILP, it is crucial to delete (nodes and) arcs corresponding to infeasible (events and) transitions. Pre-processing rules for the DARP have been proposed in [11, 13]. In [26], these have been extended for the liDARP, where the additional restrictions on vehicle operations lead to a significant decrease in event-based graph size and computation times for the event-based MILP.

In [11], the authors improve the event-based MILP formulation from [13] to the location-augmented event-based (LAEB) formulation by incorporating the time consistency of the location-based (two-index) formulation by Ropke et al. [28], effectively halving the computation times compared to state-of-the-art event-based approaches on tested benchmark instances.

In the liDARPT, we are given a set of stations $𝒮$ and a set of lines $ℐ$, where each line $i\in ℐ$ is an ordered sequence of stations ${\lambda }_i$ and each station lies on at least one line. The lines may intersect at transfer stations $s\in {𝒮}^T$. For each line $i\in ℐ$, the distance between two stations $s_1,s_2\in {\lambda }_i$ is given by $t(s_1,s_2)>0$ and respects the triangle inequality. The value $t(s_1,s_2)$ equivalently corresponds to the length of the segment between $s_1,s_2$ on line $i$. Both distance and length are measured in time.

Each line is assigned at least one vehicle $k\in 𝒦$ which travels according to the driving restrictions introduced by [26] for the liDARP: a vehicle may travel along the line in both directions, may take shortcuts or wait at stations, but may only turn when empty. Vehicles may only serve stations on their respective lines and every vehicle starts and ends its tour at a line-specific depot $s^{\text{depot}}\in 𝒮$. The vehicles assigned to the same line $i\in ℐ$ are homogeneous in the sense that they have the same capacity $c_i\in \mathbb{N}$.

Furthermore, we are given a set of requests $ℛ$. Each request $r\in ℛ$ consists of a number of passengers $q_r\in \mathbb{N}$, a pick-up station $r^{+}\in 𝒮$, a drop-off station $r^{-}\in 𝒮$, a time window for the pick-up and one for the drop-off of the request, denoted as $[e(r^{+}),l(r^{+})]$, $[e(r^{-}),l(r^{-})]$, respectively, and a maximum travel time $L_r\ge 0$ between their initial pick-up (at their origin) and last drop-off (at their destination). We assume each request is willing to wait a fixed amount of time for their pick-up/drop-off, defining the time window length. Each request can either be accepted, i.e., it is transported from its origin to destination, or rejected. We define a route option of a request as an alternating sequence of lines and transfer stations, starting at the origin and ending at the destination, that describes a set of possible options for transporting this request. Then, a request’s route consists of a route option together with the vehicle used on each line and the associated pick-up and drop-off times at the transfer points.

At each station, we assume that it takes a fixed total service time $b\ge 0$ to service all requests, i.e., for all requests to leave and enter the vehicle. Requests may transfer from one line to another at a transfer station, but we do not consider transfers between vehicles belonging to the same line.

A solution to the liDARPT then consists of a plan for each of the vehicles, and, for each request, a route - or the decision to reject the request. A vehicle’s plan specifies the sequence of stations where the vehicle stops, starting and ending with the depot associated to the vehicle’s line, as well as the arrival and departure time at each station. A route specifies when and where a passenger boards and alights vehicles.

We have two objectives that we consider in lexicographic order: our primary goal is to maximize the number of accepted requests, and the second objective is to minimize the total traveled distance by the vehicles, which may reflect both cost and environmental concerns.

Each line $i\in ℐ$ consists of an ordered sequence of stations ${\lambda }_i:=(s_1,\mathrm{\dots },s_{|{\lambda }_i|})$ with $\{s_1,\mathrm{\dots },s_{|{\lambda }_i|}\}=:{𝒮}_i\subseteq 𝒮$ and defines a complete graph on ${𝒮}_i$. Then, we denote by network the union²²2a union of two graphs $G_1=(V_1,A_1),G_2=(V_2,A_2)$ is the graph $G:=(V_1\cup V_2,A_1\cup A_2)$. of all these graphs, which share vertices at exactly the transfer stations ${𝒮}^T$. We require that the network is connected (else we consider each connected component separately). Note that this definition gives a direction to each line, according to the sequence’s order. Each line may be served both in ascending and in descending order, i.e., requests’ route options and vehicles’ plans both constitute directed paths in the underlying undirected network.

Since a network of multiple lines may allow for multiple paths between the same stations, a single request may have different route options: (unique) paths through the network along one or more lines, from the requests’ pick-up to its drop-off location. These route options may differ in length, number of transfers, and number of lines that are used.

Following [20], to represent a route option through the network, we introduce actions as follows: for a request $r\in ℛ$ which transfers between vehicles from/to a line $i\in ℐ$ at a transfer vertex $s\in {𝒮}^T$, we call ${\rho }_{s,r}^{i,-}$ the inbound action and ${\rho }_{s,r}^{i,+}$ the outbound action of $r$ at $s$ on $i$. That is, the inbound action represents the drop-off (from $i$) and the outbound action represents the pick-up (to $i$) of $r$ at $s$.

Then, a possible route option ${\varphi }^r$ for a request $r\in ℛ$ can be formalized as a sequence of (an even number of) actions $({\rho }_{r^{+},r}^{i,+},{\rho }_{s,r}^{i,-},{\rho }_{s,r}^{i^{\prime },+},\mathrm{\dots },{\rho }_{s^{\prime },r}^{i^{\prime \prime },-},{\rho }_{s^{\prime },r}^{i^{\prime \prime \prime },+},{\rho }_{r^{-},r}^{i^{\prime \prime \prime },-})$, for $s,s^{\prime }\in {𝒮}^T$, $s\ne s^{\prime }$, $i,i^{\prime },i^{\prime \prime },i^{\prime \prime \prime }\in ℐ$, where

• $\mathrm{■}$

  the first action is outbound, corresponding to a pick-up at the station $r^{+}$,

• $\mathrm{■}$

  all intermediate actions (second to penultimate action) are pairs of inbound and outbound actions at the same transfer station $s\in {𝒮}^T$, ensuring transfers,

• $\mathrm{■}$

  the last action is inbound, corresponding to a drop-off at the station $r^{-}$, and

• $\mathrm{■}$

  all actions (first to last) are pairs of outbound and inbound actions on the same line $i\in ℐ$, ensuring consecutiveness in each line.

Note that each station $s$ can only be visited once per route option, forbidding cycles in each requests’ travel path.

We divide this sequence of actions into tuples by pairing each outbound with the following inbound action, i.e., for some $s,s^{\prime }\in {𝒮}^T$, $s\ne s^{\prime }$, ${\varphi }^r:=(({\rho }_{r^{+},r}^{i,+},{\rho }_{s,r}^{i,-}),\mathrm{\dots },({\rho }_{s^{\prime },r}^{i^{\prime },+},{\rho }_{r^{-},r}^{i^{\prime },-}))$, where we call each tuple $({\rho }_{s,r}^{i,+},{\rho }_{s^{\prime },r}^{i,-})$ a split ${\psi }_{s,s^{\prime },r}^i$ of $r$ between stations $s,s^{\prime }\in 𝒮,s\ne s^{\prime }$, on line $i\in ℐ$. We construct a sequence of subroutes which are separated exactly by a transfer between two lines at a transfer station. A split may be part of multiple route options.

The length of a route option is defined as the sum of lengths of its splits, where the length of a split ${\psi }_{s,s^{\prime },r}^i$ is exactly the length $t(s,s^{\prime })$ on $i\in ℐ$.

For a request $r\in ℛ$, we use $\mathrm{\Phi }(r)$ to denote the set of all route options and $\mathrm{\Psi }(r)$ the set of all splits of $r$. Further, $𝒫(r)$ denotes the set of all actions of $r$ and $𝒫$ denotes the set of all possible actions for all requests.

An example for a request on a circular network of three lines is pictured in Figure 1. There are two possible route options for request $r$ to travel to their destination: the first route option transfers at station $s_1$ (along the green, then the blue line), the second route option transfers at $s_2$ (along the green, then the red line).

We assume that each transfer disrupts the travel experience, as it adds uncertainty to a request’s trip and could reduce customer satisfaction. Hence, we impose the following restriction: for each request $r\in ℛ$, we identify the shortest (wrt. time length) route option from $r^{+}$ to $r^{-}$ and count the amount of transfers. Then, to limit the passenger disutiliy, we only allow route options in $\mathrm{\Phi }(r)$ with at most one extra transfer, as transfers are generally perceived as an inconvenience.

The directionality property introduced by [26] enforces that a vehicle traveling along a line may only change direction when it is empty. We adopt the same property and introduce a travel direction: for each line $i\in ℐ$ with ${\lambda }_i=(s_1,s_2,\mathrm{\dots },s_{|{\lambda }_i|})$, we define the travel direction from a station $s_m$ to $s_n$, denoted by $\mathrm{dir}(i,s_m,s_n)$, to be ascending if , else descending. Then, requests traveling on a part of this line, from a transfer station $s\in {𝒮}^T$ to $s^{\prime }\in {𝒮}^T$ with $s,s^{\prime }\in {\lambda }_i$, inherit the traveling direction $\mathrm{dir}(i,s,s^{\prime })$ for this split in their route option.

Until here, we have defined route options for requests based only on lines, locations, and actions, without considering when the actions will take place. We now add a timestamp to every action, corresponding to the end of the pick-up/drop-off of this action, and call a timestamped route option a route of a request $r$. Every route needs to be feasible, i.e., it needs to respect the initial pick-up and drop-off time windows of its request, else we can disregard the route and the underlying route option.

Recall that every request $r\in ℛ$ has a (tight) time window for its pick-up and drop-off, respectively. Using these time windows, along with the service time $b$ and the length of a split, we derive a time window $[e({\rho }_{s,r}^{i,\pm }),l({\rho }_{s,r}^{i,\pm })]$ for each action ${\rho }_{s,r}^{i,\pm }$ associated with $r$.

In case an action appears in multiple route options, its time window is defined as the union of the individual time window intervals: that is, $e({\rho }_{s,r}^{i,\pm })$ is the earliest departure time and $l({\rho }_{s,r}^{i,\pm })$ is the latest arrival time among all relevant options.

Similarly, we can then derive time windows of each split from its actions: for a split ${\psi }_{s,s^{\prime },r}^i$, we have $e({\psi }_{s,s^{\prime },r}^i):=e({\rho }_{s,r}^{i,+})$ and $l({\psi }_{s,s^{\prime },r}^i):=l({\rho }_{s^{\prime },r}^{i,-})$.

In the first step of our event-based approach, we construct an event-based graph $G=(𝒱,𝒜)$, a concept that was proposed first in [13] and adapted for the liDARP in [26]. Here, we discuss how to create an event-based graph for the liDARPT.

An event $v\in 𝒱$ is defined as a tuple $v=({\rho }_{s,r_1}^{i,\pm },{\psi }_{s^{\prime },s^{\prime \prime },r_2}^i,\mathrm{\dots })$ consisting of an action ${\rho }_{s,r_1}^{i,\pm }$ and a set of at most $c_i-1$ splits of requests that may be on board of a vehicle with capacity $c_i$ traveling on the line $i\in ℐ$ when the action takes place. Each event thus represents a feasible combination of splits which may share part of their journey, in contrast to the events in [13], which consist of combinations of requests. Our representation allows us to incorporate tighter time windows at each transfer station on a requests’ route option, and explicitly models the subroutes of each requests’ path. Note that each event is associated with a station and a line, namely the station $s\in 𝒮$ and the line $i\in ℐ$ where the action ${\rho }_{s,r_1}^{i,\pm }$ takes places.

For the tuple representation of $v$, we sort the splits in $v$ in ascending order of their request’s index. We use ${\text{0}}_i$ to denote the empty state at the start and end of each vehicle’s plan at the depot of its line $i\in ℐ$. The events constitute the nodes $𝒱$ of the event-based graph.

For example, the event $({\rho }_{s_2,3}^{i,+},{\psi }_{s_1,s_3,1}^i,{\psi }_{s_1,s_4,2}^i)$ represents that a vehicle of line $i$ is currently at transfer station $s_2$ where request $3$ boards while requests $1$ (who is traveling from station $s_1$ to $s_3$) and $2$ (traveling from station $s_1$ to $s_4$) are already in the vehicle.

The arcs of the event-based graph represent feasible sequences of events. For example, $({\rho }_{s_2,3}^{i,+},{\psi }_{s_1,s_3,1}^i,{\psi }_{s_1,s_4,2}^i)$ may be connected by an arc to the event $({\rho }_{s_3,1}^{i,-},{\psi }_{s_1,s_4,2}^i,{\psi }_{s_2,s_4,3}^i)$, where request $1$ is dropped-off at transfer station $s_3$ and requests 2 and 3 are still on board.

The event-based graph $G$ consists of $|ℐ|$ connected components $G_i$, one for each line $i\in ℐ$, where the number of (potential) nodes (and arcs) of each component $G_i$ grows exponentially in the vehicle capacity $c_i$.

For this reason, we now describe a number of pre-processing steps to identify infeasible combinations of splits, and thus limit the amount of nodes we create. Specifically, our goal is to identify, for every action ${\rho }_{s,r}^{i,\pm }\in 𝒫(r)$ of every request $r\in R$, the set of compatible splits ${\psi }_{g,g^{\prime },r^{\prime }}^i\in {\bigcup }_{r^{\prime }\in ℛ\setminus \{r\}}\mathrm{\Psi }(r^{\prime })$, i.e., splits belonging to requests $r^{\prime }$ that may be on board of the same vehicle at the time when the action ${\rho }_{s,r}^{i,\pm }$ is occurring. Note that we only need to consider splits traveling on the same line $i\in ℐ$.

Let $r\in ℛ$ and ${\psi }_{s,s^{\prime },r}^i=({\rho }_{s,r}^{i,+},{\rho }_{s^{\prime },r}^{i,-})$ with $s,s^{\prime }\in 𝒮$, $s\ne s^{\prime }$, be a split of $r$ traveling on a line $i\in ℐ$. We check three conditions to determine if another split ${\psi }_{g,g^{\prime },r^{\prime }}^i$, with $g,g^{\prime }\in 𝒮$, $g\ne g^{\prime }$, $r^{\prime }\in ℛ\setminus \{r\}$, is compatible to an action in ${\psi }_{s,s^{\prime },r}^i$:

First, the directionality property: we check if the two splits travel in the same direction, i.e., if $\mathrm{dir}(i,g,g^{\prime })=\mathrm{dir}(i,s,s^{\prime })$, as there can never be two splits traveling in opposite directions in the same vehicle at the same time.

We proceed by checking the remaining two conditions for either action in the split $({\rho }_{s,r}^{i,+},{\rho }_{s^{\prime },r}^{i,-})$ individually and here describe the process for ${\rho }_{s,r}^{i,+}$ (${\rho }_{s^{\prime },r}^{i,-}$ follows analogously):

Second, the spatial overlap: we check if the action’s location $s$ lies on the subsequence of stations $(g,\mathrm{\dots },g^{\prime })\subseteq {\lambda }_i$.

Third, the temporal overlap: recall that each action is assigned a time window during which it has to occur. Then, we check if

i.e., if $r$ and $r^{\prime }$ may overlap in their time windows.

We call a split satisfying these three conditions compatible with the action ${\rho }_{s,r}^{i,+}$ (analogously ${\rho }_{s^{\prime },r}^{i,-}$) and repeat these checks for every request $r\in ℛ$.

As an example, consider the line $i$ depicted in Figure 2 with a split ${\psi }_{s_3,s_5,r}^i=({\rho }_{s_3,r}^{i,+},{\rho }_{s_5,r}^{i,-})$ of request $r$ and four other splits for requests $r_1,r_2,r_3,$ and $r_4$. Suppose the action ${\rho }_{s_3,r}^{i,+}$ has a time window of $[0,15]$, while the split ${\psi }_{s_2,s_4,r_3}^i$ has a time window of $[80,120]$ and ${\psi }_{s_3,s_7,s_4}^i$ has a time window of $[5,60]$.

Consider the outbound action ${\rho }_{s_3,r}^{i,+}$ and check the compatibility of each split in Figure 2:

• $\mathrm{■}$

  split ${\psi }_{s_6,s_1,r_1}^i$ does not fulfill the directionality property, as it travels in the opposite direction to ${\psi }_{s_3,s_5,r}^i$, hence it is disregarded.

• $\mathrm{■}$

  split ${\psi }_{s_6,s_7,r_2}^i$ does not satisfy the spatial overlap since $s_3\notin (s_6,s_7)$, as its pick-up station $s_6$ lies beyond the station $s_3$ in the travel direction, hence it is disregarded.

• $\mathrm{■}$

  split ${\psi }_{s_2,s_4,r_3}^i$ does not satisfy the temporal overlap since $[0,15]\cap [80,120]=\mathrm{\varnothing }$, as the earliest start time of its outbound action is later than the time window of ${\rho }_{s_3,r}^{i,+}$, hence is is disregarded.

• $\mathrm{■}$

  split ${\psi }_{s_3,s_7,r_4}^i$ fulfills both the directionality property and the spatial overlap as $s_3\in (s_3,\mathrm{\dots },s_7)$. Additionally, the temporal overlap is satisfied as $[0,15]\cap [5,60]=[5,15]\ne \mathrm{\varnothing }$.

Hence, only the split ${\psi }_{s_3,s_7,r_4}^i$ of request $r_4$ is compatible to ${\rho }_{s_3,r}^{i,+}$ in this example.

Once we have identified all compatible splits for each action on a line $i\in ℐ$, we incrementally build combinations of splits of size at most $c_i$. In each step, we check if the combination is feasible wrt. the time windows of the contained splits and only explore supersets further if this is guaranteed. See [7] for details on the feasibility checks based on time windows and [4] for further details on the implementation of our method.

We add two further conventions at a transfer station to limit the number of events: if multiple compatible actions take place at the same station $s\in {𝒮}^T$, then the inbound actions are handled first. This corresponds to the widely-accepted convention of letting people leave the vehicle first before boarding. Second, if multiple outbound (resp. inbound) actions are compatible and located at the same station $s\in {𝒮}^T$, then we only consider the sequence of events in which they board in descending order of their time window end $l({\rho }_{s,r}^{i,+})$ (resp. $l({\rho }_{s,r}^{i,-})$).

The vertex set $𝒱$ of our event-based graph $G$ then consists, for every line $i\in ℐ$, exactly of the feasible combinations $v=(v_1,\mathrm{\dots },v_m)$ where the first entry $v_1$ is an action and the remaining entries $v_2,\mathrm{\dots },v_m$ are splits, with $m\le c_i$. Each entry corresponds to a different request.

Every event $v=(v_1,\mathrm{\dots },v_m)\in 𝒱$ is assigned a time window during which it can occur, which is not only dependent on the time window of the action $v_1$ but also considers the travel time from every predecessor event (for the earliest start time) and the successor events (for the latest end time), similar to the check for temporal overlap.

Lastly, we define the arc set $𝒜$ of the event-based graph $G$. We add an arc $(v,v^{\prime })$ for $v=({\rho }_{s,r}^{i,\pm },v_2,\mathrm{\dots },v_m)$, $v^{\prime }=({\rho }_{s^{\prime },r^{\prime }}^{i^{\prime },\pm },v_2^{\prime },\mathrm{\dots },v_n^{\prime })\in 𝒱$ of lines $i,i^{\prime }\in ℐ$ if the following conditions are met:

• $\mathrm{■}$

  the set of requests in the vehicle after completing the action ${\rho }_{s,r}^{i,\pm }$ of $v$ is the same as the set of requests in the vehicle before completing the action ${\rho }_{s^{\prime },r^{\prime }}^{i^{\prime },\pm }$ of $v^{\prime }$, and

• $\mathrm{■}$

  the events are compatible wrt. their time windows and travel times, i.e.,

The travel time of the arc $a=(v,v^{\prime })\in 𝒜$ is given by $t(a):=t(v,v^{\prime }):=t(s,s^{\prime })$.

Now, each plan for a vehicle of line $i\in ℐ$ corresponds to a circulation on $G_i$ which starts and ends at the vehicle’s depot. However, not every circulation is a feasible plan: it has to respect the time windows and maximum travel time of every request. Additionally, the set of plans, jointly, has to ensure that, if a request $r$ is accepted, then all splits of exactly one route option of $r$ are part of the solution. That is, while the described pre-processing in the event-based graph allows to sort out many infeasible combinations of requests, and can handle the logic of vehicle routing well, there are a number of constraints that it cannot represent. This motivates the use of MILP model that we present in Section 2.4.

In this section, we present a MILP model for the liDARPT. It is based on the location-augmented event-based formulation introduced by [11] for the DARP and uses the event-based graph $G=(𝒱,𝒜)$ we have defined in Section 2.3.

The binary variables $x_a$, defined for every $a\in 𝒜$, encode which arcs of the event-based are chosen and thus encode the plan for each vehicle, as well as the selected route options for each request. For every request $r\in ℛ$, the variable $p_r$ indicates if $r$ is accepted.

For the liDARPT, we introduce variables $y_j^r$ for every route option ${\varphi }_j^r\in \mathrm{\Phi }(r)$ to denote if this route option is chosen in our solution. This information spans over multiple lines across our underlying network and thus across multiple components of the event-based graph. If a route option is chosen, then all corresponding splits must be part of our solution. At most one route option may be chosen per request, ensuring it is accepted at most once.

To represent the temporal information in our solution, we add a continuous variable $B_{{\rho }_{s,r}^{i,\pm }}$ for every action ${\rho }_{s,r}^{i,\pm }\in 𝒫$ to denote the end of this action. As in the LAEB formulation, a single $B_{{\rho }_{s,r}^{i,\pm }}$ variable is associated with all $v\in 𝒱$ with $v_1={\rho }_{s,r}^{i,\pm }$.

For an event $v\in 𝒱$, we denote its incoming arcs by ${\delta }^{\text{in}}(v)$ and its outgoing arcs by ${\delta }^{\text{out}}(v)$. The set $𝒫{(r)}^{+}$ (resp. $𝒫{(r)}^{-}$) contains all outbound (resp. inbound) actions of $r$, and the set $𝒫{(r)}_j^{+}$ contains all outbound actions belonging to the route option ${\varphi }_j^r$ of $r$.

We denote by $\sigma (k)$ the assigned line of a vehicle $k\in 𝒦$ and by ${\sigma }^{-1}(i)$ the set of vehicles assigned to line $i\in ℐ$. The earliest departure time (resp. latest arrival time) of a vehicle from the depot of its line $\sigma (k)=i$ is denoted by $e(s_i^{\text{depot}})=e({\text{0}}_i)$ (resp. $l(s_i^{\text{depot}})=l({\text{0}}_i)$).

The objective function (1a) maximizes the number of accepted requests, adding a large penalty $W$ in case request $r$ is not accepted. As a a secondary goal, the total distance driven by the vehicles (referred to as traveled distance) is minimized. Constraints (1b) are the typical flow constraints. Next, constraints (1c) guarantee that, for an accepted request $r$ and selected route option ${\varphi }_j^r$, all of the corresponding splits of ${\varphi }_j^r$ are part of the solution. There may be at most one plan per vehicle for every line $i$, enforced by constraints (1d). Constraints (1e) to (1k) handle time constraints. For subsequent events, constraints (1e) and constraints (1f) ensure the end time of the respective actions is consecutive, where constraints (1e) ensure the necessary travel and service time are respected if the events do not occur at the same station. We choose the parameter $M_1$ large enough to ensure these constraints are only active if the corresponding succession of actions is part of the solution. Then, constraints (1g) guarantee the correctness of the departure times for the very first action on the paths and similarly, constraints (1h) guarantee the correctness of the arrival times for the last action on the paths. Together, constraints (1g) and constraints (1h) ensure each vehicle travels within a pre-specified travel time span. The time windows of each action are ensured by constraints (1i). Furthermore, we make sure the the maximum travel time is upheld with constraints (1j), by checking the difference of the last split’s drop-off time and the pick-up time of the first split for a request. For the timing of all subsequent splits of the same request, constraints (1k) enforce that no user is picked up before they even arrive at a station $s$. Again, we choose $M_2$ large enough to ensure this constraint is only active if the corresponding route option is chosen. Finally, in constraints (1l), we ensure that exactly one route option is selected if and only if the request is transported.

Note that a split may be part of multiple route options and that it is not forbidden by our MILP that a split may be part of a vehicle’s plan, even though none of the corresponding route options are chosen. Hence, after every model solve, we run a clean-up routine, removing unnecessary events from the solution. These events have no effect on the solution: they may not add to the traveled distance nor may they occupy a seat which could otherwise have been assigned to a rejected request, as both would increase our objective function.

We now prove a bound on the objective function penalty $W$ to enforce our lexicographic objective function (1a).

We create a new set of benchmark instances modeled after the long-distance bus network in the region of Unterfranken, Germany. Table 1 provides an overview of the seven networks, where the total transfer degree denotes the sum of degrees of all transfer stations as a further measure of complexity. A visualization of the networks is provided in Figure 12 in the Appendix. Networks with the same base name build upon each other; for example, sw-schlee_3 consists of the sw-schlee_2 network with an additional line.

For each network, we create multiple instances with $10$ to $100$ requests distributed over a time span of three, six, or nine hours, where each request $r$ is assigned a pick-up and drop-off station under a uniform random distribution across $𝒮$. We split the time span into 5-minute intervals and, for each $r$, draw an earliest pick-up time $e(r^{+})$ uniformly at random from the resulting set of intervals. The remaining time bounds, i.e., $l(r^{+}),e(r^{-}),$ and $l(r^{-})$, are then computed from the maximum wait time of 15 minutes, and the shortest direct and maximum travel times of $r$. Finally, the number of passengers in a request is chosen by assigning a 90% probability for picking a single passenger, 9% for two, and 1% for three passengers.

Figure 3 visualizes the computation times per instance. As expected, this increases with the number of requests, with timeout first being reached at 40, 50, and 70 requests for time spans of three, six, nine hours, respectively. The computation time seems to correlate stronger with the number of requests than the number of lines of the network. Further, the temporal density, defined as the number of requests per hour, has a significant impact: the computation time reaches timeout for a temporal density greater than 13 (for three hours) and 7.77 (for six and nine hours). This may also be explained by the size of the underlying event-based graph, where a higher temporal density correlates to a larger graph, see Figure 5.

Here, the markt-karl-lohr instance with 30 requests in six hours reached a MIP gap of $0.05\%$ within 16 seconds, indicating a near-optimal solution was found early in the optimization process.

Next, Figure 4 shows the relative MIP gap⁴⁴4the relative gap between the current objective value and the best known bound, in percent., for all instances. The MIP gap tends to rise with the number of requests for a given time span, and is lower for larger time spans overall. Interestingly, the MIP gap of instances on the supposedly harder networks with more lines, sw-schlee_full and sw-geo_full, is often smaller than on the other networks, rising only for instances with large numbers of requests, e.g., sw-schlee_full at 100 request in six hours.

We postulate that this correlates to the number of available vehicles per line: since each line is assigned two vehicles, networks with less lines have a lower seat-to-request ratio, which increases the complexity when aiming to transport all passengers.

Figure 5 examines the size of the event-based graph versus the temporal density. For instances of the same temporal density, networks with less lines, such as the sw-geo_2 and sw-schlee_2, produce smaller graphs (with both less nodes and less arcs) than networks with more lines. Interestingly, one of the largest networks, sw-schlee_full is surpassed by sw-schlee_3 (a subgraph with two less lines) multiple times. This suggests that the length of the lines, as well as the number and location of transfer stations, may have an additional impact on the size of the event-based graph.

Finally, Figure 7 shows the number of variables and constraints in the MILP. Both rise with the temporal density and the number of lines in the network: the smallest networks, sw-geo_2 and sw-schlee_2, require both the smallest number of variables and constraints. Larger networks enable more transfers, which in turn also allows for more route options per request, requiring more variables and constraints in our MILP.

Both the absolute number of requests and the number of requests per hour have an impact on the number of admissible events in the event-based graph. Indeed, Figure 6 demonstrates that the computation time for the MILP increases with the size of the underlying event-based graph. This underlines the value of effective pre-processing approaches. Furthermore, we observe that, in our experiments, the ratio of number of arcs to number of nodes is quasi constant across instances and networks, suggesting that our pre-processing effectively prunes a large fraction of infeasible events and arcs.

As a large MIP gap indicates a far-from-optimal solution, we restrict our analysis to instances with $\le 60$ requests in three hours and $\le 90$ requests in six hours for this section.

Figure 8 shows that all instances accepted over 78% of requests, with those spanning nine hours accepting over 88%. Note that it may not be feasible to accept all requests in our instances with the given number of vehicles (e.g., the optimal solution on sw-schlee_2 with 30 requests in three hours denies a single request). Instances which were solved to optimality accepted the maximum amount of passengers due to our choice of penalty $W$ (see Lemma 1) and instances with the lowest acceptance rates correspond to those with the highest MIP gaps, compare Figure 4. Among all instances solved to optimality, 99.69% of requests were accepted on average.

As a measure of routing quality, [19] propose the metric system efficiency, computed as the fraction of total booked kilometers (as a straight-line path between origin and destination) to total driven distance by all vehicles. A value greater than 1 corresponds to our system saving distance compared to each passenger traveling in their own vehicle.

As can be seen in Figure 9, the system efficiency increases with the number of requests of the instances and temporal density, with more dense instances achieving a higher system efficiency, but only one instances surpasses a value of 1. The differences across networks, where networks with more routing freedom (e.g., the sw-geo_full) achieve higher efficiencies, suggests that the liDARPT can better utilize the network here.

The system efficiency metric may be overly harsh in evaluating liDARPT outcomes, as road network distances would, in most cases, significantly exceed the straight line distances used here for comparison. For this reason, we complement the system efficiency metric with the network system efficiency, which is defined as the ratio of ${\sum }_{r\in R}{t}_{r^{\ast }}$, the sum of the shortest network travel time of all requests, to the total distance traveled of all vehicles. Figure 10 shows that the network system efficiency surpasses the threshold of $1$ multiple times, with the lowest efficiency slightly below $0.4$ and overall densely clustered results. The results show a clear trend of increasing network system efficiency with larger temporal density, where notably several instances surpass the threshold of 1, indicating that the solver is able to identify more efficient paths than those in a fixed bus network.

Lastly, Figure 11 considers the vehicle utilization⁵⁵5ratio of total passenger kilometers to the total vehicle distance traveled., which increases with the number of requests, surpassing the threshold of $1$ in all three time spans for higher request numbers, and reaches values up to 1.32 for larger instances. This suggests that the liDARPT is able to effectively pool passengers for medium and high densities.

In general, smaller instances achieve a lower utilization due to limited flexibility, resulting in longer trips to reposition the vehicles between requests. Differences in network structures may additionally play a role: the sw-schlee_3 network contains two relatively long lines without a transfer point at their end, resulting in many empty driven kilometers, e.g., after a request has been transported to the end of a line and the vehicle needs to return empty, and thus an overall lower utilization when compared to similarly sized networks. However, we cannot observe a general trend related to the networks: the vehicle utilization seems to correlate strongly with the number of requests but not with the number of lines or transfer points in the network.