Approximation Models for Shared Mobility Rebalancing Under Structured Spatial Imbalance

1. Problem Statement

Shared mobility systems (e.g., bike-share, car-share, ride-hailing) suffer from persistent spatial imbalances. Vehicles accumulate at popular drop-off destinations, leaving trip origins depleted of supply. Operators must reposition empty vehicles to restore balance, incurring significant operational costs (Vehicle Kilometers Traveled, VKT).

• The Challenge: Calculating the exact minimum rebalancing cost requires solving a Transportation Linear Program (LP) based on the Earth Mover's Distance (Wasserstein-1 distance, $W_1$). For city-scale networks with thousands of zones, this is computationally prohibitive ($O(N^3 \log N)$ complexity), making it unsuitable for iterative planning or real-time benchmarking.
• The Gap: Existing analytical models (e.g., for Traveling Salesman Problems) do not apply to the many-to-many rebalancing setting. Previous stochastic models often assume zero-mean net supply, failing to capture structured spatial imbalance (systematic mismatches between origin and destination densities).
• Objective: To derive closed-form approximation models for the minimum rebalancing distance in rectangular service regions that are computationally efficient, theoretically grounded, and accurate enough for operational planning.

2. Methodology

2.1. Problem Formulation

The authors model a shared mobility system operating in a rectangular region $\Omega = [0, L] \times [0, W]$ with area $R = LW$ and aspect ratio $\kappa = L/W$.

• Inputs: Origin density $f(x)$ and destination density $g(x)$.
• Imbalance Index ($I$): Defined as the Total Variation Distance between $f$ and $g$:
  $$I = \frac{1}{2} \int_{\Omega} |f(x) - g(x)| dx$$
  This scalar quantifies the magnitude of the mismatch ($I=0$ is perfect balance; $I=1$ is complete disjointness).
• Metric: The problem is formulated as an Optimal Transport problem minimizing total distance under two metrics:
  1. Manhattan ($L_1$): For grid road networks.
  2. Euclidean ($L_2$): For unconstrained movement (theoretical lower bound).

2.2. Derivation of Approximation Models

The authors derive unified models for both metrics using Beckmann's flow reformulation, converting the discrete LP into a continuous vector flux minimization problem.

• Manhattan Model ($L_1$):

  • The 2D problem is decomposed into two independent 1D sub-problems (East-West and North-South) by projecting the imbalance density onto the axes.
  • Using scaling arguments and dimensional analysis, the per-vehicle rebalancing distance is shown to scale with the imbalance index $I$, the square root of the area $\sqrt{R}$, and a shape factor dependent on the aspect ratio.
  • Formula: $W_1^M \approx C_M \cdot I \cdot \sqrt{R} \cdot g_M(\kappa)$
  • Where $g_M(\kappa) = \frac{\kappa + 1}{\sqrt{\kappa}}$ is the shape factor.

• Euclidean Model ($L_2$):

  • Derived using Fourier mode analysis of the imbalance field. The cost is dominated by the two lowest-order modes (East-West and North-South).
  • The model inherits the same structural form and shape factor as the Manhattan model but with a different calibration constant.
  • Formula: $W_1^E \approx C_E \cdot I \cdot \sqrt{R} \cdot g_M(\kappa)$

• Unified Total Cost:
  The total rebalancing VKT for a period with $N$ trips is:
  $$E[VKT] \approx C \cdot I \cdot (\lambda h) \cdot R^{3/2} \cdot g_M(\kappa)$$
  This implies VKT scales with $R^{3/2}$ (linear increase in trips $\times$ $\sqrt{R}$ increase in distance).

2.3. Theoretical Bounds

The paper proves a rigorous upper bound for the Wasserstein-1 distance:
$$W_1(f, g) \leq I \cdot \sqrt{R} \cdot g_M(\kappa)$$
This confirms that the derived approximation models (where the constant $C \in (0, 1]$) are physically valid and bounded by the system's geometry and imbalance magnitude.

3. Key Contributions

