betaFeedback

WorksMathematics

Ride-time inequalities for the event-based formulation of the dial-a-ride problem

Abstract

The paper investigates the model structure of the event-based mixed-integer programming formulation of the Dial-a-Ride Problem. We find that the design of events allows introducing new valid inequalities on the ride times. Time progression is modelled using Big M constraints which lead to a weak LP relaxation and deteriorate the solution process. The newly introduced valid inequalities deal with this issue and allow reducing the computation times by up to 99% for benchmark instances (a-X* instances) in comparison to the state-of-the-art event-based model formulation. To evaluate the potential of the new valid inequalities, we increase the time windows on the benchmark set by another 15 minutes and evaluate the model on the same instances with a time-related objective function where the Big-M-influenced time variables directly occur in the objective function. Even for the large time windows only two instances could not be solved to optimality within two hours (final gaps of at most 0.8%). With the time-oriented objective the largest average computation time with our valid inequalities was 74 seconds.

Introduction

The Dial-a-Ride Problem (DARP) searches for optimal tours transporting passengers from their pickup to their delivery location while respecting vehicle capacities, time windows, and maximum ride time constraints. The traditional application is the transportation of elderly or disabled persons, but nowadays it has also applications in ridepooling services for the general public ([11]). The DARP was introduced by Psaraftis [13].

With respect to exact optimisation procedures Psaraftis [13] presented a dynamic program for the case with one vehicle. Later, the focus shifted to mixed-integer programming formulations starting with Cordeau [4] who presented a 3-index formulation. The model was advanced to a 2-index formulation by Ropke et al. [16] for homogeneous vehicles. Both model formulations use binary variables picturing whether a vehicle moves directly between two locations ii and jj. Gaul et al. [7] call these models location-based formulations.

More recently, Rist and Forbes [15] developed a new type of model formulation based on so-called fragments. A fragment is a part of the tour where the vehicle is empty at the beginning and at the end. A vehicle’s tour is then composed of fragments.

Only shortly after, Gaul et al. [6] presented a further model formulation based on events. An event pictures the vehicles’ current occupancy as a QQ-tuple with the vehicle capacity QQ. The detailed construction is presented in § 3. Later on, Gaul et al. [7] improved their model and added new valid inequalities using the structure of the event-based graph to improve the search within a branch-and-cut procedure.

Since then, event-based models have been applied to other problem settings in routing and beyond. Stallhofer and Parragh [19] and Zhao et al. [20] presented event-based models for the electric autonomous DARP. Further, it was used by Anzenhofer et al. [1] to evaluate the potential of governmental regulations on shared mobility-on-demand systems and by Zhao et al. [21] for the DARP with synchronized visits. Moreover, the event-based DARP model formulation was applied to the line-based DARP with Barth et al. [2] and without transfers [14, 10].

He et al. [9] suggest to apply the event-based structure for electric vehicle fleet management for ride-hailing; Ferreira et al. [5] do the same for the Prisoner Transportation Problem. Chi et al. [3] developed an event-based model for an inland multi-size container transportation problem.

These applications do not only show the potential of event-based DARP model formulations, but also highlight the need for further improvements. While the approach is naturally limited to small vehicle sizes, which however are typical in practice, the computational study by Gaul et al. [7] also showed that increasing time windows are a drawback. This is true for two reasons: First, larger time windows lead to an increased event graph. Second, larger time windows lead to larger Big MMs in the constraints modelling the time progression while Big MM terms deteriorate the solution process [18].

The paper at hand presents new valid inequalities to address the second issue. Therefore, we introduce the DARP formally in § 2. Afterwards, the event graph is introduced in § 3. Next, the event-based model formulation is presented in § 4 including the newly introduced ride-time inequalities (§ 4.3 and § 4.4). The resulting model formulation is evaluated on benchmark instances in a comprehensive computational study in § 5. The paper closes with a conclusion in § 6.

Problem formulation

We consider the Dial-a-Ride Problem of Cordeau [4] in the notation of Gaul et al. [7]. A set of requests R={1,…,n}R = \{1,\ldots,n\} is served by at most KK identical vehicles of capacity QQ that start and end their tours at a common depot 0. Request ii asks for the transport of qiq_i passengers from its pickup location i+=ii^{+} = i to its delivery location i−=n+ii^{-} = n+i. We write P={1,…,n}P = \{1,\ldots,n\} for the pickup locations, D={n+1,…,2n}D = \{n+1,\ldots,2n\} for the delivery locations, J=P∪DJ = P \cup D and Jˉ=J∪{0}\bar{J} = J \cup\{0\}. Every location j∈J‾j \in\overline{J} has a service time sjs_j and a time window [ej,ℓj][e_j,\ell_j] for the start of the service; the depot has s0=0s_0 = 0 and [e0,ℓ0]=[0,T][e_0,\ell_0] = [0,T], where TT is the planning horizon. Driving from location ii to location jj takes the time tijt_{ij} and costs cijc_{ij}. A vehicle may wait at a location before it starts the service. The ride time of request ii is the time between the end of the service at i+i^{+} and the start of the service at i−i^{-}; it is limited by LL. In the benchmark instances, only one side of a request carries a given time window. Following Cordeau [4], the window of the other side is derived from it: for an outbound request with a given delivery window we set ei+=max⁡{0,ei−−L−si+}e_{i^{+}} = \max\{0,e_{i^{-}} - L - s_{i^{+}}\} and ℓi+=ℓi−−ti+i−−si+\ell_{i^{+}} = \ell_{i^{-}} - t_{i^{+}i^{-}} - s_{i^{+}}, and for an inbound request with a given pickup window we set ei−=ei++si++ti+i−e_{i^{-}} = e_{i^{+}} + s_{i^{+}} + t_{i^{+}i^{-}} and ℓi−=ℓi++si++L\ell_{i^{-}} = \ell_{i^{+}} + s_{i^{+}} + L. Thus, ei−e_{i^{-}} is the earliest possible start of the delivery of request ii in every instance.

Event graph

The event-based model formulation of Gaul et al. [6] describes the state of a vehicle after the service at a location by an event. An event is a tuple v=(v1,…,vQ)∈Vv = (v_1,\ldots,v_Q) \in V, where v1∈Jv_1 \in J is the location that has just been served and v2>⋯>vQv_2 > \cdots> v_Q are the requests on board besides the request of v1v_1, padded with zeros. The request of v1v_1 is on board after vv if and only if v1v_1 is a pickup location. The set of events VV consists of the depot event v0=(0,…,0)v_0 = (0,\ldots,0) and of every tuple whose load respects the capacity QQ and whose requests are pairwise compatible, that is, every two requests on board admit a sequence of their four locations in the required order that respects the time windows, the ride-time limit and the horizon. For a location j∈Jj \in J let VjV_j be the events with v1=jv_1 = j, so that Vi+V_{i^{+}} and Vi−V_{i^{-}} are the events in which request ii is picked up and delivered.

The arc set AA connects the depot event with every event (i+,0,…,0)(i^{+},0,\ldots,0) and every event (i−,0,…,0)(i^{-},0,\ldots,0) with the depot event. It connects an event vv with an event ww if w1w_1 is the pickup location of a request that is not on board after vv and for which a seat is free, or the delivery location of a request that is on board after vv, and if the requests on board after ww are those on board after vv with that request added or removed. Only arcs whose requests are pairwise compatible in the resulting order are kept, as described in Gaul et al. [7] Section 2.2. An arc a=(v,w)a = (v,w) has the cost ca=cv1w1c_a = c_{v_1w_1} and the travel time ta=tv1w1t_a = t_{v_1w_1}, and δin(v)\delta^{\mathrm{in}}(v) and δout(v)\delta^{\mathrm{out}}(v) denote the arcs entering and leaving vv, respectively. By construction, every path from the depot event back to the depot event is a vehicle tour that respects the capacity and visits the pickup event of each request before its delivery event. The time windows, the ride-time limit and the horizon are not part of the graph and are enforced by the formulation below.

Preprocessing. Gaul et al. [7] Section 4.1 compute for every event vv a lower bound BvLBB_v^{\mathrm{LB}} and an upper bound BvUBB_v^{\mathrm{UB}} on the start of the service at v1v_1 in event vv. The lower bound propagates the earliest start of the service along the predecessors of vv, and the upper bound propagates the latest start along the successors, including the ride-time limit of the requests on board. We compute the bounds exactly as in their recursions, as a fixed point over the whole graph. An event with BvUB<BvLBB_v^{\mathrm{UB}} < B_v^{\mathrm{LB}} and an arc (v,w)(v,w) with BvLB+sv1+t(v,w)>BwUBB_v^{\mathrm{LB}} + s_{v_1} + t_{(v,w)} > B_w^{\mathrm{UB}} cannot be part of a feasible solution and are removed from the graph. We refer to this graph preprocessing as GP.

Event-based model formulation

Location-augmented event-based model formulation

The location-augmented event-based model formulation (LAEB) of Gaul et al. [7] uses a binary variable xax_a for every arc a∈Aa \in A and one continuous variable Bˉj≥0\bar{B}_j \ge0 for every location j∈Jˉj \in\bar{J}, the start of the service at jj. The variable Bˉ0\bar{B}_0 bounds the return times of all vehicles. For two locations i,j∈Ji,j \in J let Aij={(v,w)∈A:v1=i,w1=j}A_{ij} = \{(v,w) \in A : v_1 = i, w_1 = j\} be the arcs from ii to jj, and let Mij=ℓi+si+tij−ejM_{ij} = \ell_i + s_i + t_{ij} - e_j. The formulation reads

