← Areas of expertise/Sustainable Mobility/2025

Electric Autonomous Ride-Sharing Optimization, 31× Faster Than the Published Branch-and-Price Baseline With Up to 11× Tighter Gaps

An event-based MILP re-centered on pickups and drop-offs (not geography) plus an Adaptive Large Neighborhood Search heuristic — benchmarked across 38 standard e-ADARP instances against Su (2023) Branch-and-Price

On-demand ride-sharing with electric autonomous fleets is the urban-mobility frontier. The optimization problem is brutal: pickup/delivery time windows, battery dynamics, charging-station detours, ride-time fairness, all together, on instances with dozens of users and multiple recharging stations.

Our co-supervised Master's thesis designed an event-based graph formulation that re-centers the model on pickup and drop-off events rather than locations (implicitly encoding capacity and pairing constraints into the topology), plus an Adaptive Large Neighborhood Search heuristic that scales to instance sizes where exact methods give up.

31×

faster than Su (2023) Branch-and-Price on type-a γ = 0.4 instances (avg runtime)

11× tighter gap

vs. B&P on type-r γ = 0.1 (avg optimality gap 0.27% vs. 3.02%)

10×

ALNS heuristic speedup over the exact method with < 1% loss in objective

35 / 38

instances solved to certified optimality at γ = 0.1, vs. 33 / 38 for the B&P baseline

The challenge

The electric autonomous Dial-A-Ride Problem (e-ADARP) extends the classical DARP with battery state-of-charge dynamics, unconstrained visits to recharging stations, and a weighted multi-objective cost that trades total travel distance against excess ride time for users. Arc-based formulations (Bongiovanni et al. 2019, Su 2023) handle the model size with column generation, but the per-node combinatorics, vehicle capacity, time windows, pairing of pickups with drop-offs, produce huge LP relaxations that branch-and-price has to solve at every node.

Practitioners need both a model that captures the actual physics and a heuristic that returns deployable plans within seconds on the larger instances where exact methods stall.

Our approach

We adapted the event-based graph formulation of Gaul et al. (2022), extended for electric vehicles by Stallhofer (2023) but limited to single-visit charging, to the unconstrained-visit case studied by Su (2023). The key idea: nodes are Q-tuples encoding which users are in the vehicle, sorted in ascending order; arcs are feasible event transitions. Vehicle capacity and pickup-drop-off pairing are encoded in the graph topology itself rather than as explicit linear constraints, which shrinks the LP relaxation dramatically.

We tightened the formulation further with travel-time-aware time-window compatibility checks (an advance over Stallhofer's compatibility-without-travel-time pruning), which lets us drop many infeasible event nodes a priori. Combined with valid inequalities for infeasible multi-stop paths, the resulting MILP solves type-a instances in tens of seconds and type-r instances in a few hours on Gurobi.

On the heuristic side, we built an Adaptive Large Neighborhood Search with a portfolio of removal operators (random, worst-distance, related), insertion operators (greedy, regret-k), adaptive weight adjustment, and a simulated-annealing-style acceptance criterion. The initial-solution strategy uses the easier γ = 0.1 feasible-region pre-solve as a warm-start for the harder γ = 0.4 and γ = 0.7 cases.

We benchmarked against the exact Branch-and-Price baseline and Deterministic Annealing heuristic of Su (2023) on the standard Bongiovanni and Ropke instance sets (type-a urban scenarios, type-r realistic instances, type-u urban with charging-station relocation).

The outcome

Deliverable: an event-based MILP formulation for the electric autonomous Dial-A-Ride Problem (e-ADARP) plus an Adaptive Large Neighborhood Search heuristic, benchmarked against the published Branch-and-Price baseline of Su (2023) across 38 standard test instances (type-a, type-r, type-u) at three end-of-day battery ratios (γ = 0.1, 0.4, 0.7).

Exact-method results: 31× average speedup over B&P at γ = 0.4 on type-a (28.82 s vs. 910.33 s); 11× tighter average optimality gap on type-r γ = 0.1 (0.27% vs. 3.02%); 5× tighter gap on the hardest type-r γ = 0.7 (1.24% vs. 6.44%); solves 35 / 38 instances to certified optimality at γ = 0.1 vs. 33 / 38 for B&P. ALNS heuristic results: 10× average speedup over the exact method at less than 1% loss in objective, and on r8-96 (the largest type-r instance, 96 users) the ALNS finds 1,026.08 in 2,058 s where the exact event-based method needs 18,000 s for a slightly worse 1,026.44 — better solution in 9× less time.

Technical deep dive

The model behind the result.

The model

The e-ADARP is a multi-objective routing problem with battery physics layered on top of a classical pickup-and-delivery problem. The event-based reformulation is the centerpiece: instead of one decision variable per (vehicle, location, location) triple, which is what an arc-based formulation buys you, we have one variable per arc in an event graph where each node already encodes who is in the vehicle. Vehicle capacity (no more than Q users) and pickup-before-drop-off pairing become structural properties of the graph rather than linear constraints. The MILP then handles only the global stuff: time, battery, and the multi-objective cost.

v \in V : v = (u_{1}, u_{2}, \dots, u_{Q}) where u_{q} \in I \cup {n + i : i \in I} \cup {0, - 1}, u_{1} \geq u_{2} \geq \dots \geq u_{Q} .

Event node encoding. Each node v in the event graph is a Q-tuple recording the latest pickup/drop-off event in slot 1 and the other passengers currently in the vehicle (sorted ascending) in slots 2..Q. Zeros pad empty seats; a trailing −1 marks charging-station states. By construction the tuple cannot contain a passenger who's already been dropped off, so vehicle capacity (at most Q passengers) and pickup-before-drop-off pairing are encoded structurally in V, not as constraints.

min w_{1} a \in A \sum c_{a} x_{a} + w_{2} i \in I \sum R_{i} s.t. a \in δ^{in} (v) \sum x_{a} - a \in δ^{out} (v) \sum x_{a} = 0 \forall v \in V ∖ (V_{o} \cup V_{d}) .

Multi-objective cost and flow conservation. The objective trades vehicle routing cost (∝ travel time) against user excess ride time R_i, with weights w_1, w_2 chosen by the operator. Flow conservation says: at every non-depot event node, every incoming arc is matched by an outgoing arc. Combined with the explicit 'each user served exactly once' constraint (Σ_{δ^in(v), v ∈ V_i} x_a = 1), this gives a minimum-cost-flow problem on the event graph.

T_{w} \geq T_{v} + s_{v} + t_{(v, w)} - H (1 - x_{(v, w)}) \forall (v, w) \in A, T_{w} - T_{v} - s_{v} \leq p_{i} \forall v \in V_{i}, w \in V_{n + i} .

Time constraints. Service start time T_w at the next event must be at least the previous event's start time plus service time plus travel time, with a big-M (the horizon H) deactivating the constraint when the arc isn't used. The ride-time bound enforces user fairness: for any user i, the time between their pickup and drop-off can't exceed the maximum ride time p_i (so the system can't keep someone in the vehicle indefinitely just to optimize routing).

