Abstract
This paper introduces the Explainable Optimal Meeting Point (X-OMP) framework, an iterative, human-in-the-loop approach for urban planning. Unlike traditional black-box optimization, X-OMP identifies minimal real-world modifications—such as travel subsidies or infrastructure changes—to align mathematical optima with user preferences. We propose efficient search algorithms in the instance space, including Best-First Search (BestFS) and Breadth-First Search (BrFS) with pruning. Evaluations on synthetic and real-world Kyoto road networks demonstrate that our framework effectively generates actionable explanations, significantly outperforming baseline methods in scalability and search efficiency.
Introduction
In urban planning, finding an "optimal" meeting point is rarely a purely mathematical exercise. While a computer might suggest a location that minimizes total travel time (min-sum), a human planner might reject it as "unfair" if it imposes an excessive burden on a specific individual (min-max). Standard combinatorial optimization often acts as a black box, providing solutions without context or a clear path for adjustment when the result is unsatisfactory.
To bridge this gap, we formalize the Explainable Optimal Meeting Point (X-OMP) problem. This framework treats decision-making as a search through an "instance space," identifying the smallest set of real-world changes—such as offering travel coupons or adding new transit links—that transform a problematic scenario into one where the mathematical optimum aligns with the user’s goals.
The X-OMP Framework
The X-OMP framework consists of four primary components designed to facilitate an iterative dialogue between the system and the human planner:
- Solver: An algorithm that identifies standard optimal meeting points based on current parameters.
- Supervision: A human-in-the-loop signal (e.g., a binary "Yes/No") indicating whether the current solution meets qualitative criteria like fairness.
- Explanation Generation: Representing the delta between the initial state and the desired state as a set of combinatorial objects (e.g., travel subsidies).
- Instance Search: An automated method to navigate the space of possible problem variations to find the most efficient explanation.
Search in the Instance Space
Because exploring every possible variation of a graph is NP-hard, we developed several specialized search algorithms to find the "cheapest" explanation (the minimum set of changes) efficiently:
- BrFS (Breadth-First Search) with Pruning: This method explores neighboring instances while aggressively cutting off search branches that exceed a predefined cost threshold.
- BestFS (Best-First Search): Utilizing cost-based heuristics, BestFS prioritizes the most promising changes to find optimal explanations more rapidly than exhaustive search.
- GnT-Edit: A "Generate-and-Test" approach tailored for scenarios involving structural graph modifications, such as adding new roads or transit routes.
Experimental Evaluation
We evaluated the framework using both synthetic road networks (20 to 60 vertices) and a real-world dataset of the Kyoto road network extracted from OpenStreetMap. The synthetic tests focused on the scalability and efficiency of the search algorithms, while the Kyoto dataset demonstrated practical applications in tourist meeting point planning.
Key Insights
- Efficiency and Scalability: BestFS and BrFS with pruning significantly outperformed naive methods. Pruning allowed the system to find solutions in seconds that would otherwise take orders of magnitude longer, even as the number of customers ($k$) increased.
- Actionable Explanations: In our framework, an explanation is a set of actions. For instance, if a meeting point is unfair, the system might suggest: "If you provide a free taxi coupon for User A, this meeting point becomes fair for everyone."
- Prevalence of Negative Instances: Our tests revealed that 70–80% of randomly generated instances were "negative" (unfair), highlighting the necessity of automated search to find viable planning alternatives.
Conclusion
The X-OMP framework demonstrates that "explanations" in optimization can be more than just text; they can be actionable counterfactuals that guide human decision-makers. While current experiments were limited to graphs of approximately 100 vertices, the success of cost-based pruning suggests that this approach could be scaled further or applied to other complex combinatorial problems like vehicle routing and facility location.
Summary updated