min⁡∑a∈Acaxa(1)\min\sum_{a \in A} c_a x_a \tag*{(1)}
s.t.∑a∈δin(v)xa−∑a∈δout(v)xa=0∀v∈V,(2)\text{s.t.}\quad\sum_{a \in\delta^{\mathrm{in}}(v)} x_a - \sum_{a \in\delta^{\mathrm{out}}(v)} x_a = 0 \qquad\forall v \in V, \tag*{(2)}
∑v∈Vi+∑a∈δin(v)xa=1∀i∈R,(3)\sum_{v \in V_i^+} \sum_{a \in\delta^{\mathrm{in}}(v)} x_a = 1 \qquad\forall i \in R, \tag*{(3)}
∑a∈δout(v0)xa≤K,(4)\sum_{a \in\delta^{\mathrm{out}}(v_0)} x_a \le K, \tag*{(4)}
Bˉj≥Bˉi+si+tij−Mij(1−∑a∈Aijxa)∀i,j∈J, Aij≠∅,(5)\bar{B}_j \ge\bar{B}_i + s_i + t_{ij} - M_{ij}\left(1-\sum_{a \in A_{ij}}x_a\right) \qquad\forall i,j \in J,\ A_{ij} \ne\varnothing, \tag*{(5)}
Bˉj≥e0+t0jx(v0,(j,0,…,0))∀j∈P,(6)\bar{B}_j \ge e_0 + t_{0j}x_{(v_0,(j,0,\ldots,0))} \qquad\forall j \in P, \tag*{(6)}
Bˉ0≥Bˉi+si+ti0−Mi0(1−x((i,0,…,0),v0))∀i∈D,(7)\bar{B}_0 \ge\bar{B}_i + s_i + t_{i0} - M_{i0}\left(1-x_{((i,0,\ldots,0),v_0)}\right) \qquad\forall i \in D, \tag*{(7)}
ej≤Bˉj≤ℓj∀j∈Jˉ,(8)e_j \le\bar{B}_j \le\ell_j \qquad\forall j \in\bar{J}, \tag*{(8)}
Bˉi−−Bˉi+−si+≤L∀i∈R,(9)\bar{B}_{i^-} - \bar{B}_{i^+} - s_{i^+} \le L \qquad\forall i \in R, \tag*{(9)}
xa∈{0,1}∀a∈A.(10)x_a \in\{0,1\} \qquad\forall a \in A. \tag*{(10)}

The objective (1) minimises the routing cost. Constraints (2) are the flow conservation constraints at every event, Constraints (3) pick up every request exactly once, and Constraint (4) limits the number of tours. Constraints (5) link the service start times of two locations whenever a vehicle drives from one to the other, with the usual Big MM relaxation otherwise; Constraints (6) and (7) do the same for the first and the last location of a tour. Constraints (8) are the time windows and Constraints (9) the ride-time limit. With the preprocessing bounds, Gaul et al. [7] replace the time windows (8) for j∈Jj \in J by the tighter bounds

∑v∈VjBvLB∑a∈δin(v)xa≤Bˉj≤∑v∈VjBvUB∑a∈δin(v)xa∀j∈J,(11)\sum_{v \in V_j} B_v^{\mathrm{LB}}\sum_{a \in\delta^{\mathrm{in}}(v)}x_a \le\bar{B}_j \le\sum_{v \in V_j}B_v^{\mathrm{UB}}\sum_{a \in\delta^{\mathrm{in}}(v)}x_a \qquad\forall j \in J, \tag*{(11)}

which select the bounds of the event through which location jj is visited; we keep (8) in addition.

Valid inequalities from literature

Gaul et al. [7] Section 4.2 propose three families of valid inequalities for the event-based models: the infeasible-path inequalities, which exclude pairs of consecutive arcs and short paths that no feasible schedule can use given the preprocessing bounds; the vehicle-sharing inequalities, which state that two requests either share a vehicle or are served one after the other; and the customer-incompatibility inequalities for pairs of requests that cannot share a vehicle. We use all families with the dominance rules of their implementation, in the combination of their final benchmark, and refer to the formulation with GP and all families as the base configuration. The branch-and-cut node methods of their Sections 4.3–4.5 are not used, as in their final benchmark.

Ride-time inequalities

The time propagation constraints (5) are the main link between the arc variables and the time variables, and their Big MM relaxation becomes weak when Bˉi<ℓi\bar{B}_i < \ell_i or Bˉj>ej\bar{B}_j > e_j. Then, the constraint is satisfied by a positive ∑a∈Aijxa\sum_{a\in A_{ij}} x_a although Bˉj<Bˉi+si+tij\bar{B}_j < \bar{B}_i + s_i + t_{ij}, i.e. the arcs from ii to jj can carry flow in the LP relaxation without the time variables reflecting it. The reason is the Big MM and its choice, which is, however, necessary to ensure feasibility in the extreme case with Bˉi=ℓi\bar{B}_i = \ell_i and Bˉj=ej\bar{B}_j = e_j.

In this section, we use the structure of the event graph to overcome the drawback of the Big MM formulation. The approach follows the idea of fixed paths from Schulz and Pfeiffer [17]. Here we do not need a completely fixed path, but we know a fixed sequence of events if they are used.

Due to construction of the event graph, we know that location i−i^{-} is visited after location i+i^{+} in the same tour. Thus, we do not need a Big MM for this relation, as Bˉi−>Bˉi+\bar{B}_{i^{-}} > \bar{B}_{i^{+}} certainly holds. Moreover, we know that all events with request ii on positions 2,…,Q2,\ldots,Q in the event must either be visited between location i+i^{+} and location i−i^{-} or are not used in the solution.

Thus, we get a path

(i+,…)→(b1,…,i,…)→(b2,…,i,…)→⋯→(bk,…,i,…)→(i−,…)(12)(i^{+},\ldots) \to(b_1,\ldots,i,\ldots) \to(b_2,\ldots,i,\ldots) \to\cdots\to(b_k,\ldots,i,\ldots) \to(i^{-},\ldots) \tag*{(12)}

between the pickup and delivery location of request ii. If this path is chosen, it follows

Bˉi−≥(Bˉi++si+)+(ti+b1+sb1)+(tb1b2+sb2)+⋯+tbki−=Bˉi++∑l=0k(sbl+tblbl+1)(13)\bar{B}_{i^{-}} \ge(\bar{B}_{i^{+}} + s_{i^{+}}) + (t_{i^{+}b_1} + s_{b_1}) + (t_{b_1b_2} + s_{b_2}) + \cdots+ t_{b_k i^{-}} = \bar{B}_{i^{+}} + \sum_{l=0}^{k}(s_{b_l} + t_{b_l b_{l+1}}) \tag*{(13)}

with b0=i+b_0 = i^{+} and bk+1=i−b_{k+1} = i^{-}. This path is chosen if the corresponding arc variables are 1.

Generally, we formulate inequalities linking the ride time of a request directly to the arcs on which it is on board, without a Big MM term as follows. For a request i∈Ri \in R let

Ai={(v,w)∈A:v1=i+ or i∈{v2,…,vQ}}A_i = \{(v,w) \in A : v_1 = i^{+} \text{ or } i \in\{v_2,\ldots,v_Q\}\}

be the arcs on which request ii is on board, that is, the arcs leaving an event after which ii sits in the vehicle. In every solution, the arcs of AiA_i with xa=1x_a = 1 form exactly the path from the pickup event of ii to the delivery event of ii. Summing Constraints (5) along this path gives

Bˉi−−Bˉi+≥∑a=(v,w)∈Ai(sv1+ta)xa∀i∈R.(14)\bar{B}_{i^-} - \bar{B}_{i^+} \ge\sum_{a=(v,w)\in A_i} (s_{v_1}+t_a)x_a \qquad\forall i\in R. \tag*{(14)}

Proposition 1. Inequalities (14) are valid for model (2)–(10).

Proof. In an integer feasible solution, the graph construction ensures with Constraints (2), (3) and (5) (no cycles) that a single path of the structure of (12) exists. For it, (13) and by it (14) holds.

Proposition 2. Valid inequalities (14) ensure for model (2)–(10) that ride time feasibility holds in the weighted flow average in the LP solution.

Proof. Due to the graph construction and flow conservation constraints (2) every flow leaving a pickup event of request ii (i.e. with v1=i+v_1=i^+) transfers to a delivery event of request ii (i.e. with w1=i−w_1=i^-). Moreover, a total flow of 1 has to leave the pickup events of every request ii due to (3). In a fractional solution, the entire flow of size 1 can be decomposed into several flows with a size between 0 and 1. For each of these fractional flows between pickup and delivery location of a request ii a path (12) exists such that (14) sums up the service and travel times on the right side, i.e. aggregates the fractional flows including possible cycles, which have nonnegative length, within these paths.

Together with the ride-time limit (9), valid inequalities (14) imply

∑a∈Ai(sv1+ta)xa≤L+si+,\sum_{a\in A_i}(s_{v_1}+t_a)x_a \le L+s_{i^+},

a constraint on the arc variables alone that cuts off fractional solutions in which the arcs carrying request ii are in the weighted flow average longer than the ride-time limit allows.

Note that without valid inequalities (14) ride time feasibility in the sense of Proposition 2 is not guaranteed in the LP relaxation due to the Big-MM-type Constraints (5).

In the pure event-based formulation of Gaul et al. [6], where the time variables BvB_v are attached to events v∈Vv\in V, the inequality has a direct counterpart, when BB variables of not used events are set to 0

0≤Bv≤BvUB∑a∈δin(v)xa∀v∈V.0\le B_v\le B_v^{UB}\sum_{a\in\delta^{in}(v)}x_a \qquad\forall v\in V.

Then, Bˉi−−Bˉi+\bar{B}_{i^-}-\bar{B}_{i^+} can be replaced in (14) by

∑v∈Vi−Bv−∑v∈Vi+Bv.\sum_{v\in V_{i^-}}B_v-\sum_{v\in V_{i^+}}B_v.

However, this type of constraint cannot be transferred to further relations between pickup and delivery locations, as we do not know whether different requests are served by the same vehicle.

Strengthened ride-time inequalities

Valid inequalities (14) can be strengthened by replacing sv1+tas_{v_1}+t_a by

τa=max⁡{sv1+ta,BwLB−BvUB}.\tau_a=\max\{s_{v_1}+t_a, B_w^{LB}-B_v^{UB}\}.

This leads to inequalities

Bˉi−−Bˉi+≥∑a=(v,w)∈Aiτa⋅xa∀i∈R.(15)\bar{B}_{i^-}-\bar{B}_{i^+}\ge\sum_{a=(v,w)\in A_i}\tau_a\cdot x_a \qquad\forall i\in R. \tag*{(15)}

