We close the module with the problem that opened it. In 03-01 we worked out that the order of a van's deliveries has n! possibilities and that brute force dies beyond a dozen stops; in 03-02 we learnt to find the best path between two points, and in 03-03 to decide against an opponent. But none of those techniques solves Diego's full problem: given the map and the day's deliveries, in what order should the van visit them to drive the fewest possible kilometres? It is the famous travelling salesman problem, and it is the perfect example of an optimisation problem: we are not looking for a path in a graph, but for the best among an astronomical number of complete solutions. In this lesson we will learn to formulate it (variables, objective function, constraints), distinguish exact from approximate methods, and build three local search and metaheuristic algorithms that solve NovaMarket's travelling salesman in seconds: hill climbing, simulated annealing and genetic algorithms, validating them against brute force at small size. Then we will apply the same idea to the assignment of orders to the Zaragoza and Getafe warehouses with a capacity constraint, and see how a constraint becomes a penalty. We will finish with the connection that opens module 4: training a machine learning model is, on the inside, also an optimisation problem.

1. What an optimisation problem is: variables, objective function, constraints
2. Exact versus approximate optimisation; local search
3. Preparing NovaMarket's travelling salesman problem: the distance matrix with Dijkstra
4. Brute force as the reference (7 deliveries)
5. Hill climbing by swapping stops: local optima and random restarts
6. A bigger problem: 15 delivery addresses
7. Simulated annealing: the intuition of temperature
8. Genetic algorithms: population, tournament, crossover, mutation and elitism
9. Second example: assigning orders to two warehouses with capacity (constraints as penalties)
10. Comparison table of methods and when to use each one
11. Link to module 4: learning is optimising

An optimisation problem has three components:

Each specific assignment of values to the variables is a candidate solution; those satisfying the constraints are feasible; the feasible one with the best objective is the optimum. The difference from the search of 03-02 is one of perspective: there the object was a path built step by step from the initial state, and the cost accumulated leg by leg; here we work with complete solutions that we evaluate at once with the objective function, and the "path" we care about is not on the map but in the solution space. In 02-01 we said that a utility-based agent chooses the action that maximises a function; the algorithms of this lesson are the machinery for making that choice when there are too many options to list.

Local search starts from a complete solution (good or bad) and improves it step by step by applying small changes, called moves; the set of solutions reachable with one move from the current one is its neighbourhood. The usual metaphor is a landscape: every solution is a point, its objective is the altitude, and the algorithm is a hiker who wants to reach the highest point (or the lowest, if minimising) moving only to neighbouring points. With that image the three algorithms of the lesson are immediately understood: hill climbing always goes up and gets stuck on the first summit; simulated annealing allows itself to go down sometimes in order to escape; the genetic algorithm sends many hikers at once and crosses their routes.

A note on vocabulary: although in the travelling salesman we minimise kilometres, the literature speaks of hill "climbing" out of habit; minimising f is maximising −f, so the idea is the same.

In 03-01, brute force only accepted legs between districts connected by a direct road. Now we can do it properly: the distance between any two stops is that of the shortest path between them, which we compute with the uniform-cost search (Dijkstra) of 03-02, run from every node. The result is a distance matrix with which the travelling salesman no longer depends on the graph's topology. This separation into two layers (Dijkstra/A* for "how to get from A to B", optimisation for "in what order to visit A, B, C…") is exactly how real delivery planners work.

MATRIX[a][b] is the minimum road distance from a to b; for example, MATRIX["Warehouse_Getafe"]["Retiro"] is 17.0 (the A* result from 03-02) and MATRIX["Leganes"]["Vallecas"] is 14.0 even though there is no direct road. The full matrix, in km:

The function route_length is our objective function: it takes a permutation of the deliveries (the decision variable) and returns the kilometres of the closed route. The constraint "each delivery exactly once" is guaranteed by construction, because we will only ever handle permutations.

With 7 deliveries there are 7! = 5,040 permutations: the brute force of 03-01, now over the matrix, gives us the exact optimum that will serve as the yardstick for the approximate methods.

The optimum is 39.0 km (curiously the same one found by the restricted version in 03-01: on this map the best route already used only direct roads). Remember that this number is out of reach for brute force beyond about 12-13 deliveries.

Move: swap two stops of the route. With 7 stops there are 21 possible swaps: that is the neighbourhood. Algorithm: look at every neighbour, move to the best one if it improves the current route, and stop when no neighbour improves ("best improvement" version; the "first improvement" alternative moves to the first neighbour that improves).

