Talks and presentations

Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem

October 19, 2024

Talk, 13th International Workshop on Agents in Traffic and Transportation, Santiago de Compostela, Spain

Abstract: In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triangle inequality. Motivated by finding a sufficiently long running route in a city that minimises the air pollution exposure of the runner, we study the Prize-collecting Travelling Salesperson Problem (Pc-TSP) on sparse graphs with non-metric costs. Given an undirected graph with a cost function on the edges and a prize function on the vertices, the goal of Pc-TSP is to find a tour rooted at the origin that minimises the total cost such that the total prize is at least some quota. First, we introduce heuristics designed for sparse graphs with non-metric cost functions where previous work dealt with either a complete graph or a metric cost function. Next, we develop a branch & cut algorithm that employs a new cut we call the disjoint-paths cost-cover (DPCC) cut. Empirical experiments on two datasets show that our heuristics can produce a feasible solution with less cost than a state-of-the-art heuristic from the literature. On datasets with non-metric cost functions, DPCC is found to solve more instances to optimality than the baseline cutting algorithm we compare against.

Distributionally Robust Routing Problems

December 11, 2023

Talk, Warwick Postgraduate Colloquium in Computer Science 2023 Winter, University of Warwick, UK

Abstract: Given a probability distribution over the cost function of edges in a graph, a stochastic routing optimisation problem finds a route in the graph that minimises a risk function of the route cost. In practise, it is rare that we have access to the true data-generating distribution over edge costs. Instead, we are given a set of empirical cost observations. From the observations, we can construct a (Bayesian) machine learning model of the costs, then do out-of-sample prediction with our model on new, unseen data. If the observations are noisy or in limited supply - or if our model is misspecified - we might not trust the posterior predictive distribution of the model. In this talk, we discuss routing optimisation algorithms that are robust with respect to an ambiguity set of distributions that are close to the predictive distribution of the model. Real-world applications to air pollution are demonstrated.