Proposition 3. Inequalities (15) are valid for model (2)–(10).

Proof. As Proposition 1 shows that (14) is valid, it remains to show that replacing sv1+tas_{v_1}+t_a by BwLB−BvUBB_w^{LB}-B_v^{UB} does not violate feasibility. Thus, we assume that

BwLB−BvUB>sv1+ta.B_w^{LB}-B_v^{UB}>s_{v_1}+t_a.

If the vehicle starts service at location v1v_1 at the latest possible time BvUBB_v^{UB} and drives directly to location w1w_1, the vehicle still arrives before the tightened time window beginning BwLBB_w^{LB}. If service at vv starts before BvUBB_v^{UB}, waiting time at ww further increases. Hence, service cannot start by arrival but after a waiting time of at least

BwLB−BvUB−sv1−taB_w^{LB}-B_v^{UB}-s_{v_1}-t_a

which is exactly the amount by which τa\tau_a exceeds sv1+tas_{v_1}+t_a on the right-hand side of the inequality in comparison to (14). Thus, (15) is valid.

The proof shows that (15) strengthens (14) by necessary waiting time. Proposition 4 holds analogously to Proposition 2.

Proposition 4. Valid inequalities (15) ensure for model (2)–(10) that ride time feasibility holds in the weighted flow average in the LP solution.

Proof. Analogous to Proposition 2.

Note that valid inequalities (15) dominate valid inequalities (14) since τa≥sv1+ta\tau_a\ge s_{v_1}+t_a.

Objectives

Besides the routing cost (1), we study a customer-oriented objective in which the time variables appear directly in the objective, so that the time constraints have to be tight in every solution. We use the relative detour of Pfeiffer and Schulz [11], the delay of every passenger against the earliest possible delivery, measured in units of the direct ride time:

min⁡∑i∈RqiBˉi−−ei−ti+i−.(16)\min\sum_{i\in R}q_i\frac{\bar{B}_{i^-}-e_{i^-}}{t_{i^+i^-}}. \tag*{(16)}

A request that is delivered at its earliest possible time contributes zero. Pfeiffer and Schulz [11] measure the detour against ei++ti+i−e_{i+}+t_{i+i-}, which equals ei−e_{i-} in their setting without service times. On the benchmark instances the two readings have the same optimal solutions and differ by the instance constant

∑i∈Rqiei−−ei+−ti+i−ti+i−\sum_{i\in R} q_i \frac{e_{i-}-e_{i+}-t_{i+i-}}{t_{i+i-}}

which is the service time at the pickup for inbound requests and the slack between the earliest pickup and the delivery window for outbound requests, each in units of the direct ride time. Objective (16) is used with LAEB, where the delivery times are location variables; all constraints remain as in § 4.1. Results with this objective function are presented in Appendix § 7.

Computational study

Setting. All models are implemented in Python 3.12 with Gurobi 13.0.2 and solved on the Hummel-2 cluster of the University of Hamburg on nodes with two AMD EPYC 9654 processors (96 cores each, 2.4 GHz) and 768 GB of RAM, with one thread per solve, a relative optimality gap of zero and a time limit of 7200 seconds, as in Gaul et al. [7]. The CPU times in the tables are the pure Gurobi times. Building the event graph with the preprocessing and the model takes 0.4 to 3.6 seconds per instance on average, depending on the set, and at most 23 seconds (a8-96-X⋆⋆), and is the same for the three configurations up to the ride-time inequalities. Every reported solution is verified independently of the solver: the tours are rebuilt from the arc variables, and the routing cost, the time windows, the ride times, the capacity, the precedence of pick-up and delivery, the horizon and the fleet size are rechecked from the instance data. The optimal values of all instances solved by both studies coincide with those of Gaul et al. [7].

Configurations. We compare, for LAEB, the plain model (1)–(10), the model with graph preprocessing and the bounds (11) (GP), and the “base” configuration with GP and all valid inequalities of § 4.2, each without ride-time inequalities, with the ride-time inequalities (14) and with the strengthened ride-time inequalities (15). In the detailed tables, we compare base, base + (14) and base + (15).

The base configuration and the two configurations with ride-time inequalities are run with three Gurobi seeds and reported as means. The Gurobi seed steers decisions (e.g. primal heuristics, tie breaking, cut selection) within the Gurobi Branch-and-Cut procedure which have an influence on the results with roughly a factor of 3. For example, the three runs for instance a7-84-X⋆⋆ with base + (14) required 6268/2944/6935 s and those for b8-96-X⋆⋆ with base 898/261/213 s. A single run would not be able to isolate the effect of the inequalities from this. We, therefore, report mean results over three independent runs in the tables.

Results for plain and GP are reported for the sake of completeness shortly in the text. The benefit of ride time inequalities is so strong here that we restricted ourselves to a single Gurobi seed/run.

Test instances

We use the four instance sets of the computational study of Gaul et al. [7]. The sets a and b are the benchmark instances introduced by Cordeau [4] and Ropke et al. [16]; each set contains 24 instances with K∈{2,…,8}K \in\{2,\ldots,8\} vehicles and n∈{16,…,96}n \in\{16,\ldots,96\} requests, named aKK-nn and bKK-nn. In set a, every request has one passenger, every service takes 3 minutes, the capacity is Q=3Q = 3 and the ride-time limit is L=30L = 30 minutes. In set b, a request has qi∈{1,…,6}q_i \in\{1,\ldots,6\} passengers, the service time equals the number of passengers, Q=6Q = 6 and L=45L = 45 minutes. Half of the requests are outbound with a given delivery window and half are inbound with a given pickup window; every given window is 15 minutes long, and the other side is derived as described in § 2. The planning horizon is T=60n/KT = 60n/K minutes, that is, between 4 and 12 hours. Locations are points in the plane; travel times and routing costs are the Euclidean distances rounded to two decimals.

The sets a-X⋆^\star and b-X⋆^\star are variants where the given time window of every request, that is, the delivery window of an outbound and the pickup window of an inbound request, is extended by 15 minutes at its end, so that it is 30 minutes long. The window of the other side is derived from it and is thereby extended by the same amount. All other data, including the capacity and the ride-time limit, are unchanged (adapted from Gschwind and Irnich [8] as in Gaul et al. [7]). These sets are harder than the original ones, because wider windows admit more feasible combinations of requests per vehicle. Since every a-X⋆^\star and b-X⋆^\star instance is solved with the ride-time inequalities, we add the sets a-X⋆⋆^{\star\star} and b-X⋆⋆^{\star\star}, in which every given window is extended by 30 minutes instead of 15, so that it is 45 minutes long; all other data are unchanged, and no reference values exist for them.

Forced waiting

Inequalities (15) differ from (14) only on arcs a=(v,w)a = (v,w) with τa>sv1+ta\tau_a > s_{v_1} + t_a, on which a vehicle that starts the service at v1v_1 at the latest possible time BvUBB_v^{\mathrm{UB}} still arrives at w1w_1 before BwLBB_{w}^{\mathrm{LB}}. Table 1 counts these arcs among the arcs with a passenger on board, ⋃i∈RAi\bigcup_{i \in R} A_i, on the preprocessed graphs. Since the upper bounds of GP already propagate the time windows of the successors, forced waiting remains only where ℓv1\ell_{v_1} is tight and ew1e_{w_1} is late, and it is rare: 4.3 to 8.6 percent of the arcs with a passenger on board carry a positive waiting time, of 5.7 to 14.0 minutes on average and up to 67 minutes, and 53 to 83 percent of the requests have at least one such arc in AiA_i. With the location windows [ev1,ℓv1][e_{v_1},\ell_{v_1}] in place of the preprocessing bounds, as in the plain model, the shares are 0.4 to 1.8 percentage points lower. We therefore expect (15) to differ little from (14) in the computations although it is by definition stronger.

SetArcs on boardWith waitingShareMean (min)Max (min)Requests
a2819217746.3%5.724.7684/1108 (62%)
b2631822568.6%10.237.9584/1108 (53%)
a-X*9399142414.5%8.138.5806/1108 (73%)
b-X*6398941986.6%11.551.3613/1108 (55%)
a-X**21374990964.3%10.954.4923/1108 (83%)
b-X**12192763945.2%14.066.6653/1108 (59%)

Table 1. Arcs with forced waiting after the graph preprocessing, totals over the 24 instances of each set.

Routing cost

Tables 2–5 compare the base configuration with the base configuration plus the ride-time inequalities (14) and plus the strengthened inequalities (15) on the four instance sets from literature. For every instance they report the objective value and, for the three configurations, the gaps of the LP relaxation and of the root node, the number of branch-and-bound nodes and the CPU time as means over the three seeds, and the relative change of the CPU time against the base configuration; the notes below the tables define the columns.

