Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913544958640128 |
|---|---|
| author | O'Hara, Patrick Ramanujan, M. S. Damoulas, Theodoros |
| author_facet | O'Hara, Patrick Ramanujan, M. S. Damoulas, Theodoros |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10440 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem O'Hara, Patrick Ramanujan, M. S. Damoulas, Theodoros Data Structures and Algorithms 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. |
| title | Routing on Sparse Graphs with Non-metric Costs for the Prize-collecting Travelling Salesperson Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.10440 |