1. Scalar Imbalance Index: Introduction of $I$ as a unified metric to quantify structured spatial mismatch, distinct from stochastic variance.
2. Closed-Form Approximations: Derivation of unified models for both Manhattan and Euclidean metrics that explicitly incorporate service area size ($R$), shape ($\kappa$), and imbalance magnitude ($I$).
3. Shape Factor ($g_M$): Identification of the function $g_M(\kappa) = (\kappa + 1)/\sqrt{\kappa}$, proving that square regions ($\kappa=1$) minimize rebalancing costs regardless of the metric, while elongated regions increase costs.
4. Rigorous Validation: The models are validated against 500 exact LP solutions per metric and a real-world case study, confirming the theoretical scaling laws.

4. Results and Validation

4.1. Numerical Calibration (Synthetic Data)

• Dataset: 500 random instances per metric with varying areas, aspect ratios, and demand distributions (Uniform, Clustered, Directional).
• Calibration Constants:
  • Manhattan: $\hat{C}_M \approx 0.144$
  • Euclidean: $\hat{C}_E \approx 0.119$
  • The ratio $\hat{C}_E / \hat{C}_M \approx 0.825$ closely matches the theoretical isotropic prediction of $\pi/4 \approx 0.785$.
• Accuracy:
  • Manhattan: MAPE = 18.9%, $R^2_{log} = 0.922$.
  • Euclidean: MAPE = 25.2%, $R^2_{log} = 0.897$.
• Scaling Exponents: The fitted exponent for $\sqrt{R}$ is $\approx 1.02$, confirming the theoretical $R^{3/2}$ scaling for total VKT. The exponent for $I$ is sub-linear ($\approx 0.8$), indicating that highly concentrated imbalances do not scale linearly due to spatial diffusion effects.

4.2. Robustness

The model structure remains robust across different demand patterns (Uniform, Spatially Clustered, Directional Asymmetric). However, the calibration constant $C$ varies significantly (from ~0.12 for uniform to ~0.40 for highly directional demand), reflecting how demand structure affects the efficiency of local cancellations.

4.3. Case Study: New York City (January 2026)

• Data: 31 days of For-Hire Vehicle (FHV) trip data across 263 zones.
• Scenarios:
  1. NYC (All Boroughs): Near-square geometry ($\kappa \approx 1.06$).
  2. Manhattan Island: Elongated geometry ($\kappa \approx 2.39$).
• Findings:
  • The model successfully predicts daily $W_1$ values using exact LP solutions on the OSM road network.
  • NYC: Calibration MAPE = 10.9%, Validation MAPE = 13.8%.
  • Manhattan: Higher error (Validation MAPE = 30.2%) due to the highly structured, directional nature of commute flows which deviates from the isotropic assumptions of the base model.
  • Scaling Confirmation: The ratio of rebalancing distances between the two scenarios aligns with the $\sqrt{R}$ scaling prediction.
  • VKT Estimation: The model estimates a theoretical minimum of 238,000 km/day of empty vehicle travel for NYC, providing a benchmark for operational efficiency.

5. Significance and Implications

• Operational Benchmarking: Provides operators with a solver-free tool to benchmark rebalancing performance. If an optimization algorithm cannot beat the theoretical minimum predicted by this formula, the expansion or strategy may be non-viable.
• Strategic Planning:
  • Zone Design: Confirms that partitioning service areas into square sub-regions minimizes rebalancing costs.
  • Frequency Optimization: Enables calculation of optimal rebalancing frequency ($h$) by balancing repositioning costs against service quality.
  • Policy Impact: Quantifies how incentive programs that reduce the imbalance index $I$ directly reduce rebalancing VKT.
• Generalizability: The analytical logic extends beyond mobility to inventory repositioning, humanitarian relief, and warehouse robotics, offering a way to link demand heterogeneity, geometry, and relocation cost without solving large-scale optimization problems.

6. Limitations and Future Work

• Scalar Limitation: The index $I$ captures magnitude but not the specific spatial arrangement of surplus/deficit. The constant $C$ must be empirically calibrated for specific demand patterns.
• Geometry: The derivation assumes rectangular regions; future work should extend this to irregular polygons.
• Economies of Scale: The current model assumes cost is linear with distance and mass. Future work could incorporate hierarchical repositioning (e.g., trucks for bulk moves) to model sub-additive costs.