Notes: Arcs on board: arcs (v,w)(v,w) with at least one request on board after vv, that is, ⋃i∈RAi\bigcup_{i\in R} A_i. With waiting: those with τa>sv1+ta\tau_a > s_{v_1} + t_a; Share: their percentage. Mean, Max: mean and largest τa−sv1−ta\tau_a - s_{v_1} - t_a over these arcs in minutes. Requests: requests whose inequality (15) differs from (14), over all requests of the set. Bounds BLBB^{LB}, BUBB^{UB} of the graph preprocessing on the preprocessed graph.

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔ\DeltaCPULPgaprGapNodesCPUΔ\DeltaCPU
basebase + (14)base + (15)
a2-16294.30.4%0.0%10.030.4%0.0%10.02–0.4%0.0%10.02–
a2-20344.92.1%0.0%10.041.3%0.0%10.07–1.3%0.0%10.02–
a2-24431.12.3%0.0%10.052.1%0.0%10.05–2.1%0.0%10.05–
a3-18300.50.8%0.0%10.030.8%0.0%10.04–0.8%0.0%10.03–
a3-24344.82.4%0.0%10.092.2%0.0%10.08–2.2%0.0%10.08–
a3-30494.81.8%0.0%10.041.4%0.0%10.05–1.4%0.0%10.04–
a3-36583.22.5%0.0%10.192.5%0.0%10.08–2.5%0.0%10.09–
a4-16282.70.7%0.0%10.120.6%0.0%10.07–0.6%0.0%10.05–
a4-24375.01.7%0.0%10.041.5%0.0%10.04–1.5%0.0%10.04–
a4-32485.51.9%0.0%10.151.6%0.0%10.08–1.6%0.0%10.08–
a4-40557.71.5%0.0%10.271.5%0.0%10.18–1.5%0.0%10.18–
a4-48668.83.6%0.0%10.292.8%0.0%10.28–2.6%0.0%10.38–
a5-40498.40.6%0.0%10.140.5%0.0%10.15–0.5%0.0%10.15–
a5-50686.64.0%0.3%321.653.6%0.0%10.50-70%3.5%0.0%10.44-73%
a5-60808.32.0%0.0%10.601.8%0.0%10.31-48%1.8%0.0%10.31-48%
a6-48604.11.5%0.0%10.331.5%0.0%10.30–1.4%0.0%10.30–
a6-60819.33.0%0.0%11.642.5%0.0%10.47-71%2.5%0.0%10.63-62%
a6-72916.13.0%0.9%4572.602.6%0.0%11.60-38%2.5%0.0%11.30-50%
a7-56724.01.7%0.1%51.861.4%0.0%10.63-66%1.4%0.0%10.63-66%
a7-70875.72.1%0.0%11.192.0%0.0%10.91-24%1.9%0.0%11.07-10%
a7-841033.32.6%0.1%272.072.5%0.0%11.51-27%2.5%0.0%11.20-42%
a8-64747.52.0%0.0%13.321.9%0.0%10.72-78%1.9%0.0%10.69-79%
a8-80945.83.6%0.6%2245.373.3%0.0%11.46-59%3.3%0.0%11.33-63%
a8-961229.73.7%1.0%111216.173.4%0.0%14.09-75%3.4%0.0%243.97-75%
Total2.1%0.1%187536.51.9%0.0%2413.7-62%1.9%0.0%4713.1-64%

Table 2. Base versus base + cuts on the a instances (routing costs (1)).

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%) = time limit of 7200 s reached in every seed, largest final gap. Δ\DeltaCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

The inequalities act where branching is needed. On the a instances the base configuration needs 36.5 seconds and 1875 nodes in total, the configuration with the inequalities (14) 13.7 seconds and 24 nodes, that is, every instance is solved at the root node; the CPU time falls on all ten instances that take more than half a second, by 56 percent on average. On the a-X* instances the base configuration needs 18 584 seconds and 148 283 nodes and does not solve a8-96-X* within the time limit in any of the three seeds (final gaps 1.5 to 1.7 percent), whereas the configuration with the inequalities (14) solves every instance, in 803 seconds and 5770 nodes in total; it is faster on all sixteen instances above half a second, by 72 percent on average and

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
basebase + (14)base + (15)
b2-16309.40.6%0.0%10.060.6%0.0%10.06–0.6%0.0%10.05–
b2-20332.70.0%0.0%10.020.0%0.0%10.02–0.0%0.0%10.01–
b2-24444.71.3%0.0%10.071.3%0.0%10.12–1.3%0.0%10.06–
b3-18301.60.9%0.0%10.070.9%0.0%10.05–0.9%0.0%10.05–
b3-24394.51.9%0.0%10.161.9%0.0%10.14–1.9%0.0%10.12–
b3-30531.40.1%0.0%10.040.1%0.0%10.05–0.1%0.0%10.05–
b3-36603.80.1%0.0%10.060.1%0.0%10.06–0.1%0.0%10.07–
b4-16296.90.6%0.0%10.020.6%0.0%10.05–0.6%0.0%10.02–
b4-24371.40.1%0.0%10.080.1%0.0%10.07–0.1%0.0%10.05–
b4-32494.90.0%0.0%10.040.0%0.0%10.06–0.0%0.0%10.04–
b4-40656.60.3%0.0%10.110.3%0.0%10.10–0.3%0.0%10.11–
b4-48673.80.7%0.0%10.930.7%0.0%10.70-25%0.7%0.0%10.49-47%
b5-40613.70.4%0.0%10.140.4%0.0%10.17–0.4%0.0%10.17–
b5-50761.41.0%0.0%10.331.0%0.0%10.29–1.0%0.0%10.35–
b5-60902.01.8%0.0%11.211.8%0.0%10.81-33%1.8%0.0%10.98-19%
b6-48714.80.4%0.0%10.200.3%0.0%10.19–0.3%0.0%10.18–
b6-60860.00.1%0.0%10.260.1%0.0%10.26–0.1%0.0%10.23–
b6-72978.50.9%0.1%723.090.9%0.0%12.94-5%0.9%0.0%12.47-20%
b7-56824.00.8%0.0%11.760.8%0.0%11.86+6%0.8%0.0%12.77+57%
b7-70912.61.8%0.0%10.811.8%0.0%10.86+6%1.7%0.0%10.96+19%
b7-841203.30.8%0.0%11.190.8%0.0%11.24+4%0.8%0.0%11.84+55%
b8-64839.91.6%0.0%11.001.6%0.0%10.69-31%1.5%0.0%10.67-33%
b8-801036.40.8%0.0%11.100.8%0.0%10.59-46%0.8%0.0%10.69-37%
b8-961185.61.2%0.0%12.711.2%0.0%12.45-10%1.1%0.0%12.52-7%
Total0.8%0.0%9515.50.7%0.0%2413.8-11%0.7%0.0%2414.9-4%

Table 3. Base versus base + cuts on the b instances (routing costs (1)). Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%) = time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
basebase + (14)base + (15)
a2-16278.20.1%0.0%10.030.1%0.0%10.08–0.1%0.0%10.02–
a2-20330.70.8%0.0%10.050.8%0.0%10.04–0.8%0.0%10.04–
a2-24389.12.2%0.0%10.182.0%0.0%10.15-10%2.0%0.0%10.14–
a3-18272.76.7%0.0%10.125.7%0.0%10.13–5.2%0.0%10.09–
a3-24289.63.3%1.3%1230.592.6%0.0%10.53-10%2.6%0.0%10.46-22%
a3-30452.85.3%0.0%10.384.3%0.0%10.11–4.3%0.0%10.12–
a3-36501.01.5%0.2%500.441.3%0.0%10.21–1.3%0.0%10.20–
a4-16235.25.8%0.0%10.395.6%0.0%10.21–5.6%0.0%10.20–
a4-24359.43.6%0.0%10.172.5%0.0%10.12–2.5%0.0%10.12–
a4-32447.33.7%1.6%2081.163.2%0.0%10.48-59%3.2%0.0%10.33-72%
a4-40509.02.4%0.4%1192.092.0%0.0%11.24-41%2.0%0.0%10.91-56%
a4-48620.37.8%3.8%205221.396.2%0.0%245.09-76%6.2%0.5%487.7-67%
a5-40464.03.0%0.7%1741.652.7%0.0%10.75-55%2.4%0.0%10.81-51%
a5-50621.95.2%2.6%171116.454.4%0.7%1096.23-84%4.4%0.0%13.00-82%
a5-60745.44.7%1.3%4314.064.2%0.0%12.48-39%4.0%0.0%12.70-33%
a6-48572.55.4%2.4%203473.694.8%0.3%487.20-90%4.6%0.5%1477.06-90%
a6-60757.93.9%0.9%189224.923.5%0.0%18.74-65%3.1%0.1%305.73-77%
a6-72868.46.2%3.5%337161756.705.1%1.6%73140.98-98%5.1%1.6%82045.02-97%
a7-56663.54.7%2.4%257490.394.1%1.1%38510.51-88%4.0%1.2%3169.11-90%
a7-70815.36.7%1.5%1075123.835.8%0.0%127.48-78%5.6%0.0%124.56-80%
a7-84950.67.6%3.3%269143844.556.1%0.7%96181.64-98%5.9%0.5%117884.05-98%
a8-64701.24.8%1.4%2507261.454.2%0.7%57248.51-81%4.1%0.5%56048.22-82%
a8-80880.37.3%3.6%503695159.085.7%0.6%59673.50-99%5.5%0.7%51673.38-99%
a8-961115.15.8%3.8%22327TL (1.7%)5.4%1.5%2329490.44-93%5.4%1.4%1765442.12-94%
Total4.5%1.4%14828318583.83.8%0.3%5770803.3-96%3.8%0.3%5395755.4-96%

Table 4. Base versus base + cuts on the a-X* instances (routing costs (1)). Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%) = time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

Inst.Obj.base LPgapbase rGapbase Nodesbase CPUbase + (14) LPgapbase + (14) rGapbase + (14) Nodesbase + (14) CPUbase + (14) ΔCPUbase + (15) LPgapbase + (15) rGapbase + (15) Nodesbase + (15) CPUbase + (15) ΔCPU
b2-16282.51.5%0.0%10.261.5%0.0%10.22–1.5%0.0%10.17–
b2-20323.60.8%0.0%10.070.8%0.0%10.04–0.8%0.0%10.04–
b2-24412.30.0%0.0%10.060.0%0.0%10.06–0.0%0.0%10.05–
b3-18290.41.5%0.0%10.071.5%0.0%10.09–1.5%0.0%10.07–
b3-24363.70.5%0.0%10.110.5%0.0%10.19–0.5%0.0%10.17–
b3-30504.31.8%0.0%10.381.8%0.0%10.28–1.8%0.0%10.22–
b3-36565.90.0%0.0%10.070.0%0.0%10.08–0.0%0.0%10.08–
b4-16289.91.0%0.0%10.031.0%0.0%10.04–1.0%0.0%10.02–
b4-24347.02.0%0.0%10.422.0%0.0%10.37–2.0%0.0%10.46–
b4-32491.00.7%0.0%10.170.7%0.0%10.13–0.7%0.0%10.10–
b4-40628.30.5%0.0%10.330.5%0.0%10.23–0.5%0.0%10.21–
b4-48627.40.9%0.0%11.230.9%0.0%10.98-20%0.9%0.0%11.25+2%
b5-40585.11.8%0.0%12.221.7%0.0%11.58-29%1.6%0.0%12.13-4%
b5-50708.80.6%0.0%10.490.6%0.0%10.92+88%0.6%0.0%10.77+57%
b5-60851.91.4%0.0%11.701.4%0.0%11.59-6%1.4%0.0%11.52-11%
b6-48691.60.9%0.0%10.380.9%0.0%10.41–0.9%0.0%10.44–
b6-60841.61.3%0.0%10.891.3%0.0%10.87-2%1.3%0.0%10.98+10%
b6-72930.31.6%0.0%14.861.6%0.0%16.30+30%1.5%0.0%13.62-26%
b7-56787.90.8%0.0%14.530.8%0.0%15.94+31%0.7%0.0%16.06+34%
b7-70865.31.8%0.0%11.661.8%0.1%342.93+77%1.7%0.1%194.06+145%
b7-841141.22.4%0.7%131519.702.3%0.3%18513.82-30%2.2%0.4%32014.19-28%
b8-64818.31.4%0.0%11.651.4%0.0%12.03+23%1.4%0.0%11.99+21%
b8-80998.31.7%0.0%12.741.7%0.0%12.06-25%1.7%0.0%12.11-23%
b8-961137.72.3%0.1%6942.942.2%0.0%134.44-20%2.2%0.0%135.36-18%
Total1.2%0.0%140687.01.2%0.0%24175.6-13%1.2%0.0%36176.1-13%