In two steps it has gone from 68.5 to 47.5 km, and there it stopped: none of the 21 swaps improves that route, yet the optimum is 39.0. We have reached a local optimum: a summit from which everything you can see around is downhill, even though there are higher mountains further away. It is the structural flaw of hill climbing, and it has three classic remedies:

• Richer neighbourhoods (more possible moves: for example, reversing a segment of the route, the famous 2-opt, which we will use in section 7).
• Random restarts: repeat the climb from many different initial solutions and keep the best. It is simple, parallelises effortlessly and works surprisingly well.
• Sometimes accepting moves that make things worse, which is the idea of simulated annealing.

With 10 restarts it reaches the brute-force optimum. If you repeat the experiment with 20 different starts you will see that about 8 out of 20 end at 39.0, about as many at 39.5 and the rest at worse local optima (46-47.5 km): the probability of hitting it with a single attempt is around 40 %, but with 10 independent attempts it is over 99 %. And the total cost has been 10 × (a few steps × 21 evaluations): about 500 evaluations versus the 5,040 of brute force. With 7 stops the difference is anecdotal; with 30 it is the difference between seconds and centuries.

To give the metaheuristics something to chew on, we generate a larger instance: 15 specific customer addresses scattered around the districts of COORDINATES (03-02), with straight-line distance as an approximation of the real distance (in production we would use the Dijkstra matrix over the street network, exactly as in section 3; the optimisation algorithm does not notice the difference because it only ever looks up dist[a][b]).

The address names carry the district prefix (D04_Vall is the fourth delivery, near Vallecas). With 15 stops brute force would need 15! ≈ 1.3 trillion evaluations; simple hill climbing gets stuck at 51.8 km, and with restarts it reaches 36.45 km, which is (as the other two methods will confirm) the best known value for this instance. Keep that figure as the reference.

Simulated annealing takes its name from metallurgy: a metal heated and cooled slowly crystallises into a minimum-energy structure, whereas cooled abruptly it ends up full of defects. Translated into local search:

• At each iteration one random neighbour is generated (not all of them).
• If it improves, it is always accepted.
• If it worsens by an amount Δ, it is accepted with probability e^(−Δ/T), where T is the temperature. With high T almost everything is accepted (free exploration, jumping between valleys); with low T almost nothing that worsens is accepted (the algorithm behaves like hill climbing and refines the solution).
• T starts high and is reduced little by little (cooling), for example by multiplying it by 0.995 at each iteration.

A few numbers to fix the intuition (probability of accepting a worsening of Δ km at temperature T):

At the start it accepts almost anything; at the end, practically only improvements. As the move we will use 2-opt: pick two positions and reverse the segment between them, which on routes is more effective than the simple swap because it undoes crossings.

From the same 97.6 km initial route on which hill climbing stalled at 51.8, annealing reaches 36.45 km (or 36.84, 1 % worse) in about 1,400 evaluations, accepting along the way a hundred or so moves that made things worse: those "steps backwards" are what allow it to get out of the valleys. Three details of the code deserve attention: the best solution seen is stored separately (the current one can get worse at the end of the hot phase); the temperature is multiplied at every iteration (geometric cooling, the most common); and the number of iterations is set by the cooling rate (from 10 to 0.01 at a rate of 0.995 is about 1,380 iterations). Cooling more slowly (0.999) improves quality at the cost of more time; it is the dial Marta will adjust according to the seconds available before 8 in the morning.

Genetic algorithms are inspired by evolution: instead of one solution that moves, they maintain a population of solutions that reproduces; the best have more offspring, children combine pieces of their parents and now and then undergo mutations. Vocabulary and cycle:

• Individual / chromosome: a solution (a route); its genes are the stops.
• Fitness: the objective (fewer km, fitter).
• Tournament selection: k individuals are drawn at random and the best wins; good ones reproduce more, but bad ones still have some chance, which preserves diversity.
• Crossover: combining two parents. With permutations you cannot copy halves (stops would repeat); order crossover (OX) copies a segment from parent 1 and fills the remaining positions with the missing stops in the order they appear in parent 2.
• Mutation: a small random change (swapping two stops), which introduces novelty and prevents the population from becoming identical.
• Elitism: the best individuals pass unchanged to the next generation, so that the best solution found is never lost.

The population starts with a mean of almost 100 km and in 18 generations (about 1,000 evaluations) its best individual is already at 36.45 km. The final route makes complete geographical sense: it heads out towards Villaverde, covers Vallecas, goes up to Retiro and Arganzuela, comes down through Carabanchel and returns via Leganes. An example of OX crossover so you can see the mechanics: with parents A B C D E F G and G F E D C B A, if the chosen segment is positions 1-2, the child inherits _ B C _ _ _ _ from the first and fills in with G F E D A (the order of the second, skipping B and C): G B C F E D A. No stop is repeated or lost.

Two honest warnings: genetic algorithms are sensitive to their parameters and stochastic. With other seeds, the same configuration ends at 41.3, 43.4, 43.8 or 46.1 km: the population converges prematurely (all individuals look alike and crossover no longer contributes anything). Raising the mutation probability to 0.5 and the population to 150 makes 4 out of 5 runs reach 36.45. Compared with annealing, here the genetic algorithm needs more evaluations for the same result; its advantage shows in problems where there is no natural local move, where evaluation is parallelisable, or where several good and different solutions are of interest.

Let us change problem but not method. Every morning Diego has to decide which orders are picked in Getafe and which in Zaragoza (use case 6). Each order has a different shipping cost depending on the warehouse (because of the destination zone) and a volume in boxes; each warehouse has a daily picking capacity in boxes. Formulation:

• Variables: for each order, "Getafe" or "Zaragoza" (a list of 20 labels; 2²⁰ ≈ 1 million solutions).
• Objective: minimise the total shipping cost.
• Constraint: the sum of boxes assigned to each warehouse cannot exceed its capacity.

The most common way to handle a constraint in local search is to turn it into a penalty: add to the objective an artificial cost proportional to the violation (here, €20 for every excess box). That way every solution is "evaluable", the infeasible ones simply come out very expensive, and the algorithm learns to avoid them.

The naive assignment is the cheapest on paper (€239), but it loads 38 boxes onto Getafe, 6 above its capacity: penalised, it costs 359. Hill climbing moves two centre-zone orders to Zaragoza (the ones that lose least by changing warehouse: €15 and €3 more) and reaches a feasible assignment of €257. Since here the space has "only" 2²⁰ solutions, we can check by full enumeration that €257 is the exact optimum; with 200 orders (2²⁰⁰) that check would be impossible and local search would be the only option.

Two lessons from this example: the penalty must be high enough that no infeasible solution pays off (with €20/box it works; with €2/box the algorithm would rather pay the fine), but not so high that it flattens the differences in real cost and turns the landscape into a plateau; and the same local search skeleton serves problems of a different nature by changing only the representation, the neighbourhood and the objective function.

Marta's decision rule: if the problem is small or has known structure, exact (and there are excellent linear programming solvers, though they fall outside this course); otherwise, hill climbing with restarts as the baseline, simulated annealing when it gets stuck, and genetic when the representation calls for it. And always validate at small size against brute force, as we have done.

We close with the most important connection of the lesson. Remember learn_threshold from 01-02: it looked for the threshold that best separated two classes by trying values. That was already optimisation: variable (the threshold), objective (hits), method (brute force over a grid). Every training of a machine learning model is an optimisation problem: the variables are the model's parameters (a handful in a regression, billions in a large language model), the objective function is a measure of error on the training data (the "loss function"), and the constraints or penalties are the regularisation techniques of 04-06. The difference from this lesson is that, when the parameters are continuous numbers and the loss function is smooth, there is no need to try random neighbours: you can compute in which direction the loss decreases (its gradient) and take a step in it, over and over. That method, gradient descent, is the "hill climbing with a compass" that makes neural networks work, and we will study it in 05-03. Everything you have learnt today about local optima, step size (here, temperature and neighbourhood) and validation will carry over there as is.

• Confusing the local optimum with the global one: a hill climb that "does not improve any further" has not finished, it has got stuck. Restart, change the neighbourhood or use annealing before accepting the solution as good.
• Not validating at small size: before trusting a metaheuristic for 40 stops, check that with 7 or 8 it finds the same optimum as brute force. A bug in the objective function (for example, forgetting the leg back to the warehouse) goes unnoticed without that check.
• Seeds and reproducibility: the methods of this lesson are stochastic. Fix the seed (random.Random(seed)) so you can reproduce results and debug, and always evaluate several seeds before drawing conclusions about a parameter.
• Cooling too fast in annealing turns the algorithm into an expensive hill climb; cooling too slowly wastes time. Start with T₀ of the order of a typical "large" worsening and adjust by watching how many worsening moves are accepted.
• Crossover that breaks the representation: with permutations, a naive crossover produces routes with repeated or missing stops. Use OX or another permutation-preserving operator and check after every crossover that sorted(child) == sorted(parent1).
• Badly calibrated penalty: too low and the "optimal" solution violates the constraint; too high and the algorithm cannot tell feasible solutions apart. Always check excess == 0 in the final solution.
• Forgetting to store the best solution seen in annealing: the current solution can get worse when accepting worsening moves; always return best, not current.
• Optimising the wrong objective: as 02-01 warned, if the cost only measures kilometres, the optimal route may break every time slot. Add to the objective (or as a penalty) everything that matters.

