Introducing Payphone Tag

There are currently about 1,200 people in Australia running around at all hours, calling public payphones to make their emoji appear on a map.

I am now one of them. My emoji is an ant. 🐜

The game is called Payphone Tag. You call a payphone, enter a PIN, and you “capture” it. Other players can steal it back at any time. The game is only feasible because Telstra made payphones free across Australia in 2021¹.

Chaos reigns as players grapple for emoji dominance

I live in the inner city of Sydney, a payphone Mecca (482 within a 5km radius). My initial play style was opportunistic, nabbing a phone on my way to the shops or the train station. This was not acceptable. My ranking languished. There had to be a better way. I run a couple of times a week - could my runs become raids? Could I use Python to capture as many phones as possible while going for a run?

The goal: Build a tool that gives me a running route of a given length that maximises the number of payphones I can capture.

Spoiler - we can do it! This is what we’ll build

This post walks through how I built this app. If you just want to download the code and run it for yourself, you’ll find it at the bottom!

This is an Orienteering Problem

After some Googling, I realised my silly problem statement was not unique - it’s known as an Orienteering Problem. Orienteering is a game played on foot in which participants are let loose in a given geographic area with a simple goal: score as many points as possible within a time limit.

The “course” has markers (aka “controls”) distributed around, worth a variety of points, and it’s generally not possible to reach all controls within the time limit. Players therefore have to design a route that will yield them as many points as possible. I’ve done some urban orienteering before. It sounds simple, but trying to navigate city streets with an unlabelled map while your body is stealing all the oxygen from your brain is pretty tricky. But fun!

A map from an orienteering course I did once in Surry Hills - I didn’t do very well on account of having a stitch for a lot of it.

Anyway - the orienteering problem is a type of problem known as a “combinatorial optimisation problem” (COP) - meaning there’s a finite (but often extremely large) set of possible solutions (i.e. routes), built from combinations of discrete elements (i.e. controls), and you want to find the best solution. The famous Travelling Salesman Problem is probably the best-known type of COP.

They are very tricky to solve because the number of possible solutions grows exponentially or factorially as you scale up the number of choices. As an example, with 50 points to choose from, there are 10⁶⁴ candidate routes for an orienteering problem - not something you can crunch on your laptop (understatement). There’s therefore a whole world of maths and tools designed to solve combinatorial optimisation problems as quickly and effectively as possible.

Given our payphone problem is a form of orienteering problem, we should be able to lean on existing solver tools to find a route.

First, we need a navigation engine

To come up with an optimal route, our solver is going to need to know the distance from every payphone to every other payphone. Given I can’t fly, we can’t use the straight-line distance - we need the walking distance between the payphones.

Using straight lines allows me to hit 27 payphones over 7km - but also requires me to teleport through a lot of buildings.

Thankfully, there’s a brilliant open-source tool called OSRM that can help us. OSRM uses data from OpenStreetMap (OSM) to solve a variety of navigation problems - most usefully for us, it can calculate what’s known as a “Travel Matrix”, a grid of travel times/distances between every point in a set.

OSRM performance is pretty incredible, and it’s super easy to self-host. In a test on my laptop, generating a travel distance matrix for my nearest 1000 payphones took just 2.53 seconds - that’s a million distance calculations!

Once we’ve downloaded OSM data for my state (NSW, Australia) from Geofabrik, and run the OSRM preprocessing steps (see the README for instructions), we’ve got a local routing engine ready to go. Let’s test whether it can generate us a walking route from Central Station to Centennial Park in Sydney:

import osrm

OSRM_PATH = "routing/nsw_osm"
engine = osrm.OSRM(OSRM_PATH)

CENTRAL_STATION = (151.2064851294897, -33.882673166666244)
CENTENNIAL_PARK = (151.22782798376957, -33.89732781749257)

