用整数规划求解道路网络最小改动，让用户路线变最优。
Counterfactual Routing Using Integer Programming with Constraint Generation
- 将反事实解释建模为整数规划，逐步添加约束直至精确求解。
- 测试集平均仅9秒完成求解，速度远超第二名（118.8秒）。
- 适合需要快速生成可解释路径调整方案的交通规划场景。
我们提交了IJCAI 2025年‘反事实路径竞赛’（CRC 25）的解决方案。比赛目标是为最短路径问题提供反事实解释，即确定道路网络的最小改动，使用户选择的路线成为最优路径。这可支持类似“若道路X不设自行车道，您的建议路线本就是最优”的解释。我们的方法将问题建模为整数规划，通过迭代生成约束直至获得精确解。在保留测试集上的最终评估中，该方法在解质量上排名第四，但所有实例的求解时间均最快，平均耗时9.0秒，而次快提交平均耗时118.8秒。
原文摘要 · Abstract (English)
We present our submission to the IJCAI 2025 'Counterfactual Routing Competition' (CRC 25). The goal of the competition is to find counterfactual explanations for the shortest path problem. This requires deciding what the minimal changes to a road network would make a route chosen by the user the optimal route. This enables explanations such as "Your suggested route would indeed have been optimal, if road X were not a bicycle path." Our solution models the problem as an integer program, iteratively incorporating constraints until an exact solution is found. In the final evaluation on held-out test instances, our method ranked fourth in solution quality and obtained its solution fastest on every instance, with an average runtime of 9.0 seconds compared to 118.8 seconds for the next-fastest submission.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。