Stochastic Travelling Salesman

Stochastic travelling salesman

A van leaves a depot, serves four customers and returns to the depot. On each attempt, a road is blocked with probability 0.10. The exception is the road between B and C, which is blocked with probability 0.35. A blocked attempt costs 2 and leaves the van where it was. A successful drive costs the Euclidean distance.

location	depot	A	B	C	D
position	(0, 0)	(0, 3)	(4, 3)	(4, 0)	(2, −2)

Model

State: (current location, customers served), 34 states in total.
Actions: depot, A, B, C, D.
Transitions: a permitted move reaches its destination with probability 1 − p and leaves the van in place with probability p.
Moves that are not permitted, such as revisiting a customer or returning to the depot early, leave the van in place at a cost of 50.
Discount factor: 1. The episode ends at ("depot", ("A", "B", "C", "D")).

import aniate as an
from route import brute_force, follow, route_model

m = route_model()
sol = m.solve()
sol.start_value                      # -17.6227
follow(sol)                          # ['D', 'C', 'B', 'A', 'depot']
min(brute_force().values())          # 17.6227, the minimum over all 24 fixed tours

runs = an.simulate(m, sol, episodes=20_000, seed=0)
runs.mean_return, runs.stderr        # -17.599, 0.016
an.check(m, policy=sol).ok           # True

For a fixed tour, the number of failed attempts on each leg follows a geometric distribution. The expected cost of a leg is therefore distance + 2p / (1 − p), and brute_force() applies this formula to every tour.

The solver works on states and has no notion of a tour, yet the policy it returns follows an optimal tour. The tour A, B, C, D and its reverse have the same expected cost, 17.6227. The most expensive tour costs 25.88.

Tests

pytest tests/stsp

test	property verified
`test_solution_equals_brute_force_over_every_tour`	the optimal value equals the minimum over all tours, and the policy follows that tour
`test_simulation_and_check_agree_with_the_model`	the mean of 20,000 simulated tours lies within 5 standard errors of the exact cost; `check` passes; `describe()` is JSON-compatible

Plots

python tests/stsp/plot.py

file	content
`route.pdf`	all roads in grey and the optimal tour as arrows, with each leg labelled by its blocking probability
`overview.pdf`	for 20,000 tours: the cost distribution, the running mean, the cost accumulated over time, and the value martingale

All roads in grey and the optimal tour as arrows, with each leg labelled by its blocking probability.

For 20,000 tours: the cost distribution, the running mean, the cost accumulated over time, and the value martingale.

[View the source on GitHub]