MAS Active Controline
Bus Transport Routing Optimisation — Kandy District, Sri Lanka
Performance Summary
Route Visualisation Loading...
Real road-traced routes via OSRM. The depot is shown in orange. Passenger stops are shown in blue. Each coloured line represents a unique bus route.
Optimisation Methodology
This system solves a real-world logistics problem using classical Operations Research, powered by Google OR-Tools. Below is a full walkthrough of the model formulation, solver technique, and constraints applied.
Problem Formulation — Capacitated Vehicle Routing Problem (CVRP)
The transport scheduling problem is modelled as a Capacitated Vehicle Routing Problem (CVRP) — one of the most well-studied problems in combinatorial optimisation and Operations Research.
All buses originate from and return to the MAS Controline Pallekele factory. This is the depot node in the graph.
Each stop has a fixed passenger demand (workers to collect or drop). The solver must decide which bus visits which stops.
All buses are identical — same seat capacity. The solver allocates the minimum number of buses needed to cover all stops.
Minimise the total distance (km) travelled by the entire fleet across all routes combined for a single shift.
Real Road Distance Matrix via OSRM
Straight-line (Haversine) distances are fundamentally inaccurate for Sri Lanka's mountainous terrain. The Kandy district has steep hills and winding roads where a 5 km straight line can be a 15 km road journey.
The Open Source Routing Machine (OSRM) is called with all 100 coordinates (1 depot + 99 stops) to produce a 100×100 pairwise road distance matrix in a single API call.
OSRM uses real OpenStreetMap road network data — actual driving routes, road types, and speeds. All distances are in kilometres.
The distance matrix is cached in memory. Re-running the optimiser with different fleet/capacity/cost parameters reuses the same matrix — no repeated API calls.
Before solving, any stop whose road distance from the depot exceeds the user-set one-way limit is excluded before entering the solver — reducing problem size.
Constraints Applied to the Model
Three hard constraints are enforced. No solution that violates any of these is accepted by the solver.
The total passenger demand assigned to any single bus cannot exceed its seat capacity. Formally: ∑ demand(i) ≤ capacity for all stops i on that bus's route. This is enforced using OR-Tools' AddDimensionWithVehicleCapacity.
Each bus route has a total distance cap of 3× the one-way limit. This models a real-world commute time ceiling — workers should not be on a bus for an unreasonable duration. Enforced via OR-Tools' Distance Dimension.
The number of active routes cannot exceed the user-specified fleet size. Rather than silently adding more buses, the solver uses AddDisjunction to make stops optional with a high penalty — dropping the least-accessible stops when the fleet is insufficient instead of exceeding the limit.
Solver Engine — Google OR-Tools Routing API
The CVRP is NP-Hard — meaning an exact optimal solution for 99 stops is computationally infeasible in real time. OR-Tools uses a two-phase heuristic + metaheuristic strategy to find a near-optimal solution within a fixed time limit.
Builds an initial feasible solution by always extending the current partial route to the nearest unvisited stop. Fast and greedy — guarantees a valid starting point but not optimality. Acts as the seed for Phase 2.
Iteratively improves the Phase 1 solution by exploring neighbouring solutions (swap stops between routes, re-order within routes). GLS uses penalty terms to escape local optima — it penalises frequently visited solution features to force exploration of new areas of the search space. Runs for 4 seconds.
Baseline Comparison — Measuring the Saving
To quantify how much the optimiser saves, we compare against a naive baseline: sending one dedicated bus directly from the depot to each stop and back — no shared routes, no grouping. This is the worst-case scenario that represents an unoptimised operation.
Sum of all individual round trips:
∑ (depot→stop + stop→depot) for every active stop. Uses real OSRM road distances.
Total kilometres driven by the entire fleet under the CVRP solution — buses share routes and collect multiple stops in one trip.
(Baseline − Optimised) × Operating Cost/km. Reported in LKR per shift. Directly represents daily fuel and operational savings.
Saved km × 0.67 kg CO₂/km (standard diesel bus emission factor). Quantifies the environmental benefit of route consolidation.
Synthetic Data Generation Pipeline
Since real employee home-address data is confidential, this system generates a realistic synthetic dataset that mirrors actual factory transport patterns. The pipeline has four stages.
Coordinate Generation — Random Sampling Within Radius
Random geographic coordinates are generated uniformly within a user-configurable recruitment radius (default 40 km) around the MAS Controline Pallekele factory (7.2842°N, 80.7061°E). A bounding box is sampled first, then a Haversine distance filter discards points outside the circular radius — ensuring all stops are realistically reachable from the factory.
Road Snapping — OSRM Nearest API (Parallel)
Raw random coordinates often land in fields, rivers, or buildings — locations that cannot be reached by road. Each coordinate is submitted to the OSRM Nearest API, which snaps it to the closest drivable road point on the OpenStreetMap network.
All road-snap requests are fired simultaneously using Python's
ThreadPoolExecutor. This reduces dataset generation from ~2 minutes (sequential) to ~8–12 seconds.
Only road-snapped coordinates are accepted. Any snapped point that exceeds the radius limit is discarded. Fallback coordinates near the depot pad the dataset if too few candidates survive.
OSRM uses the Sri Lanka road network from OSM — including A-grade, B-grade, and local roads in the Kandy district. All snapped stops are reachable by standard bus.
Each accepted stop is assigned a real Kandy district area name (99 names pre-loaded) for realistic readability, shuffled randomly using the seed.
Demand Generation — Shift-Consistent Passenger Counts
For each stop, passenger demand is generated independently for two worker groups — morning shift and afternoon shift — using a Discrete Uniform Distribution U[5, 25]. The drop demands are then derived (not independently randomised) to enforce real-world logical consistency.
Demand_10AM_Collect ~ U[5, 25] — buses collect these workers from home at 10 AM.
Demand_2PM_Drop = Demand_10AM_Collect — the same workers are dropped home at 2 PM. No independent value is generated.
Demand_2PM_Collect ~ U[5, 25] — buses collect these workers from home at 2 PM.
Demand_10PM_Drop = Demand_2PM_Collect — the same workers are dropped home at 10 PM. No independent value is generated.
Shift Structure — Four Optimisable Transport Events per Day
Passenger Dataset
All 99 destination stops within the selected radius with simulated daily passenger demand per shift.