Four different approaches to the same routing problem, implemented in C and measured against each other — a naive baseline, a construction heuristic with local search, a time-limited metaheuristic, and an exact solver.
The point of the project is not to solve the VRP. It is to find out how close a fast heuristic gets to a provably optimal answer, and to build the machinery that can tell you the difference.
Built for an algorithms course during an exchange semester at Białystok University of Technology, then cleaned up and documented as a standalone project.
Vehicles leave a depot, visit a set of clients, and return. Each vehicle carries at most maxClientsPerVehicle clients, every client must be visited exactly once, and the total distance travelled should be as small as possible.
Finding the true optimum is factorial in the number of clients. That is the whole tension the project explores.
| Approach | Idea | Cost |
|---|---|---|
| Naive sequential | Visit clients in input order. Deliberately bad — it exists to be the reference point | instant |
| Nearest Neighbour + 2-opt | Greedily build a route, then repeatedly uncross pairs of edges until no improvement remains | fast |
| ILS + 2-opt | Iterated Local 搜索: perturb the current solution, re-optimise with 2-opt, keep the best; inter-route swaps for the multi-vehicle case; stops on a time budget | bounded by the clock |
| Exact backtracking | Enumerate every permutation with pruning. Guarantees the optimum | factorial — only viable for small single-vehicle inputs |
The exact solver is not a competitor. It is the ruler — for small instances it tells you what the true optimum is, so the heuristics can be judged rather than merely compared to each other.
On the bundled 9-client single-vehicle instance:
| Algorithm | Valid | Distance | Time (s) |
|---|---|---|---|
| Naive sequential | ✓ | 47.208 | 0.000 |
| Nearest Neighbour + 2-opt | ✓ | 29.866 | 0.000 |
| ILS + 2-opt | ✓ | 29.866 | 2.000 |
| Exact backtracking | ✓ | 29.866 | 0.000 |
Two things fall out of this table.
The cheap heuristic found the optimum. Nearest Neighbour followed by 2-opt landed on 29.866 — the same value the exact solver proves is optimal — in immeasurably little time. The naive baseline travels 58% further for the same set of clients.
ILS spent two seconds to confirm what 2-opt already had. It did not do worse, but on an instance this small there was nothing left to find. That is the honest reading: a metaheuristic earns its budget on hard instances, not on every instance. Reporting it as a win would have been the easy lie.
Every route produced by every algorithm passes through a separate validator before it is reported. The validator does not trust the solver that produced the route:
- each route starts and ends at the depot;
- each client is visited exactly once — none skipped, none duplicated;
- vehicle capacity is respected;
- the distance the solver stored is recomputed from scratch and compared.
That last check is the one that matters. A routing bug that shortens a route by silently dropping a client is invisible if you only look at the reported distance — it just looks like a better result. Recalculating independently is what makes the comparison table trustworthy.
Reference optima in docs/optimal_solutions.pdf are used only to report a percentage gap after the fact. They never influence route construction.
./task3 --plain < input/in.txt # distance + route lines only — machine-checkable
./task3 < input/in.txt # full comparison table, timings, validation detail, reference gapThe split exists because the two audiences are different: an automated checker wants parseable output, a human reading the results wants the reasoning.
C11, no external dependencies beyond libm.
gcc -Wall -Wextra -std=c11 \
main.c input.c distance.c validation.c heuristic.c exact.c \
-o task3 -lmCI compiles with -Wall -Wextra -Wpedantic and runs the sample instance on every push.
clientCount vehicleCount maxClientsPerVehicle
client1_x client1_y
...
clientN_x clientN_y
depot_x depot_y
The depot is node 0; clients are 1..clientCount.
main.c program flow, output modes
input.* parsing
distance.* distance matrix and route length
validation.* independent solution checks
heuristic.* baseline, Nearest Neighbour, 2-opt, ILS (535 lines — the bulk of the work)
exact.* backtracking with pruning
input/ sample and test instances
output/ example outputs in both modes
docs/ implementation notes and reference values
Roughly 1,300 lines of C across six translation units, split so that the solver, the checker and the I/O never depend on each other's internals.
MIT — see LICENSE.
Author: Ali Erdem Gedik · github.com/aeg58 Coursework — algorithms, Białystok University of Technology.