A group optimisation project implementing a Simulated Annealing metaheuristic to solve the Capacitated Vehicle Routing Problem (CVRP). The project explores neighbourhood operator design, stochastic search behaviour, and performance evaluation using TSPLIB benchmark instances. Completed as part of the third‑year university statistics course "Deterministic & Stochastic Optimisation".
- SageMath
- TSPLIB Benchmark datasets
- Jupyter Notebook
- Implementation of Simulated Annealing for CVRP
- Neighbourhood Operators (N1, N2, N1N2)
- Custom parser for .vrp files
- Precomputed Euclidean distance matrix for faster evaluation
- Benchmarking across all instances used (eil22, eil23, eil30, eil33)
The CVRP is a classic NP‑Hard optimisation problem where the goal is to construct minimum‑cost routes that start and end at a depot, visit each customer exactly once, and respect vehicle capacity constraints. Our project implemented a single‑agent stochastic metaheuristic to approximate high‑quality solutions.
We designed two neighbourhood operators:
- N1: swaps two customers within the same route
- N2: swaps customers between different routes A combined variant was also created, N1N2, selecting between the two with equal probability
Simulated Annealing was chosen due to its ability to escape local minima through controlled randomisation. Each method was run for 5000 iterations, with a cooling rate of 0.995, and evaluated over 100 independent runs.
The final report analyses solution quality, operator behaviour, and the trade‑off between exploration and exploitation in stochastic optimisation.
- How to implement a stochastic metaheuristic from scratch
- Design of neighbourhood operators and understanding their impact on search behaviour
- Parsing and structuring TSPLIB CVRP data
- Balancing feasibility constraints with optimisation moves
- Visualising multi-route solutions clearly
- Evaluating stochastic algorithms through repeated runs and performance summaries
This project was completed as a team of three with my specific contributions including:
- Implementing components of the Simulated Annealing algorithm
- Debugging neighbourhood operators
- Designing the final report structure
- Writing the Introduction, Objectives, and Algorithm & Implementation sections of the final report
- All three methods significantly improved route cost compared to the initial greedy solution
- N1 provided stable, incremental improvements
- N2 enabled broader exploration but was more disruptive and inconsistent
- N1N2 consistently produced the best overall performance across all instances
- Simulated Annealing scaled effectively across all instances
- Implement more advanced operators such as cros-exchange
- Tune parameters of SImulated Annealing
- Compare against other metahueristics (Tabu Search, Genetic Algorithm)
- Evaluate Average ratehr than best performance
- Extend to larger datasets