TL;DR
This paper introduces the Constrained Least-cost Tour (CLT) problem, a new NP-hard routing problem focused on minimizing travel cost (like air pollution exposure) within a specific distance range. They propose novel heuristics for both "weak" tours (allowing edge repetition) and "strong" tours (simple cycles), demonstrating their effectiveness on real-world urban air quality and environmental diversity routing challenges.
What Problem Does This Paper Address?
The authors tackle the challenge of finding optimal routes in urban environments that balance multiple objectives. Specifically, they address the need for routes that are not just the shortest or cheapest, but also fall within a desired range of "weight" (e.g., distance for a runner) while minimizing a "cost" (e.g., air pollution exposure). This is crucial for applications like optimizing running routes to minimize exposure to harmful pollutants, where a runner might want a route that's long enough to be a good workout but not so long that it becomes excessively taxing or time-consuming. Existing problems like the Traveling Salesman Problem with Profits (TSP-WP) often focus on maximizing profit or meeting a minimum threshold, but don't typically incorporate an upper bound on the "weight" or handle edge-based weights and costs in the same way.
Methods
The paper introduces the Constrained Least-cost Tour (CLT) problem, defined on a graph with edge weights and costs, aiming to find a tour from a starting vertex that minimizes total cost while its total weight falls within a given range $[W_1, W_2]$. They also define the Constrained Least-cost Cycle (CLC) problem, which requires the tour to be a simple cycle.
Key methodological contributions include:
- NP-hardness Proof: They prove that CLT is NP-hard, even for a simple path graph, by reducing it from the SUBSET SUM problem. CLC is also shown to be NP-hard.
- Relaxations:
- Continuous Relaxation: They consider a continuous version of the graph where edge multiplicities can be any positive real number. This relaxation can be solved efficiently using Dijkstra's algorithm and provides a lower bound for the discrete CLT problem.
- Connectivity Relaxation: They formulate CLC as an Integer Program (IP) and then relax the connectivity constraint to obtain a lower bound.
- Heuristics:
- Déjà Vu (DjV): A heuristic for the weak CLT problem that leverages the continuous relaxation. It involves traversing a path to a low-cost edge, repeating that edge a specific number of times, and returning to the origin.
- Suurballe's Heuristic (SH): A heuristic for the strong CLC problem that uses Suurballe's algorithm to find pairs of vertex-disjoint paths, forming simple cycles.
- Adaptive Heuristic (AH): An extension of SH that explores a larger solution space by considering more pairs of vertex-disjoint paths.
Datasets
The authors evaluated their algorithms on two distinct datasets:
- Air Quality in London: This dataset represents the road network of London, with edge weights as road distances and edge costs representing predicted nitrogen dioxide (NO2) pollution levels. The pollution data was derived from a Gaussian Process model.
- The Crucible: This dataset is based on a map from the game Warcraft III, where vertices represent grid squares and edges connect passable adjacent squares. The "cost" is defined by the diversity of environment types surrounding a grid square, aiming to find routes that traverse areas with high environmental diversity.
Key Insights and Ideas
- The Importance of Upper Bounds: The CLT problem's novelty lies in its inclusion of an upper bound on the tour's weight, which is crucial for practical applications like fitness or time-constrained travel.
- Edge-Based vs. Vertex-Based Objectives: Unlike many TSP variants that focus on vertex profits, CLT's weight and cost are defined on edges, making it more suitable for modeling phenomena like pollution spread along roads.
- Heuristics as a Practical Necessity: Given the NP-hard nature of the problem, the development of efficient heuristics is essential for real-world deployment, especially for applications requiring quick route computations.
- Bridging Continuous and Discrete Solutions: The DjV heuristic effectively uses insights from a continuous relaxation to guide the search in the discrete graph, showing a common strategy in optimization.
- Suurballe's Algorithm for Cycles: Adapting Suurballe's algorithm for finding disjoint paths proved effective for generating candidate simple cycles for the CLC problem.
Key Results
- Heuristic Performance: The DjV heuristic achieved consistently low-cost tours with an error of approximately 1% compared to the continuous relaxation lower bound on both datasets.
- CLC Heuristics: The Adaptive Heuristic (AH) significantly outperformed Suurballe's Heuristic (SH) on both datasets, exploring a larger solution space and achieving lower costs, though at a higher time complexity.
- Time Complexity: DjV runs in O(n log n). SH has a time complexity of O(m log n), while AH is O(nm log n). The IP-based connectivity relaxation (XR) was significantly slower, often hitting time limits.
- Real-World Applicability: The algorithms were demonstrated on realistic scenarios: minimizing NO2 exposure for runners in London and finding routes through diverse environments in "The Crucible."
Limitations and Future Work
- DjV and Odd Weights: The DjV heuristic, by design, always produces tours with even total weight. This means it cannot find solutions if the required weight range $[W_1, W_2]$ consists solely of odd integers.
- Approximation for CLC: The paper notes that if the cost function does not satisfy the triangle inequality, CLC does not have an $\alpha$-approximation algorithm for any $\alpha \ge 1$ (assuming P ≠ NP). This motivates the focus on heuristics.
- Future Work: The authors suggest extending the problem to consider multiple pollutants, varying human sensitivities to different pollutants, and incorporating uncertainty in forecasting models. They also plan to further exploit the rich problem structure of "running from air pollution."
Summary updated