Implement the nearest neighbour constructive heuristic: starting from the warehouse, always go to the nearest pending delivery. Apply it to DELIVERIES with MATRIX and to DELIVERIES15 with DIST15, compare with the known optima (39.0 and 36.45 km) and use it as the initial route for hill climbing. Does the result improve compared with a random start?

Write two_opt_neighbours(route) that generates every route obtained by reversing a segment route[i:j+1] and use it instead of swap_neighbours inside hill_climbing (parameterise the neighbourhood function). Compare, for 20 random starts on DELIVERIES15, how many times each neighbourhood reaches 36.45 km.

Change CAPACITY to {"Getafe": 30, "Zaragoza": 32} and run assignment_hill_climbing again from the naive solution. Which orders move now, what is the final cost and is it feasible? Then lower PENALTY to 2 and watch what happens to the excess of the final solution. Explain the result.

Solution 1.

With the 7 districts nearest neighbour gives 39.5 km (Leganes, Carabanchel, Usera, Arganzuela, Retiro, Vallecas, Villaverde: it goes round the map clockwise and comes back via Villaverde), just 0.5 km from the optimum, and swap-based hill climbing cannot improve it (0 steps): it is a local optimum very close to the global one. With the 15 addresses it gives 37.82 km and a single climbing step takes it to 36.45. A good initial solution saves a lot of work (compare with the 51.8 km of the random start), but on its own it does not guarantee the optimum: local search is still needed, and in general restarts or annealing.

Solution 2.

Output: swap: 1 of 20 starts reach 36.45 km versus 2-opt: 15 of 20 starts reach 36.45 km. Reversing segments undoes crossings in the route, which is the typical source of bad local optima in the travelling salesman, and that is why 2-opt is the standard neighbourhood for this problem.

Solution 3. With {"Getafe": 30, "Zaragoza": 32} the naive solution has 8 excess boxes (399 penalised). The climb moves P008 (centre, 5 boxes) and then P015 (centre, 3 boxes) to Zaragoza, leaving 30 and 30 boxes: €263, feasible, and again it is the exact optimum (check it with itertools.product). With PENALTY = 2, moving P008 to Zaragoza costs €15 more in shipping but only saves €10 in fines (5 boxes × €2), so the algorithm moves nothing and returns the naive assignment (€255 penalised, €239 real) with 8 excess boxes: the penalty is too cheap to represent a constraint that in reality is hard (the warehouse simply cannot pick any more). Moral: the penalty must exceed the largest saving that can be obtained by violating the constraint.

With this lesson we have completed the module's algorithmic toolbox. We have formulated optimisation problems with their three components (variables, objective, constraints), distinguished exact from approximate methods, and built three local search and metaheuristic algorithms: hill climbing, which climbs to the first local optimum and is rescued by random restarts; simulated annealing, which accepts worsenings with a probability that decreases with temperature in order to escape valleys; and the genetic algorithm, which evolves a population through tournament, OX crossover, mutation and elitism. All three have solved the NovaMarket van's travelling salesman problem (39.0 km on 7 districts, validated against brute force; 36.45 km on 15 addresses, where brute force is impossible) over the distance matrix that Dijkstra gave us in 03-02, and the same skeleton has solved the assignment of orders to Getafe and Zaragoza by turning capacity into a penalty. Finally we have seen that training a model is optimising, the idea that links this module with the next two.

This closes module 3. You have travelled the road from the definition of an algorithm and the combinatorial explosion (03-01) to path search with BFS, DFS, uniform-cost and A* on CITY_GRAPH (03-02), decision-making against an opponent with minimax and alpha-beta pruning (03-03) and the optimisation of complete solutions with local search and metaheuristics (03-04). NovaMarket's route planner and order assignment, which in 02-01 were only a formulation, now have working code; in 09-01 you will return to them with more exercises. In module 4, Machine Learning, we will change paradigm: instead of programming the algorithm that solves the problem ourselves, we will give the system historical data (orders.csv, reviews.csv, incidents.csv) so that it learns the rule by itself, and we will see that, on the inside, that learning is a search for the best model in an enormous space, with the same ideas of objective, local optimum and validation you have just mastered. Marta and Diego will move from optimising routes to forecasting demand and detecting fraud.