Route and speed optimisation for a fleet of vehicles on a road network, where vehicles that share an edge at the same speed form a fuel-saving platoon. The two objectives — total fuel cost and total travel time — are in conflict, so the goal is the Pareto front of trade-offs between them.
Six multi-objective metaheuristics (NSGA-II, SPEA-II, PESA-II, MOEA/D, MOPSO, MOSPEAD) are compared against the exact Pareto frontier obtained from a mixed-integer linear model solved with Gurobi.
Each vehicle has an origin and a destination and chooses a route and a per-edge
speed. A higher speed lowers travel time but raises fuel use; forming a platoon
lowers fuel but ties the platoon members to a common speed. The fuel objective sums
the per-edge fuel and subtracts the platoon savings (each of the k − 1 followers in
a k-vehicle platoon saves distance × fuel_rate × reduction_rate); the time
objective sums the free-flow edge times. The full model is in
docs/formulation.md.
| Method | Type |
|---|---|
| NSGA-II | non-dominated sorting genetic algorithm |
| SPEA-II | strength Pareto evolutionary algorithm |
| PESA-II | region-based selection with an adaptive grid |
| MOEA/D | decomposition into Tchebycheff subproblems |
| MOPSO | multi-objective particle swarm optimisation |
| MOSPEAD | decomposition hybridised with a strength-Pareto density archive |
| Weighted sum | exact, supported points (Gurobi) |
| Epsilon-constraint | exact, full frontier (Gurobi) |
src/platooning/
├── problem/ # decoder (real vector -> routes/speeds) and bi-objective cost
├── operators/ # domination, crossover, mutation, adaptive grid
├── algorithms/ # the six metaheuristics on a shared base
├── exact/ # Gurobi MILP, weighted-sum and epsilon-constraint frontiers
├── metrics/ # hypervolume, IGD, spacing, spread, MID
├── experiments/ # single-run command-line entry point
├── configs/ # per-algorithm hyper-parameters (JSON)
├── inputs/ # vehicle origin/destination data per instance
└── utils/ # Neo4j data access, I/O, results
scripts/ # network loading, vehicle generation, benchmark, figures
neo4j/ # Docker volume and grid Cypher seed scripts
tests/ # decoder, cost, domination, metrics, and algorithm tests
- Python 3.10+
- Docker and Docker Compose (for the Neo4j road-network database)
- Gurobi with a valid licence (only for the exact methods; the metaheuristics need no licence)
pip install -e .
docker compose up -dThe connection parameters live in .env (Bolt on bolt://localhost:7689,
browser on http://localhost:7476, user/password neo4j / 12345678).
Load a road network and generate its vehicle data:
bash scripts/load_neo4j_db.sh grid5
python scripts/generate_vehicles.py --db grid5 --num_vehicles 5 --seed 42 --grid_size 5The three grid networks (grid5, grid10, grid20) are rebuilt from the committed
Cypher in neo4j/import/cypher/. See
neo4j/README.md for the data model.
# Run one metaheuristic on one instance and save its Pareto front
python -m platooning.experiments.main --algorithm nsga2 --db grid5 --num_vehicles 5
# Run the full benchmark (all methods + exact frontier + scaling sweep)
python scripts/run_benchmark.py
# Build the figures and the metrics table from the saved results
python scripts/make_figures.py
# Run the tests (no Neo4j or Gurobi required)
python -m pytest tests/ -q| Network | Grid | Nodes | Directed edges | Vehicles |
|---|---|---|---|---|
| grid5 | 5 x 5 | 25 | 80 | 5 |
| grid10 | 10 x 10 | 100 | 360 | 10 |
| grid20 | 20 x 20 | 400 | 1520 | 20 |
On grid5 (25 nodes, 5 vehicles) every metaheuristic recovers a front close to the
exact epsilon-constraint frontier.
Each indicator below is the mean ± standard deviation over 10 random seeds, with the average IGD rank from a Friedman test. Hypervolume is against a common reference point (higher is better); IGD is the distance to the exact frontier (lower is better).
| Method | Solutions | Hypervolume | IGD | Spread | Runtime (s) | IGD rank |
|---|---|---|---|---|---|---|
| NSGA-II | 75 | 347014 ± 4186 | 0.1504 ± 0.0214 | 0.849 ± 0.065 | 55.6 | 3.90 |
| SPEA-II | 100 | 346176 ± 2914 | 0.1549 ± 0.0258 | 0.918 ± 0.076 | 31.1 | 4.50 |
| PESA-II | 100 | 288961 ± 93016 | 0.4687 ± 0.5457 | 0.922 ± 0.056 | 22.6 | 3.10 |
| MOEA/D | 394 | 345148 ± 30014 | 0.1815 ± 0.1271 | 1.256 ± 0.099 | 24.3 | 3.70 |
| MOPSO | 98 | 341454 ± 34163 | 0.1624 ± 0.1469 | 0.960 ± 0.062 | 23.5 | 2.40 |
| MOSPEAD | 148 | 344293 ± 32797 | 0.2014 ± 0.1511 | 0.832 ± 0.084 | 52.3 | 3.40 |
| Exact frontier | 20 | -- | -- | -- | 7.29 | -- |
A Friedman test on IGD finds no significant difference between the methods
(chi-square = 7.37, p = 0.194), so on this instance they perform comparably on average.
The clearer difference is stability across seeds: NSGA-II and SPEA-II are steady, while
PESA-II and MOEA/D collapse on a few seeds, which inflates their mean IGD and its
variance. The exact method solves grid5 in a few seconds, but its cost grows quickly
with the network size, where the metaheuristics remain practical.
A short report on the model, the methods, and these results is in docs/paper/main.pdf.
Released under the MIT License. See LICENSE.