I'm trying to work out the shortest path to travel to the maximum number of countries on an Avios ticket (or tickets - I have a ton of Avios to burn). For the nerds this is a graph theory problem - very similar to the travelling salesman problem, but traditionally called the covering salesman problem - as I don't need to travel on every flight, but just visit country once.

To begin with, I need to determine all possible flights I can possibly book on an Avios ticket (i.e. all graph vertices). Once I have them, I'll map them to an Avios cost - and report back.

Anyway, I need advice here to help me identify all flights I could notionally book on Avios (we can worry about availability later). There seems to be no complete list. I have swept up all the flights over the last week for these airlines:

• OneWorld: 1. American Airlines (AA) 2. British Airways (BA) 3. Alaska (AS) 4. Cathay (CX) 5. Finnair (AY) 6. Iberia (IB) 7. Iberia Connect (I2) 8. Japan Airlines (JL) 9. Malaysian (MH) 10. Qantas (QF) 11. Royal Air Maroc (AT) 12. Qatar (QR) 13. Sri Lankan (UL) 14. Royal Jordanian (RJ)

I know from personal experience the following are possible through BA: 1. Fiji Airlines (FJ) 2. LATAM (LA) 3. Air Nostum (YW) 4. Loganair (LM).

• Iberia Additional Options: 1. Binter Cararias (NT) 2. Vueling (VY)
• Qatar Additional Options: 1. Avianca (AV) 2. MEA (ME) 3. RwandAir (WB) 4.Virgin Australia (VA)

I'm sure there are some niches I've missed? If it is covered by a main-line flight code, it won't change the result, but I'll still add it in. Anyway - for the above flights - I've made some plots that may interest people – and maybe someone can spot flights I’ve missed:

Plot of All Avios Served Airports - Entire World:
Plot of all routes:
Plot of all Avios Routes on a Spilhaus Projection
Plot of all Avios Routes in Europe
Plot of all Avios Routes North America
Plot of All Avios Routes, South East Asia
Plot of All Avios Routes, Africa
I note my datasource includes flights that are only “technical” flights – e.g. the flights from Cambridge to Copenhagen on BA (I think for AstraZeneca?), so there may exist flights that are not bookable.
My shortest route to visit each country using Avios problem means that I am not interested in “dead ends” in the same country, i.e. flights that are only served by one Avios airport within that country. We will leave the challenge to travel to every administrative region of the world for another time. Future plots remove these airports. This is a plot of the discarded airports:

Routes I model:
Okay, so now we have all the routes we are interested in. We can measure the distance between them. This is a histogram of the distances of all routes:

This is a graph of all the connections between the airports, where the distances between the points is the real space distance between the airports.

Once I hear back from the hive mind, I'll update, but for example, taking flights within Europe:
Here is a solution (~27k miles (so ~120k Avios on the Partner chart?)), I will work on finding the optimum later) that passes through all the countries that partners fly to:
I'll only run the algorithm once I have the remaining Avios bookable flights, but the above reasonable solution for Europe plotted on a map is is: