Research map / Learning theory and algorithms / Combinatorial and search optimization
Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an end-to-end neural combinatorial optimization model (MatNet-based encoder with POMO/REINFORCE training) for the min-max regret robust TSP and CVRP under budget uncertainty, using a pre-trained TSP solver to compute worst-case regret rewards.
Problem
Robust routing (TSP and CVRP) with uncertain travel times under the min-max regret criterion and budget uncertainty sets, where evaluating a route requires solving an inner worst-case TSP that is costly across many instances.
Approach
Treat robust routing as a DRL problem: encode the upper and lower travel-time matrices separately with MatNet, decode routes autoregressively, and use the max-regret reward computed via the worst-case scenario (Theorem 1) solved by a pre-trained neural TSP solver, with POMO-style shared-baseline REINFORCE training.
Key results
- On RTSP with 20 nodes and M=100, the method with x128 augmentation reaches 4.079 objective (0.02% gap) in 9.6 s versus 0.3 s without augmentation at 0.54% gap, while exact BC/BD take up to hundreds to thousands of seconds.
- Without instance augmentation, the method's gaps stay below 2.6% on RTSP instances, solving in under one second per instance.
- On RCVRP with 50 nodes, the method with x32 augmentation attains the best reported objectives (0.00% gap by definition) while BC/BD have gaps up to 77% within the time limit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use instance augmentation ×128 instead of the unaugmented model | RTSP neural method · R-50-1000 | Obj: 9.9870 -> 9.8536 | Helped |
| Use instance augmentation ×32 instead of no augmentation | RCVRP neural method · R-20-100; R-20-1000; R-50-100; R-50-1000 | Obj: 5.3130 -> 5.1620; 4.96790 -> 4.78990; 12.2270 -> 11.9030; 11.95765 -> 11.46090 | Helped |
| Encode upper and lower bound matrices separately and sum their node embeddings rather than blend the matrices (ablation) | RTSP neural method · R-40-100 | Obj: 8.0640 -> 7.9610; 7.9095 -> 7.8985; 7.8760 -> 7.8600 | Helped |
| Encode upper and lower bound matrices separately and sum their node embeddings rather than fuse them through an MLP (ablation) | RTSP neural method · R-40-100 | Obj: 8.0080 -> 7.9610; 7.9045 -> 7.8985; 7.8645 -> 7.8600 | Helped |
| Replace the pretrained TSP solver with CMA-ES (ablation) | RTSP neural method · R-20-100 | Obj: 4.0140 -> 4.0430; 3.9895 -> 3.9925 | Hurt |
| Replace the pretrained TSP solver with LKH (ablation) | RTSP neural method · R-20-100 | training time: ≈1 min / epoch -> ≈7.5 min / epoch | Hurt |
| Use the pretrained TSP model instead of LKH (ablation) | RTSP neural method · R-20-100 | Obj: 4.0135 -> 4.0140; 3.9905 -> 3.9895 | Mixed |
| Use the proposed RTSP model rather than EGA | RTSP · R-50-1000 | Obj: 9.8234 -> 9.8536 | Hurt |
| Use the proposed RCVRP model with ×32 augmentation rather than the exact baseline | RCVRP · R-20-100 | Obj: 5.2855 -> 5.1620 | Helped |
Surprising findings
- LKH and CMA-ES as built-in worst-case TSP solvers give no clear advantage over the pre-trained neural TSP solver in solution quality, despite higher training time.
Limitations
- Scale limited to about 20 nodes (small) and 50 nodes (large) by GPU memory and POMO constraints.
- Applicable only to problems satisfying the max-regret worst-case theorem (budget uncertainty with the Theorem 1 property).
- Reward relies on an approximate pre-trained TSP solver; final objectives are recomputed with Gurobi.
Experimental setup
Datasets: randomly generated RTSP instances (R-N-M following Montemanni et al.) randomly generated RCVRP instances
Benchmarks: RTSP instances R-20/30/40/50 with M=10, 100, 1000 RCVRP instances R-20 and R-50
Metrics: average objective (max regret) gap to best-known solving time per instance
Baselines: Branch-and-Cut Benders Decomposition SA-based heuristic iDS EGA LKH CMA-ES
Builds on: MatNet POMO REINFORCE Montemanni et al. worst-case scenario theorem
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.89)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.89)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.89)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.88)
- DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems (ICML 2024 · similarity 0.88)
- GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.