On the Constrained Least-cost Tour Problem
This addresses route optimization problems with constraints for urban planning applications, though it appears incremental as it builds on existing Travelling Salesman Problems with Profits.
The paper introduces the Constrained Least-cost Tour (CLT) problem, which involves finding a minimum-cost tour in a graph with edge weights and costs while keeping total weight within a specified range, and proves it is NP-hard even for simple paths. It develops heuristic algorithms based on relaxation techniques and demonstrates their application by finding routes that minimize air pollution exposure for walking, running, and cycling in London.
We introduce the Constrained Least-cost Tour (CLT) problem: given an undirected graph with weight and cost functions on the edges, minimise the total cost of a tour rooted at a start vertex such that the total weight lies within a given range. CLT is related to the family of Travelling Salesman Problems with Profits, but differs by defining the weight function on edges instead of vertices, and by requiring the total weight to be within a range instead of being at least some quota. We prove CLT is $\mathcal{NP}$-hard, even in the simple case when the input graph is a path. We derive an informative lower bound by relaxing the integrality of edges and propose a heuristic motivated by this relaxation. For the case that requires the tour to be a simple cycle, we develop two heuristics which exploit Suurballe's algorithm to find low-cost, weight-feasible cycles. We demonstrate our algorithms by addressing a real-world problem that affects urban populations: finding routes that minimise air pollution exposure for walking, running and cycling in the city of London.