Table 5. Base versus base + cuts on the b-X⋆ instances (routing costs (1)).

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

by 96 percent in total. The LP relaxation gap improves only a little, from 4.5 to 3.8 percent on a-X⋆, because the time variables do not enter the objective; the effect shows in the root gap after Gurobi’s own cutting planes, which falls from 1.4 to 0.3 percent, and in the size of the search trees. The optimum of a8-96-X⋆, 1115.13, is proven in 391 to 564 seconds by the three seeds with the inequalities; it is also proven by GP with the inequalities in 242 seconds and by the plain model with the inequalities in 618 seconds. The b and b-X⋆ instances are solved at or near the root node by the base configuration already (95 and 1406 nodes in total), and the inequalities (14) change the totals by −11 and −13 percent with differences of a few tenths of a second per instance in both directions. The weaker configurations, run once each, show the same picture: on a-X⋆ the plain model needs 24 204 seconds with two unsolved instances and the plain model with the inequalities 902 seconds with none, GP needs 12 866 seconds with one unsolved instance and GP with the inequalities 464 seconds with none. Every run that reached the time limit belongs to a configuration without the inequalities.

The strengthened inequalities (15) behave like (14), as the small share of arcs with forced waiting suggests. Over the 144 instances with the routing costs, the LP gaps of the two configurations coincide to one decimal on 110 and are lower with (15) on 34, by at most 0.8 percentage points (a4-16-X⋆, 5.4 against 4.6 percent); the root gaps differ by a few tenths in both directions. The totals move within the variation between the seeds: on the a instances from 13.7 to 13.1 seconds, on a-X⋆ from 803 to 755 seconds and from 5770 to 5395 nodes, where (15) is faster on nine of the fifteen instances above half a second and proves the optimum of a8-96-X⋆ in 416 to 457 seconds, and on b and b-X⋆ from 13.8 to 14.9 and from 75.6 to 76.1 seconds. The weaker configurations with (15) solve every a-X⋆ instance as well, in 1018 (plain) and 497 seconds (GP) against 902 and 464 seconds with (14).

Wider time windows. Tables 6 and 7 repeat the comparison of the base configuration with and without the inequalities on the sets a-X⋆⋆ and b-X⋆⋆.

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
a2-16260.63.1%0.0%10.043.1%0.0%10.03–3.1%0.0%10.03–
a2-20317.75.8%0.0%10.425.4%0.0%10.12–5.4%0.0%10.10–
a2-24378.23.9%0.9%640.973.9%0.0%10.31-68%3.9%0.0%10.38-61%
a3-18258.06.9%3.2%4230.706.2%0.0%10.51-27%6.2%0.0%10.50-29%
a3-24282.23.0%1.8%1610.942.5%0.0%10.45-52%2.5%0.0%10.44-53%
a3-30437.25.4%3.2%9402.104.7%0.0%10.58-72%4.7%0.0%10.71-66%
a3-36473.01.6%0.0%10.531.3%0.0%10.43-19%1.3%0.0%10.39-26%
a4-16218.56.6%4.3%3060.965.4%0.0%10.73-24%4.6%0.0%10.70-27%
a4-24352.06.3%1.1%1050.816.0%0.0%10.50-38%6.0%0.0%10.54-33%
a4-32420.56.3%4.0%158413.985.6%0.3%274.13-70%5.6%0.6%1463.32-76%
a4-40492.15.4%2.0%4908189.854.6%1.5%97146.29-76%4.6%1.5%96750.08-74%
a4-48586.910.4%6.4%662292230.518.3%2.1%1105204.39-91%8.2%1.7%121397.30-96%
a5-40433.47.2%3.8%198744.166.0%0.3%363.70-92%5.9%0.4%384.41-90%
a5-50605.78.1%5.6%559222047.866.6%2.2%92475.77-96%6.6%2.3%118953.47-97%
a5-60696.89.4%5.2%238171205.647.3%1.6%136991.76-92%7.3%1.1%99156.25-95%
a6-48535.26.0%2.0%3036763.015.1%0.2%14259.44-92%4.9%0.0%124.98-97%
a6-60701.66.9%4.0%27644TL (1.3%)5.4%2.2%2959737.69-90%5.2%2.1%1526760.16-89%
a6-72797.87.6%5.3%24262TL (2.3%)5.7%1.9%815309.15-96%5.6%1.8%1566387.09-95%
a7-56626.54.8%1.8%2198459.974.3%0.0%133.48-93%4.2%0.0%122.07-95%
a7-70777.99.5%6.3%12344TL (3.4%)7.9%2.9%70542581.81-64%7.8%3.0%51491853.28-74%
a7-84899.312.0%8.7%9230TL (7.1%)8.4%3.5%129495382.39-25%8.3%3.6%159825544.69-23%
a8-64670.06.9%4.8%14639TL (1.5%)5.5%2.0%9901122.42-84%5.5%1.5%1213569.91-92%
a8-80834.311.2%7.3%7982TL (5.8%)9.1%3.9%10202TL (0.8%)–9.1%4.0%13643TL (0.8%)–
a8-961046.012.5%9.0%2372TL (8.2%)8.3%3.3%5489TL (0.8%)–8.2%3.3%7628TL (0.7%)–
Total7.0%3.8%26015657362.55.7%1.2%4504225056.1-56%5.6%1.1%5126223830.8-58%

Table 6. Base versus base + cuts on the a-X⋆⋆ instances (routing costs (1)).

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

With windows of 45 minutes the a instances become considerably harder, and the gap between the two configurations widens. The base configuration leaves seven of the 24 a-X⋆⋆ instances unsolved in every seed (a6-60, a6-72, a7-70, a7-84, a8-64, a8-80 and a8-96, final gaps 0.9 to 8.2 percent) and finds no feasible solution at all for a8-96-X⋆⋆ in two of the three seeds; the objective value reported for it is that of the remaining seed. With the inequalities (14), five of these seven instances are solved in every seed, in 309 to 5382 seconds on average, and only a8-80-X⋆⋆ and a8-96-X⋆⋆ remain open, with final gaps of 0.7 to 0.8 and 0.6 to 0.8 percent; for a8-96-X⋆⋆ all three seeds end with the incumbent 1046.04, against 1083.30 for the only base run that found a solution. The configuration with the inequalities is faster on all twenty instances on which at least one configuration solves the instance and takes more than half a second, by 68 percent on average, and needs 25 056 instead of 57 363 seconds and 45 042 instead of 260 156 nodes in total, where the totals count the time-limit runs with 7200 seconds and thus understate the difference. As on a-X⋆, the LP relaxation gap changes little (7.0 to 5.7 percent on average), whereas the root gap falls from 3.8 to 1.2 percent. On b-X⋆⋆ both configurations solve every instance; the totals fall from 3100 to 1090 seconds and from 33447 to 7223 nodes, mainly through the instances with large search trees (b7-84-X** from 2492 to 814 seconds, b8-96-X** from 457 to 124 seconds and from 1516 nodes to the root node, b5-50-X** from 12 to 5 seconds), while the instances solved at or near the root node show the same small differences in both directions as on b-X* (eight faster, nine slower, −1 percent on average). With the strengthened inequalities (15) the picture is the same: the same five instances are solved, in 387 to 5545 seconds on average, a8-80-X** and a8-96-X** remain open with the same incumbents and final gaps of 0.3 to 0.8 and 0.6 to 0.7 percent, and the totals are 23831 seconds and 51262 nodes on a-X** (5 percent less time than with (14), faster on ten of seventeen instances) and 997 seconds and 7486 nodes on b-X** (8 percent less, faster on twelve of sixteen).