params = osrm.RouteParameters(
    coordinates=[CENTRAL_STATION, CENTENNIAL_PARK],
    steps=True,
    annotations=["speed", "duration"],
    geometries="geojson",
)
route = engine.Route(params)["routes"][0]
print(f"Route: {route['legs'][0]['summary']} ({route['legs'][0]['distance']:.1f} m)")

Route: Devonshire Street, Lang Road (3115.3 m)

Nice!

Preparing the input data for our solver

Once I had a working routing engine, I needed to prep the data for it: first we pull the list of payphones from the Payphone Tag server and filter out any I’ve already captured. Then we find the closest phone to my apartment, which will be the starting point for every run. Next, we remove anything more than 8km away (I’m not running to Queensland). This filtering step is what makes the problem space small enough that the solver can actually finish before the heat death of the universe. This gets us down from ~13k payphones to 143 - much more tractable. Finally, we call the OSRM Table API (docs) to build a distance matrix between every phone that was left.

Once that was done, we had everything we needed to solve the problem:

1. A list of payphones we could visit;
2. A starting payphone; and
3. A matrix containing the travel distance between every pair of payphones.

It’s time to solve the problem!

The solver

As I mentioned above, we can’t brute-force this thing, even with just 143 payphones. Instead we’ll use a constraint programming solver from the OR-Tools library called CP-SAT. You give it variables, rules, and what you want to maximise, and it comes up with a solution.

In the context of our problem, we have:

The variables:

• Do I visit this payphone?
• Do I travel directly from phone A to phone B?

The rules:

• I have to start at my nearest payphone;
• I can only visit each phone once;
• The route has to be one continuous path (no teleporting); and
• The total distance can’t exceed my run budget.

The objective: visit as many payphones as possible. Every phone is worth 1 point.

I don’t want to run any legs that are longer than 1km, so we mark those legs as unreachable. This has the nice bonus of dramatically cutting down the number of possibilities the solver has to consider.

Finally, you’ll see references in the code to a “sink” - this tells the solver that we don’t need to end where we started. I added that because I’m happy to catch a Lime bike home after my run. Definitely a good use of my time and money.

The edited code below shows how we configure the solver with our variables, rules, and objective.

def solve_cp_sat(
    start_idx: int,
    all_indices: set[int],
    dist: list[list[float]],
    budget: float,
    max_travel_distance_per_leg_metres: float = 1000.0,
    #...
) -> list[int] | None:
    # Prep work omitted, including code that marks any leg longer 
    # than the per-leg cap as UNREACHABLE shrinking the search space
    # the solver has to explore.
 
    # The CpModel object is the container for all decision variables, constraints, and
    # the objective.
    model = cp_model.CpModel()
 
    # Variable 1: for each phone, a Boolean: 1 = included in the route, 0 = skipped.
    # The start phone is fixed to 1 — we always depart from there.
    is_visited = [model.new_bool_var(f"v_{i}") for i in range(num_phones)]
    model.add(is_visited[start_local] == 1)
 
    # --- Circuit constraint ---
    # `add_circuit` enforces our "one continuous path" rule: the selected arcs must form
    # a single closed tour covering every node exactly once. We build the arc list in
    # three stages.
    DUMMY = num_phones  # fictional "sink" node, explained in stage 3
 
    arcs: list[tuple[int, int, cp_model.BoolVarT]] = []
 
    # Stage 1 — self-loops for unvisited nodes. `add_circuit` requires every node to
    # appear in the tour, so phones we skip get a self-loop (i → i) that's active when
    # is_visited[i] == 0.
    for i in range(num_phones):
        arcs.append((i, i, is_visited[i].negated()))
 
    # Stage 2 — Variable 2: for every reachable pair (i, j), a Boolean arc t_i_j.
    # Setting t_i_j = 1 means the route goes directly from phone i to phone j.
    # Unreachable pairs (legs > 1km) are skipped entirely.
    travel: dict[tuple[int, int], cp_model.BoolVarT] = {}
    for i in range(num_phones):
        for j in range(num_phones):
            if i != j and scaled_dist[i][j] < UNREACHABLE:
                lit = model.new_bool_var(f"t_{i}_{j}")
                travel[(i, j)] = lit
                arcs.append((i, j, lit))
 
    # Stage 3 — dummy sink node to allow an open-ended route. `add_circuit` demands a
    # *closed* tour, but unlike orienteering we don't need to return to start. We solve
    # this by adding a fictional DUMMY node: every real node has an arc leading to it
    # (representing "this is the last stop"), and the DUMMY connects back to start to
    # close the circuit. Exactly one exit_i will be 1 in any valid solution — that's
    # where our route actually ends.
    exits_to_sink = [model.new_bool_var(f"exit_{i}") for i in range(num_phones)]
    for i in range(num_phones):
        arcs.append((i, DUMMY, exits_to_sink[i]))
 
    dummy_to_start = model.new_bool_var("dummy_to_start")
    model.add(dummy_to_start == 1)  # always active — just closes the loop
    arcs.append((DUMMY, start_local, dummy_to_start))
 
    model.add_circuit(arcs)
 
    # Budget rule: total distance of active travel arcs must not exceed the budget.
    model.add(
        sum(scaled_dist[i][j] * travel[(i, j)] for (i, j) in travel) <= scaled_budget
    )
 
    # Objective: visit as many phones as possible.
    model.maximize(sum(is_visited))
 
    # Omitted: warm-start hint, solve, and route reconstruction