B_{w} \leq B_{v} - β_{(v, w)} + G (1 - x_{(v, w)}), B_{w} \leq B_{v} + α E_{v} - β_{(v, w)} + G (1 - x_{(v, w)}) \forall v \in V_{z} .

Battery state-of-charge dynamics. Between non-charging events, SoC at the next node B_w equals B_v minus the discharge β_{(v,w)} = µ · t_{(v,w)} along the arc. At charging-station nodes (V_z), the battery is replenished by α · E_v where α is the charge rate and E_v is the charging duration. Symmetric ≥-versions of both constraints (omitted) pin the equality when the arc is used. End-of-day constraint B_v ≥ γG forces vehicles to return to depot with at least a γ fraction of capacity (the headline parameter in the benchmark, γ = 0.7 is the hard case).

R_{i} \geq T_{w} - T_{v} - s_{i} - t_{(i, n + i)} \forall i \in I, v \in V_{i}, w \in V_{n + i} .

Excess ride time. R_i is the user-fairness measure: it's the difference between the user's actual time in the vehicle (T_drop-off − T_pickup − service time) and the minimum possible time t_{(i, n+i)} they'd spend in a direct ride. Minimizing total Σ R_i is the second objective, without it the optimizer would happily keep someone in the vehicle for hours to consolidate trips.

∣ V_{event-based} ∣ ≪ ∣ V_{arc-based} ∣, ∣ A_{event-based} ∣ ≪ ∣ A_{arc-based} ∣.

Why the event-based formulation wins. The arc-based model (Bongiovanni 2019, Su 2023) has one variable per (vehicle, location, location) triple, but most of these triples are infeasible (wrong capacity state, time-window violation, pairing violation) and the solver has to discover that during branch-and-bound. The event-based graph pre-prunes infeasible states at construction: the time-window-and-travel-time compatibility checks drop nodes that an arc-based model would keep. For type-a instances at Q = 6, we end up with ~150-1,500 nodes and ~1,500-16,000 arcs, manageable for Gurobi's branch-and-cut.

x_{P} := a \in P \sum x_{a} \leq ∣ P ∣ - 1 \forall P \in P_{infeasible} .

Valid inequality for infeasible paths. For any user i and any two-arc path P = (a, b) in the event graph where i is in the vehicle, if the combined ride time exceeds p_i then at most |P| − 1 = 1 of the arcs can be active. Adding these inequalities up-front (instead of waiting for branch-and-bound to discover them via cuts) tightens the LP relaxation noticeably on type-r and type-u instances.

