Linear programming solution for Transport for London bus route optimisation. Minimises daily operating cost while ensuring full station coverage and respecting fleet capacity constraints.
| Metric | Value |
|---|---|
| Total Daily Cost | £5,954 |
| Buses Used | 13 / 15 |
| Stations Covered | 50 / 50 (100%) |
| Solve Time | 0.003 seconds |
| Tests | 22 passing, 0 failed |
Transport for London operates 675 bus routes across 19,000 stops. This project models a simplified 50-station, 25-route network where a fleet of 15 buses must be allocated to minimise operating cost while ensuring every station has at least one route.
Constraints:
- Every station must have at least one bus route
- Maximum 15 buses available (fleet size)
- Route variables x_j relaxed to [0,1] (LP relaxation)
Objective: Minimise total daily operating cost (£/day)
Formulated as a linear programme in standard scipy form:
minimise: c^T @ x
subject to: -A_coverage @ x <= -1 (coverage, negated for scipy)
[1,...,1] @ x <= 15 (fleet size)
0 <= x_j <= 1 (variable bounds, handled by scipy)
Solved using scipy.optimize.linprog with the HiGHS method. Coverage matrix A is 50x25 with ~80% sparsity. This version uses a LP relaxation modelling technique due to speed and computational requirements. An ILP solution would need to solve 33 million combinations for 25 routes, whilst a LP relaxation model uses continuous mathematical solution. In a production grade system ILP would be the ideal solver due to its exact binary solution.
git clone https://github.com/LukeWardle/tfl-optimiser.git
cd tfl_optimiser
REM Windows
python -m venv venv
venv\Scripts\activate
pip install -r requirements.txt # Run the full optimisation pipeline
python main.py
# Run the test suite
pytest tests/ -v
# Export results to CSV (for stakeholders)
python export_results.py Skills demonstrated:
- Linear Algebra: coverage matrix construction, sparse structures
- Optimisation: LP formulation, constraint handling, HiGHS solver
- Python: NumPy, SciPy, pytest, modular package structure
- Software Engineering: TDD, validation layers, professional Git
UK Transport Context: Similar LP formulations are used at TfL, Network Rail, FirstGroup, and National Express for route planning.
tfl_optimiser/
|-- DESIGN.md # project design from brief
|-- README.md # this file
|-- data/
| |-- generate_routes.py # module to generate routes.json
| |-- routes.json # json file containing routes data
| |-- stations.json # json file containing stations data
|-- src/
| |-- data.py # module for loading data and validating
| |-- formulation.py # module that formulates equations from data
| |-- solver.py # module that solves equations
| |-- validation.py # module that validates solver answer
|-- export_results.py # module for output results
|-- main.py # main orchestrator module
|-- requirements.txt # list of project requirements
|-- tests/
| |-- test_data.py # unit tests for data.py
| |-- test_formulation.py # unit tests for formulation.py
| |-- test_integration.py # unit tests for full pipeline integration
| |-- test_solver.py # unit tests for solver.py
| |-- test_validation.py # unit tests for validate.py
|-- verify_formulation.py # module for verifying formulation
- Dynamic demand modelling (time-of-day variations)
- Integer programming (exact binary solution)
- Sensitivity analysis (what-if scenarios)
- Integration with real TfL API data