acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
applications to robotics, autonomy, planning
Keywords:
heterogeneous graph neural networks, learning-augmented optimization, primal heuristics, branch-and-bound

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_CdHQOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose a heterogeneous GNN-based primal heuristic for the dial-a-ride problem, which aims to speed up the optimization process of exact solvers, while maintaining their guarantees and certifications. Beyond the heterogeneous graph representation of the MIP, the authors contribute with a score-refinement step and a confidence-guided primal-search step. Experimentally, the HGNN-based heuristic is shown to both produce accurate arc-level predictions and speed up the end-to-end optimization process across 10 DARP instances.

Critical strengths
  • Section 5.2 shows the proposed method is effective at predicting arc inclusion/exclusion, balancing precision and recall better than the two baselines/ablations. Section 5.3 similarly demonstrates speed-ups and optimality advantages in the end-to-end setting.

  • Overall, the idea of learning-augmented optimization via primal-search is principled and sound. The two additional proposed stages also seem sound, although their presentation is somewhat dense.

Critical weaknesses

I have two main points of criticism, both individually grounds to reject the paper in my opinion:

  • The related work on learning-based methods is limited to a single paragraph and does not position the methodological contribution sufficiently against prior work.
    • The paper cites Ding et al. (2020) and Nair et al. (2020), but does not explain how the method differs from them. This is especially relevant for Ding et al., who also uses a MIP graph representation to predict variable values.
    • There is a substantial amount of related work that also work in a related way [1-4], using predictions on the MIP graph with a subsequent solver-based search. How do these methods, and others, compare to your approach?
    • Overall, learning for the DARP and related pickup-and-delivery problems is not reviewed at all. For example, [5] uses a GNN to score arcs of a DARP-variant graph in order to restrict the solver's search space.
    • If the difference is only the heterogeneous graph formulation designed specifically for the DARP together with the refinement and search steps, the methodological contribution seems insufficient for a top deep learning venue like ICLR.
    • My impression is that the work might be better suited to an optimization or transportation venue, where the problem itself would be of interest. At the moment, it is unclear to me what wider conclusions could be relevant for the ICLR community.
  • The benchmark suite is relatively slim. Results are only presented for 10 test instances across one problem size. While the authors acknowledge this, I think a broader comparison is needed to properly assess the method.
    • Primarily, I would have liked to see comparisons with other primal heuristics, including classical ones and general learning-based ones (see point above about related work), in the end-to-end optimization experiments. Does the HGNN improve convergence speed and solution quality over strong baselines, not just the cold start approach?
    • I also think a scalability study is needed. The instances considered here are rather small.

[1] Khalil, Morris, Lodi, "MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers," AAAI, 2022.

[2] Han et al., "A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming," ICLR, 2023.

[3] Huang et al., "Contrastive Predict-and-Search for Mixed Integer Linear Programs," ICML, 2024.

[4] Huang et al., "Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning," ICML, 2023.

[5] Lu et al., "Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling," arXiv:2401.03692, 2024.

Questions for authors
  • How does the method scale with problem size? At the moment the evaluated graphs/instances are rather small. Does the heterogeneous MIP graph become prohibitively large for substantially larger instances?
  • Relatedly, the label generation seems computationally intensive, how much time does this step take with the given hardware?
Reviewer_rTQkOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper explores the use of Heterogeneous Graph Neural Networks (HGNNs) to enhance branch-and-bound search for route planning in Demand-Responsive Transit (DRT). Specifically, for the Dial-a-Ride Problem (DARP), we propose a search framework guided by a learning mechanism. This framework employs an HGNN to predict which routing arcs are likely to appear in high-quality solutions, using these predictions to steer the search process within a Mixed-Integer Programming (MIP) solver. Furthermore, the approach incorporates a path-based refinement step to address vehicle symmetry, and introduces a confidence-weighted neighborhood structure to improve robustness against prediction errors.

Critical strengths
  1. The overall framework is well-designed. Recognizing that neural predictions may be biased, the authors have incorporated a search neighborhood that allows the solver to refine these predictions. Retaining feasibility verification within the mixed-integer programming (MIP) solver is a pragmatic design choice.

  2. The speedups reported in the paper are impressive. The time required to obtain an initial feasible solution is significantly reduced; furthermore, the study evaluates both the quality of the predictions and the performance of the subsequent optimization process.

Critical weaknesses
  1. The experiments do not clearly establish which components are responsible for the improvement. The proposed method combines several components, including an HGNN, route refinement, confidence weighting, and multiple neighborhood searches. However, the optimization experiments mainly compare the complete approach against cold-start MIP solving and a few search configurations. This makes it difficult to understand how much improvement comes from the learned predictions themselves. In particular, I would like to see the same search framework guided by Root LP scores or simple heuristic scores. Comparisons with standard Local Branching and ablations of the heterogeneous graph representation, route refinement, and confidence weighting would also be valuable.

  2. The experimental evaluation is too limited to support general conclusions. The dataset contains only 51 synthetic instances, with 33 used for training and 10 for testing. All instances have 20 requests and four homogeneous vehicles.This is a narrow setting for evaluating a learning-based optimization method. It remains unclear whether the model can generalize to larger problems, different fleet sizes, or different demand distributions. The small test set also makes it difficult to judge the stability of the reported improvements. Experiments across multiple problem sizes, additional random seeds, and more diverse instance distributions would make the results considerably more convincing.

  3. The improvement in final solution quality is limited. Although the proposed method substantially reduces the time to the first feasible solution, the final objective values are nearly identical for eight of the ten test instances. The proposed approach produces a better objective on one instance, while cold start performs better on another. The reduction in optimality gap is useful, but the paper should more clearly separate improvements in feasible-solution discovery, final objective values, and solver bounds. I would also encourage the authors to clarify the abstract's reported 91.4% recall, since this corresponds to the GNN-only variant. The complete proposed method achieves 82.05% recall after refinement.

  4. This paper has relatively poor presentation, the manuscript is one page short, and the text as a whole lacks a discussion of the motivation and the core research questions.