Inst.Obj.base LPgaprGapNodesCPUbase + (14) LPgaprGapNodesCPUΔCPUbase + (15) LPgaprGapNodesCPUΔCPU
b2-16262.31.8%0.0%10.221.8%0.0%10.17–1.8%0.0%10.24–
b2-20301.40.0%0.0%10.030.0%0.0%10.03–0.0%0.0%10.03–
b2-24404.52.5%0.0%10.112.5%0.0%10.11–2.3%0.0%10.10–
b3-18281.70.9%0.0%10.540.9%0.0%10.38-30%0.9%0.0%10.22-59%
b3-24356.02.0%0.0%10.432.0%0.0%10.50+16%2.0%0.0%10.59+37%
b3-30494.12.7%0.0%10.332.7%0.0%10.59+79%2.7%0.0%10.44–
b3-36537.50.0%0.0%10.180.0%0.0%10.17–0.0%0.0%10.17–
b4-16275.40.3%0.0%10.040.3%0.0%10.04–0.3%0.0%10.04–
b4-24332.20.2%0.0%10.290.2%0.0%10.35–0.2%0.0%10.34–
b4-32475.80.5%0.0%10.110.5%0.0%10.11–0.5%0.0%10.11–
b4-40611.11.1%0.0%10.871.1%0.0%11.01+16%1.1%0.0%10.83-5%
b4-48611.82.6%0.1%1811.962.3%0.0%19.74-19%2.3%0.0%113.12+10%
b5-40553.80.1%0.0%10.850.1%0.0%11.27+49%0.1%0.0%11.06+25%
b5-50700.23.2%1.3%157411.793.1%0.6%2244.86-59%3.1%1.0%3664.58-61%
b5-60816.92.3%0.4%1258.742.3%0.2%8111.40+30%2.3%0.2%499.88+13%
b6-48666.60.9%0.0%10.760.9%0.0%10.84+11%0.9%0.0%10.77+1%
b6-60819.12.6%0.1%315.332.6%0.0%15.28-1%2.6%0.0%14.91-8%
b6-72892.32.6%0.6%115136.542.5%0.4%34337.88+4%2.5%0.7%51419.54-47%
b7-56766.91.2%0.0%119.621.2%0.1%3432.42+65%1.2%0.2%5642.86+118%
b7-70833.32.1%0.2%2511.922.1%0.1%58.29-30%2.1%0.2%448.40-30%
b7-841091.83.6%2.0%287322491.713.3%1.6%6247814.18-67%3.3%1.6%6190759.97-70%
b8-64794.72.1%0.1%2317.542.0%0.1%1522.91+31%2.0%0.1%2020.38+16%
b8-80975.92.6%0.3%23822.682.6%0.3%25813.44-41%2.6%0.3%23111.98-47%
b8-961091.22.1%0.8%1516457.202.0%0.0%1123.69-73%2.0%0.0%196.77-79%
Total1.7%0.2%334473099.81.6%0.1%72231089.7-65%1.6%0.2%7486997.3-68%

Table 7. Base versus base + cuts on the b-X** instances (routing costs (1)). Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

Conclusion

The paper presents new valid inequalities for the event-based mixed-integer programming formulation for the Dial-a-Ride Problem. A substantial weakness of this formulation is the implementation of time progression via Big MM constraints which need to hold in the extreme case and lead, therefore, often to a weak LP relaxation.

Our introduced valid inequalities (14) and the improved version (15), which additionally include enforced waiting times, address exactly this issue for the relation between a request’s pickup and delivery location. For these locations we know that the delivery location is visited after the pickup location within the same tour. Moreover, the event structure allows us to identify all visited events in between. These relations are used for the valid inequalities.

The valid inequalities are evaluated in a comprehensive computational study on the well-known DARP benchmark instances where computation times could be reduced by up to 99%. Since all X⋆X^\star instances could be solved with the inequalities, we extend their time windows by another 15 minutes. Finally, we also applied the valid inequalities to a time-related objective function. Indeed, the LP relaxation bound is zero for many instances and this objective. Nevertheless, the new valid inequalities are able to increase the root node bound and decrease the required search tree size. The strengthened inequalities (15) dominate (14) in theory, but forced waiting is rare after the graph preprocessing, so that the LP bounds of the two versions coincide on most instances and the computation times vary, slightly in favour of (15) for the routing costs and of (14) for the relative detour.

However, we only tested the LAEB formulation and instances with up to 96 customers. Our valid inequalities work in general for the event-based model formulation and can, thereby, also be applied to other problem variants like those named in the introduction. Future research, thus, should use the valid inequalities to improve on model formulations for these problems.

Relative detour

Table 8–Table 11 report the same comparison as in § 5.3 for the relative-detour objective (16), again with the same configurations; the objective values are given with two decimals.

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
basebase + (14)base + (15)
a2-161.2779.4%0.0%10.0475.8%0.0%10.02–75.8%0.0%10.02–
a2-200.30100.0%0.0%10.05100.0%0.0%10.03–100.0%0.0%10.03–
a2-243.7371.2%0.0%10.0761.6%0.0%10.07–60.1%0.0%10.07–
a3-181.15100.0%0.0%10.0488.9%0.0%10.03–88.9%0.0%10.04–
a3-240.5541.3%0.0%10.0741.3%0.0%10.07–41.3%0.0%10.07–
a3-305.8492.0%0.0%10.0635.4%0.0%10.06–34.6%0.0%10.06–
a3-365.09100.0%0.0%10.0898.1%0.0%10.07–98.1%0.0%10.08–
a4-160.8238.9%0.0%10.0638.9%0.0%10.06–38.9%0.0%10.06–
a4-240.370.0%0.0%10.040.0%0.0%10.05–0.0%0.0%10.05–
a4-322.12100.0%0.0%10.2789.1%0.0%10.13–89.1%0.0%10.16–
a4-402.2077.0%0.0%10.3177.0%0.0%10.26–77.0%0.0%10.27–
a4-480.88100.0%0.0%10.74100.0%0.0%10.39-47%100.0%0.0%10.41-45%
a5-400.460.0%0.0%10.160.0%0.0%10.18–0.0%0.0%10.16–
a5-500.00––10.24––10.22–––10.25–
a5-600.55100.0%0.0%10.3178.8%0.0%10.28–78.8%0.0%10.30–
a6-480.00––10.27––10.34–––10.32–
a6-600.5645.9%0.0%10.6145.9%0.0%10.55-10%45.9%0.0%10.56-8%
a6-720.09100.0%0.0%10.51100.0%0.0%10.47-8%100.0%0.0%10.47-8%
a7-560.410.0%0.0%10.450.0%0.0%10.43–0.0%0.0%10.35–
a7-701.0233.9%0.0%10.8533.9%0.0%10.87+2%33.9%0.0%10.96+13%
a7-840.830.0%0.0%10.850.0%0.0%10.79-7%0.0%0.0%10.97+14%
a8-641.090.0%0.0%10.540.0%0.0%10.62+15%0.0%0.0%10.59+9%
a8-8010.340.0%0.0%10.700.0%0.0%10.73+4%0.0%0.0%10.76+9%
a8-960.3413.8%0.0%11.3313.8%0.0%11.47+11%13.8%0.0%11.49+12%
Total54.2%0.0%248.749.0%0.0%248.2-6%48.9%0.0%248.5-2%

Table 8. Base versus base + cuts on the a instances (relative detour (16)).

Inst.Obj.base LPgapbase rGapbase Nodesbase CPUbase + (14) LPgapbase + (14) rGapbase + (14) Nodesbase + (14) CPUΔCPUbase + (15) LPgapbase + (15) rGapbase + (15) Nodesbase + (15) CPUΔCPU
b2-162.03100.0%0.0%10.11100.0%0.0%10.09–100.0%0.0%10.09–
b2-2018.50100.0%11.7%110.14100.0%0.0%10.04–100.0%0.0%10.04–
b2-242.42100.0%0.0%10.10100.0%0.0%10.09–100.0%0.0%10.09–
b3-182.43100.0%0.0%10.11100.0%0.0%10.10–100.0%0.0%10.10–
b3-2410.3779.9%28.7%1031.0079.9%0.0%10.61-39%79.9%0.0%10.70-30%
b3-307.2487.9%0.0%10.4587.9%0.0%10.23–87.9%0.0%10.23–
b3-3612.70100.0%0.0%10.22100.0%0.0%10.21–100.0%0.0%10.20–
b4-163.2246.1%0.0%10.0446.1%0.0%10.04–46.1%0.0%10.04–
b4-2412.08100.0%0.0%10.17100.0%0.0%10.16–100.0%0.0%10.20–
b4-320.31100.0%0.0%10.12100.0%0.0%10.11–100.0%0.0%10.13–
b4-402.2979.6%0.0%10.4579.6%0.0%10.31–79.6%0.0%10.29–
b4-487.31100.0%0.0%12.02100.0%0.0%11.13-44%100.0%0.0%11.52-25%
b5-400.00––10.65––10.51-22%––10.59-9%
b5-506.9692.5%4.7%142.0692.5%0.0%11.21-41%92.5%2.1%81.35-34%
b5-601.79100.0%16.5%222.43100.0%0.0%11.88-23%100.0%0.0%11.79-26%
b6-482.20100.0%0.0%10.59100.0%0.0%10.48-19%100.0%0.0%10.55-7%
b6-600.00––10.68––10.79+16%––10.85+25%
b6-721.120.0%0.0%12.510.0%0.0%11.89-25%0.0%0.0%12.00-20%
b7-560.00––16.68––15.18-22%––18.73+31%
b7-701.4566.0%0.0%12.8766.0%0.0%12.18-24%66.0%0.0%11.89-34%
b7-841.32100.0%83.0%3014.54100.0%16.0%143.65-20%100.0%7.7%133.57-21%
b8-640.00––12.90––11.79-38%––12.77-4%
b8-8014.703.5%0.0%12.363.5%0.0%12.25-5%3.5%0.0%12.08-12%
b8-960.00––115.71––112.36-21%––119.67+25%
Total81.9%7.6%47048.981.9%0.8%3737.3-24%81.9%0.5%4349.5+1%

Table 11. Base versus base + cuts on the b-X⋆ instances (relative detour (16)). Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

With this objective the benchmark instances are easy for every configuration: all 1440 solves end with a proven optimum, the longest in 25 seconds, and the optimal values are small, between 0 and 10.3 on the a sets and between 0 and 21.0 on the b sets, with an optimum of zero on two a and five b instances, where every request can be delivered at its earliest time. The relative gaps in the tables are therefore large in percentage terms although small in absolute terms: the LP relaxation bound is zero on many instances, because the Big MM time constraints are not binding in the relaxation. The inequalities raise it only on some of the a and b instances without extended time windows, as they bound the delivery times only through the arcs on which a request is on board.

