Transit facility allocation: Hybrid quantum-classical optimization

Technical Summary: Transit Facility Allocation via Hybrid Quantum-Classical Optimization

Problem Statement
Urban transit planning faces a fundamental trade-off between service accessibility (how easily demand nodes, such as urban areas, can reach facilities) and efficiency (the distance a route can cover within a specific time window). Increasing the number of facilities generally improves accessibility but reduces efficiency due to increased dwell times and travel distances. Conversely, reducing facilities improves efficiency but risks accessibility. The paper addresses the Transit Facility Redundancy Problem: determining the optimal allocation of a limited number of facilities ($p$) along a route to maximize accessibility and minimize redundancy without compromising service coverage. The study focuses on the B20 northbound bus route in Vancouver, British Columbia, utilizing Geographic Information Systems (GIS) data.

Methodology
The authors propose an end-to-end optimization framework that integrates GIS data, multi-criteria decision-making, and hybrid quantum-classical computing.

1. Mathematical Formulation:

   • The problem is modeled using a novel Spatial Interaction Coverage (SIC) approach, capturing non-linear interactions between facilities and demand nodes, distance decay, and inter-facility competition.
   • The model is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The objective function maximizes a weighted sum of population demand attenuated by distance, while penalizing the selection of facilities that are too close to one another (competition).
   • A constraint requiring exactly $p$ facilities to be active is incorporated as a quadratic penalty term. To reduce complexity, the authors partition this global constraint into smaller local constraints, transforming the problem graph from a dense complete graph to a sparse network.

2. Weight Estimation (TOPSIS):

   • To determine the importance (weights) of each facility, the authors employ TOPSIS (Technique for Order Preference by Similarity to Ideal Solution), a multi-criteria decision-making method.
   • Three attributes are evaluated for each facility: monthly demand, connectedness to other services, and proximity to landmarks (e.g., hospitals, schools). TOPSIS synthesizes these into a ranking used to weight the facilities in the QUBO model.

3. Hybrid Solver:

   • The optimization is solved using a hybrid quantum-classical solver built on the open-source dwave-hybrid framework.
   • The solver runs three parallel branches:
     • Classical Heuristics: Simulated Annealing (SA) and Tabu Search (TS) perform hill-climbing on the full problem.
     • Quantum Annealing (QA): Operates on smaller sub-problems containing "high energy impact" variables, utilizing quantum tunneling to escape local minima that trap classical hill-climbing methods.
   • The system iteratively combines the best solutions from all branches.

4. Theoretical Properties:

   • The authors demonstrate that under mild conditions (specifically when the ratio of retained facilities to total facilities is $>0.5$ and competition is limited), the matrix governing the QUBO problem is positive definite.
   • This implies that even if integrality constraints are relaxed (allowing continuous variables $x_j \in [0, 1]$), the optimal solution naturally converges to binary values ($0$ or $1$).
   • A theoretical upper bound for the optimal objective value is derived using the Schur-Horn theorem, calculated as the sum of the $p$ largest eigenvalues of the interaction matrix.

Key Contributions

• Novel Mathematical Model: A QUBO-based model that naturally yields integral solutions without explicit integer constraints and captures complex non-linear factors like distance decay and facility competition.
• Quantum-Ready Formulation: The model is explicitly designed to leverage quantum effects (superposition and tunneling) via Ising spin glass equivalence, making it solvable on quantum annealers, digital annealers, and gate-based quantum computers.
• Hybrid Solver Implementation: A robust solver combining classical hill-climbing with quantum tunneling to navigate complex optimization landscapes.
• Theoretical Bounds: The derivation of a tight, polynomial-time computable upper bound to assess solution quality.
• GIS Integration: A flexible workflow integrating census data and TOPSIS for data-driven facility weighting.

Results
The framework was applied to the Vancouver B20 bus route (49 stops):

• Facility Reduction: The model successfully reduced the number of bus stops by 40% (from 49 to ~30) while maintaining complete coverage of all dissemination areas (demand nodes).
• Efficiency Gains: The reduction in stops resulted in an estimated 7-minute reduction in travel time (approx. 13% of the original travel time) during work hours.
• Solution Quality: The best objective function values found were within 95% of the theoretical upper bound (specifically at $p=45$).
• Comparative Performance: In experiments on 30 synthetic datasets, the proposed hybrid solver statistically outperformed a standard SIC model solved with the APOPT classical solver in terms of demand coverage across various facility retention levels.
• Redundancy Analysis: The study identified that up to 40% of stops were redundant (multiple stops within walking distance of the same demand nodes) without significantly impacting accessibility.

Significance and Claims
The paper claims that this framework offers a significant advancement in transit planning by providing a cost-effective method to improve service quality through strategic facility consolidation. Its primary significance lies in:

1. Bridging Classical and Quantum Computing: It provides a practical, real-world application for emerging quantum hardware, demonstrating how transportation planners can utilize quantum effects alongside classical tools.
2. Model Robustness: The ability to generate naturally binary solutions and compute tight upper bounds offers a level of theoretical assurance and flexibility not present in traditional models like LSCP or p-median.
3. Scalability: The hybrid approach addresses the limitations of current quantum hardware (noise and error rates) by using classical solvers for redundancy and global search, while leveraging quantum tunneling for local optimization.

The authors conclude that while the approach has limitations regarding non-binary integer variables and inequality constraints, it successfully demonstrates that quantum-inspired optimization can effectively balance the competing goals of accessibility and efficiency in complex urban transit networks.