Updated 12 October 2026 · By Pete Bromfield, former Head of Maths with IB examining experience

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?

Make it yours, then agree it with your teacher.

Next step: plan this IA free — the planner opens with this question filled in. For feedback on your own draft, the IA package (€39 once) gives you 5 AI feedback credits and every annotated exemplar in full.

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)

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.

Real data for this idea

Primary source: OpenStreetMap. Read off coordinates (right-click, “Show address”) or use Export for a small area. Licence: Open Database Licence: credit “© OpenStreetMap contributors”; data you build from it must be shared alike.

OpenStreetMap is under the Open Database Licence: credit “© OpenStreetMap contributors”. Links checked October 2026; we link to the data and never copy it. More free data sets.

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.

Which course is it for?

Course	Fit	Maths to lean on
AA SL	Not a natural fit	The core technique sits in the AI course or at HL; an AA SL student could use it only as clearly explained new mathematics.
AA HL	Not a natural fit	The mathematics is mainly from the AI course; at AA HL the exploration would need an AA-level approach (calculus, proof or probability theory) to reach the top of Criterion E.
AI SL	Not a natural fit	The mathematics is mainly AA or HL (calculus or proof beyond AI SL); an AI SL version would need a data-driven, technology-based approach.
AI HL	Good fit	Complete weighted graphs and distance tables; Nearest-neighbour algorithm for an upper bound

Level: Solid. Needs some independent work beyond class examples. See how the IA differs between AA and AI, SL and HL.

How this idea reaches the top bands

Reflection (D)

For this idea, start with the weak points: using a table that does not satisfy the triangle inequality; and only one start vertex. Say how each one affects your answer.

Use of mathematics (E)

HL: 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), each explained in your own words and carried out correctly.

How networks & graphs explorations reach the top bands in general: Networks, graphs & algorithms IA ideas. Guides: A · B · C · D · E · self-grade sheet.

Taking it further

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

Extending it for HL

Add an HL technique the question genuinely needs: what an HL networks & graphs exploration adds.

See a complete IA, marked

What is the quickest way to deliver a leaflet to every house on my estate? (AI HL) is a complete networks & graphs exploration, marked on every criterion.

Frequently asked questions

Which IB Maths course is this IA idea for?

It works for AI HL. We rate it Solid: it needs some independent work beyond class examples.

What mathematics does this IA use?

Complete weighted graphs and distance tables, nearest-neighbour algorithm for an upper bound, deleted-vertex algorithm for a lower bound and why exhaustive search is impossible for large n (factorials).

Where can I get data for this IA?

Stops and road distances or times from an online map. Checked sources and tools: OpenStreetMap.

Turn this idea into your IA

The planner opens with “Planning the shortest delivery round: bounds for the travelling salesman problem” filled in: the question, the maths and the data sources.

Plan this IA free

Your plan is kept in this browser. A free account keeps it with your drafts on any device: Join free · Sign in

Also: free IA self-check · A–E checklist (PDF) · have a draft? AI feedback or a review with Pete (€100)

Writing it up: how to write a Maths IA, step by step · structure and format · mistakes that cost marks · annotated exemplars, marked on every criterion