The effect of the inequalities (14) shows again in the search trees and in the root gaps. On the a-X* instances the base configuration branches on five instances and needs 1299 nodes and 53.9 seconds in total (mean root gap 7.9 percent), the configuration with the inequalities branches on two instances and needs 71 nodes and 42.8 seconds (mean root gap 1.1 percent); it is faster on all fifteen instances above half a second, by 24 percent on average. On the b-X* instances the totals fall from 470 nodes and 48.9 seconds to 37 nodes and 37.3 seconds and the mean root gap from 7.6 to 0.8 percent, faster on thirteen of fourteen instances, by 23 percent on average. The a and b instances are solved at the root node by all three configurations (b2-20 already in presolve, without any node), except b7-84 with the base configuration (7 nodes) and b7-70 with base + (15) (2 nodes), in about 9 and 10 seconds in total, and the inequalities (14) change the totals by −5 and −6 percent. The weaker configurations, run once each, gain more:

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%) = time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
basebase + (14)base + (15)
b2-162.03100.0%0.0%10.04100.0%0.0%10.05–100.0%0.0%10.05–
b2-2019.4993.3%–00.0275.0%–00.01–75.0%–00.01–
b2-242.42100.0%0.0%10.05100.0%0.0%10.04–100.0%0.0%10.04–
b3-183.94100.0%0.0%10.05100.0%0.0%10.05–100.0%0.0%10.06–
b3-2414.3685.4%0.0%10.0980.4%0.0%10.11–80.4%0.0%10.12–
b3-309.3657.3%0.0%10.1757.3%0.0%10.07–57.3%0.0%10.08–
b3-3621.0223.8%0.0%10.0817.4%0.0%10.07–17.4%0.0%10.08–
b4-163.2246.1%0.0%10.0246.1%0.0%10.02–46.1%0.0%10.02–
b4-2418.03100.0%0.0%10.06100.0%0.0%10.07–100.0%0.0%10.08–
b4-320.31100.0%0.0%10.06100.0%0.0%10.06–100.0%0.0%10.06–
b4-402.2979.6%0.0%10.2079.6%0.0%10.19–79.6%0.0%10.16–
b4-488.18100.0%0.0%10.41100.0%0.0%10.36–100.0%0.0%10.35–
b5-400.00––10.19––10.16–––10.17–
b5-506.0692.5%0.0%10.5391.4%0.0%10.32-40%91.4%0.0%10.34-36%
b5-601.79100.0%0.0%10.78100.0%0.0%10.59-24%100.0%0.0%10.69-12%
b6-486.2036.4%0.0%10.3136.4%0.0%10.22–36.4%0.0%10.38–
b6-600.00––10.29––10.36–––10.33–
b6-721.120.0%0.0%10.630.0%0.0%10.67+6%0.0%0.0%10.74+17%
b7-560.00––10.99––10.97-2%––10.95-4%
b7-701.4566.0%0.0%10.6466.0%0.0%10.64+0%66.0%3.8%20.73+14%
b7-841.32100.0%14.3%71.32100.0%0.0%10.90-32%100.0%0.0%11.07-19%
b8-640.00––10.64––10.61-5%––10.53-17%
b8-8014.703.5%0.0%10.703.5%0.0%10.65-7%3.5%0.0%10.65-7%
b8-960.00––11.89––12.41+28%––12.32+23%
Total72.8%0.8%2910.271.2%0.0%239.6-6%71.2%0.2%2410.0-2%

Table 9. Base versus base + cuts on the b instances (relative detour (16)).

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%) = time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

Inst.Obj.base LPgapbase rGapbase Nodesbase CPUbase + (14) LPgapbase + (14) rGapbase + (14) Nodesbase + (14) CPUΔCPUbase + (15) LPgapbase + (15) rGapbase + (15) Nodesbase + (15) CPUΔCPU
a2-161.27100.0%0.0%10.03100.0%0.0%10.07–100.0%0.0%10.03–
a2-200.30100.0%0.0%10.06100.0%0.0%10.05–100.0%0.0%10.05–
a2-243.73100.0%19.5%190.48100.0%3.7%60.23–100.0%3.7%60.24–
a3-181.15100.0%0.0%10.12100.0%0.0%10.09–100.0%0.0%10.10–
a3-240.5541.3%0.0%10.2341.3%0.0%10.21–41.3%0.0%10.22–
a3-304.19100.0%0.0%10.33100.0%0.0%10.14–100.0%0.0%10.14–
a3-365.09100.0%49.3%5201.30100.0%20.3%430.85-35%100.0%16.0%291.16-11%
a4-160.8238.9%0.0%10.2038.9%0.0%10.18–38.9%0.0%10.16–
a4-240.370.0%0.0%10.150.0%0.0%10.13–0.0%0.0%10.13–
a4-322.12100.0%35.8%1191.29100.0%0.0%10.53-59%100.0%0.0%10.50-61%
a4-402.2077.0%0.0%11.3577.0%0.0%10.97-28%77.0%0.0%11.18-13%
a4-480.88100.0%22.4%3622.87100.0%0.0%12.03-29%100.0%0.0%11.57-45%
a5-400.460.0%0.0%10.490.0%0.0%10.48–0.0%0.0%10.48–
a5-500.00––10.95––10.72-24%––10.82-14%
a5-600.55100.0%0.0%11.26100.0%0.0%11.01-20%100.0%0.0%11.18-6%
a6-480.00––11.71––11.35-21%––11.57-8%
a6-600.5645.9%45.9%2606.9345.9%0.0%14.83-30%45.9%0.0%14.44-36%
a6-720.09100.0%0.0%12.25100.0%0.0%11.96-13%100.0%0.0%12.46+9%
a7-560.410.0%0.0%12.010.0%0.0%11.63-19%0.0%0.0%11.70-15%
a7-701.0233.9%0.0%13.4233.9%0.0%13.22-6%33.9%0.0%14.33+27%
a7-840.830.0%0.0%15.310.0%0.0%13.96-25%0.0%0.0%15.33+0%
a8-641.090.0%0.0%14.970.0%0.0%13.50-30%0.0%0.0%15.81+17%
a8-8010.340.0%0.0%15.180.0%0.0%14.67-10%0.0%0.0%16.42+24%
a8-960.3413.8%0.0%110.9813.8%0.0%19.96-9%13.8%0.0%113.04+19%
Total56.9%7.9%129953.956.9%1.1%7142.8-21%56.9%0.9%5753.0-2%

Table 10. Base versus base + cuts on the a-X⋆ instances (relative detour (16)). Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

on aa-X⋆X^\star the plain model needs 12 392 nodes and 54.9 seconds and the plain model with the inequalities 193 nodes and 20.3 seconds, GP needs 1561 nodes and 31.7 seconds and GP with the inequalities 100 nodes and 19.1 seconds; on bb-X⋆X^\star the corresponding totals are 4352 nodes and 44.0 seconds against 435 nodes and 20.0 seconds for the plain model and 1651 nodes and 27.1 seconds against 61 nodes and 17.2 seconds for GP.

With this objective the strengthened inequalities (15) are slower than (14): the totals are 53.0 against 42.8 seconds on aa-X⋆X^\star and 49.5 against 37.3 seconds on bb-X⋆X^\star, which is the level of the base configuration, and 8.5 against 8.2 and 10.0 against 9.6 seconds on aa and bb; the weaker configurations lose one to five seconds each. The search trees are as small as with (14) (57 against 71 nodes on aa-X⋆X^\star, 43 against 37 on bb-X⋆X^\star) and the LP bounds are identical; the additional time is spent in the root node, where Gurobi’s cutting-plane and heuristic loop runs longer with the coefficients τa\tau_a, while the LP relaxations take about the same time.

On the sets with windows of 45 minutes (Table 12 and Table 13) the relative-detour objective stays easy: all 432 solves end with a proven optimum, the longest in 156 seconds (a8-96-X⋆⋆X^{\star\star}, base), with optimal values between 0 and 10.3 on aa-X⋆⋆X^{\star\star} and between 0 and 18.5 on bb-X⋆⋆X^{\star\star}.

basebase + (14)base + (15)
Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔ\DeltaCPULPgaprGapNodesCPUΔ\DeltaCPU
a2-161.27100.0%0.0%10.06100.0%0.0%10.04–100.0%0.0%10.05–
a2-200.30100.0%0.0%10.14100.0%0.0%10.12–100.0%0.0%10.10–
a2-243.73100.0%38.6%740.60100.0%0.0%10.44-27%100.0%10.1%150.50-17%
a3-181.15100.0%0.0%10.29100.0%0.0%10.32–100.0%0.0%10.21–
a3-240.5541.3%0.0%10.4241.3%0.0%10.39–41.3%0.0%10.35–
a3-304.19100.0%49.1%1121.23100.0%0.0%10.30-76%100.0%0.0%10.31-75%
a3-364.87100.0%72.3%15455.40100.0%19.4%911.97-64%100.0%25.0%1151.79-67%
a4-160.8238.9%0.0%10.4338.9%0.0%10.37–38.9%0.0%10.35–
a4-240.370.0%0.0%10.460.0%0.0%10.31–0.0%0.0%10.38–
a4-322.12100.0%60.5%5153.30100.0%0.0%11.17-65%100.0%0.0%11.34-59%
a4-402.2077.0%0.0%15.0077.0%0.0%13.05-39%77.0%0.0%14.50-10%
a4-480.88100.0%65.6%26610.91100.0%0.0%16.22-43%100.0%0.0%17.35-33%
a5-400.460.0%0.0%11.300.0%0.0%11.23-5%0.0%0.0%11.22-6%
a5-500.00––12.800.0%0.0%12.20-21%0.0%0.0%12.61-7%
a5-600.55100.0%0.0%15.33100.0%0.0%14.08-23%100.0%0.0%14.27-20%
a6-480.00––112.57––111.26-10%––111.52-8%
a6-600.5645.9%30.6%30137.0545.9%0.0%128.15-24%45.9%0.0%121.94-41%
a6-720.09100.0%0.0%118.57100.0%0.0%111.76-37%100.0%0.0%113.27-29%
a7-560.410.0%0.0%111.480.0%0.0%110.91-5%0.0%0.0%110.75-6%
a7-702.0033.9%0.0%134.7433.9%0.0%124.25-30%33.9%0.0%120.12-42%
a7-840.830.0%0.0%350.600.0%0.0%125.46-50%0.0%0.0%125.90-49%
a8-641.090.0%0.0%144.400.0%0.0%125.37-43%0.0%0.0%133.49-25%
a8-8010.340.0%0.0%149.090.0%0.0%134.10-31%0.0%0.0%135.12-28%
a8-960.3413.8%0.0%1144.8113.8%0.0%169.95-52%13.8%0.0%173.57-49%
Total56.9%14.4%2833441.056.9%0.9%114263.4-40%56.9%1.6%152271.0-39%