Given these shortcomings, I would like to assign a score of 1 and reject this paper.

Questions for authors

Please see Weakness.

Reviewer_ZAeHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies learning-assisted primal search for the dial-a-ride problem. It constructs a heterogeneous graph containing arc variables, continuous state variables, constraints, passenger requests, and vehicles. The learned arc-selection scores are transformed into confidence-aware search guidance and incorporated into variable hints and complementary neighborhood searches. Candidate solutions are passed to the MIP solver for verification and continued optimization. Across ten evaluated instances, the prediction-centered parallel configuration reduces mean time to the first feasible solution by 51.1% and mean final optimality gap by 33.1% relative to cold start.

Critical strengths
  1. The solver interface has a good design. Predictions guide auxiliary searches, while the unrestricted model retains responsibility for feasibility checks and global bounds.
  2. The prediction results report meaningful tradeoffs. Route refinement improves AP from 0.1264 to 0.4141 while reducing recall from 91.36% to 82.05%.
Critical weaknesses
  1. The formulation does not guarantee pickup before delivery. The ride-time constraints are inconsistent. Equation (20) in Appendix A adds the pickup service time, while Equation (48) in Appendix F subtracts it. More importantly, the constraints in Appendix A allow a passenger to be dropped off before being picked up. The pairing, flow, and load constraints do not prevent this. A simple three-request example can satisfy all the listed constraints while violating the required pickup order.
  2. The experiments do not show which parts of the method lead to the reported improvements. Table 1 compares the prediction performance of GNN only, Proposed, and Root LP, but Table 2 does not compare them under the same search configuration. Route recovery also includes insertion, relocation, and exchange moves, which may contribute to the results. It is therefore unclear how much the learned scores help beyond route recovery and parallel search.
Questions for authors
  1. The title on OpenReview differs from the title in the PDF. Could you clarify which title is intended?
  2. What constraints in the actual implementation enforce pickup before delivery? Does the code use Equation (20) (in Appendix A) as printed? Have the training labels and reported solutions been checked by an independent DARP feasibility validator?
  3. How do GNN only, Proposed, and Root LP compare when used to guide the same search with the same computational resources? Could you also report results with and without request and vehicle nodes, and with and without confidence weighting?
  4. What search parameter values are used, how many solver instances run in parallel, and how many threads does each use? Does route recovery produce a complete feasible solution?
Reviewer_hz1KOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors train a heterogeneous GNN to guide primal search for the dial-a-ride problem (DARP). The graph includes arc variables, continuous state variables, constraints, requests, and vehicles. Predicted arc scores are refined using route information to resolve ambiguous assignments among identical vehicles, then used in variable hints and neighborhood searches. The original MIP handles feasibility checks and global bound computation. The evaluation uses 51 synthetic instances, with 20 requests and four vehicles each; ten instances are held out for testing. Refinement improves AP but reduces recall. Compared with cold start, prediction-centered parallel search reduces mean first-feasible time by 51.1% and mean final gap from 5.608% to 3.754%. Final objectives agree to two decimal places on eight of the ten test instances, so the clearest gains are in finding an initial feasible solution and reducing the final gap.

Critical strengths

The graph representation is well suited to DARP. It uses separate nodes for requests and vehicles and distinguishes arc variables from continuous variables. This captures problem-specific relationships that generic variable–constraint graphs, such as those in Neural Diving and Predict-and-Search, may miss.

Critical weaknesses
  1. I am not yet convinced that score refinement helps the solver. AP is measured against a particular reference solution whose global optimality is not guaranteed. Better agreement with that solution does not necessarily lead to better search, and refinement also lowers recall. The solver experiments compare the proposed configurations with cold start, but do not show what happens when the same search uses raw GNN scores. Without that comparison, I cannot tell how much the refinement step contributes to the reported gains. This is a significant omission because refinement is presented as one of the main contributions.

  2. All experiments use 20 requests and four vehicles, so I cannot tell how the method behaves on larger problems. This matters here because the graph includes vehicle-indexed arc variables and their constraints, and the search uses multiple copies of the MIP. The extra computation and memory could offset the search-time savings as the problem grows. Results at a single size do not establish where this trade-off becomes a limitation.

Questions for authors

Q1. How much does score refinement contribute to solver performance? A comparison of raw and refined scores using the same GNN, search setup, and compute budget would be helpful, particularly for first feasible time, final objective, and gap. Faster feasibility would be a meaningful improvement even with similar final objectives, while better AP alone is not sufficient.

Q2. Does the speedup over cold start hold for larger instances with more requests and vehicles? Please include preprocessing time and peak memory under the same compute budget. Also, can the model trained on 20 request instances generalize to larger ones without retraining?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.