Rendering the solution

We’re almost there!

The solver has given us a list of payphone IDs - but if I’m going to run between them, it’d be handy to know the actual best path between each pair of payphones. Thankfully, OSRM can generate a path between any two points. We just call engine.Route(params) for every pair of payphones in our route, which gives us a GeoJSON geometry for each leg.

It’s nice to know the optimal route, but I can’t take a GeoJSON file on a run…

Finally, a GeoJSON file is not going to help me when I’m running down the side of the road. So our last step is to generate a simple HTML page we can open in any browser to render the route. I uploaded mine to Cloudflare Pages so that I could access it on my phone when out for a run.

The results

Running our script we get the below output:

(.venv) declan@Declans-MacBook-Pro payphone-router % python payphone_router.py 
Excluding payphones held by player 'GoldenFalcon' (id 5310)
Also excluding payphones held by cell 242 members (2 cell-mates)
Fetched 13696 active payphones from the Payphone Tag server.
Filtered to 241 payphones within 8000 metres of home.
Using start payphone 2379 (-33.89675, 151.18609)
Distance matrix calculated in 1.11s.
Running solver to find optimal route...
Solver finished with status OPTIMAL
Total route distance: 6868 m (6.87 km) across 25 payphones.

It works!

Here’s the optimal solution - in a 7km run I can capture 25 payphones.

You might be wondering why the optimal route doesn’t go into the CBD, where payphones are densest. It’s because I filtered out any payphones north of Central. The payphones at Central and in the CBD are the most hotly contested in the game. People clearly love to play on their lunch break and their commute home. I’m not wading into that.

At this stage, I’d written a lot of code, but hadn’t captured any payphones. It was time to go for a run.

My run

My little ant emoji crawling all around the map

Over 6.4km I captured 24 phones.² Somewhat surprisingly, all of them were in perfect working order.

As I ran from payphone to payphone, stressing about how slow my split was gonna be from the stopping and dialling, I thought about all the other important problems constraint optimisers had solved: hospital scheduling, supply chain logistics, package delivery. I smiled knowing that the CP-SAT algorithm had finally found its truest calling.

As soon as I got home I checked my ranking - I was 64/1063.

Bonus photo of my fave payphone from the route: on the platform at Macdonaldtown station.

If you’d like to run this yourself, the Python script and webpage template are available and documented here.

Just don’t steal my payphones.