Planning the shortest delivery round: bounds for the travelling salesman problem

AI HL Solid Also in: Calculus

Research question

For [a real delivery or visiting round with 8–10 stops], how close are the nearest-neighbour upper bound and the deleted-vertex lower bound, and how does the best route I can find compare with the route actually used?

Adapt it: change the place, the data or the comparison until the question is yours.

Why it makes a good exploration

The travelling salesman problem cannot be solved quickly for large networks, so planners use bounds. Applying them to a real round — a newspaper route, a club minibus, a grandparent's shopping trip — makes the algorithms practical.

The mathematics you'll need

Complete weighted graphs and distance tables
Nearest-neighbour algorithm for an upper bound
Deleted-vertex algorithm for a lower bound
Why exhaustive search is impossible for large n (factorials)

Course labels show where a technique sits; using maths from outside your course is fine if you explain it clearly and say it is new to you.

Where the data comes from

Stops and road distances or times from an online map.

OpenStreetMap — Free map with exact coordinates of schools, hospitals, shops and stations; export or read off coordinates.

Cite every source in a footnote where you use it and in your bibliography. Check the licence of any dataset you download.

A possible outline

Build the table of shortest distances (not direct roads only).
Compute upper bounds from several starting points.
Compute lower bounds by deleting different vertices.
Find the best tour you can and compare.
Reflect on time vs distance and traffic.

Pitfalls that cost marks

Using a table that does not satisfy the triangle inequality.
Only one start vertex.
Too many stops to handle by hand without technology.

Showing personal engagement

Use a round someone you know actually does.
Time the optimised route.
Discuss how delivery companies do it at scale.

See Criterion C: personal engagement for what examiners look for.

Taking it further

Write or use a program to find the exact optimum for your small network and compare with the bounds.

Turn this idea into your IA

Plan this IAOpens the planner with this question, the maths and data sources filled in. Desmos workspacePlot your data, fit models and keep your graphs with your plan. AI feedback on a draftCriterion-by-criterion feedback with evidence from your own text. Coaching, not rewriting. Examiner reviewPete, a practising IA examiner, reads your draft and talks it through with you (€100).