Learning To Enhance Primal Search For Dial-a-ride Routing With Heterogeneous Graph Neural Networks

The dial-a-ride problem (DARP) provides a mathematical framework for routing and scheduling in demand-responsive transport. However, its tightly coupled routing and service constraints make the search of high-quality feasible solutions computationally challenging. This paper develops a graph learning-guided primal search approach for branch-and-bound to accelerate DARP optimization. A heterogeneous graph is constructed by integrating arc variables, continuous state variables, constraints, passenger requests, and vehicles, enabling graph learning to capture both the algebraic structure of the mathematical formulation and the operational information characteristics of DARP. The learned arc-selection scores are transformed into confidence-aware search guidance and incorporated into variable hints and complementary neighborhood searches. Separate deviation budgets accommodate asymmetric prediction errors, while confidence-weighted local branching directs search toward promising assignments. Feasible candidates strengthen the incumbent of the DARP mixed-integer programming formulation, preserving solver-based feasibility verification and optimality certification. Computational experiments show that the predictor achieves a mean vehicle-aligned recall of 91.4%. Across ten evaluated instances, the prediction-centered parallel configuration obtains feasible solutions in every case and reduces mean time to the first feasible solution by 51.1% relative to cold start. The mean final optimality gap decreases from 5.6% to 3.8%, a relative reduction of 33.1%. These results demonstrate the potential of integrating problem-specific graph learning with confidence-guided primal search to accelerate feasible-solution discovery and improve optimization progress in demand-responsive routing.