The event-based formulation is the structural innovation; the ALNS is the deployable engineering layer on top. On the small-to-medium instances (16-48 users, 2-5 vehicles) the event-based MILP solves to proven optimality faster than the published B&P baseline. On the largest instances (96 users on type-r, 50 users on type-u) the MILP starts hitting time limits at γ = 0.7, and the ALNS takes over with near-optimal solutions in seconds to minutes. Compared to the Deterministic Annealing baseline from Su (2023), the ALNS finds equal or better objective values in most cases, at the cost of slightly more wall-clock time. The result is a two-tier system: use the exact event-based MILP when you can, fall back to the ALNS when you can't.

Benchmark

Event-based MILP vs. Su (2023) Branch-and-Price on type-r benchmark instances (Bongiovanni-Ropke realistic test bed, end-of-day battery ratio γ = 0.7, the hardest setting). Each row is a (vehicles, users) instance. Objective values in weighted units (travel cost + excess ride time); gaps in % vs. proven lower bound. Time limit 18,000 s. Lower objective is better; lower gap is better.

Instance	Event-based Obj.	EB Gap (%)	EB Time (s)	Su (2023) B&P Obj.	B&P Gap (%)	B&P Time (s)
r5-60	686.36	0.10	18,000	688.84	0.70	18,000
r6-48	508.10	0.00	2,364	508.10	0.00	2,028
r6-60	689.55	0.00	1,703	689.55	0.00	6,605
r6-72	765.25	0.41	18,000	788.83	4.96	18,000
r7-56	615.86	0.52	18,000	616.16	0.00	14,247
r7-70	756.31	0.04	18,000	765.49	1.48	18,000
r7-84	891.38	2.39	18,000	1,004.81	21.65	18,000
r8-64	632.61	0.00	2,493	632.61	0.00	18,000
r8-80	806.87	2.19	18,000	794.41	0.00	15,051
r8-96	1,064.86	6.74	18,000	1,174.49	35.68	18,000
Avg	-	1.24	13,256	-	6.44	14,593

Two patterns. First, the event-based MILP achieves a 5× tighter average optimality gap (1.24% vs. 6.44%) on these hard γ = 0.7 instances, and on the largest one (r8-96) the gap difference is 6.74% vs. 35.68%, with the event-based solution 9.3% better in objective value. Second, on the instances both methods solve to optimality (r6-48, r6-60, r8-64), the event-based MILP is consistently faster, sometimes by a factor of 7 (r8-64: 2,493 s vs. 18,000 s for B&P). The structural pruning at graph-construction time pays off most on instances with tight time windows and many users, exactly where the arc-based B&P struggles. On easier γ = 0.1 instances (not shown), the gap is even more lopsided: event-based 0.27% avg vs. B&P 3.02%, a 11× tighter gap.

From the record

Figure 3 from the thesis: an event-based graph for n = 2 user requests, vehicle capacity Q = 3, one charging station. Nodes are Q-tuples encoding which users are in the vehicle (e.g., (1, 0, 0) = user 1 picked up, two empty seats; (2, 1, 0) = both users in vehicle; (4, 1, 0) = user 2 dropped off, user 1 still in vehicle). Arcs are feasible event transitions. Capacity constraints and pickup-before-drop-off pairing are encoded in the graph topology itself, they never appear as linear constraints in the MILP.

Mathematical formulation of Model 1. Objective (3.1) is the weighted sum of routing cost and user excess ride time. Constraints (3.2)–(3.6) are graph flow conservation plus 'each user served exactly once'. Constraints (3.9)–(3.16) define time windows, ride-time bounds, and the excess ride time variables R_i. Constraints (3.17)–(3.25) handle battery state-of-charge dynamics including the recharge at charging stations.

Tables 3 and 4 from the thesis: instance sizes for type-a (urban) and type-r (realistic) benchmarks. Note how the event-based graph stays manageable, a5-50 (the largest type-a) has 1,700 nodes and 16,838 arcs; r8-96 (the largest type-r) has 7,381 nodes and 74,306 arcs. An arc-based formulation on the same instance would have an order of magnitude more variables, because every (vehicle, location, location) triple gets one, including all the ones we've pre-pruned via time-window-and-travel-time compatibility.

Figures 7 and 8: optimal routes for the two vehicles on instance a2-16 (16 users, 2 vehicles, γ = 0.7). The blue route handles users mostly clustered in the lower-right quadrant; the orange route handles users in the upper-left. Red dots are charging stations, with light blue rectangles around the ones actually used. This is a 32-event tour computed end-to-end by the event-based MILP in 4 seconds.

Techniques

Event-based graph formulation
Mixed-integer linear programming (B&C via Gurobi)
Adaptive Large Neighborhood Search
Removal/insertion operator portfolio
Simulated-annealing acceptance
Infeasible-path valid inequalities

Stack

Julia
Gurobi
Bongiovanni-Ropke instance benchmarks

A problem like this?

We'd like to hear about it.

contact@optimally.ch