Table 12. Base versus base + cuts on the a-X⋆⋆X^{\star\star} instances (relative detour (16)).

Inst.Obj.LPgaprGapNodesCPULPgaprGapNodesCPUΔCPULPgaprGapNodesCPUΔCPU
b2-162.03100.0%0.0%10.33100.0%0.0%10.23–100.0%0.0%10.22–
b2-2018.50100.0%58.9%1010.29100.0%25.1%160.25–100.0%25.9%190.26–
b2-242.42100.0%0.0%10.16100.0%0.0%10.18–100.0%0.0%10.14–
b3-182.43100.0%0.0%10.23100.0%0.0%10.18–100.0%0.0%10.19–
b3-2410.3779.9%79.5%320511.9379.9%53.0%12263.02-75%79.9%53.4%11342.79-77%
b3-307.2487.9%0.0%10.8687.9%0.0%10.42-51%87.9%0.0%10.44-49%
b3-3610.85100.0%0.0%10.50100.0%0.0%10.38-24%100.0%0.0%10.37-26%
b4-163.2246.1%0.0%10.0746.1%0.0%10.06–46.1%0.0%10.06–
b4-2412.08100.0%0.0%10.65100.0%0.0%10.58-11%100.0%0.0%10.69+6%
b4-320.31100.0%0.0%10.22100.0%0.0%10.19–100.0%0.0%10.17–
b4-402.2979.6%0.0%10.5479.6%0.0%10.48-11%79.6%0.0%10.57+6%
b4-487.31100.0%0.0%17.03100.0%0.0%15.82-17%100.0%0.0%18.14+16%
b5-400.00––12.18––12.01-8%––11.79-18%
b5-506.0692.5%69.8%20408.6292.5%0.0%12.74-68%92.5%25.3%1443.51-59%
b5-601.79100.0%86.7%1027.98100.0%0.0%15.00-37%100.0%0.0%14.99-37%
b6-486.20100.0%0.0%12.48100.0%0.0%11.29-48%100.0%0.0%11.65-33%
b6-600.00––11.66––11.98+19%––12.04+23%
b6-721.120.0%0.0%110.340.0%0.0%17.15-31%0.0%0.0%18.22-21%
b7-560.00––161.23––110.73-82%––120.47-67%
b7-701.4566.0%22.0%298.5466.0%3.5%24.36-49%66.0%0.0%15.79-32%
b7-841.32100.0%89.1%37511.07100.0%0.0%111.54+4%100.0%3.4%310.69-3%
b8-640.00––113.64––18.46-38%––17.65-44%
b8-8014.703.5%1.2%36.173.5%0.0%14.89-21%3.5%0.0%14.77-23%
b8-960.00––1108.48––142.03-61%––153.02-51%
Total81.9%21.4%5872265.281.9%4.3%1265114.0-57%81.9%5.7%1320138.6-48%

Table 13. Base versus base + cuts on the b-X⋆⋆ instances (relative detour (16)).

Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. Δ\DeltaCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

On aa-X⋆⋆X^{\star\star} the base configuration branches on seven instances and needs 2833 nodes and 441 seconds in total (mean root gap 14.4 percent), the configuration with the inequalities (14) branches on one instance and needs 114 nodes and 263 seconds (mean root gap 0.9 percent); it is faster on all eighteen instances above half a second, by 36 percent on average. On bb-X⋆⋆X^{\star\star} the totals fall from 5872 nodes and 265 seconds to 1265 nodes and 114 seconds and the mean root Notes: means over three seeds of LPgap, rGap, Nodes and CPU. Obj.: optimal value, or the best incumbent over all configurations and seeds if no configuration proved optimality. LPgap: gap of the LP bound to the objective value of the run. rGap: gap of the bound when Gurobi leaves the root node to branch, 0 if the run is solved at the root node; –: objective zero or root node not processed. Nodes: branch-and-bound nodes (1: solved at the root node, 0: solved in presolve without a root node). CPU: pure Gurobi time in seconds (graph and model building excluded); TL (x%): time limit of 7200 s reached in every seed, largest final gap. ΔCPU: percentage change of CPU against base; –: both below 0.5 s or both at the limit. Total: sums of CPU and Nodes, means of the gaps, percentage change of the summed CPU.

gap from 21.4 to 4.3 percent, faster on sixteen of eighteen instances, by 34 percent on average. The strengthened inequalities (15) need 271 and 139 seconds on the two sets, again slightly more than (14), with search trees of the same size. The total gains by the new inequalities for this objective thus grow with the width of the time windows, from about 21-24% on the X⋆ sets to about 40-57% on the X⋆⋆ sets. The strengthened versions do not have a positive effect here. One reason is probably that the objective function aims at avoiding waiting times at least with customers on board, which is not the case of routing cost is minimised.

References

  1. [1]Fabian Anzenhofer, Simon Schmidbaur, Robert Klein, and Claudius Steinhardt. The potential of governmental regulation on shared mobility-on-demand systems. Transportation Research Part A: Policy and Practice, 192:104360, 2025. doi: 10.1016/j.tra.2024.104360.DOI
  2. [2]Jonas Barth, Kendra Reiter, and Marie Schmidt. The line-based dial-a-ride problem with transfers. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025), volume 137 of Open Access Series in Informatics (OASIcs), pages 17:1–17:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/OASIcs.ATMOS.2025.17.
  3. [3]Meiyan Chi, Xiaoning Zhu, Baicheng Yan, and Kris Braekers. An event-based model and hybrid genetic search algorithm for an inland multi-size container transportation problem. Transportation Research Part E: Logistics and Transportation Review, 208:104639, 2026. doi: 10.1016/j.tre.2025.104639.
  4. [4]Jean-François Cordeau. A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3):573–586, 2006. doi: 10.1287/opre.1060.0283.DOI
  5. [5]Luciano Ferreira, Marcos Vinicius Milan Maciel, José Valério de Carvalho, Elsa Silva, and Filipe Pereira Alvelos. A new effective heuristic for the prisoner transportation problem. European Journal of Operational Research, 323(3):753–766, 2025. doi: 10.1016/j.ejor.2025.01.029.DOI
  6. [6]Daniela Gaul, Kathrin Klamroth, and Michael Stig lmayr. Event-based MILP models for ride-pooling applications. European Journal of Operational Research, 301(3):1048–1063, 2022. doi: 10.1016/j.ejor.2021.11.053.DOI
  7. [7]Daniela Gaul, Kathrin Klamroth, Christian Pfeiffer, Michael Stig lmayr, and Arne Schulz. A tight formulation for the dial-a-ride problem. European Journal of Operational Research, 321(2):363–382, 2025. doi: 10.1016/j.ejor.2024.09.028.DOI
  8. [8]Timo Gschwind and Stefan Inrich. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem. Transportation Science, 49(2):335–354, 2015. doi: 10.1287/trsc.2014.0531.DOI
  9. [9]Qingying He, Wei Liu, and Haoning Xi. Dynamic electric vehicle fleets management problem for multi-service platforms with integrated ride-hailing, on-time delivery, and vehicle-to-grid services. Transportation Research Part B: Methodological, 199:103281, 2025. doi: 10.1016/j.trb.2025.103281.DOI
  10. [10]Antonio Lauerbach, Sven Mallach, Kendra Reiter, Marie Schmidt, and Michael Stig lmayr. Solving the line-based dial-a-ride problem by generating stopping patterns. arXiv preprint arXiv:2603.06295, 2026.arxiv.org/abs/2603.06295
  11. [11]Christian Pfeiffer and Arne Schulz. An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectrum, 44(1):87–119, 2022a. doi: 10.1007/s00291-021-00656-7.DOI
  12. [13]Harilaos N. Psarafis. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 14(2):130–154, 1980. doi: 10.1287/trsc.14.2.130.
  13. [14]Kendra Reiter, Marie Schmidt, and Michael Stig lmayr. The line-based dial-a-ride problem. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024), volume 123 of Open Access Series in Informatics (OASIcs), pages 14:1–14:20. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024. doi: 10.4230/OASIcs.ATMOS.2024.14.
  14. [15]Yannik Rist and Michael A. Forbes. A new formulation for the dial-a-ride problem. Transportation Science, 55(5):1113–1135, 2021. doi: 10.1287/trsc.2021.1044.DOI
  15. [16]Stefan Ropke, Jean-François Cordeau, and Gilbert Laporte. Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks, 49(4):258–272, 2007. doi: 10.1002/net.20177.DOI
  16. [17]Arne Schulz and Christian Pfeiffer. A branch-and-cut algorithm for the dial-a-ride problem with incompatible customer types. Transportation Research Part E: Logistics and Transportation Review, 181:103394, 2024a. doi: 10.1016/j.tre.2023.103394.DOI
  17. [18]Arne Schulz and Christian Pfeiffer. Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems. European Journal of Operational Research, 312(2):456–472, 2024b. doi: 10.1016/j.ejor.2023.07.002.DOI
  18. [19]Verena Stallhofer and Sophie N. Parragh. Event-based models for the electric autonomous dial-a-ride problem. Transportation Research Part C: Emerging Technologies, 171:104896, 2025. doi: 10.1016/j.trc.2024.104896.DOI
  19. [20]Boshuai Zhao, Adam Abdin, and Jakob Puchinger. New formulations and discretization insights for the electric autonomous dial-a-ride problem. arXiv preprint arXiv:2601.03282, 2026a.arxiv.org/abs/2601.03282
  20. [21]Boshuai Zhao, Jakob Puchinger, and Roel Leus. The dial-a-ride problem with synchronized visits. arXiv preprint arXiv:2601.00498, 2026b.arxiv.org/abs/2601.00498

Paper details

vlnc:W_z8nbhf9z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents